《操作系统导论》第9章：调度：比例份额 - 深度知识架构

1. 核心矛盾 (The Crucial Problem)

在不以优化周转时间和响应时间为首要目标的前提下，如何确保系统中的每个工作都能严格按特定比例（公平地）分享 CPU 资源？

2. 核心概念 (Core Concepts)

• 比例份额 / 公平份额 (Proportional-share / Fair-share)：
  • 定义：一种与传统调度器（如 MLFQ、SJF）截然不同的调度哲学。它的最终目标不是为了缩短任务的完成时间，而是确保每个工作获得系统承诺的一定比例的 CPU 时间。
  • 角色：系统资源分配的“天平”，专注于调度的绝对公平性。
• 彩票数 (Tickets)：
  • 定义：代表进程占有某个资源（如 CPU）的份额。
  • 角色：操作系统的“底层货币”。进程拥有的彩票数占总彩票数的百分比，直接代表了它应得的 CPU 时间的百分比。
• 彩票调度 (Lottery Scheduling)：
  • 定义：利用随机性来实现比例份额分配的调度程序。每隔一段时间，系统举行一次“抽奖”，拥有更多彩票的进程中奖（运行）的概率就越大。
  • 角色：通过概率统计来实现长期公平的决策执行者。
• 步长调度 (Stride Scheduling)：
  • 定义：为了解决随机性带来的短期不确定性而引入的确定的比例份额调度算法。
  • 角色：系统的“精准计时器”，通过确定性的步长计算，严格保证短周期内的公平性。

3. 逻辑演进 (Logical Evolution)

为了解决“按比例公平分配”的核心问题，本章展现了从随机到确定的推导逻辑：

• 最初的方案（引入彩票与随机性）：为了实现比例分配，系统为每个进程分配不同数量的彩票，并通过生成随机数来抽奖决定下一个运行的进程。
  • 遇到的问题（为什么不是确定的）：随机算法在长时间尺度下是公平的，但在短期内极度不公平。例如，在短时间内，拥有 10 张彩票的进程可能会由于运气极佳，运行时间甚至超过拥有 100 张彩票的进程，导致短期的响应或周转出现极度偏差。
• 最终的成熟方案（步长调度算法）：为了克服随机调度的短期不公平性，设计者发明了确定的步长调度 (Stride Scheduling)。系统为每个进程计算一个步长（反比于其彩票数），并跟踪其已运行的“行程（Pass）”。每次调度时，系统精确挑选当前行程值最小的进程运行，从而完美实现了无论长期还是短期都严格按比例分配 CPU。

4. 机制与策略 (Mechanisms vs. Policies)

• 机制 (Mechanisms - 底层实现手段)：
  • 彩票机制 (Lottery Mechanisms)：书中提出了一系列基于彩票的巧妙机制。例如：彩票货币 (Ticket Currency) 允许用户将自己的总彩票数按不同比例分配给自己的各个工作；彩票转让 (Ticket Transfer) 允许客户端在向服务器发请求时临时将彩票转让给服务器以加速处理；彩票通胀 (Ticket Inflation) 允许互信的进程在需要时临时增加自己的彩票数。
  • 随机数生成与状态记录（步长调度的 pass 和 stride 计算）也是底层的调度执行机制。
• 策略 (Policies - 上层决策逻辑)：
  • 如何分配彩票 (How to assign tickets) 是纯粹的策略问题。例如，到底是给工作 A 分配 100 张彩票还是 10 张彩票？这取决于系统管理员或用户的业务目标，调度器本身并不关心，只负责按给定比例执行。

5. 设计折衷 (Design Trade-offs)

• “随机算法的极简性”与“短期公平性”的折中：彩票调度（随机）牺牲了短期的精确公平性，但换取了极致的状态极简（几乎不需要记录进程的历史运行状态，也不需要处理新加入进程的状态继承问题）。而步长调度（确定性）牺牲了这种极简性（需要维护全局状态并处理新旧进程的行程同步），换取了完美的短期公平。
• “绝对公平”与“性能指标”的折中：无论彩票调度还是步长调度，它们在设计之初就完全放弃了优化周转时间或响应时间。如果工作负载同时需要极低的响应时间，这种纯粹追求比例公平的调度器可能表现糟糕。

