进程调度研究现状分析

进程调度研究现状分析

（中南大学信息学院）

【摘要】：调度算法是指根据系统的资源分配策略所规定的资源分配算法．本文详细地讨论了先来先服务调度算法、短作业（进程）优先调度算法、时间片轮转调度算法、优先级调度算法、最短剩余时间优先、高响应比优先调度算法、多级反馈队列调度算法、最晚时间限调度等八种常用作业调度算法的基本思想，并就其性能的进行了比较分析。

【关键字】：调度策略；FCFS；SPJ；RR；优先级

【Abstract】：Schedulingalgorithmisdefinedastheresourceallocationstrategyfortheallocationofresourcesrequiredbyalgorithm.Thisarticlediscussedindetailfirst-comefirst-serveschedulingalgorithm,theshortoperations(theprocess)priorityschedulingalgorithm,timeschedulingalgorithmrotarytablet,priorityschedulingalgorithm,theshortesttimeremainingpriority,highpriorityresponseratioschedulingalgorithm,multi-levelfeedbackqueueschedulingalgorithmthelatestschedulingtimelimitofeightcommonoperations,suchasthebasicideaofschedulingalgorithmanditsperformanceonacomparativeanalysis.

【KeyWords】：Schedulingstrategy;FCFS;SPJ;RR;Priority

【正文】:

1、引言

随着现代操作系统的日趋成熟，用户对计算机的需求越来越多，处理机在同一时刻能处理的资源是有限的，从而导致各种任务随时随地争夺使用处理机，因此对程序的并发能力提出了更高的要求。

引进并发技术后，为了更好地说明并发现象（尤其是动态过程），引入了进程的概念。进程是一个具有一定独立功能的可并发执行的程序关于某个数据集合的一次运行活动。一个程序的启动执行，便是一个进程的建立；一个程序执行结束（正常或非正常结束），便是一个进程的撤销。由于同时处于就绪态（争夺使用CPU资源）的进程经常比较多，因此需要CPU调度算法来决定由哪个进程获得CPU使用权进入运行态，即进程调度算法（策略）。

-1-

本文主要就现代操作系统中目前常用的几种调度算法的基本思想及其性能展开论述。现代操作系统常用的调度算法有：先来先服务调度算法（FCFS，FirstComeFirstServed）、短作业（进程）优先调度算法（SJF/SPF，ShortestJob/ProcessFirst）、时间片轮转调度算法（RR，RoundRobin）、优先级调度算法、最短剩余时间优先（ShortestRemainingTime）、高响应比优先调度算法（HRN，highest-response-tatio-nextscheduling）、多级反馈队列调度算法、最晚时间限调度（deadlinescheduling）。

2、调度算法性能评价的主要指标

(1)、周转时间：将一个作业提交给计算机系统后到该作业完成并将结果返回给用户所需要的时间。周转时间Ta=T1（外存上等待调度的时间）+T2（就绪队列等待时间）+Ts（服务时间）+To（等待I/O操作完成的时间）。(2)、带权周转时间：Tw=Ta/Ts。(3)、吞吐率：单位时间内，系统所完成的任务的数量。(4)、响应时间：从用户输入一个命令到计算机把相应的执行结果返回给用户所需要的时间。

3、常用调度算法的分析与评价

3.1、先来先服务调度算法（FCFS）

该调度算法在所有就绪进程中，选择最先进入就绪态的进程最先进入运行态，属于非抢占式方式，一个进程一旦获得处理机便将一直运行，直到该进程完成或者因为等待其他资源（如I/O设备）的到来进入阻塞状态，而自动放弃CPU。先来先服务调度算法的模型表示如下图所示（假设系统的服务器只有一个S）。

