调度

在日常生活中，我们经常面临类似「调度」的问题。例如，在超市结账时，我们是选择人更少的队伍，还是选择看起来每位顾客购买物品较少（单人服务时间短）的队伍呢？这个简单的选择背后，就蕴含了调度的核心思想：如何在有限的资源下，高效地处理一系列任务，以达成某些目标。

调度

调度（Scheduling）是操作系统中的核心功能之一。它指的是为了满足一系列既定的性能目标，按照特定的规则（调度策略），对各种计算任务（如进程、线程、数据流等）进行系统资源（如 CPU、GPU、网络连接、磁盘带宽等）分配和管理的行为。

调度指标

评估一个调度策略的优劣，通常会关注以下一些关键指标：

• CPU 利用率：CPU 被进程所使用的时间占总 CPU 时间的比例。通常我们希望 CPU 尽可能地繁忙，处理有用的工作，所以 CPU 利用率越高越好。
• 公平性：调度策略应确保同等优先级（或类似特征）的进程能够获得大致相等的 CPU 使用时间，避免某些进程长时间得不到服务。
• 吞吐量：单位时间内完成执行的进程（或任务）数量。吞吐量越大，代表系统处理任务的效率越高。
• 周转时间：指某个特定进程从提交（进入就绪队列）到完成所需的总时间。这个时间包括了等待时间和实际执行时间。周转时间越小越好。
  • $T_{\text{周转}} = t_{\text{完成}} - t_{\text{到达}}$
• 等待时间：某个进程在就绪队列中等待 CPU 执行的时间总和。一个进程在其生命周期中可能会多次进入就绪队列等待，等待时间是这些等待时段的总和。等待时间越小越好。
  • $T_{\text{等待}} = T_{\text{周转}} - T_{\text{执行}}$
• 响应时间：从用户发出请求（例如，按下键盘、点击鼠标，或任务进入就绪队列）到系统首次对该请求作出响应（例如，开始执行相应指令、屏幕出现反馈）所花费的时间。对于交互式系统，响应时间尤为重要，越小越好。

这些指标之间有时存在冲突，例如，追求极高的 CPU 利用率可能会牺牲某些任务的响应时间或公平性。因此，调度策略的设计往往需要在这些指标间进行权衡。

调度的时机

操作系统并非随时都在进行调度决策，而是在特定的调度时机触发：

1. 发生系统调用：例如，进程通过 fork() 创建子进程，或通过 exit() 终止自身。这些操作会使 CPU 控制权从用户态转换到内核态，内核可以借此机会进行调度。
2. 某个运行的进程阻塞：例如，进程执行 I/O 操作（如读文件）需要等待数据，或者调用 wait() 等待子进程结束。当前进程无法继续执行，操作系统需要选择另一个进程运行。
3. 发生中断：
   • I/O 中断：当一个 I/O 操作完成时，对应的设备会向 CPU 发出中断信号。处理完中断后，原先等待该 I/O 的进程可能变为就绪态，此时可以进行调度。
   • 时钟中断：操作系统会设置一个定时器，周期性地产生时钟中断。这使得操作系统可以周期性地收回 CPU 控制权，检查是否有更高优先级的任务需要运行，或者当前任务的时间片是否已用完（对于抢占式调度）。

这些事件的发生都意味着系统的状态（如进程状态、资源可用性）发生了变化，可能与预设的调度目标产生了偏离。此时，调度器介入，通过调整运行哪个进程，来引导系统状态向既定目标靠近。

机制与策略

机制与策略分离

「机制与策略的分离」是操作系统设计中的一个重要思想，它是一种典型的模块化设计方法，有助于降低系统复杂度，并提高灵活性和可扩展性。

• 机制（mechanism）表示「如何做」：提供实现某种功能的基础设施或能力。例如，上下文切换的程序代码就是一种机制。
• 策略（policy）表示「做什么」或「何时做」：在机制提供的能力基础上，根据系统目标做出决策。例如，选择哪个进程进行上下文切换就是一种策略。

以 CPU 调度为例：

• 机制：操作系统必须提供保存当前进程状态（上下文）、加载新进程状态并切换执行的能力，即上下文切换机制。同时，还需要维护一个数据结构（如进程控制块 PCB 或线程控制块 TCB 的队列）来存放所有就绪的进程/线程。

  // 概念性上下文切换机制
  Task *current_task; // 当前运行的任务
  Queue ready_queue;  // 就绪任务队列
  
  Context* on_interrupt(Event ev, Context *current_ctx) {
      if (current_task) {
          current_task->context = current_ctx; // 保存当前任务上下文
          enqueue(&ready_queue, current_task); // 当前任务（如果未结束）放回就绪队列
      }
  
      Task *next_task = select_one_task_from_queue(&ready_queue); // 策略：选择下一个任务
  
      current_task = next_task;
      return next_task->context; // 恢复新任务上下文并执行
  }

• 策略：select_one_task_from_queue() 函数内部实现的逻辑就是调度策略。
  • 可以很简单：随机选择一个任务。
  • 也可以是：按照任务到达就绪队列的先后顺序选择（FIFO）。
  • 还可以是：按照任务的优先级选择。

思考与权衡：

