【操作系统】七大处理机调度算法详解

前言

        处理机调度是操作系统中最核心的问题之一，它负责分配处理机的时间，使得各个进程能够按照一定的顺序得到执行。处理机调度算法的好坏直接影响到整个系统的性能和效率。因此，研究处理机调度算法对于提高计算机系统的性能和效率具有非常重要的意义。
        本文旨在详细介绍处理机调度的基本概念、算法原理，并通过实例分析来加深对处理机调度算法的理解。本文将介绍包括先来先服务（FCFS）、短作业优先（SJF）、优先级调度（PSA）、高响应比优先（HRRN）、轮转法（RR）、多级反馈队列调度算法。

预备知识

• 作业调度：

  作业调度又称为高级调度，频度较低。其主要工作是按照某种调度算法从后备作业队列中挑选作业，为选中的作业分配内存和外设等资源，并排在就绪队列上。要注意的是作业调度仅仅是将作业调入内存，并为作业创建进程、分配资源，此时进程处于就绪态，并没有执行。

• 进程调度：

  进程调度又称为低级调度，是最基本的、频度最高的调度方式。其主要任务是从就绪队列中选取一个（或几个）进程，并分配处理机的过程，这时候才可以理解为“执行”。

• 作业调度与进程调度的区别：

1. 范围不同：作业调度是宏观调度，它所选择的作业只是具有获得处理机的资格，但尚未占有处理机。而进程调度是微观调度，动态地把处理机实际地分配给所选择的进程，使之真正活动起来（执行）。
2. 执行频率不同：作业调度执行的次数一般较少，而进程调度相当频繁。
3. 调度的对象、时机、方式等不同：在分时系统和实时系统中，用户进程数一般都多于处理机数，这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。
4. 系统目标不同：作业调度从全局考虑来提高系统的吞吐量以及资源利用率，追求的是作业周转时间的缩短。而进程调度则是以提高CPU利用率为目的。

• 周转时间：指作业被提交给系统（到达），到作业完成的这段时间； 
  • 即：周转时间 = 完成时间 - 到达时间
• 平均周转时间：作业周转时间之和 / 作业个数
• 带权周转时间：带权周转时间 = 作业完成时间 / 作业运行时间=（执行时间+等待时间）/ 运行时间，也可以写成：带权周转时间=周转时间/运行时间=（完成时间-提交时间）/运行时间
  • 即：带权周转时间 = 1 +（等待时间 / 执行时间）
• 平均带权周转时间：（作业带权周转时间之和）/ 作业个数

一、先来先服务（First-Come-First-Serve，简称FCFS）

•         先来先服务算法是最简单的调度算法。既可以用于作业调度，也可以用于进程调度。
•         用于作业调度时按照作业提交的先后顺序进行调度，即先到达的作业优先将它们调入内存，为它们分配资源创建进程，然后把它们放入就绪队列。
•         进程调度采用FCFS算法时，每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或者发生某事件而阻塞后（例如先来先服务调度算法在请求共享资源被占用时会阻塞等待，但是不会将处理机分配给其他进程），该进程一直运行到完成进程调度程序才将处理机分配给其他进程。
•         FCFS算法的优点是实现简单、公平性好，每个作业都能得到公平的执行机会。先来先服务调度算法不会发生饥饿现象。在FCFS算法中，每个作业都有机会获得处理机的执行，并且等待时间与作业的执行时间成正比。因此，即使长作业等待时间较长，也不会发生饥饿现象，因为每个作业都有机会获得处理机的执行。然而，FCFS算法也存在一些不足之处，例如对于长作业而言，其执行时间可能较长，导致后面的短作业需要等待较长时间才能执行，从而造成短作业的响应时间较长。因此，在一些对响应时间要求较高的场景下，FCFS算法可能会导致较长的平均等待时间和较差的系统性能。

        接下来通过实例分析加深理解，题目有一点点长，别着急，我们现在只解决先来先服务算法，其他的我们后面再逐一击破。

由于过程比较简单，这里直接放答案:

对于完成时间和周转时间以及带权周转时间的计算上面已经给出公式，这里不多说了，直接给出答案。

二、短作业优先（Shortest Job First，SJF）

•         短作业优先（Shortest Job First，SJF）是一种作业调度算法，该算法根据作业的执行时间来决定调度顺序。SJF算法要求作业在开始执行之前预计作业的执行时间，对预计执行时间短的作业优先调入内存。SJF算法能有效地降低作业的平均等待时间，提高系统吞吐量。然而，SJF算法也存在不容忽视的缺点，例如对长作业不利。请注意，短作业优先（SJF）既可以用于作业调度，又可以用于进程调度，但两者之间存在一些差别。在作业调度中，SJF算法每次从后备作业队列中挑选估计服务时间最短的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。而在进程调度中，SJF算法从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。
•         短作业优先（SJF）分为可抢占式和不可抢占式，如果没有说明，默认是非抢占式的。非抢占式短作业优先算法会优先选择最短的作业/进程进行服务，每次调度时都选择当前已到达且运行时间最短的作业/进程。抢占式短作业优先算法则会在每次有新的进程加入就绪队列时，引发就绪队列改变。当就绪队列改变时就需要调度，如果新到达的进程的剩余时间比当前运行的进程的剩余时间更短，则有新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

        还是刚刚那到题，

