225_调度算法：时间片轮转、优先级、多级反馈队列
# 2.2_5_调度算法：时间片轮转、优先级、多级反馈队列
各位同学大家好，在这个小节中我们会学习剩下的几种调度算法，包括时间片轮转，优先级调度，多级反馈、队列调度算法。
那么在学习小节的内容和上个小节一样，大家需要注意各种算法，他们的算法思想是什么，这些算法的提出主要是为了解决什么问题。
第二点最需要关注的当然是这些算法到底是怎么运行的，它们的规则是什么？
另外呢这些算法到底适用于、作业调度还是进程调度分别有什么区别？
还有这些算法到底是抢占式的还是非抢占式的，这些都需要大家稍微注意一下。
另外优点和缺点一定是小节和上个小节，最常作为选择题考察的知识点，最后我们还需要关注这些算法到底有没有可能导致饥饿现象，那么我们会按从上至下的顺序依次讲解。
# 时间片轮转
首先我们来看一下时间片轮转调度算法，这种算法的提出其实是为了公平轮流的为各个进程服务，然后可以让各个进程在一定长度的时间间隔内都可以得到响应。
其实时间片轮转调度算法是伴随着分时操作系统的诞生而诞生的，那么这种算法的规则其实也相对来说也比较简单，就是操作系统会按照各个进程，他们到达就绪队列的顺序，轮流的让各个进程执行一个时间片，而这个时间片的长短是不一定的，就是有的操作系统可能会设置的长一点，有的可能会设置的短一点，而有的甚至有可能会动态的调整。
那么当一个进程它的时间片执行，它的时间片用完了之后，进程会被强行的剥夺处理机，然后把正在运行的进程重新放回就绪队列里，再重新排队等待调度。
而时间片轮转调度算法它一般是用于进程调度的，因为所谓时间片其实指的是处理机的时间片，而一个作业只有当它放入了内存，并且建立了相应的进程之后，只有作为进程，它才有可能被分配处理机的时间片，因为进程肯定是执行的基本单位，所以说这个算法一定是用于进程调度的
而通过刚才的这个描述，我们会发现当一个进程它的时间片用完之后，虽然说它还没有结束，但是有可能会被强行的剥夺处理机资源。所以说这种算法肯定是一种抢占式的算法，并不一定要等到进程主动的放弃处理机才会发生调度。而这种抢占或者说这种时间片的切换，是由时钟时钟装置，也就是某一种计时的硬件来发出时钟中断，来通知 CPU 时间片已到的，而时钟中断还有时钟装置这些具体的内容会在计算机组成原理那门课里进行学习。如果不考这门课的同学只需要有个了解，能有个印象就可以了。
那么我们用一个例题来具体看一下这个算法到底是怎么运转的，这些进程他们的到达次序依次是这样的，那么我们分别分析一下，如果我们把时间片大小分别设为 2 和 5 时分别是什么情况。
这个地方大家可能会注意到，在这个题目当中，我们并不像上一小节那几个调度算法一样，还来计算它的什么平均周转时间，平均等待时间这些指标，原因在于时间片轮转调度算法，它一般是用于分时操作系统的，比起之前所说的那些什么平均周转时间那些东西来说，这种类型的操作系统会更关心进程的响应时间，所以在这个地方我们也不再计算进程的什么等待时间周转时间这些指标，当然如果说题目中要求大家计算的话，也需要自己要学会分析，不过我相信经过上一小节的讲解，大家应该已经学会怎么计算了。
那么如果说我们按照时间片大小为 2 来进行来运行的话，刚开始就序对列是空的，然后在 0 这个时刻 p1 进程到达了，并且此时就绪队列当中只有 P1 这个进程，所以肯定是让 p1 上处理机运行一个时间片，而一个时间片的大小是 2 两个单位的时间长度，所以 p1 上处理机运行了两个单位的时间长度之后，这个时间片就用完了，然后会进行下一次调度，也就是在时刻二的时候会进行一次调度。
而这个时候进程 2 ，p2 刚好也在第二个时刻到达，并且 P1 它由运行态重新回到就绪态，然后又会重新插入到就绪队列的队尾，所以这个时刻 p2 到达就绪队列，然后 p1 也会重新回到对位，虽然 p1 也是在二这个时刻放下处理机，然后回到就绪队列里的，而且 p2 进程也是在二这个时刻是同时到达的。但是如果我们在题目当中遇到这种情况的话，我们一般是默认新到达的进程，也就是 p2 进程它先插入就绪队列，然后之后下处理机的进程再紧随其后，再回到就序列列，所以我们把 p2 排在前，p1 排在后。但是如果题目中有特别的说明，大家需要随机应变，根据题目给出的规则来进行分析。
所以 2 这个时刻，由于此时 p2 是处于就绪队列的队头的元素，所以我们会让 p2 上处理机运行一个时间片，也就是两个单位的时间，那么在 4 时刻 p3 到达，并且和刚才一样，p2 也会紧接着下处理机，加入到就绪队列的对位。
然后 4 这个时刻发生的调度就是选择对头的元素 p1 让他上处理机，再执行两个两个单位的时间，也就是一个时间片的大小。那么 p1 在执行了一个单位的时间，也就是到了 5 这个时刻的时候，p4 进程到达，所以 p4 会被插入到就绪队列的队尾。
但是需要注意的是，虽然此时 p4 到达，但是由于 p1 的时间片还没有用完，它的时间偏大小为二，但是此时只用了一个单位的时间，所以暂时不会发生调度。另外为什么 p1 没有出现在就绪队列里，因为此时 p1 还处于运行态，所以它肯定是在 CPU 上执行的，所以 p1 现在暂时不会出现在就绪队列当中，所以是这个样子。
那么接下来 p1 又会继续执行一个单位的时间，把他自己的时间片给用完，那么在 6 这个时刻，由于它时间片用完了，所以又会发生一次调度，p1 下处理机重新放回就绪队列队尾。然后 p3 就是对头元素上处理机运行。
然后需要注意的是 p3 的运行时间总共只需要一个单位的时间，所以虽然说就时间片的大小是二，但是由于 p3 只需要运行一个单位的时间，所以在 7 这个时刻，p3 就会主动的放弃处理机，所以虽然此时分配给 p3 的时间片他还没有用完，但是由于 p3 的主动放弃，所以我们也需要发生一次调度，选择下一个进程上处理机。那么 p3 放弃处理机之后，p2 在对头，所以 p2 上处理机运行，并且 p2 是在继续运行两个单位的时间，刚好它剩余的时间，那么 p2 在运行两个单位之后，就这个时刻又会发生调度，然后 p4 上处理机运行，接下来就和之前讲的那些情况很类似了，p4 运行一个时间片之后调度，然后 p1 再上处理机运行，p1 由于它只剩下一个单位的时间，所以当它运行了一个单位的时间，也就到 12 这个时刻， p 它也会像 p3 一样主动的放弃处理机，于是 p4 进程又会被调度上处理机执行。在 p4 执行了一个时间片之后，操作系统会再次发生调度，但是由于此时就绪，队列已经为空了，所以它会继续让 p4 接着运行一个时间片。
那么到 16 这个时刻，p4 把它剩余的这些运行时间全部运行完，所以 p4 就结束了。那么 16 这个时刻也就意味着所有的进程已经完成，这就是时间片大小为 2 的情况。
接下来我们再来看一下时间片大小为 5 的时候会发生什么情况。在刚开始 0 这个时刻只有 p1 到达，所以 p1 上去处理机运行，而由于它的运行时间只有 5 个单位的时间，并且给它分配的时间片大小也为 5，所以给它分配的时间片足够它运行结束。所以 p1 在 0~5 这段时间内，p1 都会一直运行，而期间 2 这个时刻，4 这个时刻，还有 5 这个时刻，P2，P3，P4 会依次到达，而在 5 这个时刻，p1 刚好运行完成，它下处理机之后会发生第二次调度。
这个时候 p2 进程由于它是先到达的，所以它排在就绪队列的队头，因此会选择让 p2 上处理器运行。
同样的 p2 的运行时间小于给它分配的时间片的大小，所以到 9 这个时刻 p2 的时间片没有用完，但是他会主动的放弃处理机，然后进行第三次调度，此时就绪，队列里只剩 p3 和 p4，然后 p3 是排在队头的，所以 p3 上处理机运行运行了一个单位的时间之后，p3 又主动的放弃处理机，然后 p4 上处理机运行到 15 这个时刻批次运行了一个时间片大小的这么长的时间之后，操作系统此时本来应该发生调度的，但是他发现此时就序队列已经为空了，所以它会让 p4 继续执行一个时间片，所以一直到 16 这个时刻，p4 的所有的运行时间都已经运行了，那么它会放弃处理机，然后所有的进程就执行结束，所以这就是时间片大小为 5 的情况。
接下来我们再看看一个，假如说我们按照先来先服务调度算法，来调度这些程序这些进程的话，那么它的调度顺序是这样子，有没有发现它和我们刚才时间片为 5 这种情况是很类似的，除了最后这个地方操作系统还需要做一个小小的检查之外，其他的这些就是发生调度的时机，还有甚至调度的顺序都是一模一样的。
所以我们会有这样的一个结论，如果说我们的时间片太大，导致每个进程都可以在一个时间片内完成的话，那么时间片轮转调度算法就会退化为先来先服务调度算法。在刚才咱们举的这个例子当中，假如我们把时间片的大小设置为 6 或者是，或者是比 6 更大的值，那么这个时间片轮转调度算法，就会导致每一个进程都可以在给自己分配的时间片之内就执行结束，所有的调度都只会发生在这些进程主动放弃处理机的时候，并且这些调度的顺序也会按照各个进程到达就绪队列的先后顺序来依次调度。那么这个算法就完全退化为了先来先服务的调度算法。
所以如果时间片太大的话，当然也会增大一些进程的响应时间，就失去了时间片轮转调度算法最大的一个优点，所以时间片是不能选择的太大的。
那么怎么理解它会增大各个进程的响应时间呢？比如说我们这个系统当中有 10 个进程正在并发的执行，如果说我们把时间片大小设置为 1s 的话，那么如果一个进程被响应，有可能需要等待 9 秒，如果一个用户在自己的时间片刚好用完的时候，发出了通过键盘发出了一个调试命令，那么这个调试命令就需要等待 9 秒之后才有可能被系统响应，所以这就大大的增加了进程的响应时间。
而第二点，如果我们把时间片设置得太小的话，又会导致进程的切换过于频繁。而我们在之前的小结之前的讲解当中，我们已经知道进程调度和切换，它是由于需要保存恢复运行环境，然后中间处理一系列的事情，所以调度和切换其实是需要付出一定的时间代价的。所以如果说进程切换过于频繁，那么系统会花大量的大部分的时间来处理进程，切换中间的这些事情，从而导致我们实际进行运行进程执行的时间比例反而会减少。所以可以看到经时间片的大小，如果选择太小的话，其实也是不利的。
因此我们一定要选择一个时间片大小适中的这种情况。而怎么定义这个时间片太小，一般来说在设计时间片的大小的时候，可以让就是切换进程所造成的开销比例占比不超过 1% ，那么在这种情况下，我们就认为这样的时间片不是太小，可以接受的，而一般来说不会考察，只是作为一个拓展，让大家能有更进一步的了解。
那么这就是时间片轮转调度算法的一系列的规则，还有一些细节优点，很明显对各个进程都是公平的，会轮流的为他们服务，并且响应很快，只要我们设置的时间片大小是合理的，那么就会在一定的时间间隔内就可以给各个进程各个用户都有一个响应。所以这种调度算法就比较适合于分时操作系统，可以为各个用户分配一个大小的时间片。
而缺点就是刚才咱们说的用于进程切换的时候会有一定的开销，另外这个算法它并不区分任务的紧急程度，而通过刚才对算法规则的了解，我们会发现这种算法其实是不可能导致饥饿的，因为它肯定是轮流的会为各个进程服务。
最后我们需要注意的是刚才强调的问题，就是时间片太大或者太小，分别会有什么影响，在选择题当中经常会作为考察。以上就是时间片轮转调度算法，
# 优先级调度算法
下一种算法是优先级调度算法，这种算法其实是随着计算机的发展，然后越来越多的应用场景需要根据任务的紧急程度重要程度来决定处理这些任务，处理这些进程的顺序，所以就提出了优先级调度算法。
它会为每一个作业或者进程设置一个优先级，然后在调度的时候会选择优先级最高的一个进程或者作业进行调度，那么这个算法的规则并不复杂，这个算法既可以用于作业调度，也可以用于进程调度，唯一的区别在于用于作业调度的时候，就是把一个处于外存当中的外存后备队列当中的作业，选择一个，然后进入内存。然后用于进程调度的时候，是选择一个在内存的就绪队列当中的一个进程，为它分配处理机，这一点咱们在之前的讲解当中也已经强调过很多遍，那么优先级调度算法甚至还可以用于我们之后会学到的 IO 调度。
这个算法它既有抢占式的，也有非抢占式的版本。在做题的时候我们需要注意的是非抢占式的，我们只需要在一个进程主动放弃处理机的时候来检查，这个时候进行调度就可以。而如果说题目告诉我们，采用的是抢占式的优先级调度算法的话，那么当一个就绪队列发生改变的时候，我们也需要检查是否会发生抢占
具体我们用一个例题来进行说明。各个进程的到达时间运行时间还要优先数是像这个样子，这个地方优先数越大，优先级越高，大家需要注意的是优先数和优先级概念并不一样，有的题目当中有可能是优先数越小，优先级越高，所以具体要看题目给出的信息和条件。
既然采用的是非抢占式的优先级调度算法，那么也就是说我们只需要关注各个进程，主动放弃处理机的时候，这个时刻就可以了。所以整个调度的情况是这个样子，
在 0 这个时刻，p1 整个系统当中只有 p1 进程到达，所以 p1 理所应当让它上处理机运行，而只有 p1 主动放弃处理机，也就是它运行了 7 个单位的时间之后，我们才会进行第二次的调度。
在这个时候其他的这些进程都已经到达了，但是由于 p3 的优先数最高，也就是优先级最高，所以我们会在这次调度当中选择优先级最高的 p3 进程，让它上处理机运行。而 p3 在 8 这个时刻也就运行了一个单位的时间之后，他会主动的放弃处理机，接下来就是下一次调度，那么 p2 和 p4 这两个进程他们的优先级是一样的，但是不同的在于不同点在于 p2 它的到达时间是要比 p4 更早的，所以 p2 会优先上处理机运行。
然后 P2 运行 4 个单位的时间之后再调度再进行，下次调度此时只剩下 P4，然后 P4 运行，一直到它结束，就 16 这个时刻，这就是非抢占式的优先级调度算法。
而如果我们采用的是抢占式的优先级调度算法的话，就是我们除了要关注各个进程，主动放弃处理机这样的一个时刻之外，我们还需要关注这个就绪队列发生改变的时刻，我们要检查一下到底是不是会发生抢占，是不是当前到达的进程优先级，要比此时正在运行的进程优先级还要更高。
那么在 0 这个时刻，p1 到达只有 p1，系统当中只有 p1 进程，所以 p1 理所应当上处理机。但是当它运行到二这个时刻的时候，p2 进程到达了， p2 的优先级，要比 p1 更高，所以 p2 会抢占处理机，然后 p1 回到就绪队列，
所以 p2 在抢占了处理机之后，它又会继续运行，直到 4 这个时刻，p3 进程到达就绪队列，也就是说就绪队列发生了改变。所以这个时候系统也会检查到底是否会发生抢占。由于 p3 的优先级是更高的，所以当然 p3 会抢占处理机，p3 上处理机运行。
那么当 p3 运行到 5 这个时刻的时候，它运已经运行结束，因为它只需要运行一个单位的时间，然后他会主动的放弃处理机。
接下来的调度，接下来 5 这个时刻，p4 刚好也已经到达了就绪队列，然后插到了队尾，但是由于 p2 进入就绪队列的时间更早一些，所以虽然 p2 和 p4 的优先级更高，我们依然会优先选择 p2 进程，让 p2 上处理机运行。
接下来就是 p2 刚才已经运行了两个单位的时间，接下来他只需要在运行两个单位的时间，也就是到 7 这个时刻，他就会主动的放弃处理机，在此发生调度，而 p4 的优先级又要比 p1 更高，所以 p4 先上处理机运行，最后才是让 p1 上处理机运行完他剩下的那些时间单位，所以这抢占式的优先级调度算法的一个大体的过程。
那么优先级调度算法相关的知识，我们还需要补充这么一些点。首先就是就绪队列其实未必只有一个，有的操作系统它是按照优先级来组织就绪队列的。另外如果说设置一个就绪队列的话，也有的操作系统是会按照优先级从高到低的顺序来动态的就是排队，调节就绪队列当中各个进程的位置，可会让优先级更高的进程排在更靠近队头的位置，这样的话在调度的时候就只需要从队头来选择一个进程，为它分配处理机就可以了。
另外根据优先级在在确定了之后，是否可以动态的发生改变，我们又可以把优先级分为两种，静态优先级和动态优先级。静态优先级就是创建进程的时候确定了之后就一直不变，而动态优先级是在刚开始会给它一个初始值，但是之后可能会根据具体运行的情况，在动态的调整优先级的大小。
那么我们要怎么为一个进程设置一个优先级的初始值才会比较合理，一般来说有这样一些原则。
系统进程的优先级要高于用户进程，这个很好理解，因为系统进程毕竟是用于做是作为管理者，所以管理者的优先级自然是要比被管理者要更高的。
另外前台进程的优先级要高于后台进程，其实在咱们什么 iPhone 安卓这些手机上就是有这样一个原则，因为前台进程毕竟是现在用户能够看到的进程，所以这些进程的流畅程度之类的这些指标肯定是要比后台进程要更重要，所以它的优先级也理应要高于后台进程。
第三个，操作系统会更偏好 lO 型进程，lO 型进程又称作也又可以称作 lO 繁忙型进程，与它相对应的有一个概念叫做计算型进程，也就是 CPU 繁忙性进程。那么为什么操作系统会更加偏好更加优先的处理 lO 繁忙型进程，我们可以这样理解。lO 设备它和 CPU 是可以并行的工作的。所以如果说我们让 lO 繁忙型进程的优先级比计算型的进程更高的话，那么也就意味着 lO 繁忙型的进程它可以优先的运行，而它越优先的运行就越有可能让 lO 设备尽早的投入工作，尽早的开始和 CPU 并行的工作。所以这就会直接的导致系统资源的利用率会上升，也就是 lO 设备的利用率，并且系统的吞吐量也会因为这样的策略会有所提升，所以操作系统更偏好 lO 型进程，对整体的性能提升是有帮助的，这一点需要大家理解，在选择题当中也会出现也会考察。
那么接下来考虑的一个问题是，当我们采用动态优先级这种策略的时候，我们什么时候应该调整一个进程的优先级，我们可以从追求各个进程公平竞争，还有提升资源利用率等等各种各样的系统性能的角度来考虑，比如说如果一个进程它在就绪队列当中等了太长时间，那么可以适当的提升它的优先级。如果一个进程它运行了很长时间，那么可以适当的降低它的优先级，这就是从一个公平的角度来考虑。
而上面这一条进程在就绪队列当中等了很长时间，适当提升它的优先级。这个有没有发现其实咱们之前学过的高响应比优先算法，所谓的响应比也是这样一个规则，就是当它等待的时间长了之后，响应比会增大，那么响应比其实就代表了进程的优先级，所以它的优先级也得到了提高。所以其实我们也可以认为像高响应比优先算法，它就是一种动态的优先级的一种调度算法。
另外如果我们发现一个进程，它频繁的进行 lO 操作，那么可以适当提升它的优先级，因为它频繁进行 l 操作，就说明它很有可能是一种 lO 缓慢型的进程。那么我们提升它的优先级，经过刚才的分析，我们也知道可以这样可以提升系统资源的利用率，然后系统的吞吐量这些指标也会得到提升。
所以经过刚才的讲解，大家应该已经可以体会到，优先级标注算法它的优点很明显，就是可以用优先级来区分各种任务的紧急程度重要程度，所以优先级调度算法也比较适合用于实时操作系统，我们可以很灵活的来调整对各种作业进程的偏好程度，我们希望这种进程优先被处理，那么我们就可以让它的优先级设置的更高一些。
而缺点它有可能会导致饥饿，如果说源源不断的有更高优先级的进程到达到来的话，那么低优先级的进程就有可能会发生饥饿的现象，所以是会发生饥饿的，这就是优先级调度算法。
# 多级反馈队列调度算法
接下来我们思考一个问题，像先来先服务算法，最大的优点就是公平，
而短作业优先算法的优点就是可以让短作业尽早的处理完，然后就可以追求到一个比较短的平均等待时间，平均周转时间
而时间片轮转调度算法，它的优点优势可以让各个进程可以及时的得到响应，
优先级调度算法又可以灵活的调整各个进程被服务的机会，也就是通过优先级来进行控制，
那么我们是否能设计出一种算法，能够综合上面这些算法的优点，取一个折中平衡。基于这个想法，人们就提出了多级反馈队列调度算法，这个算法就是对其他的咱们之前学过的那些调度算法的一个折中权衡，规则比较复杂，这儿先不展开，咱们之后结合例题来一点一点进行分析。
然后这算法一般来说是用于进程调度的，并且它是一种抢占式的算法，而抢占的时候也需要注意，在抢占的过程中这个规则也比较复杂，咱们会根据之后的例题再来展开讲解。
这个地方虽然说它是抢占式的算法，但是在实际的操作系统应用当中，也有可能是把它实现为非抢占式的版本。但是考试的时候咱们就以汤子营的教材为准，就是认为它是抢占式的算法，并且注意一下它在抢占的时候会发生什么事情
我们直接用一个例题来具体的了解多级反馈队列调度算法的一个规则。
首先我们会设置多级就是很多个级别的就绪队列，各个队列的优先级从高到低，然后时间片，各个队列的时间片是从小到大的，比如说第 1 级队列的执行的时间片就是一个长度的时间单位，而第二级执行的是两个长度的单位，第三级执行的是 4 个长度的单位，为各个级别的队列分配的时间片是从小到大的。
第二点，如果有一个新进程到达的话，它会先进入优先级最高的也就是第一级队列的队尾，然后按照先来先服务的这种原则，排队等待被分配时间片。
刚开始 0 这个时刻 p1 进程到达，所以它会先放入第一级对列。由于它是先到达的，而此时也没有别的进程，所以 p1 理所应当它应该被分配一个时间片
但是第一级队列的时间片大小只有一个单位的时间，所以当 p1 执行了一个单位的时间片之后，它的时间片就用完了，那么他在用完时间片之后还没有结束，所以他会进入下一级队列的队尾，也就是第二级队列，就是这个样子。
接下来在第一这个时刻，当 p1 执行结束之后，p2 也会紧随其后，也是在一这个时刻到达的。所以此时由于我们的更高级别的队列，还有一个进程没有处理完，所以暂时不会处理更低级别的这个队列当中的进程。因此在这个情况下，一这个时刻会选择 p2 进程让他上处理机运行。
同样的 P2 运行的时间片大小是一个单位的时间，所以运行了一个单位的时间之后，它会被放到下一级队列的队尾。
接下来在二这个时刻，在二这个时刻，由于更高级的第一级的队列已经全部为空了，所以这个时候我们才会对第二级更低级的队列进行调度，为队头的进程分配一个时间片。
而此时第二级对应的时间片大小是二，所以 p1 会执行两个单位的时间，那么当它执行完了之后，它的运行时间还没有全部结束，所以它还会被放到下一级的队列。
而此时下一次调度由于第二级队列还有一个进程，所以又会让 p2 运行。但需要注意的是 p2 当它运行了一个单位的时间，也就是它的时间片还没有用完的情况下，在 5 这个时刻，p3 进程到达到达第一级队列，由于此时有一个更高优先级的进程到达，所以会发生抢占处理机的情况
所以此时 p2 这个进程会被剥夺处理机，但是它并不是放到下一级队列，而是把它放回原来这一级的队列的队尾，之后让 p3 上处理机抢占处理机，让它运行。然后运行了一个单位的时间之后，刚好 p3 也只需要运行一个单位的时间，所以 p3 运行完成它就可以被调出内存了
接下来又是 p2 继续运行。由于之前 p2 总共运行了两个单位的时间。所以在这一次它上处理机运行的时候，它只需要运行完 2 个单位的时间片之后，它总共就运行了 4 个单位的时间，所以这个时候 P2 完成可以调出内存
所以当上面的这些队列当中的进程已经全部都空了的时候，才会才会调度最后面最低级的队列，然后让 p1 上处理机运行 4 个单位的时间，因为最后队列它的时间片大小是 4 个单位。然后当它运行了 4 个单位的时间之后，我们来看一下它总共运行了 1+2+4，也就是总共运行了 7 个单位的时间，但是它的运行时间是 8 个单位，但是由于此时 p1 已经在最下面一级，所以它此时已经没办法再往下了，那么它只会被放回该队列的队尾，然后再次被调度。它之前已经运行了 7 个单位的时间，最后只需要再为再让它运行 1 个单位的时间，总共运行了 8 个单位的时间，此时 p1 完成，然后再调出内存，所以这就是多级反馈队列的一个流程，比之前所有的那些算法都要复杂的多得多，大家如果结合刚才的动画的话，就应该比较能够形象的理解。
经过刚才的讲解，大家在自己暂停来看一下刚才咱们开头提出的这些算法规则，还有抢占的时候的一个规则，看看是不是已经能看得懂了，这就不再展开。
多级反馈队列，它有很多优点，对各种各样的进程都是相对公平的，每个进程刚开始进来的时候肯定都是会被优先处理的，因为刚开始的时候它优先级是最高的，而这就是先来先服务的一个优点
而且每个新到达的进程其实很快就可以得到响应，因为它优先级高，而所以在第一级队列的话，肯定很快就可以被调度，这又是时间片轮转调度的一个优点。
另外短进程只需要经历过比较高的那几个优先级比较高的那几个队列，就执行了几个较短的时间片之后就可以完成了。所以这也会导致这些进短进程的平均周转时间会比较理想，而这就是最短进程优先算法的一个优点。
另外短进程优先算法一般来说是要求用户来提供自己的进程大概需要运行多长时间这样的数据的，但是可能会有用户作假本来是长进程，他把自己的时间说得很短，所以但是像多级反馈队列这种算法，它又不必要优先事先估计进程的运行时间，从而就避免了用户作假这种造成的一系列的后果。
另外多级反馈队列也可以像优先级调度算法那样，可以灵活的调整对各种进程的偏好程度。比如说对于 CPU 型、计算型还有 lO 型这两种进程来说，如果我们想=偏好 lO 型进程，想优先的处理 lO 型进程的话，那么我们可以这么处理。当一个 lO 型进程，当它在运行的过程当中，因为发出 lO 请求而主动的阻塞的时候，我们可以把进程当它再次被唤醒的时候，让它重新放回原来那一级的队列，而不是让它降到下一级队列。这种处理就会让导致一个 lO 密集型的进程，它可以长期的保持一个较高的优先级，保持在较高优先级的队列里，所以这就是调整对各类进程偏好程度的一种方式一个例子
那么这个算法是有可能会导致饥饿的，因为如果说源源不断的有短进程到达的话，那么它可能短进程在第一级队列被分配一个较短的时间片之后就可以被处理完。然后这种进程源源不断的到来的话，那么已经被降级为更低级更低优先级的那些进程，就有可能会长期得不到服务，它从而也会导致饥饿的现象。
# 小结
那么这是小节的一些简要的一些总结，特别对于多级反馈队列这个算法，它的规则运行的规则是比较复杂的，大家要注意结合刚才的例题来进行理解。
另外优先级调度算法当中，我们需要注意它是有抢占式的版本，也有非抢占式的版本。在做题的时候，我们需要注意的是非抢占式的优先级调度算法，我们只需要注意各个进程，主动的放弃处理机这样的时刻，我们在这个时刻检查是否需要调度就可以了。
而对于抢占式的优先级调度算法来说，我们除了刚才所说的情况之外，还需要注意一个就绪队列发生改变的这种情况下，是否会发生抢占这样的事情，然后在这个时刻也需要解进行检查。
各个算法有各自的优点和缺点，但是比起之前介绍的那三种算法来说，这三种算法的优缺点是更不容易被考察的，那么他们是否会导致饥饿这个问题，大家也需要学会自己会分析。
另外我们补充的时间片轮转调度算法，我们需要注意时间片太大或者太小会有什么影响，大家现在再回忆一下。
然后优先级调度算法当中，我们也又补充了所谓的动态优先级和静态优先级，它们有什么区别呢？另外我们在为各个进程设置优先级的时候，都有哪些原则？这些在之后课后习题当中也会遇到，大家再通过题目来进行巩固和总结。
小节介绍的这几种算法是比较适合用于交互式系统的，因为比起早期的这些批处理操作系统来说，计算机的造价其实是越来越低的，所以之后出现的这些交互式的系统，包括像分时操作系统，还要实时操作系统，这些操作系统它会更注重这些对于各个进程的响应时间，还有公平性平衡性这些指标，而不是一味的追求批处理操作系统当中的什么平均周转时间，这些很宏观的一些指标。所以这几种算法刚好又是特别适用于这种交互式系统的这一系列的需求，可以提供比较快的响应时间，然后也可以用一系列的这种策略来追求一个比较公平平衡的这种性能，所以他们是适合用于交互式系统的。比如说像 Unix 系统使用的就是多级反馈队列调度算法
那么最后还是要强调一下这些调度算法相关的知识点，大家一定要通过动手做课后习题，来再进一步的巩固总结
