今天我们来谈一谈进程调度算法：

1. 先来先服务调度算法（FCFS）

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

算法优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平 算法缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程

2. 短作业（进程）优先调度算法（SJF）

短作业（进程）优先调度算法，它作用于作业调度和进程调度。短作业优先是从后备队列当中选择一个或者若干个运行时间最短的作业，调入内存当中运行。 短进程优先是从就绪进程队列当中选出一个时间最短的进程，将处理机分配给它，立即执行并且一直执行到完成，当发生其他问题的时候，这个时候就重新调度。

算法优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。 算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。

3.优先权调度算法

优先级调度算法又被称为优先权调度算法，这个算法既可以用于作业调度，也可以用于进程调度，这个算法中的优先级用于描述作业运行的紧迫程度。

在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为： * 非剥夺式优先级调度算法。当某一个进程正在处理机上运行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在运行的进程继续运行，直到由于其自身的原因而主动让出处理机时（任务完成或等待事件），才把处理机分配给更为重要或紧迫的进程。 * 剥夺式优先级调度算法。当一个进程正在处理机上运行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给更重要或紧迫的进程。

而根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种： * 静态优先级。优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。 * 动态优先级。在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据为进程占有CPU时间的长短、就绪进程等待CPU时间的长短。

4.高响应比优先调度算法（HRRN）

高响应比优先调度算法主要用于作业调度，是堆FCFS和SJF的一种平衡。

FCFS是只考虑每个作业的等待时间不考虑执行时间长短，而SJF是只考虑执行时间未考虑等待时间的长短。

所以高响应比同时考虑每个作业的等待时间和估计运行时间，在每次进行作业调度时，先计算后备作业队列当中的每个作业响应比，然后找出响应比最高的作业投入运行。

响应比R定义如下： R =(W+T)/T = 1+W/T

其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。 算法优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF 法时的吞吐量。 算法缺点：由于每次调度前要计算响应比，系统开销也要相应增加。

5.时间片轮转算法

主要用于分时系统。这种算法中，系统将所有的就绪进程按照到达时间先后次序排成一个队列，按照先来先服务的原则运行，但是仅仅只能运行一个时间片，使用完一个时间片的时间以后，即使进程并未完成其运行，也必须释放出处理机给下一个就绪的进程，而被剥夺的进程返回就绪队列末尾重新排队，等候再次运行。并且通过上下文切换执行当前的队首进程，京城可以未使用完一个时间片，就让出处理机。

在整个过程中，时间片的大小尤为重要，时间片过大，那么所有的进程都能在一个时间片内执行完毕，则时间片轮转算法就会退化成为FCFS,如果太小，那么进程之间频繁切换，那么处理机的开销很大，真正用于运行用户进程的时间将减小。因此时间片需要选择恰当。

时间片大小的确定： 1. 系统对响应时间的要求 2. 就绪队列中进程的数目 3. 系统的处理能力

算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。 算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当。

6.多级反馈队列

多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。多级反馈队列调度算法可以兼顾多方面的系统目标。

多级反馈队列调度算法的实现思想如下： * 1.应设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。 * 2.赋予各个队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的运行时间片就越小。例如，第2级队列的时间片要比第1级队列的时间片长一倍， ……第i+1级队列的时间片要比第i级队列的时间片长一倍。 * 3.当一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样地按FCFS 原则等待调度执行；如果它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列……如此下去，当一个长进程从第1级队列依次降到第 n 级队列后，在第 n 级队列中便釆用时间片轮转的方式运行。 * 4.仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行；仅当第1 ~ (i-1)级队列均为空时，才会调度第i级队列中的进程运行。如果处理机正在执行第i级队列中的某进程时，又有新进程进入优先级较高的队列（第 1 ~ (i-1)中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i级队列的末尾，把处理机分配给新到的更高优先级的进程。

多级反馈队列的优势有： * 终端型作业用户：短作业优先。 * 短批处理作业用户：周转时间较短。 * 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。