进程调度算法

调度算法

先来先服务（FCFS)

先来先服务算法（First Come First Serve)强调公平性，按照进程先来先服务的思想调度，在作业调度时，考虑的是那个作业先到达后备队列，用于进程调度的时候，考虑的是哪个进程先到达就绪队列。是一种非抢占式的算法，即不会有进程中途插队的情况出现。

例如各进程到达就绪队列的时间、需要的运行时间如下表所示，如果使用FCFS算法来调度进程，那么下列的各进程的等待时间，平均等待时间，周转时间，平均周转时间和带权周转时间与平均带权周转时间各是多少？

首先周转时间=完成时间-到达时间，带权周转时间=周转时间/运行时间，等待时间=周转时间-运行时间。按照先来先服务的算法调度，那么就是根据到达的先后顺序调度，当然也就是等待时间越久（说明来的越早）的进程优先得到服务。所以调度的顺序就是P1->P2->P3->P4。如下图：

P1先执行，即到达就先运行，运行7个时间单位，在P1运行途中P2，P3和P4实际上已经都到达了就绪队列了，但是P1执行完，P2等待时间肯定是最久的，所以他执行，然后P3,P4。所以周转时间=完成时间-到达时间可以算出各个进程的周转时间如下表：

然后计算带权周转时间如下表：

等待时间如下表:

所以平均周转时间=(7+8+9+11)/4=8.75，平均带权周转时间=(1+2.25+8+2.75)/4=3.5,平均等待时间=(0+5+7+7)/4=4.75，注意本题的进程都是纯计算的进程，一个进程到达要么在等待，要么在运行，如果是又有计算，又有I/O操作的进程，那么其等待时间就是周转时间-运行时间-I/O操作时间（本题不考虑这种情况）。我们通过上面的3个表可以看出当带权周转时间大的时候说明等待时间所占整个的周准事件比例也就越大，所以使用户的满意度也就降低了，并且这种FCFS算法很明显很不合理，对于某些运行时间非常短的且来的较晚的进程，如果其前面具有一个周转时间非常大的进程时，就会出现长时间的等待从而造成带权周转时间很大，从整体来看，也会影响到平均带权周转时间较大（当然FCFS不会造成平均周转时间大），并且这种算法当面对突发紧迫重要的进程任务时也不能及时处理，所以现代的操作系统是不采取这种调度算法的，这种算法对长作业有利，但是对于短作业不利，当然这种算法也不会造成饥饿现象。

思考：什么是饥饿？

可以理解为排队买东西，老是有人中间插队造成后面的排队的人迟迟无法得到需求。进程亦是如此，当前面的进程总是出现插队现象，就会造成后面的进程一直长时间无法得到相应造成饥饿现象，当然FCFS虽然不合理，但是总是能得到服务的，所以不会造成饥饿现象，而接下来介绍的算法就有可能造成饥饿现象。

短作业优先（SJF）

短作业优先（Shortest Job Fiirst)追求最少的等待时间，最少的平均周转时间，最少的平均带权周转时间，既然FCFS会造成运行时间的短作业长时间等待，那么我就每次都让运行时间短的短作业先进行服务，长时间的大作业多等待一会也不会造成非常离谱的带权周转时间。这种短作业进程优先服务的进程调度算法也是非抢占式的算法，但是也有抢占式的算法例如最短剩余时间优先算法（SRTN,Shortest Remaining Time Next),但是SJF算法有可能会导致饥饿现象。

思考：SJF和SPF的区别？

SJF是对于作业调度（即高级调度）的短作业优先算法，所以叫Shortest Job First而SPF是对于进程调度（低级调度）的短作业优先算法，所以叫做Shortest Process First。

思考:什么是抢占式算法？什么是非抢占式算法？

