计算机理论基础

操作系统（三）：CPU 调度

整理《Operating System Concepts》 第七版第五章（CPU 进程调度），内容均为原书和中文版翻译的摘录，其中原书摘录部分由我 按个人理解简化、翻译为中文，可能存在一些不准确之处 。

概念

  • CPU 调度是多道程序操作系统的基础，在进程之间切换 CPU 可以提高计算机的吞吐率。
  • 进程执行由 CPU 执行和 I/O 等待 周期（cycle） 组成，进程在这两个状态之间切换。进程执行从 CPU区间（CPU burst） 开始，之后在 CPU 区间和 I/O 区间 交换。
  • CPU 区间的长度随进程和计算机的不同而变化，通常具有大量短 CPU 区间和少量长 CPU 区间。I/O 约束（bound） 程序具有很多短 CPU 区间，CPU 约束程序具有更多的长 CPU 区间。
  • 每当 CPU 空闲时，操作系统必须从就绪队列中选择一个能够执行的进程并为之分配 CPU。进程选择由 短期调度程序 或 CPU 调度程序执行。就绪队列不一定是先进先出（FIFO）队列，也可以被实现为优先队列、树、无序链表等。队列中的记录通常为进程控制块（PCB）。
  • 在下面四种情况中，CPU 调度需要做出决策：
    • 某个进程从运行状态切换到等待状态（如等待 I/O 或调用 wait 等待子进程）
    • 某个进程终止
    • 某个进程从运行状态切换到就绪状态（如出现中断）
    • 某个进程从等待状态切换到就绪状态（如 I/O 完成）
  • 在上面四种情况中，如果调度程序只在前两种情况发生时运行，则调度方案是 非抢占（nonpreemptive）调度 ，否则该调度方案是 抢占（preemptive）调度 。简单的说，非抢占调度指，一旦 CPU 被分配给一个进程，除非该进程终止或者切换到了等待状态，否则该进程不会释放分配的 CPU 资源，这部分 CPU 资源也无法被分配给其它进程；抢占调度指，分配给一个进程的 CPU 资源可能在该进程运行期间被重新分配给其他进程，此时这部分资源所属的原来的进程会被切换到就绪状态。
  • 分派程序（dispatcher） 是一个用来将 CPU 控制权交付给由短期调度程序选择出的要执行的进程的模块。每次进程切换时都会调用分派程序，它应当尽可能快。分派程序停止一个进程并启动另一个要花费的时间称为 分派延迟（dispatch latency） 。它的功能包括：
    • 切换上下文
    • 切换到用户模式
    • 跳转到用户程序的合适位置，以重新启动程序

调度算法

  • 不同的 CPU 调度算法依据不同的属性来选择进程，可通过以下准则衡量调度算法的特点和优势：
    • CPU 利用率（utilization）：调度算法应使 CPU 尽可能忙，40%（轻负荷）~90%（重负荷）
    • 吞吐量（throughput）：一个时间单元内所完成的进程的数量，对于长、短进程，吞吐量也有所不同
    • 周转时间（turnaround time） ：一个特定进程 从进程提交到进程完成所需的时间 ，该时间为所有时间段之和，包括等待载入内存、在就绪队列中等待、在 CPU 上执行和 I/O 等待时间
    • 等待时间（waiting time） ：进程在 就绪队列 中等待所花费的时间之和
    • 响应时间（response time） ：对交互系统而言需要考虑响应时间，该准则指的是从提交请求到产生第一响应的时间（开始响应所需要的时间，而不是输出响应所需要的时间）
  • 需要使 CPU 利用率和吞吐量最大化，而周转时间、等待时间和响应时间最小化。多数情况下需要优化平均值，少数情况需要优化最小值或最大值。例如对于分时系统，为保证所有用户得到更好服务，需要尽可能使最大响应时间最小。

先到先服务

  • 最简单的 CPU 调度算法是 先到先服务（first-come，first-served，FCFS） 调度算法：先请求 CPU 的进程先分配到 CPU，该算法可用 FIFO 队列实现，且平均等待时间通常较长。
  • 当系统中存在一个 CPU 约束进程和多个 I/O 约束进程时，可能出现 CPU 约束进程占用 CPU，同时其他进程处理完 I/O 请求并在就绪队列中等待，此时 I/O 设备空闲。当 CPU 约束进程结束、转移到 I/O 区间后，这些 I/O 约束进程很快会执行完计算任务（仅有很短的 CPU 区间）并移回 I/O 区间，此时 CPU 空闲。之后该状态会反复，即多个进程等待一个长进程释放 CPU，此现象称为 护航效果（convoy effect） 。这将导致 CPU 和设备利用率变得更低。
  • FCFS 调度是非抢占的，因此不适合分时系统，允许一个进程保持过长的 CPU 时间是非常严重的错误。

