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

4次阅读

共计 5332 个字符，预计需要花费 14 分钟才能阅读完成。

思考因素
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，让A、B、C 运行工夫不同，思考 FIFO 是否存在均匀周转工夫较长的状况
假如 A、B、C 三个工作，A 运行工夫为 100s，B 和 C 运行工夫为 10s，如果仍旧是 A 先早到一点，而后是 B，最初是 C（依然近似认为是同时达到的），此时零碎的 均匀周转工夫较长（100+110+120）/3=110
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

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

当初，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 ，就将零碎的工作 重新加入到最高优先级队列 中。