你可能会疑惑到SJF里可能会出现晚到但是先执行的情况出现，难道还不是抢占式算法？这里的抢占式是指某个任务在运行过程中还没有运行完时被剥夺cpu占用权，使另一个进程开始在cpu上运行。而SJF虽然会每次都挑选就绪队列中运行时间最短的短作业，但也是一定保证这个任务一次性执行完。所以SJF和FCFS都是非抢占式，而SRTN就是抢占式了，他每次都会实时监视计算那个任务有最短剩余时时间谁就上cpu及时前一个任务还没有执行完也要下cpu等待，当然当这个任务又可以上cpu时还是可以继续执行没完成的部分，不需要重新开始，即PCB会帮助记录状态信息以便恢复，一般SRTN又称作具有抢占式的短作业优先进程调度算法。

接下来，我们也计算一个SJF的题，为了更好的理解抢占式，我们做的是具有抢占式的短作业优先算法题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用抢占式的短作业优先调度算法， 计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。 所以实际上做的是SRTN的算法题。

最短剩余时间算法：每当有进程加入到进程就绪队列时就需要进行调度即使现在还有任务在cpu上运行，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则新进程抢占cpu，当前运行进程在PCB记录相关信息后让出cpu重新回到就绪队列等待直至其又是最短剩余时间的作业时在上cpu。同时，当然运行任务结束后还要执行调度。

如下图：

需要注意的是，每次当有新进程到达时就绪队列都会改变，按照上述的规则进行检查。所以每次到达新进程时都要格外注意计算剩余时间。如上，在0-2时只有进程1，所以其先执行，但是当来到时刻2，插入一个新的作业2，他的剩余时间为4(因为还没有执行过，所以剩余运行时间=运行时间)，而此时作业1还有5的运行时间比作业2长，所以虽然作业1没有运行完也要下cpu,作业2抢占cpu。

所以可以用下表表示整个过程Pi(remain time):

0时刻（P1到达）：P1（7），7上cpu执行。

2时刻（P2到达）：P1（5），P2（4），2上cpu执行

4时刻（P3到达）：P1（5），P2（2），P3（1），3上cpu执行

5时刻（P3完成且P4到达）：P1（5），P2（2），P4（4），2上cpu执行

7时刻（P2完成）：P1（5），P4（4），4上cpu执行

11时刻（P4完成且只剩下1）：P1（5），1上cpu执行

16时刻，所有进程完成，调度算法结束。

我们同样计算一下周转时间：

带权周转时间：

等待时间：

所以平均周转时间=(16+5+1+6)/4=7,平均带权周转时间=(2.28+1.25+1+1.5)/4=1.50,平均等待时间=(9+1+0+2)/4=3。我们发现对于短作业优先，其平均的指标要明显低于FCFS算法，同时我们这里给出非抢占式的SJF算法的平均指标：

我们会发现抢占式的短作业优先算法比非抢占式的短作业优先算法的平均指标更小，也就意味着平均性能更好。

注意：小细节

1. 如果题目中并未特别说明，所提到的“短作业/进程优先算法”默认都是非抢占式的即SJF。
2. 很多的教材上都会说“SJF调度算法的平均等待时间，平均周转时间”最少，严格来说，这个表述是错误的，不严谨的。之前的例子已经表明，最短剩余时间优先算法（即抢占式的短作业优先算法）还要更少。应该再加上“在所有进程同时可运行时，采用SJF调度算法的平均等待时间，平均周转时间最少”或者“在所有进程几乎同时到达时，采用SJF调度算法的平均等待时间和平均周转时间最少”。否则在判断题中如果未加上上面的条件，那么SRNT是平均等待时间，平均周转时间最少的。
3. 平均等待时间最短未必平均带权周转时间最短，毕竟后者同时由运行时间和周转时间决定。但是一般来说平均等待时间和平均带权周转时间正相关，即平均等待时间较小一般平均带权周转时间也不会太大。

短作业优先调度平均等待时间和平均周转时间短显而易见，但是却不公平，这种进程调度算法对短作业有利，但是对长作业不利，很有可能造成饥饿现象，即在排队过程中总是出现短作业，这样就会一直插队造成长作业一直等待不能得到相应的饥饿现象。

思考：有没有一种较为中和的算法，不会产生过于极端的情况？