该算法易于实现，系统开销较小。该算法从表面上看对于所有的作业都是公平的，每个进程什么时候获得处理机，以及一个作业的等待时间是可以预先估计的。但是从另一方面来看也不一定公平，当一个长作业先到达系统时就会使长作业后面进入就绪队列的许多短作业等待很长时间，先到先服务算法有利于长作业，不利于短作业．先到先服务算法使得一批作业的平均周转时间较长，即提供给用户的平均服务较差．从作业的类型角度看，先到先服务算法有利于CPU繁忙型的作业(需要大量的CPU时间进行计算而很少请求I/O)，不利于I/O繁忙型的作业(CPU进行处理时需频繁的请求I/O．

-2-

今天先来先服务调度算法已很少用作主要的调度策略，尤其是不作为分时系统和实时系统的主要调度策略，但它常常用作辅助调度策略被结合在其它调度算法中使用．

3.2、短作业（进程）优先调度算法（SJF/SPF，SHortestJob/ProcessFirst）

短作业（进程）优先调度算法，最先执行占用CPU时间最短（估计占用CPU时间最短）的进程（作业），是一种非抢占方式的算法，该调度算法的系统吞吐率相对于FCFS有了很大的提高。

该调度算法对长作业和紧迫性作业不利。由于该算法每次都是从就绪队列中选择短作业获得CPU使用权，可能导致长作业即使进入了就绪队列，但是由于不断有短作业进入就绪队列，从而长期得不到调度，周转时间变的很大，出现饥饿现象。对于紧迫性作业来说，由于调度的依据是作业占用CPU时间的长短，根本没有考虑作业（进程）的紧迫性，因而紧迫作业也不能得到及时处理。

3.3、时间片轮转调度算法（RR）

该算法的基本思想是：系统为每个进程分配一段运行时间（时间片），允许进程在系统为它分配的时间片内运行。若在分配的一个时间片内，该进程还没有结束，系统强行将它挂到就绪队列，并根据调度算法将CPU交付给后备队列中的另外一个进程；若该进程运行完成，则系统正常将CPU交付给后备队列中的某一个进程。该调度算法相对于前面两个调度算法，提高了进程的并发性，缩短了每一个作业的相应时间，提高了系统资源利用率，一般不会出现饿死现象。

时间轮转算法中时间片的大小的选择对计算机性能有很大的影响:(1).时间片＜进程执行时间，进程需交替执行；(2)时间片＞进程执行时间，退化为FCFS。

在不考虑时间片相应外，基于上述算法原理的时间片轮转算法系统吞吐率也没有达到最佳状态，在进程运行到即将结束的时候，即系统为之分配的时间片要结束了，如果按照上面的算法原理，它必须等待下一轮时间片的到来，这十分不利于系统吞吐率的提高。于是对算法做出的如下的改进，即进程在运行到即将执行完毕时，通过增加一定的时间片值，使得当前进程能不被调度程序切换出去而连续的执行完剩下的工作。其原理为：在时间片轮转凋度算法中对进程最后一次执行时间片进行优化，即当进程按时间片轮转法调度时，如果当前进程运行还需占用的CPU时间已不足进程分配到的时间片值的二分之一(此值可调整)时，调度算法自动为当前进程增加一定的时间片值，使之能继续获得CPU的使用权，从而立即完成剩余代码的执行。[1]

-3-

特别对于我们所讨论的实时操作系统中，对于同一优先级的任务用改进后的时间片轮转法进行调度，具有更为的重要意义，因为在实时系统中任务在规定的期限内能否执行完毕将可能导致灾难性的后果。从对改进前后的原理的比较分析可知，用改进前的时间片轮转法算法对同一优先级任务进行调度时，对于当前获得CPU的任务在仅差几个时间片甚至半个时间片就能运行完的情况，前一个调度算法不会加以特殊考虑，该任务仍然会被进程调度程序切换出去，从而导致系统吞吐率的下降，使本可以在规定的期限内完成的任务延迟，而改进后的算法则能避免这种可能性的发生。

3.4、优先级调度算法

不同进程的重要程度和紧急程度是不同的，优先级算法给每个进程赋予一个优先级，带有最高优先级的进程最先执行。优先级调度算法分为静态优先级和动态优先级两种。静态优先级是在创建进程的时候就确定的，且规定它在进程的整个运行过程中保持不变；静态优先级是指在创建进程时所赋予的优先级，可以随着进程的推进而变动，可以防止优先级高的进程不停地执行，低优先级进程饿死。

根据优先级的确定的方式不同，优先级调度方式分为抢占式和非抢占式两种。在静态优先级下，属于非抢占式，每次都是将CPU的使用权交给就绪队列中具有最高优先权的进程，直到该进程执行完成，即使在进程执行过程中，就绪队列中存在优先级更高的进程。在动态优先级方式下，属于抢占式，一旦就绪队列中有比当前任务优先级更高的进程，该任务的CPU使用权就会被剥夺，分配给就绪队列中当前具有最高优先级的进程。

静态优先权调度算法简单易行、系统开销小,但是不太灵活,很可能会出现低优先权的进程长期得不到调度而等待的情况;动态优先权调度算法比较灵活、科学,可以防止有些进程一直得不到调度,也可防止有些进程长期垄断处理机,但是系统动态地确定进程的优先级需要花费相当多的程序执行时间,因而花费的系统开销比较大。[2]

但是，在作为服务器的系统中运用动态优先调度方式，尤其在大用户量的交互系统中，该调度算法还是存在以下一些缺点：(1)对于系统负担较重的情况下，预定义的时间片过大。但如果定得过小，处理器在进程间的切换工作过于频繁，其系统调度所占的时间比例将增大，使系统的效率降低。(2)不能很好地考虑系统的吞吐量。尤其是不能减少短进程的平均等待时间。(3)不能得到较好的输入输出设备的利用率。(4)不能因交互用户需及时响应而照顾输入输出型进程。

-4-

3.5、最短剩余时间优先算法（SRT）

最短剩余时间优先算法（SRT）可以看成是抢占式的短作业优先算法，即当一个新进程进入就绪队列时，若其需要的运行时间比当前运行进程的剩余时间短，则它将抢占CPU。[3]

与短作业优先算法一样，很难准确确定进程的剩余执行时间，且对长进程不公平。但是，它不象先到先服务算法偏袒长进程，也不象时间片轮转算法会产生很多中断而增加系统负担。由于短进程提前完成，故其平均周转时间比短作业优先算法短。

3.6、高响应比优先调度算法（HRN）

该算法优先执行相应比最高的进程，响应比公式为：响应比R=（等待时间+要求服务时间）/要求服务时间。

由响应比R计算公式可以看出，一个作业的R会随着它的等待时间的增加而增加．因此一个作业只要它的等待时间足够长，它总会由于响应比的提高而获得运行的机会，这就克服了饥饿现象．该算法有利于短作业，因为在作业等待时间相同的情况下，要求服务的时间越短，其优先权越高；对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机；当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务；它是FCFS和SJF的一个较好的折衷，因为它既考虑了作业到达的先后，又考虑了作业的长短．一个不利的因素是每次要进行调度时，需要重新计算后备队列中作业的R。，这样导致增加系统开销。

3.7、多级反馈队列调度算法

多级反馈队列，是对时间片轮转调度算法的发展，其不必估计进程运行时间的大小，是目前最常用的算法（WindowsXP/2000/2003和Solaris都用它），它结合了FIFO、RR、优先级算法和SJF算法。该算法有多个进程就绪队列，同一队列中的进程优先级相同，每个队列对应一个调度级别，各级都有不同的运行优先级。每个就绪队列中的进程具有相同的时间片长度。优先级最高的第1级队列巾的进程的时间片最小，随着队列的级别增加其进程的优先级降低，但时问片长度相应增加。增加的幅度可以根据系统的情况制定。通常优先级每高一级，时间片增加一倍。

-5-

其调度方法为：当一个新进程进入系统后，它被加入第1级就绪队列的末尾。该队列中的进程按先来先服务原则分给处理器，并运行一个对应于该队列的时间片。如果进程在这个时间片中完成了其全部工作或因等待某些事件(如等待输入输出)而主动放弃了处理器，那么该进程或撤离系统(任务完成)或进入相应的等待队列，从而离开当前就绪队列。如果进程使用完了整个时间片后，还未完成而仍需运行(也未产生输入输出要求)，那么该进程被抢占处理器，同时将它放入下一级就绪队列的队尾。

多级反馈队列调度算法最大的优势是，优先级和时间片结合在一起：优先级越高，时间片越短；优先级越低时间片越长。它有利于交互型作业(常为短作业)，有利于短批处理作业，但是它还是存在某些方面的不足：当不断有新进程到来，则长进程可能饥饿。

3.8、最晚时间限调度（deadlinescheduling）

该算法的基本思想是：按用户的时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限要求最近的任务优先占有处理机，以保证在每个进程必须完成的最晚时间限前运行完该进程。

最晚时间限调度算法是抢先式的。抢先式时限调度算法必须把新到达任务的时限要求和当前正在执行任务的时限要求进行比较，如果新到达任务的时限要求更近，则应执行新到达的任务。它也可以用于非周期性任务调度。频率单调调度算法是一种被广泛用于多