最短作业优先

  • 最短作业优先（shortest-job-first，SJF） 调度算法：当 CPU 空闲时，调度程序选择需要 CPU 区间最短的进程执行，如果有多个进程的下一次 CPU 区间长度相同，则在这些进程间使用 FCFS。即，先比较需要的 CPU 区间长度，长度越短优先级越高，长度相同时，到达时间越早优先级越高。
  • SJF 调度算法可证明为 最佳 的，对于给定的一组进程， SJF 算法的平均等待时间最小 。这一点的证明可以考虑贪心算法。
  • 因为无法获知进程下个 CPU 区间的长度，一种替代方法是近似 SJF 调度，即通过先验长度 预测 下一个 CPU 区间长度。我们认为，下一个 CPU 区间长度与此前的相似，可视作此前 CPU 区间测量长度的 指数平均（exponential average） ：设 t_n 为某进程第 n 个 CPU 区间的长度，则该进程下一个 CPU 区间的预测值 τ_n+1 = αt_n + (1-α)τ_n，这里 0 ≤ α ≤ 1。τ_n代表着过去的历史，而 t_n 为最近的信息，参数 α 控制了最近和过去历史在预测中的相对加权。
  • SJF 算法可能是抢占的或非抢占的。对于抢占 SJF 调度算法，当一个新进程到达就绪队列且当前正在执行的进程剩余时间比新进程所需 CPU 时间长，则新进程抢占 CPU。抢占 SJF 调度也称为 最短剩余时间优先（shortest-remaining-time-first）调度 ，与之相反的，新进程始终等待原有进程运行结束的 SJF 调度为非抢占 SJF 调度。

优先级调度

  • SJF 实际是通用 优先级（priority）调度算法 的一个特例。每个进程与一个优先级关联，具有最高优先级的进程会被先分配，具有相同优先级的进程按 FCFS 顺序调度。SJF 算法属于简单优先级算法，其优先级为进程预测 CPU 区间的倒数，CPU 区间长度越大则优先级越小。
  • 通常按照 高 优先级和 低 优先级讨论调度，优先级通常为某个固定区间的数字，如 0 ~ 7，对于不同的系统，0 可以是最高，也可以是最低优先级。
  • 优先级调度算法可以是抢占的或者非抢占的，对于抢占的优先级调度算法，具有更高优先级的新到达进程会抢占 CPU。
  • 主要问题： 无穷阻塞（indefinite blocking） 或 饥饿（starvation） ，此调度算法会导致低优先级进程无穷等待 CPU。
  • 解决饥饿： 老化（aging） 技术可以逐渐增加在系统中等待时间过长的进程的优先级，即每过一段时间递减等待进程的优先级的值，最终低优先级的进程会成为高优先级的进程并得以执行。
  • 动态优先级例题 ：假设某系统采用基于动态优先级的抢占式调度算法，且优先数越大的进程优先级越高，系统为所有新建进程赋予优先级值 0，当一个进程在就绪队列中等待 CPU 时，其优先级值变化速率为 α；当进程获得 CPU 并执行时，执行过程中优先级值变化速率为 β：
    • 若 β > α > 0，则调度算法相当于：FCFS
    • 若 α < β < 0，则调度算法相当于：FCLS

轮转法（RR）

  • 轮转法（round-robin，RR） 调度算法是 专门为分时系统设计 的，类似 FCFS 调度，但强制通过抢占切换进程。该调度算法定义一个较小的 时间单元（time quantum） 或时间切片，通常在 10 ~ 100 ms之间。就绪队列是环形的，并保持 FIFO 性质， 新到达的进程会被添加到队列末尾 。调度算法从就绪队列的头部移出进程 A，为其分配 CPU 并执行，同时也会设置一个定时器，当进程 A 执行时间到达一个时间单元时，如果进程 A 仍未结束，则将被就绪队列的下一个进程 B 抢占，进程 A 再次被加入就绪队列。注意，因为就绪队列为环形链表，队列头指针现在已经跳转到进程 B，所以进程 A 已成为整个队列的最后一个进程。
  • 使用 RR 策略调度的平均等待时间通常比较长。
  • RR 算法的性能很大程度上依赖时间单元的大小。考虑极端情况：
    • 时间单元（时间片）非常大，则 RR 算法等价于 FCFS 算法
    • 时间单元非常小，则 RR 算法称为 处理器共享（processor sharing） ，此时 n 个进程看起来就像运行在各自独立的 CPU 上，每个 CPU 的运行速度是真实 CPU 的 1/n。
  • 通常希望 时间单元比上下文切换时间长 ，例如上下文切换时间为时间片的 10%，则约有 10% 的 CPU 时间浪费在上下文切换上。现代操作系统时间片通常为 10 ~ 100ms，而上下文切换时间通常少于 10μs。
  • 周转时间依赖于时间片大小 ：若绝大多数进程能在一个时间单元内完成，则平均周转时间会改善。
  • 根据经验，80% 的 CPU 区间应当小于时间片。

