Appearance
公平调度算法
2026 大纲 二（二）4 CPU 调度算法里以公平性为目标的两个算法：保证调度（对进程公平）与公平分享调度（对用户公平）。指标口径沿用 调度的基本概念与目标。
前面七种都在承诺次序，这一种承诺份额
回头看前面七种算法，它们承诺的东西其实是同一类：次序。 FCFS 承诺"按来的顺序"，SJF 承诺"短的先跑"，RR 承诺"轮着来"， 优先级承诺"重要的先跑"，MLFQ 承诺"短的自动优先"。
次序解决不了一个问题：我到底能分到多少 CPU？ 在 RR 下，进程数一多，每个人分到的都变少，但没人告诉你会变成多少。
公平调度换了个承诺：不承诺你什么时候跑，承诺你能拿到多少。
保证调度为每个进程保证约
用比值而不用差值是有理由的：差值没法在应得份额不同的进程之间比较， 比值把欠账折算成了相对于自身应得份额的比例。
还有一个附带的好处：分母（应得时间）随时间单调增长， 所以一个进程只要一直没跑，它的比率就会一直往下掉，早晚被选中—— 它天然不饥饿，也不需要老化补丁。老化被内建进了比较键里。
⚠️ 最后一处要分清：对进程公平不等于对用户公平。 进程数是用户自己决定的——一个用户开 10 个进程，就能拿走 10 份。 公平分享调度因此改按用户分配份额，本质是按用户加权的 RR。
一、保证调度算法
实现分五步：
| 步骤 | 做什么 |
|---|---|
| ① | 跟踪计算每个进程自创建以来已经执行的处理时间（实际获得） |
| ② | 计算每个进程应获得的 CPU 时间 = （当前时刻 − 创建时刻）/ |
| ③ | 计算公平比率 = 实际获得 / 应获得 |
| ④ | 比较各进程的公平比率 |
| ⑤ | 调度比率最小的进程，让它一直运行，直到它的比率超过最接近它的那个进程为止 |
三进程的公平比率逐步演算：超额者怎么被晾住、又怎么自己回到队首（想看比率如何随时间收敛时展开）
设
每一步都做同一件事：先算三个进程各自的"应得"，再用"实得 ÷ 应得"得到比率，选比率最小者运行 1 个单位。
| A 实得/应得 = 比率 | B 实得/应得 = 比率 | C 实得/应得 = 比率 | 选中 | |
|---|---|---|---|---|
| 6 | 4 / (6−0)/3 = 4/2 = 2.000 | 1 / (6−2)/3 = 1/(4/3) = 0.750 | 0 / (6−4)/3 = 0/(2/3) = 0.000 | C |
| 7 | 4 / (7/3) = 1.714 | 1 / (5/3) = 0.600 | 1 / 1 = 1.000 | B |
| 8 | 4 / (8/3) = 1.500 | 2 / 2 = 1.000 | 1 / (4/3) = 0.750 | C |
| 9 | 4 / 3 = 1.333 | 2 / (7/3) = 0.857 | 2 / (5/3) = 1.200 | B |
| 10 | 4 / (10/3) = 1.200 | 3 / (8/3) = 1.125 | 2 / 2 = 1.000 | C |
| 11 | 4 / (11/3) = 1.091 | 3 / 3 = 1.000 | 3 / (7/3) = 1.286 | B |
| 12 | 4 / 4 = 1.000 | 4 / (10/3) = 1.200 | 3 / (8/3) = 1.125 | A |
| 13 | 5 / (13/3) = 1.154 | 4 / (11/3) = 1.091 | 3 / 3 = 1.000 | C |
演算完成后累计获得的 CPU 时间为 A: 5、B: 4、C: 4。三处值得停下来看：
- t=6 时 A 的比率高达 2.000，此后连续 6 步都没被调度，直到 t=12 才轮到它。这就是"超额者暂缓"的实际形态：不是惩罚，只是让别人先把欠账补上。
- A 的比率从 2.000 一路降到 1.000，它什么也没做——分母随时间增长而分子不变。这正是保证调度的自我修正机制，也是它天然不饥饿的原因。
- 三个比率在收敛：从 (2.000, 0.750, 0.000) 逐步收拢到 (1.154, 1.091, 1.000)，这就是"每个进程约获得 1/n"这个承诺在时间上的兑现过程。
粒度说明：上表按 1 个时间单位重算一次，是最容易手算的粒度；教材给的规则是"让选中的进程一直运行，直到它的比率超过最接近它的那个进程"，粒度更粗、重算次数更少，但两者的选人依据（比率最小）完全一致。按题目给的粒度走即可。
二、公平分享调度算法
保证调度以进程为公平单位，但进程数是用户自己决定的：
系统中只有两个用户，用户 1 启动了 4 个进程 A、B、C、D，用户 2 只启动了 1 个进程 E。轮转调度让每个进程各轮一个时间片 ⇒ 每个进程拿到 1/5 ⇒ 用户 1 拿到 80%、用户 2 只拿到 20%。
对进程而言这非常公平，对用户 2 就明显不公平。公平分享调度因此改按用户分配份额，再用下面这条生成规则把"用户份额"翻译成"进程序列"：周期长
| RR | 公平分享调度 | |
|---|---|---|
| 轮转的对象 | 进程 | 用户（用户内部再对进程 RR） |
| 每一轮谁拿一片 | 每个进程各一片 | 每个用户按权重拿 |
| 一个用户的总份额 | 与他的进程数成正比 | 与他的进程数无关 |
| 是否带权 | 不带权 | 带权 |
第三行正是这个算法存在的理由：只有"总份额与进程数无关"，多开进程才占不到便宜。
三种权重下调度序列的逐周期生成（想自己推任意权重的序列时展开）
情形一：权重 1 : 1。
| 周期 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 用户 1 的那一片 | A | B | C | D |
| 用户 2 的那一片 | E | E | E | E |
两个用户各占 50%，而用户 1 的四个进程每人只有 12.5%。
情形二：权重 2 : 1。
| 周期 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 用户 1 的两片 | A B | C D | A B | C D |
| 用户 2 的一片 | E | E | E | E |
用户 1 占 2/3 ≈ 67%，用户 2 占 1/3 ≈ 33%。
情形三：权重 3 : 1（教材未给，用规则自己推）。
| 周期 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 用户 1 的三片 | A B C | D A B | C D A | B C D |
| 用户 2 的一片 | E | E | E | E |
一个完整循环长 16 个时间片，用户 1 占 12/16 = 75%，用户 2 占 4/16 = 25%，正是 3 : 1。注意用户 1 的四个进程需要 4 个周期才轮完一圈——这是"用户份额固定、内部再分"的必然结果：进程越多，每个进程分到的越少。
有了这条规则，给定任意权重都能自己把序列写出来，不必去记教材上那两串字母。
三、两种算法对比
| 特性 | 保证调度 | 公平分享调度 |
|---|---|---|
| 公平单位 | 进程 | 用户 |
| 分配依据 | 每个进程获得约 | 每个用户按权重获得 CPU 份额 |
| 判据（选谁） | 公平比率最小的进程 | 当前周期里份额还没发完的用户，其内部下一个待轮进程 |
| 需要维护什么 | 每个进程的已执行时间与创建时刻 | 每个用户的权重、已用份额，以及用户内部的轮转指针 |
| 会不会饥饿 | 不会——不被调度时比率自动下降，早晚成为最小 | 不会——每个周期每个用户都有份额 |
| 多开进程有没有用 | 有用（进程越多，该用户占的总份额越大） | 没用（用户总份额固定） |
| 适用场景 | 进程间公平 | 多用户系统中用户间公平 |
考点速记
- 公平调度换的是承诺的东西：前面七种算法承诺次序，它承诺份额。
- 保证调度为每个进程保证约
的处理机时间，靠公平比率 实际获得 应当获得选人，每次挑比率最小的。比率 表示系统亏欠它， 表示它已超额。 - ⚠️用比值而不用差值，是为了把欠账折算成相对于自身应得份额的比例——应得份额不同的进程之间，差值没法比。
- ⚠️它天然不饥饿、也不需要老化补丁：分母（应得时间）随时间单调增长，一个进程只要一直没跑，比率就会一直往下掉，早晚被选中。"老化"被内建进了比较键里。
- ⚠️对进程公平不等于对用户公平——进程数由用户自己决定，一个用户开 10 个进程就能拿走 10 份。
- 公平分享调度因此改按用户分配份额：周期长
，每周期用户 拿 个时间片，用户内部跨周期连续 RR。本质是按用户加权的 RR。
这一节在真题里被考过的形式：
公平调度至今不单独成题。 本页下方练习区渲染的是整个 cpu-scheduling-algorithm 标签下的 12 道题、由 8 篇算法共享，范围比本节宽，属正常。
它在大纲的"CPU 调度算法"条目下，不能跳过，但投入按"读懂即可"来定。 它的价值主要有两处：
第一，第四条那个"不饥饿"的机制值得单独理解。 前面的算法防饥饿都要外挂老化补丁 （优先级调度、MLFQ 都是），而公平调度把老化内建进了比较键—— 分母随时间单调增长，欠账自然会被补上。这是一种和"打补丁"完全不同的解法。
第二，第五条那个"对进程公平 ≠ 对用户公平"是理解调度目标的一处分辨点。调度的基本概念里说"公平不等于平均"， 这里给出了另一层：公平的对象是谁，本身就是一个要先定下来的问题。
复习优先级：读一遍即可，不必记公式。 记住"承诺份额而非次序""比率最小者先跑" "对进程公平不等于对用户公平"三句话就够。周期长
易错：认为公平调度也需要老化防饥饿。不需要——分母单调增长，老化已被内建进比较键。
易错：用差值而不是比值衡量欠账。应得份额不同的进程之间，差值没法比。
易错：认为对每个进程公平就是对每个用户公平。进程数由用户自己决定，开得多就拿得多。
易错：把公平调度当成一种"更好的 RR"。它换的是优化目标——从承诺次序变成承诺份额。
教材出处
- 汤小丹《计算机操作系统》3.3.6 基于公平原则的调度算法（保证调度的五个功能步骤与"调度比率最小的进程、让它一直运行到超过最接近它的进程比率为止"；公平分享调度的 80%/20% 问题与 1:1、2:1 两条强制调度序列），印刷 p96–p97
相关知识
多级反馈队列调度｜多处理机调度｜调度的基本概念与目标｜优先级调度