调度

为了满足既定目标，对计算任务进行资源分配的行为

• 既定目标：吞吐量、等待时间、响应时间、公平…
• 计算任务：进程、线程、数据流…
• 资源分配：CPU/GPU、网络连接…

调度指标	说明	备注
CPU利用率	CPU被进程所使用的时间在所有CPU时间的占比	越大越好
公平	同等优先级下的进程获得的CPU使用时间应该尽可能相等	-
吞吐量	单位时间内完成执行的进程数	越大越好
周转时间	某个进程需要完成的时间	越小越好
等待时间	某个进程在就绪队列的时间	越小越好
响应时间	从发出申请执行到第一次获得响应执行的时间	越小越好

1. 等待时间 = 周转时间 - 获得 CPU 执行的时间
2. 一个进程可能会多次放到就绪队列中，等待时间是这些等待的总和

调度的时机：CPU 回到操作系统的掌控之中

• 发生系统调用：比如 fork、exit
• 某个运行的进程阻塞了（wait 子进程或者等待一个 I/O 完成）
• 发生中断，比如 I/O interrupt，clock interrupt

这些事件的发生都意味着系统的状态发生了变化，可能和既定的目标发生了偏离，需要调整（调度）来让系统往既定的目标靠近

1 策略与机制

• 操作系统中的一个重要设计思想：机制与策略的分离
  • 模块化思想，降低系统的复杂度
  • 策略表示 “可以做什么”
  • 机制表示 “怎么做”
• 在一个已有的机制上，可以考虑的问题是，有哪些策略？有没有 “最优” 的策略？
• 在一个给定的策略上，可以考虑的问题是，实现这个策略需要什么样的机制？已有机制是否具备这个能力？实现效果是否高效？

比如有了上下文切换的机制，再维护一个 PCB（TCB）的队列，当发生一个时间中断时，就可以从这个队列中挑选一个进行执行

• 不同的策略都可以在这个机制上运行
• 问题就是在这个机制下，最好的调度策略是什么（基于某个评价指标）

按照进程的执行所需时间进行调度的策略，不现实，无法获取进程的执行所需时间

调度策略大体可以分为如下几类任务

• 批处理任务的调度
• 交互性任务的调度
• 实时任务的调度

2 批处理任务的调度*

2.1 先来先服务（FCFS）

• 按照到达系统（就绪）的先后顺序进行调度

等待时间：P1 = 0，P2 = 24ms，P3 = 27ms。平均等待时间：17ms

2.2 最短任务优先（SJF）

• 将每个任务与其需要运行时间关联
• 需要运行时间最短的优先被调度

等待时间：P4 = 0，P1 = 3ms，P3 = 9ms，P4 = 16ms。平均等待时间：7ms

SJF 的一些缺陷

• 并不公平！
• 等待时间差异大：进程饿死
• 进程的需要运行时间难以给定
• 可以轻易被愚弄（长任务切位多个短任务再批量运行）

2.3 最短剩余时间优先（SRTF）

• 非抢占式调度算法：选择一个进程来运行，然后就让它一直运行，直到它被阻塞（无论是在 I/O 操作上还是等待另一个进程），或者自愿释放 CPU。
• 抢占式调度算法：选择一个进程，并允许其运行一段固定的最长时间。如果在时间间隔结束时它仍在运行，则被挂起，调度器选择另一个进程来运行。（需要时间中断的机制支持）

最短任务优先的可抢占版本：选择剩下需要时间最短的进程进行运行

2.4 时间预测算法

• \(t_n\)：第 \(n\) 次实际运行时间
• \(\tau_{n+1}\)：进预测下一次 \((n + 1)\) 的执行时间
• \(\alpha\)：相关系数
• \(\tau_{n+1} = \alpha t_n + (1 - \alpha) \tau_n\)

最近的执行时间更加影响当前的预测，而更之前的执行时间则影响较小

• 两个极限情况：
  • 当 \(\alpha = 0\) 那么 \(\tau_{n+1} = \tau_n = \ldots = \tau_0\)，意味着最近的执行历史没有关联
  • 当 \(\alpha = 1\) 那么 \(\tau_{n+1} = \alpha t_n\)，意味着仅仅和最近的历史相关
• 一般而言，\(\alpha\) 为 \(0.5\)

3 交互性任务的调度

在调度策略中，有两类进程会被区别对待：计算密集型和 I/O 密集型

• CPU 密集型程序主要消耗 CPU 计算资源，例如数学运算、图形处理或数据分析等任务。这些程序通常会在 CPU 上执行大部分时间的计算和逻辑判断等操作，而不需要等待外部资源（如磁盘读写或网络通信）完成。
• I/O 密集型指的是系统大部分的时间在等待 I/O（硬盘/内存/键盘）的读取/写入操作（即 和外界进行频繁交互的进程），此时 CPU 负载并不高，需要消耗 CPU 计算的时间很少

3.1 时间片轮转调度（RR）*

• 每个任务都会获得一段固定时间的资源（时间片）
  • 如果任务没有完成，它将重新回到队列中