多级队列调度

  • 在进程容易分组的情况下（如划分为 前台（交互） 进程和 后台（批处理） 进程），可使用 多级队列（multilevel queue）调度算法 。该算法将就绪队列划分为多个独立队列，进程按自身属性被 永久地 分配到一个队列，每个队列使用自己的调度算法。例如，前台队列可能使用 RR 算法（分时系统），而后台队列使用 FCFS 算法。
  • 队列之间必须存在调度，通常采用 固定优先级抢占调度 。例如，前台队列要比后台队列具有绝对优先级。
  • 举例：存在 4 个队列的多级队列调度算法，按优先级排列为：系统进程 > 交互进程 > 交互编辑进程 > 批处理进程。队列之间存在绝对优先级，只有系统进程、交互进程、交互编辑进程队列均为空时，批处理队列内的进程才可运行；在批处理队列有进程运行时，更高优先级队列进入新进程会抢占批处理进程。
  • 队列之间可划分时间片，每个队列有一定的 CPU 时间用于调度进程，例如前台队列可以将 80% 的 CPU 时间用于进程间的 RR 调度，后台队列可以有 20% 的 CPU 时间采用 FCFS 算法调度。

多级反馈队列调度

  • 多级反馈队列（multilevel feedback queue）调度算法 允许进程在队列之间移动，根据不同 CPU 区间来区分进程。
  • 如果进程使用过多 CPU 时间，则它会被转移到更低优先级队列。这种方法将 I/O 约束和交互进程留在更高优先级队列。
  • 在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列，这种老化阻止了饥饿的发生。
  • 考虑如下的多级反馈队列调度程序，它包含三个队列（0~2），优先级从高到低，只有队列 0 空，队列 1、2 内的进程才可执行，到达队列 0 的进程可以抢占队列 1、2 的进程。进入就绪队列的进程被放入队列 0，队列 0 中每个进程有 8 ms 时间片，如果该进程不能在这个时间片内完成，则它将被移动到队列 1 的尾部；当队列 0 为空时，队列 1 的头部进程会得到一个 16 ms 的时间片，若该进程不能在此时间片内完成，则将被抢占并放置到队列 2 的尾部。
  • 多级反馈队列调度程序由以下参数定义：
    • 队列数量
    • 每个队列各自的调度算法
    • 何时升级到更高优先级队列
    • 何时降级到更低优先级队列
    • 进程在需要服务时应当进入哪个队列
  • 多级反馈调度程序是最通用的 CPU 调度算法，但也最复杂。

高响应比优先（补充）

  • 高响应比优先（highest response-ratio next，HRRN）算法 ：非抢占调度，响应比定义为 R = (W+T)/T = 1+W/T，其中 W 是某个进程在就绪队列中的等待时间，T 是该进程的 CPU 区间长度。
  • 具有最高响应比的进程会被调度。HRRN 算法同时考虑了等待时间和 CPU 区间。
  • 缺陷：为每个进程计算响应比需要消耗系统资源。

多处理器调度

  • 存在多个 CPU 使 负载分配（load sharing） 成为可能，多处理器调度只考虑处理器同构的系统，并可以将任何处理器用于任何队列内的任何进程。
  • 非对称多处理（asymmetric multiprocessing） ：使一个处理器（主服务器）处理所有的调度决定、I/O处理以及其他系统活动，其它处理器只执行用户代码
  • 对称多处理（symmetric multiprocessing，SMP） ：每个处理器自我调度，所有进程可能处于一个共同的就绪队列，或每个处理器拥有自己的私有就绪队列。调度通过每个处理器检查共同就绪队列并选择一个进程执行。
  • 处理器亲和性（processor affinity） ：多数 SMP 系统试图避免将进程从一个处理器移动到另一个处理器，而是努力让一个进程在同一个处理器上运行。一个操作系统使用策略使一个进程保持在同一个处理器上运行，但不能做任何保证时，称为 软亲和性（soft affinity） ；有的操作系统，如 Linux，提供一个支持 硬亲和性（hard affinity） 的系统调用保证了进程无法转移到其它处理器。
  • 负载均衡（load balancing） 保证了所有处理器的工作负载平衡以完全利用多处理器的优点，它仅在每个 CPU 有私有就绪队列的情况下才有必要。它和处理器的亲和性相悖。有两种方法可实现：
    • 推送迁移（push migration） ：一个特定的进程间歇性的检查每个处理器的负载，假如当前负载不均衡，则将过载处理器上进程推送到空闲处理器。
    • 拉取迁移（pull migration） ：一个空闲处理器从一个忙处理器拉取一个处于等待状态的进程。

专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（二）：进程与线程
此专栏的下一篇文章：操作系统（四）：进程互斥

参考资料：《操作系统概念 英文第七版》，恐龙书，英文名《Operating System Concepts》，作者 Abraham Silberschatz、Peter Baer Galvin、Greg Gagne

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2016/11/23/os-concepts-3/) 、作者信息（Forec）和本声明。

分享到