进程调度算法的简单总结

正文中有关操作系统的专业名词，可以参考 操作系统常用名词解释。

调度算法分为作业调度算法和进程调度算法，但是作业是用户提交给系统的一个任务，一个作业通常包括几个进程，几个进程共同完成一个任务，就是作业。所以对作业的调度，本质上也就是一种对进程的特殊调度，接下来就介绍几种常见的调度算法。

非抢占式进程调度算法

FCFS 先来先服务算法

概述：在就绪队列中选择最先进入队列的进程/作业，分配处理机，直至完成。 优点：算法简单，有利于CPU繁忙型任务（CPU繁忙型作业），常被结合在其他调度策略中使用。 缺点：效率低，不利于I/O繁忙型。 适用范围：进程调度或作业调度

SJF 短作业优先算法

概述：从就绪队列选择一个估计运行时间最短的作业，分配处理机，直至完成。 优点：平均等待、平均周转时间很（最）少 缺点：导致长时间进程迟迟得不到处理（饥饿现象） 适用范围：进程调度或作业调度

HRRN 高响应比优先调度算法

概述：实际上HRRN也是基于作业优先权进行调度的，但是优先权的计算，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能。HRRN是介于FCFS（先来先服务算法）与SJF（短作业优先算法）之间的折中算法。高响应比优先调度算法（Highest Response Ratio Next）是一种对CPU中央控制器响应比的分配的一种算法。

优先权的计算： 优先权 = （等待时间 + 要求服务时间） / 要求服务时间 由于，系统响应时间 = 等待时间 + 要求服务时间，所以，优先权又可以进行如下计算： 优先权 = 系统响应时间 / 要求服务时间 因此，该优先级又被称为响应比，所以叫做HRRN 高响应比优先调度算法。

优点：同时具备了两种算法的优势 缺点：计算优先权需要额外的开销

抢占式进程调度算法

时间轮片算法

time slice round robin(TSRR) 概述： 1、根据FCFS策略将进程排成一个就绪队列 2、设置一个时间间隔（30min）定期产生中断，以激活操作系统的进程调度程序，完成一次调度，将处理机分配给就绪队列中的第一个进程（队首进程）。 3、如果在一个时间片内，正在运行的进程已经完成，就立即激活调度程序，从就绪队列中删除当前进程，然后选择下一个队首进程获得处理机进行运行。如果在一个时间片内没能完成运行，则剥夺资源，将剥夺资源后的进程返回就绪队列尾部。然后选择下一个队首进程获得处理机进行运行。

关键点： 所以时间片大小对系统性能影响很大，太大则会退化为 FCFS 算法；太小则会因为频繁切换，增加开销。

时间片长短由： 系统响应时间（系统响应时间 = 等待时间 + 要求服务时间），就绪队列中进程数，系统处理能力决定。一般情况下，设置时间安排略大于一次典型的交互所需要的时间，这样就能使得大多数交互式进程能够在一个时间片内完成，从而获得很小的响应时间。

多级反馈队列调度算法

背景

1、单队列调度算法的缺点

前面说的FCFS、SJF、HRRN算法，都是基于一个进程就绪队列的，由于只有一个队列，所以OS的低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制的缺点更显突出，由此，多级队列调度算法能够在一定程度上弥补这一缺点。

2、多队列调度算法

该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。（比如说一些CPU密集型的进程就可以放到一个队列里面，统一采用FCFS算法。而一些对实时性要求比较高的进程就可以放到一个队列里面，统一采用抢占式的优先级调度算法。）

补充：多队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。
在多处理机系统中，该算法由于安排了多个就绪队列，因此，很方便为每个处理机设置一个单独的就绪队列，实施单独的调度策略。 对于一个含有多个线程的进程而言，可以根据其要求将其所有线程分配在一个就绪队列，全部在一个处理机上运行。再者，对于一组需要相互合作的进程或线程而言，也可以将它们分配到一组处理机所对应的多个就绪队列，使得它们能同时获得处理机并行执行。

多级反馈队列调度算法（multileved feedback queue）

多级反馈队列调度算法是多队列调度算法的一种具体实现，除了多级反馈队列调度算法以外，还有很多种多级队列算法。 \[ \mbox{多级反馈队列调度算法} \in \mbox{多队列调度算法} \] 原理：多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合发展，通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。

