Appearance
公平调度算法
考情分析
公平调度算法以选择题形式偶有考查，重点在于理解"对进程公平"与"对用户公平"的区别。属于 🔥 低频考点。
之前的调度算法关注吞吐量、响应时间，但有一个问题被忽略了：如果一个用户开了 100 个进程，另一个用户只开了 1 个，按进程平分 CPU 对后者公平吗？
保证调度算法
前面介绍的调度算法主要关注响应时间、吞吐量或周转时间，但未将公平性作为核心目标。保证调度算法则为每个进程提供可量化的 CPU 时间分配保证。
核心思想
系统中有 n 个并发进程，每个进程应获得约 1/n 的 CPU 时间。
实现方式
- 跟踪每个进程自创建以来已获得的 CPU 时间
- 计算每个进程应获得的 CPU 时间（进程存在时间 / n）
- 计算公平比率 = 实际获得的 CPU 时间 / 应获得的 CPU 时间
- 调度公平比率最小的进程（即最"亏欠"的进程），让它运行直到比率超过最接近它的进程
| 公平比率 | 含义 |
|---|---|
| < 1 | 未达应得份额，优先调度 |
| > 1 | 超额占用，暂缓调度 |
公平分享调度算法
保证调度对进程公平，但未必对用户公平。
问题
假设用户 1 启动了 4 个进程，用户 2 只有 1 个进程。采用轮转调度（RR）：
- 每个进程都获得 1/5 的 CPU 时间（对进程公平）
- 但用户 1 获得 80% CPU 时间，用户 2 只获得 20%（对用户不公平）
解决方案
公平分享调度按用户（而非进程）分配 CPU 份额。不论用户启动多少进程，每个用户获得相同（或按比例）的 CPU 时间。
示例
用户 1 有进程 A、B、C、D，用户 2 有进程 E。
两个用户平均分配 CPU 时间：
调度序列: A E B E C E D E A E B E C E D E ...用户 1 和用户 2 各获得 50% 的 CPU 时间。
用户 1 获得用户 2 两倍的 CPU 时间：
调度序列: A B E C D E A B E C D E ...用户 1 获得约 67%，用户 2 获得约 33%。
两种算法对比
| 特性 | 保证调度 | 公平分享调度 |
|---|---|---|
| 公平单位 | 进程 | 用户 |
| 分配依据 | 每个进程获得 1/n CPU 时间 | 每个用户按权重获得 CPU 份额 |
| 适用场景 | 进程间公平 | 多用户系统中用户间公平 |
考研高频考点
- 🔥 保证调度：对进程公平，按公平比率（实际/应得）调度比率最小的进程
- 🔥 公平分享调度：对用户公平，按用户分配 CPU 份额，不因进程数不同而偏袒
到这里，各种调度算法的理论都介绍完了。下一篇通过调度算法对比模拟器，用同一组数据直观比较各算法的差异。