首先是不可抢占的SJF： A进程时间0到达，此时就绪队列只有它一个进程，显然A分配处理机开始执行，又由于是不可抢占的，即使B的服务时间更短也不影响A，因此A执行3个时间单位后结束，让出处理机。

此时C、D、E进程还未到达，显然B进程得到处理机开始执行，同理B进程不可被抢占，一直执行到完成。当B进程完成，此时C、D、E进程已经全部到达就绪队列。

由于剩下的进程里E进程的服务时间最短，C进程次之，D进程最长，所以按E、C、D的顺序执行。

现在来看看可抢占的SJF：

A进程时间0到达，此时就绪队列只有它一个进程，显然A进程分配处理机开始执行，当执行到时间2时，B进程到达就绪队列，由于是可抢占的，我们要看当前执行的进程（A进程）和B进程哪一个是运行时间最短的，显然是A，那么A继续执行。A在时间3执行完成，此时只有B进程，显然B开始执行，B执行到时间4时，C进程到达就绪队列，同理进行判断，由于C进程运行时间最短，C进程抢占处理机，当前运行进程（B进程）重新回到就绪队列。

C进程执行到时间6，D进程进入就绪队列......之后同理进行分析即可 。

下面给出答案：

三、优先级调度算法

• 优先级调度算法是一种常见的作业/进程调度算法，该算法根据作业/进程的优先级来进行调度。在优先级调度中，每个作业/进程都有一个优先级，优先级高的作业/进程会先于优先级低的作业/进程获得处理机。
• 优先级调度算法可以分为静态优先级调度和动态优先级调度。
• 静态优先级调度在作业/进程进入系统或创建时被赋予一个优先级，该优先级在作业/进程生命周期内不会再改变。这种调度算法简单、开销小，但有可能出现优先级低的作业/进程长时间得不到调度的的情况。
• 动态优先级调度在作业/进程进入系统或创建时被赋予一个优先级，但随着时间的推进，不同调度对象的优先级不断地进行动态调整，避免资源浪费。这种调度算法更公平、更灵活，能更好地利用资源，但实现起来可能更复杂。
• 在优先级调度算法中，根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为非剥夺式优先级调度算法和剥夺式优先级调度算法。非剥夺式优先级调度算法让正在执行的进程继续执行，直到由于其自身的原因而主动让出处理机时（任务完成或等待事件），才把处理机分配给更为重要或紧迫的进程。剥夺式优先级调度算法则允许新的更高优先级进程抢占正在执行的进程的处理机。

四、高响应比优先（HRRN）算法

•         高响应比优先（HRRN）算法是一种折中的作业调度算法，它既考虑了作业的等待时间，又考虑了作业的运行时间。HRRN算法在FCFS（先来先服务）和SJF（短作业优先）之间取得平衡。
•         具体来说，高响应比优先算法给每个作业一个动态优先级，这个优先级随着时间的推移而变化。等待时间越长，优先级就越高，这意味着等待了更长时间的作业将获得更多的关注。同时，如果一个作业的运行时间较短，那么它的优先级也会相应提高，从而使其更有可能被优先执行。这种优先级的计算公式为：响应比 =（等待时间+要求服务时间）/ 要求服务时间。
• 响应比要与带权周转时间做一个区分：带权周转时间和响应比的值是一模一样的，但是概念完全不一样。
•         HRRN算法的优点在于它同时考虑了长作业和短作业，避免了FCFS算法只考虑作业等待时间而忽视运行时间的问题，也避免了SJF算法只考虑作业运行时间而忽视等待时间的问题。因此，HRRN算法可以在处理机调度中实现较好的折中，既照顾了短作业又不致使长作业等待时间过长。然而，每次计算响应比都会花费一定的时间，即时间开销，其性能略差于SJF算法。

还是熟悉的那道题：

A进程先运行，之后根据其他作业的响应比决定运行顺序。在时间为3时，由于只有B进程在就绪队列中，所以B执行。B执行完成后，C、D、E进程都进入了就绪队列，则根据响应比决定运行顺序。

C进程的响应比：1+（5/4）=2.25

D进程的响应比：1+（3/5）=1.6

E进程的响应比：1+（1/2）=1.5

所以C进程得到处理机开始运行。

 只剩下D、E进程，重新计算响应比：

D进程的响应比：1+（7/5）=2.4

E进程的响应比：1+（5/2）=3.5

所以E进程得到处理机开始运行。