仔细对比发现FCFS和SJF都是很大几率出现较为极端的情况的，前者会对短作业不友好且平均性能不好，后者对长作业不友好，虽然平均性能不错，但是却会造成饥饿现象，那么我们可以发明一种更平和的算法，牺牲部分平均性能，但是对于长短作业都有所考虑，且不会造成饥饿的算法–高响应比优先算法。

高响应比优先算法（HRRN）

高响应比优先算法（Highest Response Ratio Next)要综合考虑作业/进程的等待时间和要求服务的时间，这里我们首先需要引入一个新的概念–响应比

$$响应比=等待时间+要求服务时间/要求服务时间=等待时间/要求服务时间+1$$

要求服务时间就是运行时间，所以可以看出响应比一定是>=1的，自HRRN算法中每次调度时都会计算各个作业/进程的响应比并且选择响应比最高的作业/进程服务。仔细思考响应比我们会发现等待时间更长且运行时间更短的作业/进程会优先选择，这样就实现了既不会让短作业等待也太长时间也不会让短作业永远最先被服务，相应的，也就实现了不会让长作业等待太长时间，折中了SJF和FCFS的优点，并且这种算法也是非抢占式的，只有在该作业/进程运行完毕或者中途主动放弃时才会触发调度，才需要即需要计算响应比，很显然这种算法不会产生饥饿现象。

下面我们还是对于上面的那4个任务按照HRRN算法调度计算：

每次调度时我们都计算响应比，并选择响应比高的上cpu

0时刻：只有P1到达了就绪队列，P1上处理机

7时刻：P1完成，就绪队列中有P2，P3,P4，P2的响应比为((5+4)/4=2.25),P3的响应比为((3+1)/1=4),P4的响应比为((2+4)/4=1.5)，显然选择3，虽然2和4都是一样的运行时间，但是2等待时间更长响应比也就越高。

8时刻：P3完成，此时剩下P2和P4，刚刚就算过两个任务的运行时间一样，经过相同的等待时间，P2还是比P4等待的时间长，所以2上cpu（不信可以计算响应比）。

12时刻：P2完成，还剩下P4，4上cpu

16时刻：所有任务完成，调度算法结束。

我们同样计算一下平均性能，首先计算周转时间

带权周转时间

等待时间

所以平均周转时间=(7+10+4+11)/4=8,平均带权周转时间=(1+2.5+4+2.75)/4=2.56，平均等待时间=(0+6+3+7)/4=4

前三种算法的总结

首先我们对比一下平均性能

我们发现FCFS确实平均性能有点拉胯，而SJF和SRNT虽然平均性能优秀但是饥饿现象导致也不太好，而RHHN不但没有饥饿现象，而且平均性能也较好甚至这题的情况下平均性能和SJF一样优秀，所以RHHN整体应该较为出色，但是每次都要计算响应比又加大了计算开销。

这几种算法主要关心的是对用户的公平性，平均周转时间和平均等待时间等平均性能的指标，但是并不关心响应时间，前面我们也提高到过平均性能一般是操作系统关心的，但是用户关心的是自己的任务能否更快完成，所以上面这几种方法对于用户来说交互性很糟糕，因此这三种算法一般适用于早期的批处理系统，当然FCFS现在也扮演着某些情况的重要角色。但是接下来我们在介绍几种更适合于交互式系统的调度算法。并且要注意上面的这几种算法对于高级调用和低级调用均可以采用。

时间片轮转（RR）

不陌生呀，前面介绍操作系统发展史时分时系统就是时候用的这个时间片从而大幅推进了系统的发展，那么接下来我们就详细了解一下时间片轮转调度算法。时间片轮转（RR,Round-Robin)公平的，轮流的为各个进程服务，让每一个进程在一定的时间间隔内都可以得到相应。按照各进程到达就绪队列的顺序，轮流的让各个进程执行一个时间片（如100ms）。若进程未能在一个时间片内执行完，则剥夺处理机（外中断），将进程重新放到就绪队列队尾重新排列。并且注意此时的时间片轮转只能适用于低级调度（进程调度），因为作业只有放入内存建立了相应的进程后才能分配给处理机时间片，所以高级调度不适用。很明显，RR是一种抢占式的进程调度算法，计时装备由时钟装置完成，到达一个时间片后，就由时钟中断来通知cpu时间已到。因为各个进程都会得到相应，所以不会造成饥饿现象。

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用时间片轮转调度算法，分析时间片大小分别为2,5时的进程情况。