• 时间片应该相对于上下文切换时间较大，否则开销会太高！当然时间片也不能过大，否则就蜕变为 FCFS 调度
  • 一般来说时间片大概设置为 \(10ms\) 到 \(100ms\)（上下文切换一般小于 \(10\mu s\)）

缺点一：平均周转时间较长，并且有较高的系统开销

缺点二：I/O 密集型任务响应延迟高（存在不必要的等待开销）

• 在运行既有 I/O 密集型任务又有计算密集型任务的情况下，当 I/O 密集型任务执行 I/O 操作时，它会让出处理器（由于需要的 CPU 计算很短，没有用完时间片就让出 CPU 了）
• 这时即使 I/O 操作很快完成，也必须等待重新分配处理器，直到其他计算密集型任务用完他们完整的 CPU 切片。

3.2 基于优先级的调度

• 问题：饿死 — 低优先级的进程可能永远不会执行
• 解决方案： 老化 — 随着时间的推移增加进程的优先级
• 需要一种能动态改变优先级的策略，如：多级反馈队列

3.3 多级反馈队列（MFQ）

• 一个进程可以在各个队列（代表不同优先级）之间移动
• 多级反馈队列调度器由以下参数定义：
  • 队列的数量
  • 每个队列的调度算法
  • 确定何时将进程提升优先级的方法
  • 确定何时将进程降优先级的方法
  • 确定当某个进程需要服务时该将进入哪个队列的方法

一个典型的多级反馈队列：

• 一组轮转队列
  • 每个队列都有单独的优先级
• 高优先级队列拥有短的时间片
• 低优先级队列拥有长的时间片
• 调度器选择最高优先级队列中的第一个进程
• 进程加载到内存中时初始在最高优先级队列中
• 如果时间片到期，任务会降低一个级别

例子： 三个优先级队列

• Priority 3：轮转调度，时间片为 8 毫秒
• Priority 2：轮转调度，时间片为 16 毫秒
• Priority 1：先进先出（FCFS）可视为时间片无穷大

调度过程如下：

• 新进程进入队列 Priority 3（最高优先级），以轮转调度的方式服务
• 当获得 CPU 时，该进程获得 8 毫秒的时间片
• 如果在 8 毫秒内未完成，则将进程移动到队列 Priority 2
• 在 Priority 2 中，作业再次以轮转调度的方式服务，并获得 16 毫秒时间片
• 如果仍然没有完成，则被抢占并移动到队列 Priority 3，进行 FCFS 调度

当使用多级反馈队列（MFQ）时：

• CPU 密集型进程将下沉到长时间片的优先级队列
  • 如果使用完时间片，进程会下降一个优先级
  • 较大的时间片可以减少上下文切换的开销
• I/O 密集型进程将保持在高优先级队列中
  • 如果一个进程没有完成其时间片（在 I/O 操作上被阻塞），那么它将保持在相同的优先级水平

多级反馈队列仍然存在饥饿问题：

• 大量交互式进程或者频繁创建新进程，则高优先级队列中始终有可用任务，低优先级队列中的 CPU 密集型进程将永远不会被调度

一个相关的问题是，一个交互式进程可能最终会处于低优先级水平。

• 如果一个进程的某个时期变得 CPU 密集型，它就会降到低优先级水平，而且注定会永远留在那里（游戏初始化为 CPU 密集型，初始化完成后要流畅）

因此，MFQ 需要一个策略（老化）来定期增加进程的优先级，以确保它会被调度运行。一个简单的方法是定期将所有进程提升到最高优先级队列，即重置

MFQ 仍可被愚弄：在时间片到期之前强制系统在某些低延迟的 I/O 操作上阻塞

解决办法：追踪 — 追踪进程在长时间间隔（几个时间片）内运行的总时间，超出优先级队列关联的最大 CPU 时间分配则降低优先级

3.4 乐透调度*

• 有的时候不能简单的优先级高的一定先执行，优先级低的一定等优先级高的执行完再执行

  • 更加希望的是：两者获得的 CPU 时间上呈一定精确的比例！高优先级的占比高一点，低优先级的占比低一点

• 一个灵活的调度算法：乐透算法

  • 给每个作业分配一定数量的彩票票数
  • 然后随机选择一个中奖票（拥有更多票数的作业有更大的中奖机会）
  • 为了避免饥饿，至少给每个作业分配一张彩票

4 实时任务的调度

• 实时系统：必须在截止日期之前得到服务
• 周期性：截止日期以规律的间隔发生

• 计算时间 \(t\)，截止日期 \(d\)，时间周期 \(p\)

  • \(0 \le t \le d \le p\)

• 周期性任务的执行速率为 \(\frac{1}{p}\)

• 准入控制：

  • 给定 \(m\) 个周期性进程，每个进程的周期时间为 \(P_i\) 和周期内的计算时间为 \(C_i\)，那么它满足以下条件时可调度（一般默认截止日期就是周期的时间）：

• m 个任务的 CPU 利用率

4.1 单调速率调度

根据其速率（即周期的倒数）分配优先级