最后执行D：

即如下图所示：

计算答案自己对照：

五、轮转法（RR）

•         轮转法（Round-Robin，RR）主要用于分时系统中的进程调度。为了实现 RR 调度，我们再次将就绪队列视为进程的FCFS队列。新进程添加到就绪队列的尾部。为实现轮转调度，系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，进程调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。时间片是一个小的时间单位，通常为10~100ms数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，把它放入就绪队列的末尾；然后，把CPU分给就绪队列的队首进程，同样也让它运行一个时间片，如此往复。需要注意的是，轮转法通常采用循环方式进行调度，即当就绪队列中的所有进程都被执行一遍后，调度程序会从头开始再次选择进程执行。
• 注意：如果某一个进程下机，同时新进程到达，默认新到达的进程先进入就绪队列。

还是这道题：

分析：

时间为0-2时：就绪队列里只有A（规定右边是队头），所以A执行两个时间片

时间2开始时：（也就是A进程第二个时间片的末尾）A进程停止执行准备下机，此时B进程同时到达，根据如果某一个进程下机，同时新进程到达，默认新到达的进程先进入就绪队列，所以B进程排在队头，就绪队列如下：

        所以B执行，执行后B进程排到队尾：

时间3开始时：由上图接下来A进程执行，A进程执行完这个时间片就结束了。所以A进程的完成时间是4。

时间4开始时：由上图接下来B进程执行，同时C到达就绪队列，B执行完一个时间片后排到队尾：

时间5开始时：由上图接下来C进程执行，执行完后排到队尾：

时间6开始时（也就是时间5的末尾）：由上图接下来B进程执行，时间5的C进程下机的同时D到达就绪队列，由上面提到的注意可知D先进入就绪队列排在C之前，B执行完一个时间片后排在队尾：

时间7开始时：由上图接下来D进程执行，执行完后排到队尾：

时间8开始时：由上图接下来C进程执行，时间7的D进程下机的同时E到达就绪队列，E进程先进入就绪列排在D之前，C执行完一个时间片后排在队尾：

时间9开始：此后以B、E、D、C的顺序循环两轮后，E进程（时间10和14开始时分别执行一个时间片，时间15结束）和C进程（时间12和16开始时分别执行一个时间片，时间17结束）都结束了。

时间17开始：B进程执行一个时间片，此时B进程也结束了，就绪队列只剩下D进程，之后将D进程执行完毕即可。所以B进程的完成时间是18。D进程完成时间是20。

如下图：

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

调度机制：

(1) 设置多个就绪队列。

        赋予每个队列不同的优先级，第一个队列优先级最高，第二个次之，其余逐个降低。
(2) 每个队列都采用FCFS算法。
        当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，调度程序将其转入第二队列的末尾等待调度；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。如果此时已经在最下级的队列，则重新放回最下级队列队尾。
(3) 按队列优先级调度。
        调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行；换言之，仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。

重点理解：

• 多级反馈队列调度是可抢占的
• 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
• 被抢占处理机的进程重新放回原队列队尾  

话不多说，上题（马上就拿下了，坚持就是胜利！）：

首先看立即抢占式的：（规定右边是队头）

对照这个图更好理解，画图好难，这里偷懒：

进程A在第1级队列执行1个时间片（2的0次方），进程A没有结束，进入第2级队列。

此时第1级队列就为空：

进程A在第2级队列执行一个时间片后，B进程到达，进入第1级队列，当新进程进入任一优先级较高的队列，此时须立即把正在运行的进程（A进程）放回到当前队列（第2级队列）的末尾，而把处理机分配给新到的高优先级进程（B进程）。

接下来B进程执行一个时间片之后，B进程没有结束也进入第2级队列：

A进程执行一个时间片后就结束了，此时C进程恰好到达，进入第1级反馈队列，C进程执行一个时间片后，由于未结束，继续进入第2级队列的队尾：

B进程执行一个时间片后，进程D恰好到达，D进程就进入了第1级反馈队列，处理机分配给优先级高的进程D执行一个时间片，并且将进程B放到第2级队列的队尾，D进程未结束，进入第2级反馈队列，放在队尾。

C进程执行一个时间片后，进程E就进入了第1级反馈队列，同理，E进程执行一个时间片并且将C进程放在第2级队列的队尾，E进入第2级队列，放在队尾。

B进程在第2级队列执行两个时间片后，B进程未结束，继续放在第3级队列的队尾，接下来D进程执行两个时间片，也未结束，进入第3级队列的队尾。

C进程在第2级队列执行两个时间片后，恰好结束，接下来E进程执行1个时间片就结束了

此时只剩下第3级队列里有两个进程，B进程执行两个时间片就结束了，之后D进程也执行了两个时间片结束。

文章来源地址https://www.toymoban.com/news/detail-768495.html

到了这里，关于【操作系统】七大处理机调度算法详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！