---

前言

本文的主要内容是调度算法的介绍，包括先来先服务(FCFS)、最短时间优先(SJF)、最高响应比优先(HRRN)、时间片轮转(RR)、优先级调度和多级反馈队列这六种方法，这些调度算法会从其算法思想、算法规则、该方法用于作业调度还是进程调度、进程调度的方式(抢占式和非抢占式)、优缺点以及是否会导致饥饿这几个方面展开介绍，同时在介绍每种调度算法时还会举例子辅助理解。

---

一、先来先服务(FCFS)

饥饿是进程或者作业长期得不到服务而产生的一种状态。
先来先服务(FCFS, First Come First Serve)
算法思想：从公平的角度考虑，类似于排队购物、打饭等。
算法规则：按照作业或者进程到达的先后顺序进行服务。
方法用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。
进程调度的方式：非抢占式算法。
举一个 FCFS 算法的例子，如下图所示。

优缺点：优点是算法公平且实现简单；缺点是排队在长作业或长进程后面的短作业或短进程需要等待很长的时间，带权周转时间很大，对短作业或进程的用户体验不好。所以先来先服务算法对长作业有利，对短作业不利。
是否会导致饥饿：不会导致饥饿。

---

二、最短时间优先(SJF)

最短时间优先(SJF, Shortest Job First)
算法思想：追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间。
算法规则：最短的作业或者进程优先得到服务，这里的最短指的是要求服务的时间最短。
方法用于作业/进程调度：即可用于作业调度，也可以用于进程调度，用于进程调度时称为最短进程优先算法(SPF, Shortest Process First)。
进程调度的方式：最短时间优先和最短进程优先是非抢占式算法，但也有抢占式的算法——最短剩余时间优先算法。
最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)是每当有进程加入就绪队列发生改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列，此外，当一个进程完成时也需要重新调度。
举一个非抢占式 SJF 算法的例子，如下图所示。

同样是上面的例子，但是采用非抢占式 SJF 算法要比 FCFS 算法的平均周转时间、平均带权周转时间和平均等待时间都要短。
再举一个抢占式 SJF 算法的例子，也就是最短剩余时间优先算法(SRTN)，如下图所示。

下图是对上面例子各时刻的分析，其中括号内的数值表示此刻该进程的最短剩余时间，红色的表示该时刻处理机正在运行的进程。

可以看到，在 SRTN 算法下，每个进程的完成可能不是一气呵成的，但是该方法比非抢占式 SJF 算法的平均周转时间、平均带权周转时间和平均等待时间都要短。
SJF 算法默认是非抢占式的，该算法的平均等待时间、平均周转时间相对来说较短。在所有进程同时可运行时(或者所有进程几乎同时到达时)，采用 SJF 算法的平均等待时间和平均周转时间最少。
优缺点：优点是有较短的平均等待时间和平均周转时间；缺点是不太公平，对短作业有利，对长作业不利，可能产生饥饿现象，此外，作业或者进程的运行时间是由用户提供的，并不一定真实，所以不一定能做到真正的短作业优先。
是否会导致饥饿：会导致饥饿，如果源源不断的有短作业或短进程到来，可能会使得长作业或者长进程长时间的得不到服务，因此产生饥饿现象，如果一直得不到服务，则称为饿死。

---

三、最高响应比优先(HRRN)

FCFS 算法是在每次调度的时候选择一个等待时间最长的作业或进程为其服务，但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题。
SJF 算法是选择一个执行时间最短的作业为其服务，但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。
最高响应比优先(HRRN, Highest Response Ratio Next) 算法就要综合作业或进程的运行时间和等待时间。
算法思想：综合考虑作业或进程的等待时间和要求服务的时间。
算法规则：在每次调度时先计算各个作业或进程的响应比，选择响应比最高的作业或进程为其服务。
响应比=$\frac{等待时间+要求服务的时间}{要求服务的时间}$，由该公式可知，响应比一定是大于等于1的。
方法用于作业/进程调度：即可用于作业调度，也可用于进程调度。
进程调度的方式：非抢占式算法，所以只有当前运行的作业或进程主动放弃处理机时，才需要调度和计算响应比。
举一个 HRRN 算法的例子，如下图所示。

由上图可知，HRRN 算法是非抢占式，因此只有某个进程完成时才会计算其他进程的响应比，然后按照响应比分配处理机。
优缺点：综合考虑了等待时间和运行时间，当等待时间相同时，要求服务时间短的优先(SJF 算法的优点)；当要求服务时间相同时，等待时间长的优先(FCFS 算法的优点)。对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。
是否会导致饥饿：不会导致饥饿。
上面提到的这几种算法主要关心用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心响应时间，也不区分任务的紧急程度，因此对用户来说，交互性比较差，所以这几方法适用于早期的批处理系统。

---

四、时间片轮转(RR)

时间片轮转(RR, Round-Robin)
算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。
算法规则：按照各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
方法用于作业/进程调度：只能用于进程调度，只有作业放入内存建立了相应的进程后，才能被分配处理机时间片。
进程调度的方式：抢占式算法，由时钟装置发出时钟中断来通知 CPU 时间片已到。
举一个 RR 算法的例子，如下图所示。

时间片大小为2时的结果如下图所示。

