| 配套 | 第 5 篇：调度、第 6 篇：MLFQ、第 7 篇：CFS |
| 语言 | Python 3 |
| 验收 | ⭐ 第二部分由 Linux 内核裁判：你的模型预测的份额，要和 /proc/<pid>/sched 里的实际数字对得上 |
这个实验的重点在第二部分
调度策略没法用"跑通了"来验收——它是策略，不是机制。所以这个实验分两段：
- 第一部分：写模拟器。它只验证你把算法理解对了。
- ⭐ 第二部分：用同样的负载去问真实的 Linux，看你的模型和内核的实际行为差多少。
第二部分才是重点。 模型和现实对不上的地方，就是你还没理解的地方。
环境
docker run --rm -it --cpuset-cpus=0 -v "$PWD:/lab" -w /lab oslab bash
⚠️ --cpuset-cpus=0 限定一个核。多核会让所有对照实验的结果失去意义。
第一部分：模拟器
输入格式
# 每个作业：(名字, 到达时刻, 需要的 CPU 时间)
JOBS = [("A", 0, 10), ("B", 0, 3), ("C", 0, 3)]
起步骨架
def simulate(jobs, policy, quantum=1):
"""返回 [(名字, 首次运行时刻, 完成时刻), ...]"""
...
def report(name, result, jobs):
arrive = {n: a for n, a, _ in jobs}
turn = [(f - arrive[n]) for n, s, f in result]
resp = [(s - arrive[n]) for n, s, f in result]
print(f" {name:<8} 平均周转 {sum(turn)/len(turn):6.2f} 平均响应 {sum(resp)/len(resp):6.2f}")
要实现的策略
- FIFO——按到达顺序，跑完为止。
- SJF——同时到达的里挑最短的。
- STCF——抢占版：新作业到达时比一比剩余时间。
- RR——时间片轮转，
quantum可调。 - ⭐ CFS——每个作业一个
vruntime，每次选最小的跑一个时间片，跑完vruntime += 时间片 × 1024/权重。
自查（不用我给答案，你自己就能验）
- ⭐ 在所有作业同时到达的情况下，SJF 的平均周转必须是所有策略里最小的。 这是第 5 篇给的定理，你的模拟器要能验证它——跑一百组随机作业，如果有任何一组 SJF 输了，那是你的实现错了。
- RR 的平均响应必须最小，而且
quantum越小它越小。 - 权重全相同时，CFS 的行为应该和 RR 非常接近。 对不上就是 vruntime 更新写错了。
⭐ 第二部分：和真实内核对照
实验 A：nice 值的实际比例
第 7 篇实测过 nice=0 和 nice=19 的 vruntime 倍率是 68.3，而公式是 1024/15 = 68.27。
你的任务：把整张权重表验证一遍。
内核里 nice 值到权重的表大致是这样（相邻两档比值约 1.25）：
nice 0 → 1024 nice 5 → 335 nice 10 → 110
nice 1 → 820 nice 10 → 110 nice 15 → 36
nice 3 → 526 nice 15 → 36 nice 19 → 15
写一个程序：起两个死循环进程，nice 分别设成 0 和 N，跑 3 秒，从 /proc/<pid>/sched 读 se.sum_exec_runtime，算出实际的 CPU 份额比。
def sched_field(pid, key):
for line in open(f"/proc/{pid}/sched"):
if line.startswith(key):
return float(line.split(":")[1])
验收： 对 N ∈ {1, 3, 5, 10, 15, 19}，实测比值和 1024/weight[N] 的相对误差应当在 10% 以内。
⚠️ 如果差得远，先检查三件事：是不是真的只有一个核？两个进程是不是同时启动的？有没有别的东西在抢 CPU？
实验 B：交互型进程的待遇
重现第 6 篇那个实验，然后扩展它：
- 让"交互型"进程的睡眠时间从 1 毫秒变到 100 毫秒，各测一遍唤醒延迟。
- 画出（或列出）延迟随睡眠时间的变化。
要回答的问题： ⭐ 睡得越久，醒来时的优先级越高吗？还是有个上限？ 用你的数据说话，并解释为什么内核要设这个上限。
实验 C：找出模拟器错在哪
用同样的三个作业（一个长两个短），分别：
- 在你的模拟器里跑 RR，记下平均周转和响应。
- 在真实 Linux 上跑（三个进程同时启动，固定工作量），记下实际的完成时刻。
它们不会一致。你的任务是解释每一处差异。 至少有这几个来源：
- 切换开销——模拟器假设切换免费。
- CFS 不是纯 RR——时间片是动态算的（第 7 篇第三节）。
- 进程启动本身要时间——
fork+ Python 解释器启动。 - 别的进程也在跑——你的 shell、内核线程。
⭐ 把每一项的量级估出来，看看能不能凑出观察到的差值。 凑不上的那部分，就是你还没想到的机制。
交上来的东西
- 模拟器代码 + 五种策略的对比表。
- 实验 A 的表：nice 值、公式预测比、实测比、相对误差。
- 实验 B 的数据和你对"上限"的解释。
- ⭐ 实验 C 的差异分析——这一项最重要，也最能看出你是不是真懂了。