224_FCFS、SJF、HRRN调度算法
# 2.2_4_FCFS、SJF、HRRN调度算法
各位同学大家好，在这个小节中我们会学习几种调度算法，分别是先来先服务，短最优先和高响应比优先这三种算法。那么在学习的过程中，我们会按照一定的框架思路来依次分析各个算法。 首先我们会介绍每一种算法的提出，它是想解决什么问题，出于什么目的而提出的这个算法，然后出于这个目的，它又采用了什么样的算法规则。
之后这些算法到底是用于作业调度还是用于进程调度，用于作业调度和进程调度的时候有没有什么区别，这个也是我们需要关注的一个问题。
之后，各个算法可能会有抢占式的版本和非抢占式的版本，这个就是咱们之前介绍的调度方式强调的两个知识点抢占式和非抢占式。
另外我们在考试的选择题当中还经常会考察各个算法的优点和缺点，所以这个也很重要。
然后，我们会重点关注一下各个算法有没有可能导致饥饿的问题。饥饿这个概念可能之前还没有提过，其实很简单，就是指如果一个进程或者一个作业长期得不到服务，那么进程或者说作业它就处于饥饿的状态，那么我们会按照这样的框架来依次分析各个算法。
# 先来先服务算法
首先来看先来先服务算法，这个算法的思想其实和我们日常生活中排队买东西特别类似，主要是从公平的角度来考虑。和他的名字一样，也就是说先到达就绪队列，或者先到达后备队列的进程或者作业，就先为他提供服务。
那么当用于作业调度的时候，考虑的其实是哪一个作业先到达后备队列，后备队列是在外存中的，咱们在上一个小节也强调过知识点，如果说是用于进程调度的话，那么考虑的是哪一个进程先到达的就绪队列。就绪队列是在内存中的，这是当它作为作业调度或者进程调度的时候，有的一个小小的区别。
另外先来先服务算法，一般是非抢占式的算法，也就是说对于当前正在占用处理机的进程或者说作业，那么只有进程他主动的放弃处理机的时候才会进行调度，才会用这个调度算法的规则来选择下一个应该得到服务的进程。
那么我们直接来看一个具体的例子，可能会更容易易理解。有这样几个进程，p1到p4个进程，他们的到达时间和运行时间分别是这样的一个数据，这个时间大家认为是秒或者毫秒都可以无所谓。那么如果我们采用的是先来先服务的调度算法。我们待会计算一下这些进程的等待时间，等待平均周转时间，还要带权周转时间这些我们在之前的小节当中介绍过的评价一个调度算法的指标。
那么先来先服务调度算法，它的规则很简单，其实就是按照到达的先后顺序来依次进行调度，所以因为它是到达的先后顺序，所以事实上他考虑的是哪一个进程，他到了之后等待的时间更长，等待时间越久的进程就会越优先的得到服务，那么这是先来先服务调度算法考虑的一个点，也就是考虑的是各个进程或者作业的等待时间。
所以这个调度顺序其实很容易就看出来，根据到达顺序0245，他们p1、p2、p3、p4是依次到达的，所以会按这样的顺序进行调度，那么 p1从0时刻到达就开始运行，然后运行了7个时间之后，那么p2是第二个被调度的，它会运行4个时间，之后是p3运行1个时间，然后p4运行4个时间，就是这样的顺序
那么我们来计算一下他们的这几个指标，周转时间的话其实就是用各个进程的完成时间减掉到达时间。 P1是在7这个时刻完成的，而它到达的时间是0，所以p1的周转时间就是7-0，也就是7
而p2是11这个时刻完成的，但是它到达的时间是2，所以p2的周转时间就是11-2也就是9。
那么p3和p4这些也是类似的，而带权周转时间和周转时间是不一样的，带权周转时间我们要用周转时间除以运行的时间，那么p1就是周转时间是7，它运行的时间也是7，所以p1的带权周转时间是1，P2，P3，P4这些大家再具体思考一下，然后这就不展开了。
等待时间的话，其实在这个题当中比较简单，我们可以直接用周转时间减掉运行时间，其实就是各个进程的等待时间，所以把上面的这些式子依次的除号变成减号，然后一计算就可以得到各个进程的等待时间分别是多少。
但是大家需要注意的一点是，在这个题目当中，我们给出的例子当中的这些进程其实都是纯计算型的进程，也就是说这些进程其实只需要CPU为他们服务，但是所以说一个进程在他到达以后，肯定只会有两个状态，要么它就是在等待被CPU处理被调度，要么它就是处于运行的状态。所以对于这个题目这种纯计算型的进程来说，我们只需要用它的整个周转时间来减掉它的运行时间，那么剩下的肯定就是等待时间这个部分。
但是有的题目可能会给出的是一些既有计算还有lO操作的这些进程。那么在计算这些进程的等待时间的时候，我们就不能简单的用周转时间减去运行时间这样来计算，我们需要用周转时间，也就是它整个完成时间到达时间总的时间段的长度，减掉它在CPU上运行的时间，还要再减掉IO设备为它服务的时间，这样得到的才是这种又有计算又有lO操作的进程的等待时间，这个地方大家稍微注意一下。所以这个公式不要认为它是一成不变的，要具体问题具体分析，这种例子我们暂时不展开，如果在课后习题遇到的话，大家自己再巩固一下。
平均周转时间，平均债权周转时间和平均等待时间计算起来就很简单了，其实就是把他们这些数据全部加起来，然后除以进程的个数4，那么分别得到的是这样的数据，现在我们先不用关心，一会这些数据还会再列出来
所以这就是先来先服务算法它具体的一个调度的规则。很简单，就是按照到达的时间顺序，或者说等待的时间越久的进程，它就越发排在前面，就是按照这样的规则来进行调度的。
那么在这个地方大家可能会注意到一个点，就是对于p3这个进程来说，我们在计算它的带权周转时间的时候，这个权值我们计算得了8是非常大的一个值，因为带权周转时间其实表示的是进程的整个周转时间比运行时间要大多少倍这样一个指标。所以说带权周转时间这么大，也就意味着进程本来只需要很少的时间为他服务，但是他需要等很长的时间才可以被处理完，因此对于p3进程的用户来说，可能他的体验就是特别糟糕的。那么我们接下来就再来继续讨论一下它的优点的话，其实就很公平，又因为类似于我们平时排队买东西，先到的先被服务，而且这个算法其实很简单，实现起来也不复杂。那缺点就是刚才我们提到的p3进程，带全周转时间算出来会特别的大，也就是说对于一个排在长作业后面的短作业或者排在后面的短进程来说，它需要等待很长的时间才可以被服务。那么对于短进程或者短作业的用户来说，就体验会特别糟糕，所以先来先服务算法，其实是对长作业有利，对短作业不利的，
那么这个地方为了让大家能够有更感性的体验，我们来举一个排队买奶茶的例子。假如说你去某一个奶茶店排队买奶茶，那么一般来说他们采用的规则就是先来先服务，先到的肯定先给你做奶茶，但是如果这个时候你的面你的面前突然出现了一个要买20杯奶茶，那么这家店可能做这20杯奶茶需要半个小时的时间。虽然说你只买一杯奶茶，做你的奶茶的时间只需要一分钟，但是由于你的前面突然出现了一个长作业或者说长进程，所以对于你这个短作业或者短进程来说，你的体验就会特别糟糕。可以算一下你的带权周转时间，特别大，所以它是对长作业有利，对短作业不利的，这样讲大家应该就可以体会到什么叫有利，什么叫不利了。
那么对于先来先服务算法来说，其实是不会导致饥饿的，因为不管是哪个作业，他只要一直等着，反正他前面的那些作业或者进程总会被处理完，所以它是不会导致饥饿的。这就是先来先服务算法
# 短作业优先
那么从刚才这个例子我们已经知道先来先服务算法，对于带权周转时间，还有平均等待时间，这些指标其实是不太优秀的，所以短作业优先算法的提出，其实就是为了追求更少的平均等待时间，还有平均周转时间，平均带权周转时间短，
短作业优先算法，它的规则也很简单，最短的作业或者进程优先的得到服务。而这个地方所谓的最短其实是指这个作业或者说进程它要求服务的，要求被服务的时间最短的，优先得到服务。
那么短作业优先算法是用于作业调度的，当然也可以这种规则，这种规则也可以用于进程调度，但是用于进程调度的时候，一般是称为短进程优先算法，也就是SPF这个。SJF的 j指的是job，然后用作进程调度的话，SPF的 p指的是process就是进程
短作业优先算法默认一般来说是非抢占式的，但是也有短作业优先算法的抢占式版本，称为最短剩余时间优先算法。SRTN这是它的英文缩写
那么我们具体来看一下，用一个例子来看一下这两种算法到底有什么区别。还是刚才的题目，只不过我们把它改成了使用非抢占式的短作业优先算法，也就是SJF这个算法。这个例题当中给出的是用于进程调度的这种场景，所以这个地方严格来说，我们应该是说使用非抢占式的短进程优先调度算法，而不是短作业优先。不过很多题目中也不会太在意这个细节，大家只需要知道他们的规则其实是一样的，就是根据要求服务时间，也就是运行时间来做优先级的排列就可以了
这个调度算法就是每一次调度的时候，他会选择当前已经到达的，注意是当前已经到达的，并且运行时间最短的一个作业或者进程，为它进行服务分配处理机，所以这个调度顺序也很好确定，在0这个时刻只有p1进程是已经到达的，所以这个时候只能为p1进程服务，只能调度p1，所以第一个进程肯定是p1
当p1运行完了之后，也就是到了时刻7，这个时刻其他的这些所有的进程全部都已经到达了，但是p3的要求运行的时间是最短的，所以p1之后会调度p3，当p3运行完了之后，还剩p2和p4两个进程，但是由于p2它是先到达就绪队列的，所以虽然它俩的运行时间是一样的，但是会优先调度p2进程，因此整个过程的运行情况是这个样子。
这个地方我们可以用这个图结合各个进程的到达时间，来很快速的算出每个进程的周转时间，带权周转，还有等待时间分别是多少，并且把这些指标加加和在除以4之后就可以得到平均周转，平均带权周转和平均等待时间。这个地方大家也最好自己动手算一下
我们和之前先来先服务算法，得到的这三个指标来进行一个对比，会发现采用了非抢占式的短作业优先算法之后，平均周转时间从8.75降为了8，平均带权周转从3.5降为了2.56，而平均等待时间从4.75降为了4。所以从这三个指标来看，短作业优先算法在这些方面的表现，它是要优于先来先服务算法的。
# 抢占式的短作业优先调
我们如果采用的是抢占式的短作业优先调度算法，抢占式的短作业优先，刚才我们也已经强调过，它也有另外一个名字叫做最短剩余时间优先算法，英文缩写是SRTN用这个算法的话，由于它是抢占式的，所以每当有一个新的进程进入到就绪队列的时候，会引发就绪队列改变。当就绪队列改变的时候，我们就需要看一下它到底这个新来的进程到底会不会抢占处理机。所以当就绪队列对这些改变的时候，我们就需要计算一下当前新到达的进程，它的剩余时间，就剩余的运行时间，比起当前正在运行的进程，剩余的时间到底是不是更短？如果更短的话，我们就会把新来的进程让它抢占处理机，所以这就是抢占式造成的一个结果。
那么当前正在运行的进程，如果被抢占处理机之后，它就会回到就绪队列当中。另外如果说当前运行的进程主动放弃处理机的时候，也就是一个进程，它正常的完成的时候，也需要用这样的调度算法来进行一个调度。所以这是这种算法当中我们需要注意的两个时间点，一个是就绪队列改变的时候，另外一个是一个进程完成的时候。
那么我们按照这样的规则来依次分析一下这个时刻。首先在零这个时刻只有p1到达，那么P1当前的剩余时间，也就是剩余的运行时间，整个也就是7个时间，那么就是这个样子。所以此时因为只有p1在就绪队列当中，当然是为p1分配处理机p1上处理机运行。
但是当p1运行了两个单位的时间的时候，在2这个时刻p2到达了就绪队列，因此就发生了就绪，队列发生了改变这样的事情。所以这个时候系统会重新计算一下当前正在运行的进程，p1剩余5个时间，而新到达的进程p2它只剩于总共4个单位的时间，所以p2的剩余时间更短，因此会选择p2进程让他抢占处理机，然后p1重新回到就绪队列。
同样的到4这个时刻，虽然p2还没有完成，但是p3进程到达。由于此时p3的运行剩余运行时间比起前两个比起其他进程来说是最少的，所以这是这个时候p3正常的被抢占处理机，
到第五这个时刻p3正常完成了，但同时 p4进程它也在5这个时刻到达，所以此时就绪队列中剩余p1、p2、p4这样4个进程，但是p2之前已经运行了两个单位的时间，它在运行两个单位的时间就可以了，所以p2又会被分配处理机运行，在p2运行了剩余的两个时间之后，又剩下p1和p4再对比，又是p4的剩余时间最短，所以p4又会处理机运行，当p4运行完了之后才是最后再把p1上处理机，把剩下的这5个单位的时间运行完，所以整个过程就是这个样子大家再结合我们刚才的分析，也可以动手画一下。
这个地方我们可以结合这个图和各个进程的到达时间，就可以很方便地算出咱们之前提到过很多次的这一系列的指标。这个地方我们需要注意的是抢占式的短作业优先算法中，这些进程的执行可能是断断续续的，比如说p1执行了这样一段，p2也是执行了这样两段，那么这和咱们之前介绍的那两种算法是不太一样的，所以对于算法的这些指标的计算，大家也要自己动手算一下，看看能不能得到正确的结果。
我们再把之前非抢占式的短作业优先得到的这三个指标把它们放在一块，我们会发现采用了抢占式的短作业优先，或者说最短剩余时间优先之后，得到的平均周转，平均带权周转，还有平均等待时间，这三个指标比非抢占式的还要更小，也就意味着采用抢占式的这种算法之后，它在这些方面的表现要优于非抢占式的短最优先算法。
所以这个地方大家除了了解这两种不同的抢占式和非抢占式，在具体的做题的过程当中有什么区别之外，我们还需要注意几个小细节。如果说在题目当中提到短作业优先或者短进程优先算法的话，那么默认的其实是非抢占式的。但是在很多书上包括咱们的王道书上，大家会看到这样的一句话，短作业优先算法，得到的平均等待时间和平均周转时间是最少的，但是根据刚才咱们计算的结果可以看到，其实最短剩余时间优先算法，所得到的平均等待时间和平均周转时间还要更少，所以这句话其实严格来说表述是错误的不严谨的，那么如果要让这句话变得更严谨一点，我们应该加一个条件，在所有的进程同时可运行的时候，采用最短作业优先调度算法所得到的平均时间或者平均周转时间是最少的
或者我们还可以改一种说法，如果说所有的进程几乎都是同时到达的，那么采用这种算法得到的平均等待时间和平均周转时间是最少的，这个地方为什么要强调要用一个几乎这样的表述，因为进程的到达肯定还是有先后顺序的，只不过在宏观上看，我们可以认为的到达那些进程几乎是同时到达的，然而他们事实上也会有先后顺序，只不过是微观上看有先后顺序，宏观上看这些进程几乎同时到达。
还有另外一种说法，如果说我们不要所有的进程都几乎同时到达这个条件的话，我们可以说抢占式的就是刚才所提到的最短剩余时间优先，这个算法所得到的平均等待时间和平均周转时间是最少的，这个是没有问题的，如果数学基础好的同学可以试试看，能不能证明这个算法为什么是平均等待时间，平均周转时间最少。
第三点，虽然短作业优先算法，它的平均等待时间平均周转时间不一定是最少的，刚才咱们已经说过，但是相比于想先来先服务，还要最高响应比优先，相比于这样的算法来说，短作业优先算法其实仍然是可以获得比较少的平均等待时间，平均周转时间这两个指标的，所以在有的题目当中有可能会遇到刚才咱们说的这句话这样的选项，如果说遇到这样的选项的话，大家一定要再判断一下其他的那三个选项是不是有很明显的错误，如果别的那些选项都错得很明显的话，我们也可以选择这个选项认为它是正确的。
因为我们操作系统这门课，其实它和像物理数学这些基础理学的这些学科不太一样，它并不是一个很对于很多概念，很多算法的这一些说法定义，可能不同版本的教材也会有所不同，所以他并没有一个很严格的说法，所以大家在做课后习题的时候，可能也会发现有一些我们在之前讲的，还有课后习题当中说法不一致，前后有那么一点点矛盾的那种现象，但是大家也需要学会适应这种情况，然后在考试的时候最好判断一下所有的选项，然后选一个错误更少的更合适的选项
经过刚才两个例题，相信大家对这个抢占式和非抢占式到底应该怎么做，应该已经有了一个比较直观的理解。所以短作业优先算法它的优点就是可以得到 “最短”的平均等待时间和平均周转时间最短，为什么打双引号呢？大家应该已经知道了，大家在遇到的时候稍微注意一下，知道一个这句话不严谨，这样的一个细节就可以了。
而缺点的话其实也很明显对于短作业有利，长作业不利，如果说就绪队列中源源不断的有更短的作业到来的话，那么就有可能会产生长作业饥饿的现象。另外像作业或者进程的运行时间，其实是由用户提供的一个数据，所以这个用户可以把自己本来应该是长作业，但是把自己提交的数据把它写得很短，所以事实上短作业优先这种算法并不一定真正的能够做到短作业优先这件事。
是否会导致饥饿：刚才我们已经说了是会导致饥饿的，并且如果一个进程或者一个作业，他一直得不到服务的是一直得不到服务的话，那么这种更加严重的饥饿现象就可以称作进程饿死或者作业饿死了，这就是短作业优先算法。
# 高响应比
那么经过刚才的讲解，我们会发现对于来先服务和短作业优先这两种算法来说，先来先服务算法，他每次调度的时候其实考虑的是每一个作业或者进程，它的等待时间哪一个最长，他考虑的是等待时间，但是对于每一个作业它的运行时间到底是长是短，这些他并不关心，所以这就导致了先来先服务算法，对长作业友好，对短作业不友好的问题。
相反的短作业优先这个算法，他又是只考虑了一个作业或者进程的执行时间，他每次都是给估计的执行时间，估计运行时间最短的作业或者进程为它来调度它的，所以他并不考虑每一个进程到底等待了多长时间，所以这就会导致另外一个相反的问题，对长作业不友好，甚至还会导致长作业饥饿的这种现象。
那么我们能不能设计一种算法，既考虑到每一个作业的等待时间，同时还能兼顾每一个作业或者说进程的运行时间。因此人们就用这样的想法就提出了高响应比优先算法。
高响应比优先算法就是刚才咱们所说的这样的一个思想，既要考虑它的运行时间，还要考虑到要求服务的时间，也就是估计的运行时间。这个算法的规则就相对来说要复杂一些，在每一次调度的时候会计算各个当前已经到达的这些进程或者作业的响应比，然后选择一个响应比最大的最高的进程为他们服务。
响应比的计算方式是这样的，等待时间加上要求服务时间或者说运行时间再除以要求服务时间这个算法，从这个式子当中我们也会发现响应比肯定是一个大于等于一的数，因为等待时间它是一个正的，然后要求服务时间上下都有，所以分子肯定要比分母更大。
这个算法既可以用于作业调度，也可以用于进程调度，这个算法一般来说是非抢占式的，所以只有当一个作业或者一个进程，他主动的放弃处理机的时候，我们才需要使用这个调度算法来计算各个进程的响应比。
为了让大家更直观的理解，还是用刚才的例题，这些进程的到达时间和运行时间还是一样的，然后使用的是高响应比优先算法。这个算法我们就是当一个进程他主动的放弃CPU的时候，也就是当它正常或者异常的完成终止，或者说当进程主动的要求阻塞的时候，我们才需要使用调度算法来计算各个进程的响应比。
但是这个题目当中由于它是纯计算型的一些进程，所以并不会有lO操作，也就是并不会主动的要求阻塞，因此这个情况咱们暂时不需要考虑响应比的。计算公式是刚才说的这个样子，所以在0这个时刻，由于整个系统的就绪队列当中，只有p1是到达的，所以不管它P1的响应比到底是多少，肯定是p1上处理机，然后由于它是非抢占式的算法，所以只有p1主动的放弃CPU，也就是p1运行了7个时间，7个单位的时间当它结束的时候才会进行第二次调度。
第二次调度是7这个时刻，会发现就绪队列当中有p2、p3、p4这样三个进程。 P2的等待时间它是从二这个时间点到达的，然后一直到了7这个时间点，到这个时候他总共等待了7-2，也就是5个单位的时间，然后他要求服务的时间是4，然后再除以要求服务时间是4，就可以得到2.25，P3，P4这些也是一样的，大家再自己分析一下，经过计算会发现p3进程的响应比它是最高的，所以当然让p3上处理机运行
然后p3的运行时间只有一个单位的时间，所以当他主动放弃处理机的时刻，就是8这个时刻还剩下p2和p4两个进程，那么还是用刚才相同的这种规则再来计算，发现p2的相应比要更高，所以p2右上处理机运行，然后p2执行了4个时间之后，12这个时间 p2完成就续队列里就只剩下p4进程了，所以当然也不用计算它的响应比。P4肯定是下一个上处理机运行的进程，所以整个过程就是p1、p3、p2、p4
这个地方大家可能会发现响应比这个公式它是等待时间加上要求服务时间再除以要求服务时间，所以p2和p4这两个进程，他们的要求服务时间也就是运行时间其实是相等的，既然p2先到达就绪队列的话，那么就意味着p2的等待时间是要更大的，而另外的要求服务时间它们都是相等的，所以p2的等待时间更大的，当然 p2的响应比计算出来肯定也更大，看这个时刻p2是2.25，p4是1.5，然后这个时刻p2是2.5，p是1.75，它肯定都是大于p4的，所以这是响应比优先，计算响应比的一个特点，具体的运行就是这个样子就不再展开了
所以想高响应比优先这个算法，综合考虑了一个进程的等或者说作业的等待时间和要求服务时间。在两个进程等待时间相同的情况下，要求服务时间更短的进程计算出来的响应比会更大，所以要求服务时间更短的会优先，这也是我们短作业优先算法的一个优点。
另一方面如果要求服务时间一样的话，那么就像刚才咱们聊到的p2和p4两个进程一样，等待时间更长的会优先，所以又是先来先服务算法的优点，所以这个算法其实是综合了前两个算法的优点，然后做了一个折中的处理。对于一个长作业来说，随着时等待时间越来越大，那么它的响应比肯定也会越来越大，所以它被调度的机会也会越来越高，所以这个算法也避免了短作业优先算法造成的长作业饥饿的问题，所以这个算法其实是不会导致饥饿的。
# 小结
那么这个地方对这几个算法做了一个简要的总结，对于这些算法的思想，还有这些算法具体怎么算怎么做题，这个规则大家需要自己回忆，并且一定要结合课后习题来进行巩固。
这个地方需要注意的是短最优先算法，他得到了“最短”的平均等待和平均周转时间最短的，为什么打双引号，大家再思考一下回忆一下。
其实这三种算法它主要关心的是对用户作业或者用户进程的一种公平性的问题，就像先来先服务这种他要求绝对的公平。另外这几种算法还追求平均周转时间，平均等待时间这些，这些其实都是用来评价系统的整体性能，整体表现的这指标，所以这几种算法大家会发现他其实并不关心响应时间，并且也不会区分各种任务的紧急程度，所以这三种算法对于用户来说其实是基本没有交互性的，交互性特别糟糕。
那么这三种算法它一般使用在早期的批处理系统当中，因为当时那批处理在早期的批处理阶段，其实计算机也很昂贵，所以人们主动的更追求系统的整体表现，而不是对于各个用户对于各个用户来说的一种用户体验，其实也是情有可原的。
这几种算法当中先来先服务这个算法，现在也经常会结合其他的一些算法来使用，所以该算法在现在的计算机当中也扮演了很重要的角色。
除了批处理系统使用的调度算法之外，下面一个小节我们还会继续介绍，将适合适用于交互式系统的一些调度算法。这个地方强调一下，在学习这个小节，还有下一个小节的这些调度算法的时候，大家一定要尝试动手输出一下