时间片轮转算法轮流让就绪队列中的进程依次执行一个时间片（每次选择的都是排在就绪队列队头的进程）按照上表，就绪队列如下：

假设现在时间片为2那么

0时刻（P1(5)）：0时刻只有p1到达就绪队列，让P1上处理机运行一个时间片。

2时刻（P2(4)->P1(3）:2时刻P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾，此时2排在了队头，因此2上处理机（注意：此时P1由于运行完一个时间片刚下处理机，然后此时插进入了P2，那么默认他是排在刚刚完成的P1的前面即P2插入队尾紧接着P1插入队尾）。

4时刻（P1(3)->P3(1)->P2(2)）：4时刻，P3到达，先插到队尾，紧接着P2下处理机也插到队尾，此时又轮到P1上处理机。

5时刻（P3(1)->P2(2)->P4(6)）：5时刻，时间片还没结束，此时P4先任务插到末尾，由于一个时间片还没结束，所以此时1任务还在cpu上执行。

6时刻（P3(1)->P2(2)->P4(6)->P1(1)）：6时刻，P1时间片用完，下处理机，重新回到就绪队列的末尾，发生调度，3上处理机。

7时刻（P2(2)->P4(6)->P1(1)）：虽然P3的时间片还没用完，但是由于此时P3只需要一个时间，所以7时刻它运行完主动放弃了cpu，因此也发生调度，队头进程2上处理机。

9时刻（P4(6)->P1(1)）：进程2时间片用完，并且刚好运行结束，发生调度，P4上处理机。

11时刻（P1(1)->P4(4)）：P4时间片用完，重新回到就读队列队尾，队头任务1上处理机。

12时刻（P4(4)）:此时虽然时间片还有，但是1已运行完，主动放弃处理机，此时只剩下了P4，4上处理机。

14时刻（）：就绪队列为空，P4接着上cpu执行。

16时刻：所有进程运行结束，调度算法结束。

对于时间片5和上面类似，可以自己尝试。

这种RR算法更注重的是响应时间，因而不计算周转时间，一般来说，设计RR算法目的就是要让响应时间合适，即时间片要让切换进程的开销占比不超过10%。比如一个系统中有10个进程在并发执行，如果时间片为1s,则一个进程被相应的时间可能至少需要9s,也就是说用户在自己进程的时间片外通过键盘发出调试命令，可能需要等待9秒才能被系统响应（当然，如果实在自己的时间片内就会被立即响应）。这样时间片的大小也要制定合适，如果太大了，使得每一个任务都可以在

一个时间片内就完成，则时间片轮转调度算法就退化为FCFS算法了，并且会增大进程的响应时间。如果太小的话，进程调度、切换有时间代价（保存、恢复运行环境），因此如果时间片太小会导致花费大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例也减小了。

优先级调度算法（PSA)

优先级调度算法（PSA,Priority Scheduling Algorithm)的提出就是为了适应随着现代计算机的发展，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序的情况。每个作业/进程都有各自的优先级，调度时永远选择优先级最高的作业/进程，这种算法即可用于作业调度，也可用于进程调度，甚至，还会用于之后学习的I/O调度。PSA同时具有抢占式和非抢占式的两种情况，但是面对实际情况，一般的PSA都是抢占式的，非抢占式的实现简单，但是实际应用意义不太大。

思考:抢占式和非抢占式的PSA区别？

非抢占式的PSA需要在进程主动放弃处理机时进行调度，仍然没能有效解决实现紧急重要任务的初衷问题，而抢占式就是可以在就绪队列变化时检查是否产生了更高的优先级的任务，则进行抢占式切换所以肯定也是外中断了。

