第 5 篇：调度——周转时间和响应时间不能同时最优

一、现在轮到"选谁"了

第 4 篇解决了怎么把 CPU 拿回来。拿回来之后还剩一个问题：下一个给谁？

这个问题看着简单，但它有个讨厌的性质：你没法说哪个答案是对的，因为"好"本身就有好几种互相打架的定义。

先把两个定义摆出来。假设作业在 0 时刻全部到达：

周转时间（turnaround）= 完成时刻 − 到达时刻。“我什么时候能拿到结果”——批处理、编译、跑数据的人关心这个。

响应时间（response）= 第一次跑起来的时刻 − 到达时刻。“我按下回车之后多久有动静”——用编辑器、点网页的人关心这个。

这一篇的全部内容就是：这两个指标会互相拆台。

打个比方

想象一个只有一个收银员的超市。

顾客就是作业，收银员就是 CPU。周转时间是"我从排上队到拎着袋子走出去用了多久"，响应时间是"收银员多久开始扫我的第一件商品"。

你马上能看出问题在哪：前面那位推着满满一车的大爷，会把后面所有只买一瓶水的人全堵在那儿。

这个画面接下来会一直用。

二、最笨的办法：先来先服务

FIFO：谁先来谁先跑，跑完为止。实现两行代码，谁都会。

它的问题在一句话里：一个大块头排在最前面，后面所有人都陪着。 这有个名字叫护航效应（convoy effect）——一长串小船跟在一艘大货轮后面，全被拖成了货轮的速度。

我们量一下它到底有多贵。三个作业：一个长的、两个短的，只换顺序：

# sched_lib.py —— 后面几个演示共用
import time
LONG, SHORT = 66_000_000, 10_000_000   # 在这台机器上约 2.0 秒 / 0.3 秒

def burn(n):
    """做固定的活儿：n 次加法。和有多少人跟你抢 CPU 无关。"""
    x = 0
    for i in range(n): x += i
    return x

# turnaround.py
import time
from sched_lib import burn, LONG, SHORT

def run_serial(jobs):
    start = time.time()
    return [(n, (burn(w), time.time() - start)[1]) for n, w in jobs]

for label, jobs in [
    ("A. 长作业排在最前（FIFO 撞上一个大块头）",
     [("长作业", LONG), ("短作业1", SHORT), ("短作业2", SHORT)]),
    ("B. 短作业排在最前（SJF）",
     [("短作业1", SHORT), ("短作业2", SHORT), ("长作业", LONG)]),
]:
    res = run_serial(jobs)
    print(label)
    for n, t in res:
        print(f"    {n:8s} 周转 {t:5.2f} 秒")
    print(f"    ---- 平均周转 {sum(t for _, t in res)/len(res):.2f} 秒\n")

A. 长作业排在最前（FIFO 撞上一个大块头）
    长作业      周转  0.77 秒
    短作业1     周转  0.89 秒
    短作业2     周转  1.01 秒
    ---- 平均周转 0.89 秒

B. 短作业排在最前（SJF）
    短作业1     周转  0.12 秒
    短作业2     周转  0.23 秒
    长作业      周转  1.00 秒
    ---- 平均周转 0.45 秒

⭐ 总活儿一点没变，只换了顺序，平均周转从 0.89 降到 0.45——少了一半。

（绝对秒数每次跑都会浮动，看比例就行。）

这个"短的先跑"的策略叫 SJF（Shortest Job First，最短作业优先）。而且它不只是"比较好"——在所有作业同时到达的前提下，SJF 的平均周转时间是理论最优的，没有任何策略能更低。

道理很直白：把一个作业往前挪一位，它自己省下的时间，等于它后面每个人多等的时间之和。所以应该让"让别人等得最少"的那个先走——也就是最短的那个。

三、可惜 SJF 用不了

最优策略，两个致命伤。

