常用调度算法及其应用-操作系统原理

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

先来先服务（First Come First Service）算法是一种最简单的调度算法，可以应用于高级调度（作业调度）也可以应用于低级调度（进程调度）。高级调度时，FCFS调度算法按照作业进入后备作业队列的先后顺序选择作业进入内存，即先进入后备作业队列的作业被优先选择进入内存，然后为选中的作业创建进程并分配该作业所需资源。低级调度时，FCFS调度算法每次从内存的进程/线程就绪队列中选择一个最先进入的进程/线程，然后由进程/线程调度程序将CPU分配给它并使其运行。

FCFS调度算法实现简单，在等待时间上保证了一定的公平性，但也存在明显的缺陷，即没有考虑作业的类型或进程/线程执行时间的长短，使得短作业或I/O进程/线程等待时间过长。也就是说，FCFS更适合于处理多个CPU繁忙型（计算型）的作业或进程/线程，表3-1以进程为例，列出了进程P1、P2、P3和P4到达系统的时间、运行的时间和开始执行的时间，并给出了采用FCFS调度算法获得的各进程完成时间、等待时间、周转时间和带权周转时间。

表3-1　FCFS调度算法下的进程运行情况表

从表3-1可以看出，FCFS调度算法有利于计算型进程，而不利于占用CPU时间较短的I/O型进程。在单CPU系统中，当一个计算型进程正在占用CPU运行时，所有的I/O型进程都必须等待（因此无法启动I/O设备工作，即I/O设备得不到充分利用）。计算型进程释放CPU时，这些就绪的I/O型进程各自占用CPU短暂地运行后（仅完成启动I/O设备的工作）就可能阻塞（等待I/O操作的完成），因此插入相应的I/O阻塞队列中等待。如果这时计算进程也阻塞了（假定系统中只有一个计算进程），就会在系统中出现没有等待执行的就绪进程而使CPU空闲，从而造成CPU得不到充分利用的极端情况出现。在使用FCFS调度算法的系统中，作业的平均周转时间与进程提交给系统的顺序有关。在表3-1中，如果P3在P2之前提交，即P3的到达时间为1，而P2的到达时间为2，其他条件保持不变，则平均周转时间就降低到75.25。因此，优先提交短进程的FCFS调度算法能够获得更好的平均周转时间。

FCFS调度方法现在已很少作为主要的调度算法单独使用，尤其是在分时系统和实时系统中，通常是与其他调度算法结合使用。如在优先级调度策略中，对优先级相同的进程则按FCFS调度方法进行调度。

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

到银行办理储蓄业务的人都知道，如果排队人群中有一个需要办理很多业务的人排在前面，那么排在他后面的人都要等待很长时间，如果让这个人排在后面，则在他之前的人不受影响。所以应尽可能让业务量少的人先办理业务，而业务量多的人暂时让一让，这样平均效率要高得多（等待时间少得多）。这就是短作业/短进程优先（Short Job First/Short Process First）的调度思想。

短作业优先（SJF）调度算法每次从后备作业队列中，选择估计运行时间最短的作业进入内存，并创建相应的进程。SJF调度算法也可以应用于低级调度，将SJF应用于进程调度时，则称为短进程优先调度（SPF）。短进程优先调度算法每次从进程就绪队列中选择估计运行时间最短的进程，由进程调度程序将CPU分配给它使其投入运行。当两个或两个以上作业/进程具有相同的估计运行时间时，SJF/SPF调度算法则按照FCFS算法进行调度。

SJF/SPF调度算法是一种非抢占式调度算法，某作业的进程一旦获得了CPU，就一直运行到进程完成或因某事件阻塞而放弃CPU。所以SJF/SPF调度算法不适合分时系统或实时系统。

与FCFS调度算法相比，SJF/SPF调度算法更加偏向短作业/短进程，使得系统在单位时间内完成的作业/进程数增加，能够获得更好的平均周转时间和平均带权周转时间。

短作业/短进程优先调度算法没有考虑长作业或运行时间较长的进程。当后备作业队列或进程就绪队列中总有短作业或短进程进入时，长作业或长进程就会因长期得不到调度而出现饥饿现象。这就像前述银行储蓄中，业务量大的人始终让业务量少的人先办理业务，而业务量少的人却源源不断地来，这样到银行下班时业务量大的人也未能办理业务。

短作业/短进程优先调度方法能有效地降低作业/进程的平均等待时间，提高系统的吞吐量，但缺点是用户提供的估计运行时间不一定准确，此外，长作业/长进程有可能长时间等待而得不到运行。