我们先来看一下非抢占式的PSA：各进程到达就绪队列的时间，需要运行的时间，进程优先数如下表所示（优先数越大，优先级越高）

非抢占式PSA每次调度选择当前已经到达且优先级最高的进程，当前进程主动放弃处理机时发生调度。

0时刻（P1）：只有P1到达，P1上处理机。

7时刻（P2,P3,P4）：P1运行完成放弃处理机，其余的三个进程都已经到达，选择优先级最高的P3上处理机。

8时刻（P2,P4）：P3完成，P2,P4优先级相同，则等待时间更长的（更早到达就绪队列的）先上，所以P2上处理机。

12时刻（P4）：P2完成，就绪队列只剩下P4,P4上处理机。

16时刻（）：P4完成，没有任务了，算法结束。

同样的我们在采取抢占式的PSA对上面的进程表进行调度：

抢占式的PSA永远要保证运行着的是优先级最高的任务，如果新到的任务优先级比正在运行的优先级高，则抢占，如果相同，则仍然等待（毕竟人家先到的）。

0时刻（P1）：只有P1到达，P1上处理机。

2时刻（P2）：P2到达就绪队列，发现此时P2优先级更高，虽然P1还在运行，抢占，P2上处理机，P1回到就绪队列。

4时刻（P1,P3）：P3到达，优先级比P2还高，虽然P2还在运行，抢占，P3上处理机，P2回到就绪队列。

5时刻（P1,P2,P4）：P3完成了，主动释放处理机，同时，P4也到达，由于P2比P4更先进入就绪队列，所以2上处理机。

7时刻（P1,P4）：P2完成，就绪队列只剩下P1,P4且P4优先级高，P4上处理机。

11时刻（P1）：P4完成，P1上处理机。

16时刻（）：P1完成，所有进程均已运行完，算法结束。

并且在PSA中就绪队列未必就只有一个，可以按照不同的优先级来组织，另外，也可以吧优先级高的进程排在更靠近队头的位置（使用优先级队列）。并且我们又跟据优先级是否动态改变分为了静态优先级和动态优先级两种。

静态优先级：创建进程时优先级确定，之后不发生改变。动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。

一般系统进程优先级是高于用户进程的，前台进程优先级高于后台进程，操作系统更偏好I/O型进程（或者称为I/O繁忙性进程），这样I/O设备和cpu可以并行工作（注意不是并发）。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早的投入工作，则资源利用率、系统吞吐量也就会得到提升。因此与I/O型进程相对立的就是计算型进程（或者称为cpu繁忙型进程）。

思考：为什么要存在动态优先级PSA？

可以从追求公平，提升资源利用率等角度考虑，如果某进程在就绪队列中等待了很长的时间则可以适当的提高其优先级，如果某进程长时间的占用处理机运行了很长时间，则可适当的降低其优先级，如果一个进程频繁的进行I/O操作，则可适当的提升其优先级。并且仔细思考，对于静态优先级的PSA，如果每次就绪队列中都会出现新的优先级高于进程P的进程，那么P就会长时间无法得到相应，造成饥饿现象的出现，所以动态优先级的PSA也可有效避免饥饿现象。

在PSA算法中用优先级区分紧急程度，重要程度，适用于实时操作系统，可灵活的调整对各个作业/进程的偏好程度。缺点是对于静态优先级的PSA可能会造成饥饿。

思考：有没有更好的算法?

思考我们已经介绍过得算法貌似都有自己的优缺点，FCFS公平但平均性能不好，SJF短作业永远优先平均性能优秀但是容易饥饿，高响应RHHN比虽然这种了FCFS和SJF但是对于用户交互糟糕且计算开销大，时间片RR虽然各进程相应但是应急能力一般，优先级PSA灵活调整各种进程服务的机会但是静态优先级易饥饿动态优先级实现较为复杂，所以有没有一种更好的这种考虑以上所有算法优点的同时缺点又不是那么明显的算法？有–多级反馈队列调度算法。

多级反馈队列调度算法（MFQSA）