调度机制

简答版本，7个要点：

1. n个队列
2. 每个队列都实施时间片轮转算法，先按照FCFS的原则将进程排列成就绪队列。
3. 第1个队列的时间片略大于一次典型的交互所需要的时间。
4. 从第1个队列到第n个队列，优先级逐级递减。时间片在上个队列的基础上加倍。
5. 当新进程进入内存之后，首先被放入到第1个队列的队尾，按照FCFS原则等待调度。轮到当这个进程运行时，如果它能在一个时间片内完成，就将其从系统中撤销，激活调度程序，处理下一个队首进程。否则调度程序会将该进程放到第2个队列的末尾。
6. 在第2个队列中，轮到当这个进程运行时，如果它能在一个时间片内完成，就将其从系统中撤销，激活调度程序，处理下一个队首进程。否则调度程序会将该进程放到第3个队列的末尾，以此类推。
7. 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。 在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。

详细过程：

1、在OS中设置n个就绪队列。在每个就绪队列中实施时间片轮转算法，先按照FCFS的原则将进程排列成就绪队列。 2、从第一个队列到第n个队列，优先级越来越低（用0-255的数字表示优先级），时间片越来越长。一般设置第1个队列的时间片略大于一次典型的交互所需要的时间。之后的第2个队列的时间片是第1个队列的时间片的两倍，以此类推。 3、当新进程进入内存之后，首先被放入到第1个队列的队尾。按照FCFS原则等待调度，轮到当这个进程运行时，如果它能在一个时间片内完成，就将进程撤销系统。否则调度程序会将该进程放到第2个队列的末尾。 同样，该进程在第2个中按照FCFS原则等待调度，轮到当这个进程运行时，如果它能在一个时间片内完成，就将进程撤销系统。否则调度程序会将该进程放到第3个队列的末尾，以此类推。 4、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，当且仅当在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 5、在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。换而言之，任何时刻，只有当第1~i1队列全部为空时，才会去执行第i队列的进程（抢占式）。特别说明，当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。

性能

在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好地满足各种类型用户的需要。 （1）终端型用户。由于终端型用户提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列规定的时间片内完成，便可使终端型用户感到满意。 （2）短批处理作业用户。对于这类作业，如果可在第一队列中执行完成，便获得与终端型作业一样的响应时间。对于稍长的短作业，也只需在第二和第三队列各执行一时间片完成，其周转时间仍然较短。 （3）长批处理作业用户。对于长作业，它将依次在第1，2，…，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。

优点

1、不需要提前知道各个进程所需要的运行时间。 2、在各种类型的os中都能实现比较好的调度性能。

抢占或非抢占式进程调度算法

PSA (Priority-Scheduling Algorithm) 优先级调度算法

概述：优先级调度算法是基于进程的紧迫程度对进程进行调度的，由外部赋予进程优先级，调度算法根据优先级进行调度。

抢占式（剥夺式）优先级调度算法

处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。

因此，在采用这种调度算法时，每当系统中出现一个新的就绪进程i时，就将其优先级P；与正在执行的进程j的优先级P；进行比较，如果P；≤P，原进程P，便继续执行；但如果是P；>P，则立即停止P，的执行，进行进程切换，使i进程投入执行。抢占式的优先级调度算法常用于对实时性要求较高的系统中。

非抢占式（非剥夺式）优先级调度算法

该算法规定，一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。

两个关键点

基于优先级的调用算法，要确定两个问题，优先级如何确定和使用静态还是动态优先级。

优先级如何确定

1. 进程类型。通常系统进程（如接收进程、对换进程）的优先级高于一般用户进程的优先级。
   
2. 进程对资源的需求。对资源要求少的进程应赋予较高的优先级。
   
3. 用户要求。根据进程的紧迫程度及用户所付费用的多少确定优先级。

使用静态还是动态优先级

静态优先级

静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如0~255中的某一整数，又把该整数称为优先数。 优点：静态优先级法简单易行，系统开销小， 缺点：但不够精确，可能会出现优先级低的进程长期没有被调度的情况。

动态优先级

动态优先级是指在创建进程之初，先赋了其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。