3.时间片轮转调度算法（RR）

时间片轮转（Round Robin）调度算法主要用于低级调度。在采用时间片轮转调度算法的系统中，进程/线程就绪队列总是按进程/线程到达系统时间的先后次序进行排队，进程/线程调度程序按先来先服务的原则，选择就绪队列中的第一个进程/线程，将CPU分配给它执行。进程/线程每次使用CPU的时间只能是一个时间片，当运行进程/线程用完规定的时间片时必须放弃CPU的使用权。这时，进程/线程调度程序又将CPU分配给当前就绪队列的第一个进程/线程，而放弃CPU的进程/线程，则回到就绪队列的队尾，等待下次轮转到自己时再投入运行。所以只要是处于就绪队列中的进程/线程，按时间片轮转法调度将迟早会获得CPU而得到运行，并不会发生无限期等待的情况。

如果某个正在运行的进程/线程其时间片尚未用完，但却因发生某事件（如I/O请求）而被阻塞，这时就不能把该进程/线程返回到就绪队列的队尾，而是将其插入相应的阻塞队列中。只有阻塞它的等待事件已经结束（完成），才能重新返回到就绪队列的队尾，等待再次被调度执行。

时间片轮转调度算法的核心是时间片。如果时间片很长，则可能大多数进程/线程都能在一个时间片内完成，这时时间片轮转调度算法实际上已退化为FCFS调度算法；如果时间片很短，则CPU真正用于运行用户进程/线程的时间就很少，这样会导致进程/线程频繁切换，从而使大量的CPU时间消耗到系统处理时钟中断，以及运行进程/线程调度程序上。一个理想的时间片长短通常设计成略长于一次典型交互所需要的时间，即能够使运行进程/线程产生一个I/O请求。为了考虑不同类型作业的需求，还可以采用可变的时间片长短。

时间片轮转调度方式实际上是一种基于时钟的抢占式调度算法。在使用该调度算法的系统中，系统周期性地产生时钟中断。当时钟中断发生时，运行进程/线程使用的CPU被剥夺，该进程/线程重新回到就绪队列的队尾。

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

高响应比优先（Highest Response Ratio First）调度算法实际上是一种基于动态优先数的非抢占式调度算法，可以应用于作业调度，也可以应用于进程/线程调度。按照高响应比优先调度算法，每个作业或进程/线程都拥有一个动态优先数，该优先数不仅是作业或进程/线程运行时间（估计值）的函数，还是其等待时间的函数。高响应比优先调度算法中的优先数通常也称为响应比Rp，其定义为

高响应比优先调度算法在每次调度作业/进程运行时，都要计算后备作业队列中每个作业的响应比，或者计算进程就绪队列中每个进程的响应比，然后选择最高响应比的作业/进程投入运行。当然，初始时短作业/短进程的响应比一定比长作业/长进程的响应比高，但随着等待时间的增加，长作业/长进程的响应比会随之提高，只要等待一定时间，长作业/长进程就会因成为响应比最高者而获得运行。

高响应比优先调度算法既照顾了短作业/短进程，又不使长作业/长进程等待时间过长，是先来先服务调度算法和短作业/短进程优先调度算法的一种很好的折中调度方案。但缺点是需要估计每个作业或进程/线程的运行时间，而且每次调度时都要计算后备作业队列中所有作业或进程就绪队列中所有进程的响应比，这需要耗费不少的CPU时间。表3-2给出了四个进程P1、P2、P3和P4在高响应比优先调度下的周转时间、带权周转时间和平均周转时间。从平均周转时间来看，短作业/短进程优先最短，高响应比优先次之，而先来先服务最长。

表3-2　采用高响应比优先（HRRF）调度的进程执行示例(www.xing528.com)

5.优先级调度算法

优先级调度算法既可用于高级调度，也可用于低级调度，还可用于实时系统。若调度的对象为作业，优先级调度算法每次从后备作业队列中选择优先级最高的作业调入内存，为其分配相应的资源并创建进程放入进程就绪队列。若调度的对象为进程，则优先级调度算法每次从进程就绪队列中，选择优先级最高的进程为其分配CPU而投入运行。如果有多个优先级最高的作业/进程，则可结合先来先服务或短作业/短进程优先调度策略。

（1）静态优先级