1. 基于现有机制，探索策略：如果我们已经有了上下文切换和就绪队列的机制，那么可以研究哪种选择策略（如 FIFO, SJF, RR）在特定评价指标（如平均等待时间）下表现最好。
2. 为实现策略，改进机制：如果我们想实现一个「按照进程总执行时间最短优先」的策略，但现有机制并不记录或提供这个信息，那么就需要改进机制，例如在 PCB 中增加一个字段来存储（或预测）总执行时间，并让内核可以访问。然而，准确预测总执行时间通常不现实，这就引出了更现实的机制，如基于历史执行时间进行预测。

机制与策略的分离使得我们可以独立地修改和优化策略，而无需改动底层的复杂机制，反之亦然。

调度策略分类

CPU 调度策略多种多样，根据服务对象的任务类型和主要优化目标，大体可以分为以下几类：

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

批处理任务的调度

批处理系统的主要目标通常是最大化吞吐量和 CPU 利用率，对响应时间要求不高。

先来先服务（First-Come, First-Served, FCFS）

FCFS 是一种最简单的调度算法，也称为先进先出（First-In, First-Out, FIFO）。其核心思想是按照进程到达就绪队列的先后顺序进行调度。

• 优点：简单、易于实现、公平（按到达顺序）。
• 缺点：平均等待时间可能较长，特别是当短任务排在长任务之后时。

假设有三个进程 P1, P2, P3 同时到达，它们的执行时间分别为 $\pu{24ms}$, $\pu{3ms}$, $\pu{3ms}$。

如果按照 P1, P2, P3 的顺序执行（FCFS）：

gantt
    dateFormat x
    title FCFS 调度（P1, P2, P3）
    axisFormat %Lms
    section CPU
    P1 :0, 24
    P2 :24, 27
    P3 :27, 30

• P1 等待时间：$\pu{0ms}$
• P2 等待时间：$\pu{24ms}$
• P3 等待时间：$\pu{27ms}$
• 平均等待时间：$(\pu{0ms} + \pu{24ms} + \pu{27ms})/3 = \pu{17ms}$

护航效应

FCFS 调度容易产生护航效应（Convoy Effect）。当一个需要长时间运行的 CPU 密集型任务先占用了 CPU，后面即使有很多短的 I/O 密集型任务或其他短的 CPU 任务，它们也必须排队等待，就像慢速的卡车（长任务）挡住了一队快速的小汽车（短任务）一样。这会导致短任务的等待时间大大增加，从而拉高了平均等待时间，降低了系统整体效率。

graph LR
subgraph FCFS 队列
    direction LR
    LongTask[长任务（如卡车）] --> ShortTask1[短任务 1（小汽车）]
    ShortTask1 --> ShortTask2[短任务 2（小汽车）]
    ShortTask2 --> ShortTask3[短任务 3（小汽车）]
end
style LongTask fill:#f99
style ShortTask1 fill:#9cf
style ShortTask2 fill:#9cf
style ShortTask3 fill:#9cf

如果上例中 P2, P3 先于 P1 执行（例如，如果它们先到达，或者我们改变调度顺序）：

gantt
    dateFormat x
    title 改进顺序（P2, P3, P1）
    axisFormat %Lms
    section CPU
    P2 :0, 3
    P3 :3, 6
    P1 :6, 30

• P2 等待时间：$\pu{0ms}$
• P3 等待时间：$\pu{3ms}$
• P1 等待时间：$\pu{6ms}$
• 平均等待时间：$(\pu{0ms} + \pu{3ms} + \pu{6ms})/3 = \pu{3ms}$

可见，仅仅改变执行顺序就能显著改善平均等待时间，这启发我们寻找更优的调度策略。

最短任务优先（Shortest Job First, SJF）

SJF 调度算法会选择当前就绪队列中预计需要运行时间最短的进程来执行。

• 优点：在所有任务同时到达的情况下，SJF 能够获得最小的平均等待时间。
• 缺点：
  • 需要预知每个任务的运行时间，这在实际中很难准确获得。
  • 可能导致饥饿：如果不断有新的短任务到达，长任务可能永远得不到执行。
  • 非抢占式的 SJF，一旦长任务开始执行，即使后续来了更短的任务，也必须等待长任务完成。

例子：假设有四个进程 P1, P2, P3, P4 同时到达，它们的执行时间分别为 $\pu{6ms}$ (P1), $\pu{8ms}$ (P2), $\pu{7ms}$ (P3), $\pu{3ms}$ (P4)。

SJF 调度顺序：P4, P1, P3, P2

gantt
    dateFormat x
    title SJF 调度
    axisFormat %Lms
    section CPU
    P4 (3ms) :0, 3
    P1 (6ms) :3, 9
    P3 (7ms) :9, 16
    P2 (8ms) :16, 24

• P4 等待时间：$\pu{0ms}$
• P1 等待时间：$\pu{3ms}$
• P3 等待时间：$\pu{9ms}$
• P2 等待时间：$\pu{16ms}$
• 平均等待时间：$(\pu{0ms} + \pu{3ms} + \pu{9ms} + \pu{16ms})/4 = \pu{28ms}/4 = \pu{7ms}$

SJF 的最优性（平均等待时间）

命题：对于一批同时到达的、非抢占式的任务，SJF 调度算法产生的平均等待时间是最短的。