6. 关键洞察 (Key Insights)

• 随机性是规避状态复杂度的终极武器：在系统设计中，当精确计算和状态维护异常复杂时（例如调度器需要处理任务的不停加入和退出），引入概率和随机数往往能以极低的代码和空间成本，实现长期意义上的正确性。
• 货币与经济学模型的系统学应用：将系统资源的分配抽象为“彩票（货币）”并引入通胀、转让等机制，展现了将经济学思想完美融入计算机系统资源管理的工程智慧。

📄 补充知识文档：高响应比优先 (HRRN) 调度

1. 核心矛盾 (The Crucial Problem)

在追求“短作业优先（以降低平均周转时间）”的同时，如何避免长作业被无限期推迟（即饥饿 Starvation 问题）？

2. 核心概念 (Core Concepts)

• 响应比 (Response Ratio, RR)：定义为一个任务的“满意度”指标。

  $$R=\frac{W+S}{S}=1+\frac{W}{S}$$

  • $W$ (Wait Time)：任务到目前为止已经等待的时间。

  • $S$ (Service Time / Expected Run Time)：任务预计需要的执行时间。

• 非抢占式 (Non-preemptive)：HRRN 通常在任务主动退出或阻塞时才进行下一次计算，不会在任务运行中途强行夺走 CPU。

3. 逻辑演进 (Logical Evolution)

为了解决调度中的公平与效率问题，逻辑经历了以下演进：

1. 先来先服务 (FCFS)：绝对公平，但遇到长作业在前面时，会导致严重的护送效应（短作业等太久）。

2. 短作业优先 (SJF)：效率最高（平均周转时间最优），但会导致长作业饥饿。

3. HRRN 的诞生：为了平衡两者，设计者引入了“时间”这个变量。

   • 当任务刚到达时，$W$ 很小，此时 $R$ 的大小主要取决于执行时间 $S$（此时表现接近 SJF，短作业优先）。

   • 随着长作业等待时间 $W$ 不断变大，它的响应比 $R$ 会随之提高。最终，长作业的 $R$ 会超过新来的短作业（这就是**“老化 Aging”**机制）。

4. 机制与策略 (Mechanisms vs. Policies)

• 机制 (Mechanisms)：系统需要记录每个进程的到达时间，并在每次调度决策点计算 Ready 队列中所有进程的 $R$ 值。

• 策略 (Policies)：选择 $R$ 值最高的进程运行。这里的策略逻辑是：谁等的越委屈（$W$ 大），或者谁干活越快（$S$ 小），谁就优先。

5. 设计折衷 (Design Trade-offs)

• “公平”与“计算开销”的折衷：HRRN 虽然解决了饥饿问题，但它要求系统在每次调度时都对所有等待进程计算一次公式。相比之下，彩票调度（随机抽奖）或 FCFS（直接取队头）的开销要小得多。

• “非抢占”的局限：由于它是非抢占的，一旦一个超长作业开始运行，新来的紧急短作业仍然无法立刻插队。

6. 关键洞察 (Key Insights)

• “老化 (Aging)”是解决不公平的万灵药：在计算机系统设计中，如果你发现某个策略会导致“强者恒强、弱者饿死”，最简单的逻辑补丁就是引入一个随时间增长的权重。

• 预测的代价：和 SJF 一样，HRRN 依赖于对运行时间 $S$ 的预估。如果预估不准，这个逻辑闭环就会破裂。

导师的下一步建议：

比例份额调度通过彩票和步长机制，在不依赖预测的前提下实现了CPU的公平分配。但上述所有调度算法都假设系统只有一个CPU核心。随着多核处理器的普及，调度问题变得更加复杂——缓存亲和度、锁竞争和负载均衡等新的挑战扑面而来。下一章将深入探讨多处理器调度（SQMS和MQMS），揭示软件架构如何必须屈从于硬件物理特性。

MOC · 下一章：Ch10 多处理器调度