关于操作系统:操作系统导论2

过程的调度

• 思考因素

  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

• 最短工作优先（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

• 联合 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 就进一步实现了它的指标，让交互型工作疾速运行。

• 如何进步优先级（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 ，就将零碎的工作 重新加入到最高优先级队列 中。