伤一：它要求你知道每个作业要跑多久。 你不知道。收银员看不见顾客车里到底有多少件东西，操作系统也看不见一个程序要跑多久——那等价于停机问题。

伤二：作业不是同时到达的。 短作业 2 秒后才来，这时候长作业已经跑上了，你还是得等。

伤二有个补丁：抢占。第 4 篇刚给了你这个能力。新来一个作业时，比一比"新来的总时长"和"当前这个还剩多久"，谁短谁上。这叫 STCF（Shortest Time-to-Completion First），是 SJF 的抢占版，平均周转最优。

但伤一治不了。所有基于"作业要跑多久"的策略，都卡死在这一条上。

⚠️ 这是这门课里第一次遇到**“最优解已知，但用不了”**。后面还会遇到好几次——第 15 篇的页面置换里，最优算法要求知道未来哪一页最晚被用；那也用不了。这类地方的正确读法是：把最优解当尺子，用来量你实际用的那个差多远。

四、换个指标看，SJF 也不好

就算你真的能预知未来，SJF 还有个更根本的毛病：它对交互式程序糟透了。

一个长作业跑起来，你在编辑器里敲一个字——按 SJF 你得等它跑完。两秒。你的编辑器卡两秒。

这就是响应时间这个指标存在的理由。而对付它的办法很简单粗暴：别让任何人跑太久，到点就换。 这叫时间片轮转（Round Robin，RR）。

# response.py
import os, sys, time
from sched_lib import burn, LONG, SHORT

JOBS = [("作业A(长)", LONG), ("作业B(短)", SHORT), ("作业C(短)", SHORT)]

print("场景一：FIFO —— 一个跑完再跑下一个")
start = time.time()
for name, w in JOBS:
    print(f"    {name} 首次拿到 CPU：{time.time()-start:5.2f}s", flush=True)
    burn(w)
    print(f"    {name} 跑完：        {time.time()-start:5.2f}s", flush=True)

print("\n场景二：三个同时上 —— 只有一个核，由内核轮转")
sys.stdout.flush()                      # fork 之前必须清空缓冲区
start = time.time()
for name, w in JOBS:
    if os.fork() == 0:
        os.write(1, f"    {name} 首次拿到 CPU：{time.time()-start:5.2f}s\n".encode())
        burn(w)
        os.write(1, f"    {name} 跑完：        {time.time()-start:5.2f}s\n".encode())
        os._exit(0)
for _ in JOBS:
    os.wait()

场景一：FIFO —— 一个跑完再跑下一个
    作业A(长) 首次拿到 CPU： 0.00s
    作业A(长) 跑完：         0.91s
    作业B(短) 首次拿到 CPU： 0.91s
    作业B(短) 跑完：         1.04s
    作业C(短) 首次拿到 CPU： 1.04s
    作业C(短) 跑完：         1.16s

场景二：三个同时上 —— 只有一个核，由内核轮转
    作业A(长) 首次拿到 CPU： 0.00s
    作业B(短) 首次拿到 CPU： 0.00s
    作业C(短) 首次拿到 CPU： 0.00s
    作业C(短) 跑完：         0.44s
    作业B(短) 跑完：         0.45s
    作业A(长) 跑完：         1.27s

把三个策略的账并排算一下（用各自演示里的真实数字）：

⭐ RR 的响应时间是三者最好的（0.00），周转时间却比 SJF 差了六成。 这不是实现得不好，是必然的：RR 把每个作业都撕成很多片穿插着跑，结果是几乎所有作业都在接近末尾才完成。

看那个长作业：FIFO 里它 0.91 秒就跑完了，RR 里拖到 1.27 秒。它的时间被切给别人了。

回到超市：RR 就是规定每人只结十件商品，然后回队尾重排。 买一瓶水的人马上被服务到了（响应好），但推整车的大爷要来回排七八趟，总时长反而更久——而且收银员每次重新开始都要再拿一次扫码枪（这就是切换开销）。

五、⭐ 这不是实现问题，是结构性的