• 周期较短的任务具有较高的优先级
  • 例如，有两个进程 P1 和 P2，它们的周期分别是 50 和 100，那么 P1 首先被调度，然后是 P2，P1 可以抢占 P2

为需要更频繁占用 CPU 的任务分配更高的优先级

• 例子：两个进程：P1 和 P2

  • P1 的周期为 50，处理时间为 20
  • P2 的周期为 100，处理时间为 35
  • 截止期限都为下一个周期之前

• 首先这个例子满足准入控制 \(\displaystyle \sum_{i=1}^{m} \frac{C_i}{P_i} \leq 1\)

  • \((20/50 + 35/100) < 1\)

P1 (计算时间20) 和 P2 (计算时间35) 的速率分别为 1/50 和 1/100

• 如果不使用率单调调度，P2 首先被调度，则 P1 过了截止时间，调度失败

• 如果按照单调速率进行调度，P1 和 P2 都会调度成功

声明：单调速率调度被认为是最优的，因为如果一组进程不能被这种算法调度，那么它就不能被任何其他分配静态优先级的算法调度（静态优先级最优）

单调速率的失效

• 两个进程：P1 和 P2
  • P1 的周期为 50，处理时间为 25
  • P2 的周期为 80，处理时间为 35
  • • 截止期限都为下一个周期之前
• 首先，这个工作负载是符合准入控制的 \(\displaystyle \sum_{i=1}^{m} \frac{C_i}{P_i} \leq 1\)
  • \((25/50 + 35/80) = 0.9375 < 1\)
• 使用单调速率调度，由于 P1 (计算时间25) 和 P2 (计算时间35) 的速率分别为 1/50 和 1/80，所以 P1（优先级大）首先被调度
• 但 P2 在时间 80 处错过了截止日期

声明：对于一组具有固定优先级的实时任务，处理器利用率的最小上界（LUB）为

\[U=n(2^{\frac{1}{n}}-1)\]

在上述例子中代入 2 约为 0.828，最大上界小于总利用率 0.9375

4.2 最早截止日期优先（EDF）

• 根据截止期限分配优先级：截止期限越早，优先级越高
• 注意：这与率单调调度不同，率单调调度中优先级是固定的（周期不变），而最早截止期限优先调度根据任务的截止期限调整优先级

• 时间 50 处，Dead2-P1 涌现，但 100 > 80，故仍处理 P2
• 时间 100 处，Dead3-P1 涌现，150 < 160，故先处理 P1

定理：EDF 是抢占式单处理机上的最优调度算法。通过调度周期性进程，EDF 的利用率上限为 100%（动态优先级最优）

5 真实操作系统调度器*

• 调度类别：每个类别都有特定的优先级
• 调度器选择最高调度类别中的最高优先级任务
• 包括两个调度类别，可以添加其他类别：
  • 实时类别：FCFS，RR，EDF
  • 普通类别：完全公平调度器（CFS），IDLE

5.1 完全公平调度策略（CFS）

目标：每个进程获得相等份额的 CPU 时间（公平性）

• \(N\) 个线程下，每个线程在任意时刻获得等份的 CPU 时间 \(t/N\)
• 无法在实际硬件上实现这一点

更加实际的做法：不断跟踪到目前为止给予进程的 CPU 时间 动态的根据每个进程当前已经给予的时间来进行调度决策：

• 每次选择 CPU 使用时间最少的线程执行
• 如果线程进入睡眠状态然后重新唤醒，则重置 CPU 使用时间为当前就绪的红黑树中 “最小” 的时间
• 不然其使用时间会远远小于其他进程，那么调度器就会疯狂的给这个进程找补

与之前的调度器不同，CFS 不是维护任务的运行队列，而是维护一个按时间排序的红黑树

• 调度时只挑选树的最左边的叶子结点（时间最少），可以提供一个指针指向这个叶子，因此调度复杂度为 \(O(1)\)
• 上下文切换时，根据这次执行的时长更新这个 current 进程的所获得运行 CPU 时间总长，然后根据其值，重新插入红黑树，时间复杂度 \(O(\log n)\)

• 如果有些进程优先级高，不想和其他进程公平
• 核心想法: 给每个进程 \(i\) 附上其权重 \(w_i\)
  • Original Basic equal share: \(Q = \frac{\text{CPU Time}}{N}\)
  • Weighted Share: \(Q_i = \left(\frac{w_i}{\sum_{j=1}^{j=N} w_j}\right) \times \text{CPU time}\)
• 跟踪线程的虚拟运行时间 (virtual runtime) 而不是其真实的物理运行时间。
  • 较高的权重：虚拟运行时间增长更慢。
  • 较低的权重：虚拟运行时间增长更快。

6 优先级反转问题*

调度和并发的 “组合” Bug

高优先级任务反而阻塞于一个持有锁的低优先级任务

解决方式：

• 每当一个任务获取一个锁时，该任务的优先级被提升到与该锁关联的优先级上限相同的优先级

• 当一个任务持有一个锁时，如果其他更高优先级的任务试图获取该锁，那么持有锁的任务的优先级将被提升到那个更高优先级的任务的优先级（优先级继承）