证明思路（反证法或调整法）：

假设存在一个非 SJF 的调度序列 $S$，其平均等待时间比 SJF 更优或相等。如果 $S$ 不是 SJF 序列，那么其中必然存在至少一对相邻的任务 $P_i, P_{i+1}$，使得 $P_i$ 在 $P_{i+1}$ 之前执行，但 $P_i$ 的执行时间 $t_i$ 大于 $P_{i+1}$ 的执行时间 $t_{i+1}$（$t_i > t_{i+1}$）。

现在，我们交换 $P_i$ 和 $P_{i+1}$ 的执行顺序，得到新序列 $S'$。

设共有 $N$ 个进程，进程 $k$ 的执行时间为 $t_k$。

一个序列的总等待时间 $W_{\text{total}} = \sum_{k=1}^{N} W_k = \sum_{k=1}^{N-1} (N-k)t_k$（这里 $t_k$ 是序列中第 $k$ 个执行的任务的执行时间）。平均等待时间 $W_{\text{avg}} = W_{\text{total}}/N$.

在原序列 $S$ 中，包含片段 $\dots, P_i, P_{i+1}, \dots$。在交换后的序列 $S'$ 中，片段变为 $\dots, P_{i+1}, P_i, \dots$。

比较 $W_{\text{total}}(S)$ 和 $W_{\text{total}}(S')$：只有涉及到 $t_i$ 和 $t_{i+1}$ 的项的系数会改变。假设 $P_i$ 是原序列中第 $k$ 个执行的任务，则 $P_{i+1}$ 是第 $k+1$ 个。

有

$$\begin{aligned} W_{\text{total}}(S) &= \dots + (N-k)t_i + (N-(k+1))t_{i+1} + \dots\\ W_{\text{total}}(S') &= \dots + (N-k)t_{i+1} + (N-(k+1))t_i + \dots \end{aligned}$$

于是

$$\begin{aligned} W_{\text{total}}(S) - W_{\text{total}}(S') &= [(N-k)t_i + (N-k-1)t_{i+1}] - [(N-k)t_{i+1} + (N-k-1)t_i]\\ &= (N-k - (N-k-1))t_i + (N-k-1 - (N-k))t_{i+1}\\ &= t_i - t_{i+1} \end{aligned}$$

由于我们假设 $t_i > t_{i+1}$，所以 $t_i - t_{i+1} > 0$。因此，$W_{\text{total}}(S) > W_{\text{total}}(S')$，即 $W_{\text{avg}}(S) > W_{\text{avg}}(S')$。

这意味着通过将执行时间较长的 $P_i$ 与紧随其后的执行时间较短的 $P_{i+1}$ 交换顺序，我们减少了总等待时间（从而也减少了平均等待时间）。

这个过程可以不断重复（类似冒泡排序，将执行时间长的任务向后移动，执行时间短的任务向前移动），每一步交换都会减少平均等待时间，直到序列变为按执行时间升序排列，即 SJF 序列。此时，无法再通过交换相邻任务来减少平均等待时间。因此，SJF 序列具有最小的平均等待时间。

最短剩余时间优先（Shortest Remaining Time First, SRTF）

SRTF 是 SJF 算法的抢占式版本。

• 非抢占式调度（Non-preemptive）：一旦 CPU 分配给一个进程，该进程就会一直持有 CPU 直到它自愿释放（例如，完成任务、等待 I/O）或被阻塞。
• 抢占式调度（Preemptive）：操作系统可以强制剥夺当前正在运行进程的 CPU 使用权，并将其分配给另一个进程（例如，当一个更高优先级的进程到达时，或者当前进程的时间片用完时）。这需要时钟中断等机制支持。

SRTF 算法会选择就绪队列中剩余执行时间最短的进程运行。如果一个新到达的进程比当前正在运行的进程的剩余执行时间还要短，SRTF 就会抢占当前进程，让新进程执行。

例子：

进程	到达时刻（ms）	执行时间（ms）
P1	0	8
P2	1	4
P3	2	9
P4	3	5

gantt
    title SRTF 调度
    dateFormat x
    axisFormat %Lms
    section CPU
    P1 :done, 0, 1
    P2 :1, 5
    P4 :5, 10
    P1 :active, 10, 17
    P3 :17, 26

时刻（ms）	事件描述	就绪队列（剩余时间）	当前执行进程
0	P1 到达，开始执行	空	P1(8)
1	P2 到达（4ms），P1 已执行 1ms（剩余 7ms）。P2(4) < P1(7)，P2 抢占 P1	P1(7)	P2(4)
2	P3 到达（9ms），P2 已执行 1ms（剩余 3ms）。P3(9) > P2(3)，P2 继续	P1(7), P3(9)	P2(4)
3	P4 到达（5ms），P2 已执行 2ms（剩余 2ms）。P4(5) > P2(2)，P2 继续	P1(7), P3(9), P4(5)	P2(4)
5	P2 完成。选择剩余时间最短的 P4(5) 执行	P1(7), P3(9)	P4(5)
10	P4 完成。选择剩余时间最短的 P1(7) 执行	P3(9)	P1(7)
17	P1 完成。就绪队列只剩 P3	空	P3(9)
26	P3 完成。所有进程执行完毕	空	空

等待时间计算：

• P1（到达 0） 第一次等待 0。被抢占后从 t=1 等到 t=10。总等待 $\pu{9ms}$。
• P2（到达 1） 等待 0。总等待 $\pu{0ms}$。
• P3（到达 2） 等到 t=17。总等待 $\pu{15ms}$。
• P4（到达 3） 等到 t=5。总等待 $\pu{2ms}$。
• 平均等待时间：$(\pu{9ms} + \pu{0ms} + \pu{15ms} + \pu{2ms})/4 = \pu{6.5ms}$。

SRTF 同样能达到很好的平均周转时间，但仍有饥饿问题和需要预测运行时间的挑战。

如何获取任务运行时间？—— 时间预测算法

SJF 和 SRTF 的一个主要障碍是需要预知进程的（剩余）执行时间。对于 CPU 执行时间，这通常是未知的。一种常见的方法是基于进程过去的行为来预测其下一次 CPU 执行的长度。指数移动平均是一种常用的预测技术。

设：

• $t_n$：第 $n$ 次 CPU 执行的实际长度。
• $\tau_n$：对第 $n$ 次 CPU 执行长度的预测值。
• $\tau_{n+1}$：对下一次（第 $n+1$ 次） CPU 执行长度的预测值。

预测公式为：

$$\tau_{n+1} = \alpha \cdot t_n + (1-\alpha) \cdot \tau_n$$

其中，$0 \le \alpha \le 1$ 是一个权重系数，决定了历史数据和最近实际值在预测中的相对重要性。

• 如果 $\alpha = 0$，则 $\tau_{n+1} = \tau_n$。预测值永远不变，完全忽略最近的实际执行时间。
• 如果 $\alpha = 1$，则 $\tau_{n+1} = t_n$。预测值完全等于上一次的实际执行时间，忽略了更早的历史。
• 如果 $\alpha = 0.5$，则 $\tau_{n+1} = 0.5 t_n + 0.5 \tau_n$。最近的实际值和之前的预测值各占一半权重。

展开 $\tau_{n+1}$ 的递推式：

$$\begin{aligned} \tau_{n+1} &= \alpha t_n + (1-\alpha) (\alpha t_{n-1} + (1-\alpha)\tau_{n-1})\\ &= \alpha t_n + \alpha(1-\alpha)t_{n-1} + (1-\alpha)^2 \tau_{n-1}\\ &= \dots \\ &= \alpha t_n + \alpha(1-\alpha)t_{n-1} + \dots + \alpha(1-\alpha)^j t_{n-j} + \dots + (1-\alpha)^{n+1} \tau_0 \end{aligned}$$

其中 $\tau_0$ 是初始预测值。
这个展开式表明，最近的 $t_n$ 拥有最大的权重 $\alpha$，而较早的 $t_{n-j}$ 的权重 $\alpha(1-\alpha)^j$ 随着 $j$ 的增大而指数级衰减。因此，这个算法更侧重于近期的行为。

SJF/SRTF 的缺陷

尽管 SJF/SRTF 在平均等待/周转时间上表现优异，但它们存在一些固有缺陷：

1. 不公平/饥饿：长任务的优先级持续低于新到达的短任务，可能导致长任务长时间得不到执行，甚至饿死。
2. 等待时间差异大：短任务很快完成，长任务等待很久，用户体验可能不均衡。
3. 运行时间难以准确预测：虽然有指数移动平均等方法，但预测总有误差，尤其对于行为不规律的进程。
4. 易被愚弄（gaming）：如果调度器依赖于预测的短时间运行，恶意用户或程序可以将一个长任务伪装成一系列「非常短」的小任务（例如，在预测的短时间片结束前主动进行一次不必要的、快速完成的 I/O 操作），从而骗取更高的调度优先级，破坏公平性。

交互性任务的调度

交互式系统的主要目标是提供良好的响应时间，同时兼顾公平性和吞吐量。用户期望他们的操作（如键盘输入、鼠标点击）能得到快速反馈。

CPU 密集型 vs. I/O 密集型

在调度交互性任务时，区分进程类型非常重要：

• CPU 密集型（CPU-bound） 进程：大部分时间花费在 CPU 计算上，很少进行 I/O 操作。它们倾向于长时间占用 CPU，直到完成计算或时间片用尽。例如：科学计算、视频编码。
• I/O 密集型（I/O-bound） 进程：大部分时间花费在等待 I/O 操作完成上（如读写磁盘、网络通信、等待用户输入）。它们通常只进行短暂的 CPU 计算，然后就发起 I/O 请求并阻塞。例如：文本编辑器、Web 服务器处理简单请求。

调度策略需要平衡这两类进程的需求，通常会倾向于优先响应 I/O 密集型任务，因为它们快速完成 CPU 部分后会主动释放 CPU，从而提高系统整体的交互性和资源利用率。

时间片轮转（Round-Robin, RR）

RR 是一种简单且广泛应用的交互式系统调度算法。

• 原理：每个进程被分配一个固定的时间段，称为时间片（time slice 或 quantum）。进程在该时间片内运行。
  • 如果进程在时间片用完前完成，它会自愿释放 CPU。
  • 如果时间片用完时进程仍在运行，它会被抢占，并被放回就绪队列的末尾，等待下一轮调度。
• 时间片大小的选择：
  • 过小：频繁的上下文切换会带来显著的开销，降低系统效率。
  • 过大：RR 算法会退化为 FCFS 算法，响应时间变差。
  • 通常选择在 $\pu{10ms}$ 到 $\pu{100ms}$ 之间，而上下文切换时间一般远小于此（如小于 $\pu{10\mu s}$）。

RR 的问题：当系统中混合了 I/O 密集型和 CPU 密集型任务时，RR 可能对 I/O 密集型任务不够友好。

• 例如，一个 I/O 密集型任务（如 Vim 编辑器响应按键）可能只需要 $\pu{1ms}$ 的 CPU 时间来处理输入并更新屏幕，然后就会阻塞等待下一次输入。但在 RR 中，如果时间片是 $\pu{20ms}$，它在运行 $\pu{1ms}$ 后主动放弃 CPU，下次轮到它可能需要等待其他 CPU 密集型任务用完它们完整的 $\pu{20ms}$ 时间片。这会导致交互应用的响应延迟。

基于优先级的调度（Priority Scheduling）

这种策略为每个进程分配一个优先级，调度器总是选择具有最高优先级的就绪进程来执行。优先级可以是静态的（一旦分配就不变）或动态的（随进程行为或等待时间而改变）。

• SJF 可以看作一种优先级调度，其优先级与预测的下一个 CPU 执行时间的倒数成正比。
• Linux 优先级示例：
  • 实时任务：优先级范围 0-99（值越小，优先级越高）。
    • chrt -r -p <priority> <PID> 可设置实时优先级。
  • 普通任务：优先级范围 100-139（对应 nice 值 -20 到 +19）。nice 值越小，优先级越高（nice -20 映射到 100，nice +19 映射到 139）。
    • nice 命令调整新进程的 nice 值，renice 命令调整已存在进程的 nice 值。

假设下面优先级数字越大，优先级越高。

进程	执行时间（ms）	优先级
P1	10	3
P2	1	5（最高）
P3	2	2
P4	1	1（最低）
P5	5	4

调度顺序（非抢占式，若同时就绪）：

gantt
    dateFormat x
    title 优先级调度（P2, P5, P1, P3, P4）
    axisFormat %Lms
    section CPU
    P2 :0, 1
    P5 :1, 6
    P1 :6, 16
    P3 :16, 18
    P4 :18, 19

平均等待时间：$(\pu{0ms} + \pu{1ms} + \pu{6ms} + \pu{16ms} + \pu{18ms})/5 = \pu{8.2ms}$。

• 问题：饿死。低优先级的进程可能长时间（甚至永远）得不到 CPU，因为总有更高优先级的进程就绪。
• 解决方案：老化。逐步增加那些长时间等待的进程的优先级。例如，每隔一段时间，将所有等待超过特定阈值的进程的优先级提升一级。这样，即使是最初优先级很低的进程，最终其优先级也会变得足够高从而获得执行机会。

多级反馈队列（Multilevel Feedback Queue, MFQ）

MFQ 是一种试图平衡周转时间、响应时间并防止饥饿的复杂调度算法。它使用多个就绪队列，每个队列对应一个不同的优先级级别。

核心思想：

1. 多个队列：系统维护多个就绪队列，例如 Q0 (最高优先级), Q1, Q2, … Qn (最低优先级)。
2. 不同队列不同策略/参数：
   • 高优先级队列通常分配较短的时间片（例如 Q0 使用 RR，时间片 $\pu{8ms}$）。
   • 低优先级队列分配较长的时间片（例如 Q1 使用 RR，时间片 $\pu{16ms}$）。
   • 最低优先级队列可能使用 FCFS。
3. 进程移动：进程可以在队列之间移动，这是「反馈」的关键。
   • 降级：如果一个进程用完了其在某个队列中的整个时间片（表明它可能是 CPU 密集型的），它会被移到更低优先级的队列。
   • 升级：如果一个进程在低优先级队列中等待时间过长（老化机制），或者一个进程在时间片用完前就阻塞（表明它可能是 I/O 密集型的，应该保持较高响应性），它可以被移到更高优先级的队列。
4. 调度规则：调度器总是先从最高优先级的非空队列中选择进程执行。只有当所有高优先级队列都为空时，才处理次高优先级队列中的进程。同一队列内的进程按该队列的调度策略（如 RR）执行。

典型 MFQ 行为：

• 新进程：通常进入最高优先级队列。
• I/O 密集型进程：它们倾向于在时间片用完前就因 I/O 阻塞，因此它们会停留在（或很快返回到）高优先级队列，获得良好的响应时间。
• CPU 密集型进程：它们会用完高优先级队列的短时间片，然后逐渐「下沉」到低优先级队列。在低优先级队列中，它们会获得更长的时间片，从而减少上下文切换的开销。

MFQ 的问题与改进：

1. 饥饿：如果高优先级队列持续有大量交互式任务或新任务进入，低优先级队列中的 CPU 密集型任务可能饿死。
   • 解决：实现老化策略，例如周期性地将所有任务提升到最高优先级队列（重置）。
2. 愚弄 MFQ 系统：恶意程序可以通过在时间片即将用完前执行一次非常短暂的 I/O 操作，来欺骗调度器，使其认为自己是 I/O 密集型的，从而保持在高优先级队列中。
   • 解决：调度器不仅看单次时间片使用情况，还应追踪一个进程在更长时间窗口内（跨越多个时间片）的总 CPU 使用量。为每个优先级队列设置一个在此窗口内的最大 CPU 时间分配额度，超出则强制降级。
3. 参数调优：队列数量、各队列时间片长度、升降级策略等参数的选择对性能影响很大，调优复杂。

乐透调度（Lottery Scheduling）

乐透调度是一种基于概率的调度算法，旨在提供对 CPU 时间的按比例共享，而不是绝对的优先级。

原理：

1. 为每个进程分配一定数量的「彩票」（tickets）。进程的重要性或期望的 CPU 份额越高，分配的彩票越多。
2. 调度器在每次调度时，随机抽取一张「中奖彩票」。持有该中奖彩票的进程获得下一个 CPU 时间片。
3. 拥有更多彩票的进程，其中奖概率自然更高，从而在长期来看能获得更多的 CPU 时间。

优点：

• 响应性：短任务即使彩票少，也有机会被抽中。
• 公平性控制：通过调整彩票分配，可以精确控制不同进程间的 CPU 时间比例。
• 避免饥饿：只要每个进程至少拥有一张彩票，它就永远有被调度的机会。

实现：可以通过维护一个包含所有彩票编号的列表，然后随机选择一个编号。或者更高效地，维护一个按进程排序的列表，每个进程占据与其票数成正比的一段区间，然后生成一个覆盖总票数范围的随机数，看落在哪个进程的区间内。

实时任务的调度

实时系统对时间有严格要求，任务的正确性不仅取决于计算结果，还取决于结果产生的时间。

实时系统特点：

• 截止日期：每个任务或任务的每个实例都有一个必须完成的截止日期。错过截止日期可能导致严重后果（硬实时系统）或性能下降（软实时系统）。
• 周期性任务：许多实时任务是周期性的，以固定的时间间隔重复执行。
  • 计算时间 $C$：一次执行所需 CPU 时间
  • 周期 $P$：任务激活的间隔
  • 截止日期 $D$：相对于激活时间
  • 通常 $0 \le C \le D \le P$
• 准入控制：在接受一个新实时任务前，系统必须判断是否能在满足所有现有任务和新任务截止日期的前提下调度它们。一个简单的准入条件（针对周期性任务，且 $D_i = P_i$）是 CPU 利用率总和不超过 1：

  $$\sum_{i=1}^{m} \frac{C_i}{P_i} \le 1$$

  • 如果该条件不满足，则系统肯定无法调度所有任务。满足该条件也并不总是意味着所有任务都能按时完成（取决于调度算法）。

单调速率调度（Rate Monotonic, RM）

RM 是一种经典的静态优先级实时调度算法。

• 优先级分配：任务的优先级根据其速率（即周期的倒数 $1/P$）来确定。周期越短（速率越高），优先级越高。优先级一旦分配，在任务执行期间保持不变。
• 调度：总是选择就绪队列中优先级最高的任务执行，可抢占。
• 最优性：Liu 和 Layland 在 1973 年证明，对于静态优先级分配的抢占式调度，如果一个任务集可以被任何静态优先级算法调度成功，那么它一定可以被 RM 调度成功。
• 可调度性分析：RM 并非总能利用 100% 的 CPU。其可调度的 CPU 利用率上限（充分条件 Least Upper Bound）为：

  $$U_{\text{LUB}} = n(2^{1/n} - 1)$$

  • 其中 $n$ 是任务数量。当 $n \to \infty$ 时，$U_{\text{LUB}} \to \ln 2 \approx 0.693$。如果任务集的总利用率 $\sum \frac{C_i}{P_i} \le U_{\text{LUB}}$，则 RM 一定能成功调度。如果超过此上限，RM 可能成功也可能失败。

例子：

• 任务 P1：$C_1=20, P_1= D_1=50$（优先级高）
• 任务 P2：$C_2=35, P_2= D_2=100$（优先级低）
• 总利用率：$20/50 + 35/100 = 0.75$

$n=2, U_{\text{LUB}} = 2(2^{1/2}-1) \approx 0.828$，由于 $0.75 \le 0.828$，RM 可以成功调度。

RM 失效的例子：

• 任务 P1：$C_1=25, P_1= D_1=50$（优先级高）
• 任务 P2：$C_2=35, P_2= D_2=80$（优先级低）
• 总利用率：$25/50 + 35/80 = 0.9375$

此时 $0.9375 > U_{\text{LUB}} \approx 0.828$，RM 不保证成功。

在 P1 第二个周期中，P1 首先被调用，在 t=75 时完成，但 P2 在 t=80 就到了截止日期。

最早截止日期优先（Earliest Deadline First, EDF）

DDL 驱动算法

EDF 是一种动态优先级实时调度算法。

• 优先级分配：任务的优先级根据其当前的绝对截止日期来确定。截止日期越早，优先级越高。由于任务的每次激活都会产生新的截止日期，所以优先级是动态变化的。
• 调度：总是选择就绪队列中绝对截止日期最早的任务执行，可抢占。
• 最优性：对于抢占式的单处理器系统，EDF 是最优的动态优先级调度算法。如果一个任务集可以被任何算法调度成功，那么它一定可以被 EDF 调度成功。
• 可调度性：EDF 可以达到 100% 的 CPU 利用率。即，只要任务集的总利用率 $\sum \frac{C_i}{P_i} \le 1$，EDF 就能成功调度所有任务（假设 $D_i=P_i$）。

例子（使用 RM 失效的例子）:

• 任务 P1：$C_1=25, P_1= D_1=50$
• 任务 P2：$C_2=35, P_2= D_2=80$

真实操作系统调度器案例：Linux CFS

现代通用操作系统如 Linux，其调度器通常非常复杂，需要平衡多种需求。Linux 2.6.23 版本之后引入了完全公平调度器^[1]（Completely Fair Scheduler, CFS） 作为普通任务的默认调度器。

Linux 调度类别：Linux 将任务分为不同的调度类别，每个类别有其优先级。调度器首先选择优先级最高的调度类别，然后从该类别中选择任务。

• 实时类别：包括 FCFS (SCHED_FIFO), RR (SCHED_RR)，以及后来加入的 EDF (SCHED_DEADLINE)。这些任务优先级高于普通任务。
• 普通类别：主要由 CFS (SCHED_NORMAL 或 SCHED_OTHER) 和 IDLE (SCHED_IDLE, 最低优先级) 处理。

完全公平调度器（CFS）

• 目标：实现「完全公平」，即在理想情况下，如果有 $N$ 个活动线程，每个线程在任意时刻 $t$ 都应该获得 $t/N$ 的 CPU 时间。这是一种理想化的模型，实际硬件无法完美实现。
• 核心机制：虚拟运行时间
  • CFS 不直接使用固定的时间片，而是为每个任务维护一个虚拟运行时间（vruntime）。vruntime 记录了该任务已获得的、经过规范化的 CPU 时间。
  • 调度器总是选择当前就绪任务中 vruntime 最小的任务来执行。
  • 任务执行时，其 vruntime 会随着实际执行时间的增加而增加。
  • 如果一个任务睡眠后被唤醒，其 vruntime 通常会被调整（例如，设置为当前红黑树中所有任务 vruntime 的最小值附近），以避免它因长时间睡眠而积累了过小的 vruntime，从而在唤醒后长时间霸占 CPU。
• 数据结构：红黑树
  • CFS 不使用传统的运行队列，而是将所有就绪任务组织在一个以 vruntime 为键值的红黑树中。
  • 选择下一个任务执行时，只需选取红黑树的最左边节点（vruntime 最小），时间复杂度为 $O(1)$（如果维护了指针）。
  • 任务执行完毕或被抢占后，其 vruntime 更新，然后重新插入红黑树，时间复杂度为 $O(\log n)$，其中 $n$ 是就绪任务数量。
  • 
• 优先级/权重处理：
  • CFS 通过权重来实现不同优先级的任务之间的公平共享。nice 值映射到不同的权重。高优先级（nice 值小）的任务拥有更高的权重。
  • 任务的 vruntime 增加速率与其权重成反比：
    $\Delta \text{vruntime} = \frac{\text{weight}_0}{\text{weight}_{\text{task}}} \times \Delta \text{actual\_runtime}$
    其中 $\text{weight}_0$ 是一个基准权重（例如 nice 0 对应的权重）。
  • 这意味着，权重越高的任务，其 vruntime 增长得越慢，从而在红黑树中更容易保持在左侧，获得更多的 CPU 执行机会。最终效果是，每个任务获得的 CPU 时间与其权重成正比。

调度相关的其他问题*

多核 CPU 调度

• 不对称多处理（Asymmetric Multiprocessing, AMP）：一个主处理器负责所有调度决策和系统活动，其他处理器只执行用户代码。简单但主处理器易成瓶颈。
• 对称多处理（Symmetric Multiprocessing, SMP）：每个处理器都运行操作系统的副本（或共享内核代码），并能独立进行调度决策。这是现代多核系统的主流。
  • 队列机制：
    1. 统一就绪队列：所有 CPU 共享一个全局就绪队列。
       • 优点：负载自动均衡。
       • 缺点：需要锁来保护共享队列，可能成为瓶颈；缓存亲和性差。
    2. 每 CPU 私有就绪队列：每个 CPU 维护自己的就绪任务队列。
       • 优点：无需锁竞争（或竞争很小）；更好的缓存亲和性。
       • 缺点：可能导致负载不均。
       • 这是 SMP 系统中最常见的方法。

负载均衡

在采用每 CPU 私有队列的 SMP 系统中，需要机制来确保工作负载在各个 CPU 之间均匀分布，以提高效率。

• 推迁移：一个周期性任务（或内核线程）检查各 CPU 的负载。如果发现某个 CPU 过载，而其他 CPU 空闲或负载较低，则将任务从过载 CPU「推送」到其他 CPU。
• 拉迁移：当一个 CPU 的就绪队列为空或负载很低时，它会主动从其他繁忙的 CPU 的就绪队列中「拉取」等待的任务来执行。

处理器亲和性

当一个线程在某个处理器上运行时，该处理器的高速缓存中会加载该线程访问过的数据和指令。如果线程下次还在同一个处理器上运行，它可以直接从缓存中快速获取这些内容，这就是处理器亲和性。

• 软亲和性：操作系统会尽量让进程保持在同一个处理器上运行，但不保证。
• 硬亲和性：允许进程指定它只能在哪些处理器上运行。

负载均衡可能会破坏处理器亲和性：当一个任务被迁移到另一个 CPU 时，它在新 CPU 的缓存中是「冷」的，需要重新加载数据，可能导致性能下降。因此，调度器和负载均衡器需要在保持亲和性和均衡负载之间进行权衡。

NUMA 与调度

非统一内存访问（Non-Uniform Memory Access, NUMA） 架构中，系统有多个处理器节点，每个节点有自己的本地内存。访问本地内存速度快，访问其他节点的内存速度慢。
NUMA 感知的操作系统在调度时，应尽量将线程调度到其数据所在的内存节点的 CPU 上，或者将线程的内存分配在其即将运行的 CPU 的本地内存中，以减少远程内存访问延迟。

优先级反转

优先级反转（Priority Inversion）

优先级反转是指一个高优先级任务的执行被一个低优先级任务所阻塞或延迟的现象。

1. 两级反转（简单阻塞）
   • 低优先级任务 TL 持有一个锁（如互斥锁）。
   • 高优先级任务 TH 开始运行，被调度器选中取代 TL，尝试获取该锁，但由于锁被 TL 持有，TH 阻塞^[2]。
   • 此时，TL 继续执行直到释放锁。TH 的等待时间取决于 TL 在临界区内的执行时间。
2. 三级反转（经典反转）
   • 低优先级任务 TL 持有一个锁。
   • 高优先级任务 TH 开始运行，尝试获取该锁，阻塞等待 TL。
   • 此时，一个中优先级任务 TM（TM 不用这个互斥锁）变为就绪态。由于 TM 优先级高于 TL，TM 会抢占 TL 并开始执行。
   • 结果：TH 不仅要等 TL 释放锁，还要等 TM 执行完毕后 TL 才有机会运行并释放锁。TH 实际上被优先级低于它的 TM 间接阻塞了。

sequenceDiagram
participant TL as 低优先级任务（L）
participant TM as 中优先级任务（M）
participant TH as 高优先级任务（H）
participant Lock as 互斥锁

TL->>Lock: 获取锁
Note over TL: 进入临界区

TH->>Lock: 尝试获取锁（被 TL 阻塞）
Note over TH: 被阻塞

Note over TM, TL: TM 抢占 TL
loop TM 运行期间（TH 等得花都谢了）
    TM->>TM: 运行
    Note over TH: TH 仍然被阻塞，等待 TL，<br/>但 TL 不能运行因为 TM 在运行。
end

Note over TM: 完成或阻塞
Note over TL, TH: TL 恢复（如果 TM 已完成）
Lock-->>TL: 释放锁
Note over TL: 退出临界区

TH->>Lock: 获取锁
TH->>TH: 运行

解决方案：

1. 优先级继承：当一个高优先级任务 TH 阻塞等待一个由低优先级任务 TL 持有的锁时，TL 临时「继承」TH 的高优先级。这样可以防止中优先级任务 TM 抢占 TL，使得 TL 能尽快执行并释放锁，从而让 TH 尽快获得锁。一旦 TL 释放锁，它就恢复到原来的低优先级。
   • 
2. 优先权上限：
   • 为每个共享资源（如锁）预先设定一个「优先级上限」，该上限等于可能访问该资源的最高优先级任务的优先级。
   • 当一个任务 T 获取锁时，如果 T 的当前优先级低于该锁的优先级上限，则 T 的优先级被提升到该上限。
   • 当 T 释放锁时，其优先级恢复原状（或根据其他规则调整）。
   • 这种方法可以更主动地防止优先级反转的发生，并且可以避免优先级继承可能导致的链式继承和死锁问题（在更复杂的场景下）。
   • 

总结

• 机制与策略：调度机制（如上下文切换、就绪队列管理）为调度策略（如 FCFS, SJF, RR, 优先级, MFQ, CFS）提供实现基础。
• 调度算法：
  • 批处理：
    • FCFS：简单但有护航效应
    • SJF：平均等待时间最优，但需预测且可能饿死
    • SRTF：SJF 抢占版
  • 交互式：
    • RR：响应好，但周转时间可能长,
    • 优先级：灵活，但可能饿死，需老化
    • MFQ：试图平衡各方面，但复杂且可能被愚弄
    • Lottery：按比例公平
  • 实时：
    • RM：静态优先级，周期短优先
    • EDF：动态优先级，截止期早优先，利用率可达 100%。
  • 现代通用 OS：Linux CFS（基于 vruntime 和权重的公平调度）。
• 评价调度策略：需综合考虑 CPU 利用率、吞吐量、周转时间、等待时间、响应时间、公平性等指标。
• 高级主题：多核调度（SMP、负载均衡、亲和性、NUMA），优先级反转及其解决方案（继承、上限）。

---

1. Linux 内核从 6.6 版本开始向 EEVDF(Earliest Eligible Virtual Deadline First) 调度器迁移，不再使用 CFS。 ↩︎

2. 使用「阻塞」而非「忙等待」，否则的话 TH 会不断尝试获取锁，但锁在优先级更低的 TL，永远不会释放锁。 ↩︎