把上面这张表读第二遍。

周转时间要求"让一件事从头做到尾，别打断"。响应时间要求"每件事都尽早开始，多打断几次"。 这两句话是直接矛盾的。任何调度器都得在这条线上选一个位置站。

所以调度这件事没有标准答案，只有"你在乎哪个"：

• 跑一夜的批处理集群 → 在乎周转，时间片可以很长，甚至不抢占。
• 你的笔记本 → 在乎响应，宁可总吞吐低一点。
• 音视频、工业控制 → 在乎的是最坏情况的响应时间，宁可平均值差一点也不能有长尾。

时间片多长

时间片是这条线上的旋钮：

• 太短 → 响应好，但切换太频繁。第 4 篇算过，每次切换的显性开销是几百纳秒，隐性开销（缓存和 TLB 变冷）更大。时间片 1 毫秒、切换开销 0.1 毫秒，你有 10% 的 CPU 花在换人上。
• 太长 → 切换开销摊薄了，但退化成 FIFO，响应变差。

经验值在几毫秒到几十毫秒之间。Linux 现在的做法更聪明一点——不给固定值，而是用一个"目标延迟"除以当前可运行进程数，进程越多片越短，但不低于一个下限。这是第 7 篇。

六、还有一件事：I/O

上面所有讨论都假设作业只用 CPU。真实作业会阻塞（第 2 篇那条边）。

一个作业发起磁盘读，它就进了阻塞态，几毫秒内用不上 CPU。这几毫秒必须给别人，否则 CPU 空转。

所以真实调度器把每个作业的 CPU 阶段拆开来看：一个"算 10 毫秒 → 读盘 → 算 10 毫秒 → 读盘"的作业，被当成一串 10 毫秒的小作业。这样一来，它天然就是"短作业"，天然该被优先——而这恰好让交互式程序（大量等待、少量计算）自动获得高优先级。

⭐ 这个观察是下一篇的全部起点：既然你没法预知作业要跑多久，那就看它过去的行为。 一个总是很快就让出 CPU 的作业，多半下次也一样。

七、小结

• 有了抢占之后，问题变成"选谁"。而"好"至少有两个互相打架的定义：周转时间和响应时间。
• FIFO 简单，但一个大块头会把后面全堵住（护航效应）。实测：同样的活儿，只换顺序，平均周转 0.89 → 0.45。
• SJF/STCF 的平均周转是理论最优，但它要求预知每个作业要跑多久——做不到，等价于停机问题。⚠️ 遇到"最优但用不了"的算法，把它当尺子用。
• RR 把响应时间压到 0.00，代价是平均周转变差六成。这是结构性的，不是实现问题：周转要求别打断，响应要求多打断。
• 时间片是这条线上的旋钮。太短则切换开销吃掉 CPU，太长则退化成 FIFO。
• I/O 阻塞让"交互式程序天然是短作业"，这是下一篇的起点：预知不了未来，就观察过去。

思考题

1. 第二节说 SJF 在"同时到达"下平均周转最优。用一个反例说明：如果作业不是同时到达，SJF 可能输给 STCF 多少？
2. 第四节表里，RR 的响应时间是 0.00 秒。这个数字是不是有点太好看了？想想它为什么会是 0.00，而在只有一个核的真实系统里理论上应该是多少。
3. 假设你要给一个跑机器学习训练的集群写调度器，任务全是长作业、没有人盯着屏幕。你会把时间片设多长？为什么？
4. 超市那个比方里，“预知不了作业要跑多久"对应"收银员看不见车里有多少件”。那超市其实是怎么解决这个问题的？（提示：想想"十件以下快速通道"，它凭什么知道？）这个办法能不能搬到操作系统里？

延伸

• 上一篇：第 4 篇：受限直接执行——内核怎么把控制权拿回来
• 下一篇：第 6 篇：多级反馈队列——不问你是谁，只看你干过什么