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

【关键字】：调度策略；FCFS；SPJ；RR；优先级【Abstract】：Scheduling algorithm is defined as the resource allocation strategy for the allocation of resources required by algorithm. This article discussed in detail first-come first-serve scheduling algorithm, the short operations (the process) priority scheduling algorithm, time scheduling algorithm rotary tablet, priority scheduling algorithm, the shortest time remaining priority, high priority response ratio scheduling algorithm, multi-level feedback queue scheduling algorithm the latest scheduling time limit of eight common operations, such as the basic idea of scheduling algorithm and its performance on a comparative analysis.【Key Words】：Scheduling strategy; FCFS; SPJ; RR; Priority【正文】:1、引言随着现代操作系统的日趋成熟，用户对计算机的需求越来越多，处理机在同一时刻能处理的资源是有限的，从而导致各种任务随时随地争夺使用处理机，因此对程序的并发能力提出了更高的要求。

引进并发技术后，为了更好地说明并发现象（尤其是动态过程），引入了进程的概念。

进程是一个具有一定独立功能的可并发执行的程序关于某个数据集合的一次运行活动。

一个程序的启动执行，便是一个进程的建立；一个程序执行结束（正常或非正常结束），便是一个进程的撤销。

由于同时处于就绪态（争夺使用CPU资源）的进程经常比较多，因此需要CPU调度算法来决定由哪个进程获得CPU使用权进入运行态，即进程调度算法（策略）。

本文主要就现代操作系统中目前常用的几种调度算法的基本思想及其性能展开论述。

现代操作系统常用的调度算法有：先来先服务调度算法（FCFS，First Come First Served）、短作业（进程）优先调度算法（SJF/SPF，Shortest Job/Process First）、时间片轮转调度算法（RR，Round Robin）、优先级调度算法、最短剩余时间优先（Shortest Remaining Time）、高响应比优先调度算法（HRN，highest-response-tatio-next scheduling）、多级反馈队列调度算法、最晚时间限调度（deadline scheduling）。

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．今天先来先服务调度算法已很少用作主要的调度策略，尤其是不作为分时系统和实时系统的主要调度策略，但它常常用作辅助调度策略被结合在其它调度算法中使用．3.2、短作业（进程）优先调度算法（SJF/SPF，SHortest Job/Process First）短作业（进程）优先调度算法，最先执行占用CPU时间最短（估计占用CPU时间最短）的进程（作业），是一种非抢占方式的算法，该调度算法的系统吞吐率相对于FCFS有了很大的提高。

该调度算法对长作业和紧迫性作业不利。

由于该算法每次都是从就绪队列中选择短作业获得CPU使用权，可能导致长作业即使进入了就绪队列，但是由于不断有短作业进入就绪队列，从而长期得不到调度，周转时间变的很大，出现饥饿现象。

对于紧迫性作业来说，由于调度的依据是作业占用CPU时间的长短，根本没有考虑作业（进程）的紧迫性，因而紧迫作业也不能得到及时处理。

3.3、时间片轮转调度算法（RR）该算法的基本思想是：系统为每个进程分配一段运行时间（时间片），允许进程在系统为它分配的时间片内运行。

若在分配的一个时间片内，该进程还没有结束，系统强行将它挂到就绪队列，并根据调度算法将CPU交付给后备队列中的另外一个进程；若该进程运行完成，则系统正常将CPU交付给后备队列中的某一个进程。

该调度算法相对于前面两个调度算法，提高了进程的并发性，缩短了每一个作业的相应时间，提高了系统资源利用率，一般不会出现饿死现象。

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

在不考虑时间片相应外，基于上述算法原理的时间片轮转算法系统吞吐率也没有达到最佳状态，在进程运行到即将结束的时候，即系统为之分配的时间片要结束了，如果按照上面的算法原理，它必须等待下一轮时间片的到来，这十分不利于系统吞吐率的提高。

于是对算法做出的如下的改进，即进程在运行到即将执行完毕时，通过增加一定的时间片值，使得当前进程能不被调度程序切换出去而连续的执行完剩下的工作。

其原理为：在时间片轮转凋度算法中对进程最后一次执行时间片进行优化，即当进程按时间片轮转法调度时，如果当前进程运行还需占用的CPU时间已不足进程分配到的时间片值的二分之一(此值可调整)时，调度算法自动为当前进程增加一定的时间片值，使之能继续获得CPU的使用权，从而立即完成剩余代码的执行。

]1[特别对于我们所讨论的实时操作系统中，对于同一优先级的任务用改进后的时间片轮转法进行调度，具有更为的重要意义，因为在实时系统中任务在规定的期限内能否执行完毕将可能导致灾难性的后果。

从对改进前后的原理的比较分析可知，用改进前的时间片轮转法算法对同一优先级任务进行调度时，对于当前获得CPU的任务在仅差几个时间片甚至半个时间片就能运行完的情况，前一个调度算法不会加以特殊考虑，该任务仍然会被进程调度程序切换出去，从而导致系统吞吐率的下降，使本可以在规定的期限内完成的任务延迟，而改进后的算法则能避免这种可能性的发生。

3.4、优先级调度算法不同进程的重要程度和紧急程度是不同的，优先级算法给每个进程赋予一个优先级，带有最高优先级的进程最先执行。

优先级调度算法分为静态优先级和动态优先级两种。

静态优先级是在创建进程的时候就确定的，且规定它在进程的整个运行过程中保持不变；静态优先级是指在创建进程时所赋予的优先级，可以随着进程的推进而变动，可以防止优先级高的进程不停地执行，低优先级进程饿死。

根据优先级的确定的方式不同，优先级调度方式分为抢占式和非抢占式两种。

在静态优先级下，属于非抢占式，每次都是将CPU的使用权交给就绪队列中具有最高优先权的进程，直到该进程执行完成，即使在进程执行过程中，就绪队列中存在优先级更高的进程。

在动态优先级方式下，属于抢占式，一旦就绪队列中有比当前任务优先级更高的进程，该任务的CPU使用权就会被剥夺，分配给就绪队列中当前具有最高优先级的进程。

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

]2[但是，在作为服务器的系统中运用动态优先调度方式，尤其在大用户量的交互系统中，该调度算法还是存在以下一些缺点：(1)对于系统负担较重的情况下，预定义的时间片过大。

但如果定得过小，处理器在进程间的切换工作过于频繁，其系统调度所占的时间比例将增大，使系统的效率降低。

(2)不能很好地考虑系统的吞吐量。

尤其是不能减少短进程的平均等待时间。

(3)不能得到较好的输入输出设备的利用率。

(4)不能因交互用户需及时响应而照顾输入输出型进程。

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

]3[与短作业优先算法一样，很难准确确定进程的剩余执行时间，且对长进程不公平。

但是，它不象先到先服务算法偏袒长进程，也不象时间片轮转算法会产生很多中断而增加系统负担。

由于短进程提前完成，故其平均周转时间比短作业优先算法短。

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