过程的调度

  • 思考因素

    1. 为了构建调度策略，须要做一些简化假如，这些假如和零碎中运行的过程相干，统称为工作负载(workload)

      （1）每一个过程（工作）运行雷同的工夫

      （2）所有工作同时达到，有时候当多个工作达到的工夫相差很小的时候，也近似认为是同时达到的

      （3）一旦开始工作，每个工作将放弃运行直到实现

      （4）所有工作只是应用CPU，即：它们不执行I/O操作

      （5）每个工作的运行工夫是已知的

    2. 为了可能掂量不同调度策略的优缺点，提出一个指标——周转工夫（turnaround time)

      （1）定义：工作实现工夫减去工作达到的工夫，即：

 （2）当满足假如同时达到时，达到工夫为0，周转工夫等于实现工夫 （3）周转工夫是一个**性能**（performance）**指标**。而性能和偏心在调度零碎往往时矛盾的。调度零碎能够优化性能，但代价时阻止一些工作运行，这就升高了偏心

  • 先进先出（FIFO）

    1. 先进先出（First In First Out)：先就绪的工作先执行
    2. 假如有A、B、C三个工作，A比B早一点点，B比C早一点点，此时依据咱们的假如，能够将A、B、C近似看作时同时达到的。然而依据理论状况，是A先执行，其次是B，最初是C。假如每个工作运行10s，求工作的均匀周转工夫（average turnaround time)？
 A的周转工夫为10s，B的周转工夫为20s，C的周转工夫为30s 均匀周转工夫为（10+20+30）/3=20
    1. 当初放宽假如1，让A、B、C运行工夫不同，思考FIFO是否存在均匀周转工夫较长的状况
    2. 假如A、B、C三个工作，A运行工夫为100s，B和C运行工夫为10s，如果仍旧是A先早到一点，而后是B，最初是C（依然近似认为是同时达到的），此时零碎的均匀周转工夫较长（100+110+120）/3=110

    3. FIFO呈现4这种状况被称为护航效应（convoy effect），即：一些耗时较少的潜在资源耗费者排在重量级的资源消费者前面。例如：在杂货店只有一个排队队伍的时候，你看见后面的装满了3辆购物车的货物时，这会让你等很长时间

    • 最短工作优先（SJF）

      1. 最短工作优先（Shortest Job First）：先运行最短的工夫，而后是次短的工夫，如此持续
      2. 仍旧在上述4的状况下，依照SJF的策略，均匀周转工夫为（10+20+120）/3=50，和FIFO相比，显著升高了均匀周转工夫。但前提是满足假如2——同时达到
      3. 当初放宽假如2，即：工作可能随时达到，思考SJF均匀周转工夫较长的状况
      4. 仍旧是FIFO中4的状况，假如A在t=0时达到，并且须要运行100s，而B和C在t=10s达到，各自运行10s。则A的周转工夫为100s，B的周转工夫为110-10=100，C的周转工夫为120-10=110。均匀周转工夫为（100+100+110）/3=103.33s
      5. 很显著当工作可能随时达到的状况下，SJF可能会呈现平均周转工夫较长的状况

    • 最短实现工夫优先（STCF）

      1. 最短实现工夫优先（Shortest Time-to-Completion First）：放宽假如3，即：调度程序能够安顿其它工作抢占正在运行的工作占用的CPU。
      2. 在SJF中增加了抢占，每当新工作进入就绪状态时，它就会确定残余工作和新工作中，谁的实现工夫起码，而后调度这个工作
      3. 在上述4的状况下，STCF将抢占A并先运行完B和C后，才会持续运行。则A的周转工夫为120s，B的周转工夫为10s，C的周转工夫为20s，均匀周转工夫为(120+10+20)/3=50，显著升高了SJF雷同状况下的均匀周转工夫

    • 减少思考因素

      1. 当合乎假如4、5成立时，即：晓得工作长度，并且工作只应用CPU，依据以后的惟一掂量指标为周转工夫时，STCF是一个很好的策略。然而，引入分时系统时，就呈现了问题，因为此时须要工作和用户进行交互，而周转工夫无奈掂量工作的交互性
      2. 响应工夫（response time）：可能掂量工作的交互性，定义为从工作达到零碎到首次运行的工夫

    • 轮转（RR）

      1. 轮转（Round-Robin）：在一个工夫片内运行一个工作，而后切换到运行队列的下一个工作，而不是运行一个工作直到完结。它重复执行，直到所有工作实现。
      2. 工夫片长度必须时时钟周期的倍数。如果不是，进行上下文切换的时候须要期待一段时间，此时CPU没工作，就节约了CPU资源
      3. 假如3个工作，A、B、C在零碎中同时达到，并且它们都心愿运行5s，SJF调度程序必须运行完当前任务能力运行下一个工作，而1s工夫片的RR可能疾速循环工作。RR均匀响应工夫为：（0+1+2）/3=1（注：同时达到，达到工夫为0），SJF算法均匀响应工夫为（0+5+10）/3=5

    1. 工夫片长度对RR至关重要，越短，RR在响应工夫上的体现越好，然而工夫片不能设置得太短：忽然上下文切换会影响整体性能。因为上下文切换的老本不仅仅来自保留和复原大量寄存器的操作系统操作。程序在运行时，还会在CPU高速缓存、TLB、分支预测器和其余片上的硬件中建设了大量的状态。所以工夫片长度须要谨慎衡量，让它足够长，以便摊销上下文切换老本，而又不会让零碎不及时响应
    2. 摊销（amortize)：通过缩小老本的频度（即：执行较少的操作），零碎的总成本就会升高。例如：如果工夫片设置为10ms，并且上下文切换工夫为1ms，大概会节约10%的工夫用于上下文切换。为了摊销这个老本，能够把工夫片长度减少到100ms，则只有不到1%的工夫会用于上下文切换。
    3. 在3中，咱们只思考了响应工夫，没思考周转工夫，如果计算RR的周转工夫，A为13，B为14，C为15，均匀14。而SJF的周转工夫为，A为5，B为10，C为15，均匀10.此时RR尽管响应工夫较好，然而周转工夫较差。
    4. 到目前为止。有两类调度程序

      （1）SJF、STCF优化了周转工夫，然而响应工夫——交互性不好

      （2）RR优化了响应工夫，然而周转工夫不好

    • 联合I/O

      1. 放宽假如4，即：工作会执行I/O，此时调度程序会面临两个问题

        （1）发动I/O申请做出决定，因为以后运行的工作在I/O期间不会应用CPU，它会被阻塞期待I/O实现。这时调度程序须要思考是否期待该工作的执行还是安顿另一项工作

        （2）I/O实现时做出决定。I/O实现时会产生中断，操作系统运行并将收回I/O的过程从阻塞状态移回到就绪状态。此时调度程序将思考是继续执行该工作，还是执行其余工作

      2. 假如有两项工作A、B，每项工作须要50ms的CPU工夫。A每运行10ms，就会收回一次I/O申请，而B只是单纯地应用CPU50ms.调度程序先运行A再运行B。假如构建STCF调度程序。能够将A的每个10ms的子工作看作是一项独立的工作。所以工作运行时，先执行A10ms的子工作，实现后，会执行B，当I/O申请实现后，就会抢占B并运行10ms，这样就会充分利用零碎。

      3. 当交互式作业（即：I/O申请较多）正在执行I/O时，其余CPU密集型工作（即：I/O操作很少）将运行，从而更好的利用处理器

    • 多级反馈队列（MLFQ）

      1. 多级反馈队列（Multi-level Feedback Queue，MLFQ）须要解决的问题

        （1）优化周转工夫

        （2）放宽假如5，即：不晓得工作运行工夫

        （3）升高响应工夫，获取更好的交互体验

      2. 根本形成：有许多独立的队列，每个队列有不同的优先级（priority level）
      3. 根本规定：

        （1）规定1：如果A的优先级>B的优先级，运行A（不运行B）

        （2）规定2：如果A的优先级=B的优先级，轮转运行A和B

      4. 如何扭转优先级（1）？

        （1）零碎须要执行的工作能够分为下列两类

        a. 运行工夫很短、频繁放弃CPU的交互性工作

        b. 须要很多CPU工夫、响应工夫不是很重要的长时间计算密集型工作

        （2）优先级调整算法

        a. 规定3：工作进入零碎时，放在最高优先级（最上层队列）

        b. 规定4a：工作用残缺个工夫片后，升高优先级（移入下一个队列）

        c. 规定4b：如果工作再其工夫片内被动开释CPU，则优先级不变

        （3）实例1：单个长工作

        下图展现了一个有三个队列的调度程序。该工作首先进入最高优先级（Q2），执行10ms的工夫片后，优先级-1，最终进入Q1，并始终到执行结束

     （4）实例2：来了一个短工作 有两个工作：A时一个长时间运行的CPU密集工作，B是一个运行工夫很短的交互型工作。假如A执行一段时间后B达到。下图中A（用彩色示意）在最低优先队列中（由（3）可知：长时间工作很长时间都会在最低队列中），B（用灰色示意）在工夫T=100时达到，并退出最高优先级队列中。因为它运行工夫很短，通过两个工夫片，在被移入最低优先级队列之前，B执行结束。而后A持续运行。 ![在这里插入图片形容](https://img-blog.csdnimg.cn/20200927185023424.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzI2NzQ0,size_16,color_FFFFFF,t_70#pic_center) （5）MLFQ算法的指标：如果不晓得工作时短工作还是长工作，那么就在考试的时候假如它时短工作，并赋予最高优先级。如果的确是短工作，则会很快执行结束。否则就会被缓缓移入低优先级队列，而这个时候该工作也被认为是长工作了。通过这种形式，MLFQ近似于SJF。 （6）实例3：有I/O 依据4b，交互型工作中有大量的I/O操作（比方期待用户的键盘或鼠标输出），它会在工夫片用完之前放弃CPU，在这种状况下，咱们会放弃它的优先级不变 假如交互型工作B（用灰色示意）每执行1ms便须要进行I/O操作，它与长时间运行的工作A（用彩色示意）竞争CPU。MLFQ算法放弃B在最高优先级，因为B总是让CPU。如果B是交互型工作，MLFQ就进一步实现了它的指标，让交互型工作疾速运行。
    1. 当初，MLFQ在长时间工作之间能够偏心地分享CPU，又能给短工作或交互型工作很好地响应工夫。这样就完满呢？其实还有问题

      a. 饥饿问题（starvation）问题。即：零碎有许多交互型工作，就会不停地抢占长时间工作地CPU，让它们永远无奈失去CPU

      b. 愚弄调度程序（game the scheduler）。即：过程在工夫片用完之前，调用一个I/O操作（比方拜访一个无关的文件），从而被动开释CPU。如此便能够放弃吃在高优先级，占用更多的CPU工夫

      c. 一个程序可能在不同工夫体现不同。即：一个计算密集型的过程可能在某段时间体现为一个交互型的过程

    • 如何进步优先级（2)?

      1. 如何解决上述5中的问题？

        周期性地晋升所有工作地优先级。最简略的就是周期性的将所有工作放到最高优先级队列中

        规定5：通过一段时间S，就将零碎的工作重新加入到最高优先级队列中。

      2. 新规定解决的问题

        （1）过程不会饿死——在最高优先级队列中，它会以RR的形式，和其余高优先级工作分享CPU，从而最终取得执行

        （2）如果一个CPU密集型工作变成了交互型，当它的优先级晋升，调度程序会正确对待它

      3. 下边有两张图，右边没有优先级晋升，长时间工作在两个短工作达到后被饿死。左边的每隔50ms就有一次优先级晋升（50ms只是举例），因而至多保障了长工作的工作会有肯定的过程，每过50ms就被晋升到最高优先级，从而定期取得执行。

      4. 残余问题

        （1）S的值如何设置？如果S设置得太高，长工作会被饿死，如果太低，交互型工作得不到适合的CPU工夫比例

        （2）如何阻止调度程序被愚弄？工作在工夫片以内开释CPU就保留它的优先级是存在问题的

    • 抉择好的计时形式

      1. 更欠缺的CPU计时形式：调度程序应该记录一个过程在某一层耗费的总工夫，只有过程用完了本人的配额，就将它降到低一级的优先级队列中。
      2. 重写规定4a和4b

        规定4：一旦工作用完了其在某一层的工夫配额（无论两头被动放弃了多少次的CPU），就升高其优先级（移入低一级队列）

      3. 下图比照了在规定4a、4b的策略下（左图），以及在新的规定4（右图）的策略下，同样试图愚弄调度程序的过程的体现。灭有规定4的爱护下，过程能够在每个工夫片完结前发动一次I/O操作，从而垄断CPU工夫，有了这样的爱护，无论过程的I/O行为如何，都会缓缓升高优先级

    • MLFQ调优以及其余问题

      问题：

      （1）配置多少队列

      （2）每一层队列的工夫片配置多大

      这些问题没有不言而喻的答案，只有利用对工作负载的教训以及后续对调优程序的调优，才会获得令人满意的均衡

      例如：高优先级队列通常只有较短的工夫片，使得交互型工作可能更快的切换。而低优先级队列中更多的是CPU密集性工作，配置更长的工夫片会更好

    • MLFQ规定小结

      （1）规定1：如果A的优先级>B的优先级，运行A（不运行B）

      （2）规定2：如果A的优先级=B的优先级，轮转运行A和B

      （3） 规定3：工作进入零碎时，放在最高优先级（最上层队列）

      （4）规定4：一旦工作用完了其在某一层的工夫配额（无论两头被动放弃了多少次的CPU），就升高其优先级（移入低一级队列）

      （5）规定5：通过一段时间S，就将零碎的工作重新加入到最高优先级队列中。