一、主循环只有四步

第一步，推进 IO。所有在等 IO 的进程，剩余等待时间减一。这一步与调谁跑无关，永远要做。 第二步，挑人。从【没跑完、也没在等 IO】的进程里，按策略挑出 ncpu 个。 第三步，跑一拍。被挑中的进程剩余 CPU 时间减一；如果它跑满了自己的 IO 间隔，就转入 IO 等待。 第四步，判完。剩余时间归零的，记下完成时刻。 四步循环，直到全跑完或超出观察窗口。

二、为什么用【离散时间】而不是真时钟

因为要可复现。真时钟跑两次结果不一样；离散的拍跑一百次结果完全一致。 代价是把时间抹平了：真实系统里每拍的耗时不一样（缓存命中不同），模型里每拍一样长。但这不影响我们看【结构性的差别】。 这条权衡值得记住：模拟换的是精度，买的是可复现。凡是【规律性】的问题，模拟都能答；凡是【绝对值】的问题，模拟答不了。

三、代码里的三个设计决定

一、IO 按拍推进，不按事件。简单，但要求拍长足够细。细到 1 拍，误差就够小了。 二、时间片用【取整除法】算起点，(t // quantum)——保证每 quantum 拍换一批人。这是实现轮转最省事的写法。 三、切换次数单独统计：每次被挑中的人跟上一拍不一样，就记一次。有这个计数器，才能把【切换的代价】变成可量的数。

四、三十行代码能答什么，不能答什么

能答：时间片变大变小对吞吐与延迟的影响（4.10）、多核能带来多少加速（4.12~4.15）、优先级怎么改变分配比例（4.20）。 不能答：真实系统里一个上下文切换到底多少微秒（那要真机量）、缓存带来的差异（模型里没有缓存）、调度器内部那些精细的启发式。 知道边界在哪，才不会把结论用过头。

五、动手 Demo：最小实现——一个只有三个要素的调度器

下面这个模拟器一共三十行左右，跑的是三个各 6 拍的进程、一个 CPU、时间片 2。 先看时间线（谁在 CPU 上），再看三个数字（跑完用多久、平均周转、切换几次）。

class Proc:
    def __init__(self, name, cpu, io_each=0, io_len=0):
        self.name, self.remain = name, cpu
        self.io_each, self.io_len = io_each, io_len
        self.since_io = self.io_left = 0
        self.done_at = None

def run(procs, quantum, ncpu=1):
    t = 0
    while any(p.remain > 0 for p in procs):
        for p in procs:                       # ① 推进 IO
            if p.io_left > 0:
                p.io_left -= 1
        ready = [p for p in procs if p.remain > 0 and p.io_left == 0]
        for i in range(ncpu):                 # ② 挑人
            cur = ready[(t // quantum * ncpu + i) % len(ready)]
            cur.remain -= 1                   # ③ 跑一拍
            cur.since_io += 1
            if cur.io_each and cur.since_io >= cur.io_each:
                cur.io_left, cur.since_io = cur.io_len, 0
            if cur.remain == 0:               # ④ 判完
                cur.done_at = t + 1
        t += 1
    return t

实跑输出：

--------------------------------------------------------------------
最小实现——一个只有三个要素的调度器
--------------------------------------------------------------------
① 三个各 6 拍的进程，一个 CPU，时间片 2

      tick    CPU 上是谁
      --------------------------
      0       A
      1       A
      2       B
      3       B
      4       C
      5       C
      6       A
      7       A
      8       B
      9       B
      10      C
      11      C

      跑完用了                    18 拍
      完成个数                    3 个
      平均周转                    16.0 拍
      上下文切换                  8 次

  **三个进程干的是同样多的活（各 6 拍），所以合计必然 18 拍。**
  **时间片 2 让它们轮流跑**——这正是【分时】最朴素的样子。

② 时间片放大到 6 会怎样

  时间片     跑完用     平均周转     切换次数
  --------------------------------------------
  2          18         16.0         8
  6          18         12.0         2

  **总时间没变（活儿就那么多），变的是【平均周转】与【切换次数】。**
  **时间片越大，切换越少、但单件事等得越久——这个取舍就是 4.10 的正题。**

时间线是 A A B B C C A A …——时间片 2 让它轮流跑。这一列就是【分时】这两个字的全部内容。 三个各 6 拍，合计必然 18 拍——活儿的总量决定了总时间，调度改不了这一点。 时间片从 2 放大到 6，总时间还是 18 拍，但平均周转从 16.0 降到 12.0、切换从 8 次降到 2 次。 这就是后面九节要拆的账：总时间不可改，能改的只有【谁等多久】与【换人多少次】。

30 秒实验

1. 把 quantum 改成 1，看时间线变成什么（提示：每个 tick 都换人）。
2. 把三个进程改成 4、8、12 拍，看平均周转怎么变。
3. 把 ncpu 改成 2，看时间线一行里出现两个名字——这就是【两个核】的样子。

常见误区

1. 【调度器能让总时间变短】。总时间由活儿的总量与机器的能力决定。调度改的是分配方式，不是产能。
2. 【模拟时间线就是真实进程的调度过程】。真实系统里进程会被中断、会被优先级抢占、会被迁移到别的核。模型只保留了骨架。
3. 【代码这么短，肯定不准】。它的用途是看规律不是看绝对值。能用一个下午写出来的模型，往往比一套搭三个月的平台更能说明问题。

• ☐ 4.3 实验

相关笔记

• 关于实验程序的设计 — 设计那三问
• 实验 — 跑起来看时间线
• 吞吐量与延迟 — 这一章的正题
• 🐧 Linux是怎样工作的 · 索引