如果在某一时刻，有一个新进程到达且有一个进程的时间片已到但是还没运行完，那在排序时，新到达的进程在前，该进程排在队尾。
下图是时间片为5的 RR 算法和 FCFS 算法的比较，可以发现，两者非常相似。

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间，因此时间片不能太大。另一方面，进程调度和切换是有代价的，如果时间片太小，会导致进程切换过于频繁，系统会花费大量的时机来处理进程切换，从而导致实际用于进程执行的时间比例减少，所以时间片也不能太小。一般来说，设计时间片时要让切换进程的开销占比不超过1%。
优缺点：优点是公平，响应快，且适合于分时操作系统；缺点是由于高频率的进程切换，因此有一定的系统开销，同时也不区分任务的紧急程度。
是否会导致饥饿：不会导致饥饿。

---

五、优先级调度

算法思想：随着计算机的发展，特别是实时操作系统系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
算法规则：每个作业或进程有各自的优先级，调度时选择优先级最高的作业或进程。
方法用于作业/进程调度：可用于作业调度，也可用于进程调度，还会用于I/O调度。
进程调度的方式：抢占式和非抢占式都有，区别在于非抢占式只需要在进程主动放弃处理机时进行调度，而抢占式的还需要在就绪队列变化时检查是否会发生抢占。
举一个非抢占式优先级调度算法的例子，如下图所示。

再举一个抢占式优先级调度算法的例子，如下图所示。

通过这两个例子就可以看出两者的区别，即非抢占式优先级调度算法只需要在进程主动放弃处理机时进行调度，而抢占式优先级调度算法还需要在就绪队列变化时检查是否会发生抢占，然后再分配处理机。
合理地设置各类进程的优先级：
①系统进程优先级高于用户进程；
②前台进程优先级高于后台进程；
③操作系统更偏好 I/O 型进程(I/O 繁忙型进程)。
这里解释一下为什么操作系统更偏好 I/O 型进程，与 I/O 型进程相对的是计算型进程(CPU繁忙型进程)，I/O 设备和 CPU 可以并行地工作，所以如果让 I/O 型进程优先运行的话，则越有可能让 I/O 设备尽早地投入工作，则资源的利用率和系统吞吐量等都会得到提升。
根据优先级是否可以动态地改变，可以将优先级分为静态优先级和动态优先级两种。静态优先级在创建进程时就已经确定，之后一直不变；动态优先级创建进程时有一个初始值，之后会根据情况动态地调整优先级。
动态优先级的调整时机：从追求公平、提升资源利用率等角度考虑。如果某进程在就绪队列中等待了很长时间，可以适当提升其优先级；如果某进程占用处理机运行了很长时间，可以适当降低其优先级；如果发现一个进程频繁地进行I/O操作，可以适当提升其优先级。
优缺点：优点是用优先级区分紧急程度、重要程度，适用于实时操作系统，可灵活地调整对各种作业或进程的偏好程度；缺点是若源源不断地有高优先级进程到来，则可能导致饥饿。
是否会导致饥饿：会导致饥饿。

---

六、多级反馈队列

FCFS 算法的优点是公平；SJF 算法的优点是能尽快处理完短作业，平均等待时间、平均周转时间等参数优秀；时间片轮转调度算法可以让各个进程得到及时的响应；优先级调度算法可以灵活地调整各种进程被服务的机会。为了综合以上各算法的优点，多级反馈队列应运而生。
算法思想：对其他调度算法的折中权衡。
算法规则：设置多级就绪队列，各级队列优先级从高到低，时间片从小到大；新进程到达时先进入第一级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经是在最下级的队列，则重新放回该队列队尾；只有第 k 级队列为空时，才会为 k+1 级队列头的进程分配时间片；被抢占处理机的进程重新放回原队列队尾。
方法用于作业/进程调度：只用于进程调度。
进程调度的方式：抢占式算法，在 k 级队列的进程运行过程中，若更上级的队列中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾。
举一个多级反馈队列算法的例子，如下图所示。

注意在执行的过程中，每执行完一个级别的时间片，若进程没有执行完，则该进程优先级下降，移动到下一级队列的队尾，当然在运行的时候，如果更高级别进入了一个新进程，即使当前运行的进程时间片还没运行完，也会被剥夺处理机，该进程在原队列队尾等待更高优先级的进程运行完成。
优缺点：优点是对于各类型进程相对公平(FCFS 的优点)；每个新到达的进程都可以很快就得到响应(RR 的优点)；短进程只用较少的时间就可完成(SPF 的优点)；不必实现估计进程的运行时间(避免用户作假)；可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程 (可以将因 I/O 而阻塞的进程重新放回到原队列而不是优先级更低的下一级队列，这样 I/O 型进程就可以保持较高的优先级) 。缺点是可能会导致饥饿。
是否会导致饥饿：被降级的进程可能会一直等待，因此会导致饥饿。
比起早期的批处理操作系统，由于计算机造价大幅降低，因此之后出现的交互式操作系统更注重系统的响应时间、公平性、平衡性等指标，而时间片轮转、优先级调度和多级反馈队列算法正好能够满足交互式系统的需求，因此这三种算法适合于交互式系统。

---

总结

以上就是操作系统——调度算法的所有内容了，本文中大致分为批处理操作系统时期使用的先来先服务、最短时间优先和最高响应比优先算法和交互式系统中的时间片轮转、优先级调度和多级反馈队列算法，重点掌握这些方法的算法思想、算法规则、该方法用于作业调度还是进程调度、进程调度的方式、优缺点以及是否会导致饥饿等这几个方面。
参考视频：
FCFS、SJF、HRRN调度算法
时间片轮转、优先级调度、多级反馈队列