作业/进程在进入系统或创建时被赋予一个优先级，该优先级一旦确定则在其整个生命期内不再改变。对于作业，其优先级可依据费用来确定；对于进程，其优先级主要依据进程的类型（系统进程还是用户进程）、进程的资源需求（资源需求少的进程优先级高）、时间需求（短进程优先）和用户要求来确定。

静态优先级的优点是比较简单，系统开销小；缺点是不够公平也不太灵活，有可能出现低优先级的作业/进程长时间得不到调度的情况。

（2）动态优先级

动态优先级在调度对象（作业/进程）刚进入系统时，也需要依据某种原则为其赋予一个优先级。但随着时间的推进，不同调度对象的优先级在不断地进行动态调整。如当进程获得某种资源时，其优先级被动态提高使其能更快地获得CPU投入运行，以避免资源浪费。又如当进程处于就绪状态时，其优先级随着等待CPU的时间增长而提高，而占有CPU的进程其优先级则随着使用CPU时间的增长而降低，这样来保证系统的公平性。

动态优先级的优点是公平性好、灵活、资源利用率高，既可以防止有些调度对象长期得不到调度，又可以防止有些调度对象长期占用CPU。

在采用优先级法的低级调度中，又分为抢占式和非抢占式两种调度方式。

（1）抢占式优先级调度。这种方式下具有最高优先级的就绪进程/线程首先得到CPU运行，并在运行过程中允许被具有更高优先级的就绪进程/线程抢占CPU。抢占式优先级调度算法能更好地满足紧迫性任务的要求，通常应用于要求比较严格的实时系统中，但会增加系统中进程/线程切换的开销。

（2）非抢占式优先级调度。某个就绪进程/线程一旦获得CPU就会一直运行下去，直到该进程/线程完成或因某等待事件发生而阻塞，才放弃CPU的使用权。非抢占式优先级调度算法通常用于批处理系统中。

6.多级反馈队列调度算法（MLFQ）

前面介绍的各种低级调度算法或多或少都存在一定的局限性。先来先服务调度算法倾向于长进程，因此会使得短进程的等待时间过长；短进程优先调度算法和高响应比优先调度算法，要事先估计各进程大致的运行时间，否则将无法完成调度。多级反馈队列（Multi-Level Feedback Queue）调度算法考虑了这些因素，并对时间片轮转调度算法和优先级调度算法进行了综合和改进，形成了这种基于时间片抢占式动态优先级调度算法。

多级反馈队列调度算法为就绪状态的进程设置多个队列，第1级队列的优先级最高但时间片最少，以下各级队列的优先级逐次降低但时间片却逐次增加，通常向下一级其时间片增加一倍。各级队列均按先来先服务（FCFS）原则排序。多级反馈队列调度示意如图3-10所示（图3-10省略了进程运行中发生等待事件的情况）。

图3-10　多级反馈队列调度示意图

多级反馈队列的调度方法主要有以下三种。

（1）设置多个进程就绪队列，每个进程就绪队列对应一个优先级，且按队列逐级降低，就绪队列Q1的优先级最高。每个队列执行的时间片长度也不同，原则是优先级越低则时间片越长。

（2）新进程（就绪状态）进入内存后，先放入进程就绪队列Q1的队尾。运行按时间片轮转法（RR）调度，若按队列Q1设置的时间片未能运行完，则下放到进程就绪队列Q2的队尾，队列Q2同样按时间片轮转法调度。如此下去，最终可降至Qn队列，Qn队列可按时间片轮转算法或先来先服务算法进行调度，直到完成。

（3）仅当前面较高优先级的队列均为空时，才能调度后面较低优先级队列中的进程运行。如果进程运行中有新进程进入更高优先级的队列，则新进程将抢占CPU，被抢占CPU的进程则回到原队列的队尾。

多级反馈队列调度算法的主要优点：①短进程能够得到优先处理，因为短进程通常在优先级较高的几个队列中即被执行完毕；②系统开销不大，因为运行时间长的进程主要将在优先级较低的队列中运行，由于这些队列的时间片较长，因此引起进程的切换就相对较少，也即开销较小；③对分时系统来说，用户提交的大多是I/O型进程/线程，而多级反馈队列第一级队列的时间片设计应为略长于大多数I/O进程/线程产生一个I/O请求所需的时间，即交互型请求通常能够在第一个进程就绪队列中完成。所以多级反馈队列算法适用于同时支持分时、实时和批处理的通用操作系统。

多级反馈队列调度算法的主要缺点：如果优先级较高的队列一直不为空，则优先级较低队列中的进程可能长时间得不到运行，即会导致饥饿的发生。