例如，可以规定在就绪队列中的进程随其等待时间的增长，使其优先级相应提高。或者当前进程的优先级随运行时间的推移而下降。 这里可能会出现一个极端的情况，若所有的进程都具有相同优先级初值，则最先进入就绪队列的进程会因其优先级变得最高，而优先获得处理机，这相当于FCFS算法。 若所有的就绪进程具有各不相同的优先级初值，那么对于优先级初值低的进程，在等待了足够的时间后，也可以获得处理机。 当采用抢占式优先级调度方式同时规定当前进程的优先级随运行时间的推移而下降，则可防止一个长作业长期地垄断处理机。

各种进程调度算法的应用场景

• 批处理操作系统 先来先服务，短作业优先
• 实时操作系统 抢占式的优先级调度算法常用于对实时性要求较高的系统中。《计算机操作系统》汤小丹等 P94
• 分时系统 高响应比、时间片轮转、多级反馈队列

如何评价进程调度算法性能？

通过对比带权周转时间，就能确定哪一个调度算法更好。

这里以先来先服务（FCFS）以及短作业优先（SJF）两种调度算法的相关计算做一个说明和比较。

首先我们必须明确：FCFS和SJF两种调度算法，只有在进程的完成时间计算上有一些区别，其他时间（周转时间等）的计算都是相同的。 周转时间

周转时间=完成时间-到达时间 带权周转时间=周转时间/服务时间（除法运算） 平均周转时间/系统响应时间=总周转时间/进程数（除法运算） 平均带权周转时间=总带权周转时间/进程数（除法运算）

FCFS的完成时间计算步骤：

step1：找出最先到达的进程（该进程的完成时间=到达时间+服务时间）；
step2 : 根据给出的到达时间，找出下一个到达的进程（和SJF不一样的地方）（该进程的完成时间=上一进程的完成时间+该进程的服务时间）；
step3 :重复step2直至完成所有进程的计算；

举个例子：

进程名	A	B	C	D	E
到达时间	0	1	3	4	6
服务时间	5	7	3	8	2
完成时间	5	12	15	23	25
周转时间	5-5=0	12-1=11	15-3=12	23-4=19	25-6=19
带权周转时间	5/5	11/7	12/3	19/8	19/2

平均带权周转时间：18.4

step1. 根据例子中给出的进程到达时间，确定A进程是最先到达的。计算出进程A的完成时间为：A的到达时间+A的服务时间=5+0=5； step2. 根据到达时间，确定下一到达进程为B。计算出进程B的完成时间为：进程A的完成时间+进程B服务时间=5+7=12； step3. 重复step2。根据到达时间，确定下一到达进程为C。计算出C的完成时间为：进程B的完成时间+进程C的服务时间=12+3=15...依次类推计算D和E进程的完成时间。

SJF的完成时间计算步骤：

step1：找出最先到达的进程（该进程的完成时间=到达时间+服务时间）；
step2：根据上一进程的完成时间，找到在这个完成时间内所有到达的进程，并找到这些进程中服务时间最短的那个（和FCFS不一样的地方），然后计算它的完成时间（该进程的完成时间=上一进程的完成时间+该进程服务时间）； step3：重复step2，直至完成所有进程的计算。

还是上面的那个例子：

进程名	A	B	C	D	E
到达时间	0	1	3	4	6
服务时间	5	7	3	8	2
完成时间	5	17	8	25	10
周转时间	5-0=5	17-1=16	8-3=5	25-4=21	6-10=4
带权周转时间	5/5	16/7	5/3	21/8	4/2

平均带权周转时间：9.57

step1. 根据例子中给出的进程到达时间，确定A进程是最先到达的。计算出进程A的完成时间为：A的到达时间+A的服务时间=5+0=5；
step2.根据上一进程A的完成时间5,可确定已经到达的进程为A、B、C、D（进程E的到达时间为6，所以时间为5时进程E还没到达）；其中由于C的服务时间最短，所以下一进程确定为C，C的完成时间为：A的完成时间+C的服务时间=3+5=8；
step3. 重复step2。根据上一进程C的完成时间10，可确定，已经到达的进程有A、B、C、D、E；其中由于E的服务时间最短，所以下一进程确定为E,E的完成时间为：C的完成时间+E的服务时间=8+2=10...依次可计算出其他进程的完成时间。

通过比较平均带权周转时间可知，SJF调度算法优于FCFS。