多级队列反馈队列调度算法（Multilevel Feedback Queue Scheduling Algorithm）综合了上面算法的优点，他是设置多级就绪队列，各级队列优先级从高到低，时间片从小到大，新进程到达时先进入第1级队列队尾，按照FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进入下一个队列的队尾，在等待FCFS分配时间片，如果已经到达了最下级的队列还没执行完就重新放回该队列的队尾（所以永远是以非递增的顺序向低级队列插入），只有当第k级队列为空时，才会为k+1级队头的进程分配时间片用于进程调度。所以从整体来看，各个队列之间有静态PSA的特点，对于某一个队列里的进程又有RR的特点，同时从某个进程来看又有动态PSA和FCFS的特点，真实太妙了。当然这个算法也是抢占式的算法，即在k即队列的进程运行过程中(此时1~k-1级队列应该都已经为空)，若更上级的队列（1~k-1级)中又进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列的队尾。

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用MFQSA算法，分析运行情况。

0时刻：只有P1，P1上处理机运行一个时间片，下处理机。

1时刻：P2到达，P1还未能在一个时间1的情况下运行完，P1移动至第二队列，开始执行P2，P2上处理机。

2时刻：P2执行完一个时间片1，也没能执行完，所以也插到队列2，此时队列1空了，开始给队列2分发时间片。此时1先到的队列2，所以P1先执行，再次上cpu

4时刻：P1又执行完一个时间片2，此时还是没能执行完，插到队列3队尾，发现队列2还没空还有P2，P2上处理机。

5时刻：此时P2在cpu上执行了时间片2的一半，还没运行完，但是来了新任务3插入到了队列1末尾，此时队列1不是空的，抢占，2下cpu重新插回到队列2末尾。

6时刻：P3执行了一个时间片1执行完了，下cpu，不用在插入到队列2了，此时队列2的P2重新上cpu。

8时刻：P2又运行完了一个时间片2，此时P2完成，不需要在插到队列3了，此时队列1,2都空了，只剩下了队列3的P1，P1上cpu

12时刻：P1又执行完了一个时间片4，此时已经完成了7/8，还差1，所以重新插回到队列3的队尾，此时队列3只有P1，所以P1又上cpu

13时刻：P1运行完成，所有进程都结束，算法结束。

MFQSA对各类的进程都相对公平（FCFS的优点），每个进程到达都可以很快得到相应（RR的优点），短进程只用较少的时间就可以完成（SPF的优点），不必事先估计进程的运行时间（避免用户作假），可灵活的调整各类进程的偏好程度，比如cpu密集型进程，I/O密集型进程（拓展：MFQSA可将因I/O而阻塞的进程重新放回到原队列，这样I/O型进程就可以保持较高的优先级），唯一的缺点就是还是有可能造成饥饿现象的，但是概率不会像SPF那么大。

后三种算法的总结

比起早期的批处理操作系统来说，由于计算机的造价大幅下降，因此之后的交互式的操作系统（包括分时操作系统和实时操作系统等）更注重系统的响应时间、公平性和平衡性等指标。而这后面的这几种算法能较好的满足交互式系统的需求，因此这三种算法适用于交互式系统。（比如UNIX使用的就是多级反馈队列调度算法）。

总结

经过上面的6个算法的介绍，我们对各个算法都有了一定的了解，并且最好是记住英文缩写名字，因为考试有时候只给英文要对其有印象。前面三种要熟练掌握计算指标的方法，后面的三种方法要可以熟练表述运行过程并且了解优缺点，尤其是最后的MFQSA。这里我列出以下注意点总结希望你可以有所收获。

1. 抢占!=饥饿，对于抢占式动态PSA算法不会造成饥饿。

2. RR和MFQSA不适用于作业调度（高级调度），因为时间片的原因必须进入内存分配成进程后才能实现。

3. 等待时间最大!=带权周转时间最大，只是成正相关。

4. 有可能造成饥饿的算法：SJF,SPF,SRTN,抢占式的静态PSA和MFQSA。

5. 交互式糟糕的算法：FCFS,SJF,HRRN，交互式好的算法：RR,PSA,MFQSA