Erlang 的调度器：它是怎么决定"跑什么、什么时候跑"的

本文基于 The BEAM Book: Understanding the Erlang Runtime System（Erik Stenman，2025 版）第 10 章 "Scheduling"。
原书对应印刷页 116–126（PDF 页 117–127）。

要理解 ERTS 系统里时间花在了哪里，就得先理解它决定哪段 Erlang 代码去跑、什么时候去跑的机制。这些决策是由调度器（Scheduler）做出的。调度器也负责系统的实时性保证。不过这里要澄清一个概念：在严格的计算机科学定义里，"实时系统"必须能在指定时间内保证响应，也就是有真实的截止期限（deadline），每个任务都要在截止期前完成。而 Erlang 并没有这种保证——Erlang 里的 timeout 只保证"不会早于设定时间触发"，它可能比预期晚一些才真正执行。

在一个像 Erlang 这样要处理各种程序和负载的通用系统里，调度器不得不做出一些折中。总会有某些极端情况（corner cases）让一个通用调度器表现得不理想。读完这一章后，你会更深层地理解 Erlang 调度器的工作方式，尤其是它在什么情况下可能无法达到最优。你应当能够设计系统来避开这些极端情况，并且能够分析一个表现异常的调度系统。

10.1 并发、并行与抢占式多任务

Erlang 是一门并发语言。当我们说进程"并发运行"时，意思是：从一个外部观察者的角度看，两个进程看起来在同时执行。在单核系统上，这靠的是抢占式多任务（preemptive multitasking）——一个进程先运行一段时间，然后虚拟机的调度器把它挂起（suspend），让另一个进程去跑。

而在多核或分布式系统里，我们可以实现真正的并行（parallelism），也就是两个或多个进程在同一时刻真的同时在执行。在启用了 SMP（对称多处理）的模拟器里，系统会用多个 OS 线程来间接执行 Erlang 进程——每个线程运行一个独立的调度器和 emulator。在 ERTS 默认设置下，每个启用的核（物理核或超线程）对应一个线程。

我们可以检查系统是否支持并行执行：

1> :erlang.system_info(smp_support).
true

也可以查看系统当前有多少个调度器在线：

1> :erlang.system_info(schedulers_online).
4

在 Observer 里也能看到这些信息。如果我们启动的进程数量超过调度器数量，并让它们做一些"忙活"（busy work），就能看到一部分进程在并行运行，另一部分进程"可运行但当前没在跑"。用 erlang:process_info/2 就能观察到这一点：

1> Loop = fun (0, _) -> ok; (N, F) -> F(N-1, F) end,
   BusyFun = fun() -> spawn(fun () -> Loop(1000000, Loop) end) end,
   SpawnThem = fun(N) -> [ BusyFun() || _ <- lists:seq(1, N)] end,
   GetStatus = fun() -> lists:sort([{erlang:process_info(P, [status]), P}
                        || P <- erlang:processes()]) end,
   RunThem = fun (N) -> SpawnThem(N), GetStatus() end,
   RunThem(8).

[{[{status,garbage_collecting}],<0.62.0>},
 {[{status,garbage_collecting}],<0.66.0>},
 {[{status,runnable}],<0.60.0>},
 {[{status,runnable}],<0.61.0>},
 {[{status,runnable}],<0.63.0>},
 {[{status,runnable}],<0.65.0>},
 {[{status,runnable}],<0.67.0>},
 {[{status,running}],<0.58.0>},
 {[{status,running}],<0.64.0>},
 {[{status,waiting}],<0.0.0>},
 {[{status,waiting}],<0.1.0>},

...

本章后面会详细讲进程的各种状态。现在只需要知道：一个处于 running 或 garbage_collecting 状态的进程，是真的在某个调度器上跑着的。因为示例机器有 4 个核、4 个调度器，所以有 4 个进程在并行运行（shell 进程加 3 个忙进程）。另外还有 5 个忙进程处于 runnable 状态，在等待执行。

在 Observer 的 Load Charts 标签页里，可以看到忙进程执行期间，4 个调度器都处于满载状态。

2> observer:start().
ok
3> RunThem(8).

10.2 ERTS 中的抢占式多任务

Erlang 层面的抢占式多任务，实际上是通过 C 层面的协作式多任务（cooperative multitasking）实现的。Erlang 语言、编译器和虚拟机三者协作，以确保一个 Erlang 进程的执行会在有限时间内让出，从而让下一个进程运行。用来测量和限制允许执行时间的这项技术，叫做规约计数（reduction counting），稍后会详细展开。

10.3 Reductions（规约）

可以把 BEAM 里的调度描述为：协作式调度之上的抢占式调度。一个进程只能在执行的特定点被挂起，比如在 receive 处或函数调用处。从这个意义上说，调度是协作式的——进程必须执行"允许被暂停"的代码。

Erlang 代码的特性使得一个进程几乎不可能在不进行函数调用的情况下运行很久。不过仍有少数内置函数（BIF）可能在不让出的情况下花掉很长时间。此外，如果你在实现不当的本地实现函数（NIF）里调用 C 代码，可能会把一个调度器阻塞很长时间（如何写表现良好的 NIF，见第 16 章）。

由于除了递归和列表推导式之外没有其他循环结构，不做函数调用就不可能无限循环。每个函数调用都被计为一个 reduction；当进程的 reduction 限制达到时，它就被暂停。

术语来源：reduction 这个词来自 Erlang 的 Prolog 血统。在 Prolog 中，每个执行步骤都是一个"目标化简"（goal-reduction）——每个步骤把一个逻辑问题化简为它的组成部分，然后尝试求解每个部分。

10.3.1 你能得到多少 reductions？

当一个进程被调度时，它会获得一个由 CONTEXT_REDS 定义的规约数（定义在 erl_vm.h 中，当前值为 4000）。用完了它的规约，或者在收件箱里没有匹配消息时做 receive，进程就会被挂起，一个新的进程被调度。

注：在 OTP-20.0 之前，CONTEXT_REDS 的值是 2000。

如果 VM 已经执行了 INPUT_REDUCTIONS 定义的规约数量（当前为 2×CONTEXT_REDS，同样定义在 erl_vm.h 中），或者没有可运行的进程，调度器就会进行系统级活动——基本上是检查 IO（细节稍后展开）。

10.3.2 reduction 到底是什么？

"reduction" 并没有一个完全明确的定义，但至少每个函数调用都应该计为一个 reduction。当谈到 BIF 和 NIF 时情况就复杂了。

一个进程不应该能够"运行很久"而不用掉一个 reduction 并让出。用 C 写的函数不能在中途让出，它必须确保自己处于干净状态并返回。为了可重入（re-entrant），它必须在返回前以某种方式保存内部状态，然后在重新进入时重新建立状态。这会非常昂贵，尤其对于那些"有时只做一点点活、有时做很多活"的函数。用 C 写函数而不是 Erlang 的原因通常是追求性能、避免不必要的簿记工作。

由于除了 Erlang 层面的函数调用之外没有清晰的"一个 reduction 是什么"的定义，存在这样的风险：用 C 实现的函数每个 reduction 消耗的时钟周期可能远多于普通 Erlang 函数。这会导致调度器失衡，甚至进程饥饿（starvation）。

例如，在 R16 之前的 Erlang 版本中，BIF binary_to_term/1 和 term_to_binary/1 是不让出的，只算作一个 reduction。这意味着对大型 term 调用这些函数的进程，可能让其他进程饿死。这在 SMP 系统下也可能发生，原因是进程在调度器之间是平衡的（稍后会讲到）。

当进程在运行时，emulator 在（寄存器映射的）变量 FCALLS（见 beam_emu.c）中保存剩余要执行的规约数。reds 字段记录进程自上次被挂起以来已执行的总 reduction 数。通过监控这个数字，你可以看到哪些进程做了最多的工作。

你可以通过调用 erlang:process_info/2 并把原子 reductions 作为第二个参数，查看一个进程的总 reduction 数（reds 字段）。你也能在 Observer 的 process 标签页里看到，或者在 Erlang shell 里用 i/0 命令看到。

如前所述，每次进程启动时，fcalls 字段被设为 CONTEXT_REDS 的值；进程每执行一个函数调用，fcalls 减 1。当进程被挂起时，reds 字段增加已执行的规约数。在一些类 C 的代码里，类似：

p->reds += (CONTEXT_REDS - p->fcalls)

通常一个进程会做完它分配的所有规约，此时 fcalls 为 0；但如果进程在 receive 中挂起等待消息，它还会剩下一部分规约。

当一个进程用完所有规约时，它会让出，让另一个进程运行：它会从 running 状态转到 runnable 状态；如果它是在 receive 中让出的，则进入 waiting（等待消息）状态。下一节我们看进程能处于的所有不同状态。

10.4 进程状态（Process State）

PCB 中的 status 字段保存进程状态，可以是：free、runnable、waiting、running、exiting、garbing、suspended。

  • free：进程退出时被标记为 free。你永远不应该能看到处于此状态的进程——这是一个短暂状态，对系统其余部分而言进程已不存在，但仍有一些清理工作（释放内存和其他资源）。
  • running：进程当前正在某个调度器上执行代码。
  • waiting：进程进入 receive 且消息队列中没有匹配消息时，变为 waiting，直到消息到达或超时。
  • runnable：进程用完所有 reductions 后变为 runnable，等待调度器再次拾取它。一个 waiting 进程收到消息或超时后，会变为 runnable。
  • garbing：进程需要做垃圾回收时进入 garbing 状态，直到 GC 完成。做 GC 时它把旧状态保存在 gcstatus 字段，完成后用 gcstatus 把状态恢复回去。
  • suspended：仅用于调试。你可以在另一个进程上调用 erlang:suspend_process/2 强制它进入 suspended 状态。每次一个进程对另一个进程调用 suspend_process，suspend count 就加 1，记录在 rcount 字段中。挂起进程调用 erlang:resume_process/1 会使 suspend count 减 1。一个处于 suspend 状态的进程，直到 suspend count 归零才会离开该状态。
  • rstatus（恢复状态）：跟踪进程挂起前的状态。如果挂起前是 running 或 runnable，恢复时以 runnable 启动；如果是 waiting，则回到等待队列。一个 suspended 的 waiting 进程收到超时后，rstatus 被设为 runnable，于是以 runnable 状态恢复。

每个进程状态都是进程状态机（Process State Machine）中的一个状态。超时、消息投递等事件会触发状态机边上的转换。

原书此处有一张"Figure 25. Process State Machine"图（见 ch10-figures/fig25-process-state-machine.png）。

进程的常规状态是 runnable、waiting、running。

10.5 进程队列

调度器的主要工作是维护工作队列——也就是进程和端口的队列。调度器必须处理两种进程状态：runnable 和 waiting。等待接收消息的进程处于 waiting 状态。当一个 waiting 进程收到消息时，发送操作会触发接收进程移动到 runnable 状态。如果 receive 语句带超时，调度器必须在超时时触发状态转换到 runnable。

10.5.1 就绪队列（The Ready Queue）

处于 runnable 状态的进程被放入调度器处理的一个 FIFO（先进先出） 队列，称为就绪队列。该队列由 first 指针和 last 指针实现，以及每个参与进程 PCB 中的 next 指针。

  • 新增进程时，跟随 last 指针，以 O(1) 操作把进程加到队列末尾。
  • 新进程被调度时，它只是从队列头部（first 指针）弹出。
First: -->  P5       +---> P3       +-+-> P17
            next: ---+     next: ---+ |  next: NULL
                                      |
Last: --------------------------------+

在 SMP 系统（多个调度器线程）中，每个调度器有一个队列：

Scheduler 1       Scheduler 2      Scheduler 3      Scheduler 4

Ready: P5         Ready: P1        Ready: P7        Ready: P9
       P3                P4               P12
       P17                                P10

优先级让事情更复杂：Erlang 进程有优先级，每个调度器实际上有三个队列——一个 max 优先级、一个 high 优先级、一个包含 normal 和 low 优先级的队列。

Scheduler 1       Scheduler 2      Scheduler 3      Scheduler 4

Max:    P5        Max:             Max:             Max:
High:             High:  P1        High:            High:
Normal: P3        Ready: P4        Ready: P7        Ready: P9
        P17                               P12
                                          P10

调度规则：

  1. 如果 max 队列有进程，调度器选这些进程执行；
  2. 如果 max 为空但 high 队列有进程，选 high 的进程；
  3. 只有 max 和 high 都为空时，才从 normal/low 队列选第一个进程。

优先级与调度计数（schedule count）：

  • normal 进程：schedule count = 1
  • low 优先级进程：schedule count = 8

当进程从队列头部被选中时，schedule count 减 1；若计数归零则被调度，否则被插回队列末尾。也就是说，低优先级进程要绕队列 7 次才被调度。

10.5.2 等待、超时与时间轮（Waiting, Timeouts and the Timing Wheel）

一个进程对空邮箱、或没有匹配消息的邮箱做 receive 时，会 yield（让出）并进入 waiting 状态。

当消息被投递到收件箱时，发送进程会检查接收者是否正在 waiting 状态休眠；如果是，就唤醒进程，把状态改为 runnable，并放到相应就绪队列的末尾。

如果 receive 语句带超时子句，会为进程创建一个计时器，在指定超时时间后触发。运行时系统对超时的唯一保证是：它不会在设定时间之前触发——进程被调度并获得执行机会之前，可能会晚一些。

计时器由 VM 中的时间轮（timing wheel）处理——一个不断环绕的时间槽数组。在 Erlang 18 之前，时间轮是全局资源，很多进程插入计时器时写锁可能有竞争。如果你大量使用计时器，请确保使用较新的 Erlang 版本。

时间轮配置：

  • 默认大小 TIW_SIZE：65536 个槽位（为小内存构建的系统则是 8192 槽位）。
  • 当前时间由数组索引 tiw_pos 指示。
  • 超时为 T 的计时器插入到槽位 (tiw_pos + T) % TIW_SIZE。
  0 1                                      65535
 +-+-+- ... +-+-+-+-+-+-+-+-+-+-+-+ ... +-+-----+
 | | |      | | | | | | |t| | | | |     | |     |
 +-+-+- ... +-+-+-+-+-+-+-+-+-+-+-+ ... +-+-----+
              ^           ^                       ^
              |           |                       |
           tiw_pos     tiw_pos+T               TIW_SIZE

多个计时器插入同一槽位时，会通过 prev 和 next 字段链接成链表，count 字段设为 T/TIW_SIZE。

时间轮里存的是指向 ErlTimer 结构体的指针（见 erl_time.h）：

/*
** Timer entry:
*/
typedef struct erl_timer {
    struct erl_timer* next; /* next entry tiw slot or chain */
    struct erl_timer* prev; /* prev entry tiw slot or chain */
    Uint slot;          /* slot in timer wheel */
    Uint count;         /* number of loops remaining */
    int    active;      /* 1=activated, 0=deactivated */
    /* called when timeout */
    void (*timeout)(void*);
    /* called when cancel (may be NULL) */
    void (*cancel)(void*);
    void* arg;        /* argument to timeout/cancel procs */
} ErlTimer;

10.6 端口（Ports）

一个端口（port）是 Erlang 虚拟机外部通信点的抽象。与 socket、管道、文件 IO 的所有通信，在 Erlang 侧都通过端口进行。

端口和进程一样，是在与创建进程相同的调度器上创建的。和进程一样，端口也用 reductions 决定何时让出，也能运行 4000 个 reduction。但由于端口不运行 Erlang 代码，没有 Erlang 函数调用来计为 reduction；而是每个端口任务被计为一定数量的 reduction。目前，一个任务使用略多于 200 个 reduction，外加与传输数据大小相关的 reduction（每千字节对应一部分）。

一个端口任务是一次对端口的操作，比如打开、关闭、发送若干字节或接收数据。要执行一个端口任务，执行线程必须对端口加锁。

端口任务在每次调度器循环迭代中、在挑选新进程之前被调度和执行。

10.7 / 10.8 调度器循环（The Scheduler Loop）

原书说明：10.7 和 10.8 标题相同，开篇三段一字不差，区别是 10.8 给每一步加了说明。这看起来是排版上的重复，本文合并为一节。

概念上，调度器像是 Erlang VM 里程序执行的驱动。但实际从 C 代码结构看，是模拟器（beam_emu.c 中的 process_main）在驱动执行，它把调度器当作一个子程序（subroutine）来找下一个要执行的进程。

我们这里假装是反过来的（调度器选进程、把执行权交给模拟器），因为这形成一个不错的调度器循环概念模型。

调度器循环如下：

  1. 更新 reduction 计数器——每个进程被分配一定数量的规约（执行的小单位）。当计数超过限制时，该进程被抢占，另一个进程被调度。
  2. 检查定时器——定时器（如 receive ... after）通过时间轮检查。如果超时已过期，相关进程被移到就绪队列。
  3. 必要时检查平衡——系统偶尔检查某些调度器线程是否过载；若是，做出负载平衡决策。
  4. 必要时迁移进程和端口——进程和端口可在调度器线程间移动，以在多核环境重新平衡 CPU 负载。
  5. 执行辅助调度器工作——包括处理脏 NIF、进程退出、跟踪钩子和其他延迟的运行时维护任务。
  6. 必要时检查 IO 并更新时间——轮询文件描述符或端口的 IO 就绪情况，可能更新系统时间或墙钟。
  7. 在需要时选择端口任务执行——在调度进程之前先执行端口任务，如 TCP 读写或调用驱动回调。
  8. 选择一个进程执行——从运行队列中选一个可运行进程（考虑优先级和公平性），交给模拟器执行。

10.9 负载均衡（Load Balancing）

当前负载均衡策略的目标是：用尽可能少的调度器，同时不让任何 CPU 过载。这样当进程共享同一个 CPU 时，能通过更好的内存局部性获得更好的性能。

需要注意：调度器做的负载均衡是在调度器线程之间，不一定在 CPU 或核之间。启动运行时系统时，你可以指定调度器如何分配到核。默认行为是交给 OS 来分配调度器线程到核，你也可以选择把调度器绑定到核。

负载均衡假设每个核上运行一个调度器，这样把一个进程从过载的调度器移到利用不足的调度器，就能获得更多并行处理能力。如果你改动了调度器与核的分配方式，或者 OS 过载、不擅长给线程分配核，负载均衡反而可能降低性能。

负载均衡用两种技术：任务窃取（task stealing）和迁移（migration）。

10.9.1 任务窃取（Task Stealing）

当一个调度器的运行队列为空、却该选新进程时，它会尝试从其他调度器窃取工作。

流程：

  1. 先对自己加锁，防止其他调度器来窃取当前调度器的工作；
  2. 检查是否有不活跃的调度器有可窃取任务；
  3. 如果没有，则查看活跃调度器（从 ID 更高的开始），寻找可窃取任务；
  4. 一次只看一个调度器，尝试窃取它的最高优先级任务。

特点：

  • 速度很快，调度器每次迭代、只要没任务就能做；
  • 倾向于把任务向编号较低的调度器移动（从编号高的窃取，但也会环绕到编号低的），最终使进程分散在所有活跃调度器上。

10.9.2 迁移（Migration）

要最优利用调度器，会采用更精细的迁移策略。当前策略是：把负载压缩到尽可能少的调度器，同时分散得让没有调度器过载。

迁移由 erl_process.c 中的 check_balance 函数完成。

迁移先制定一个迁移计划，然后调度器按这个计划执行，直到制定新计划。每经过 2000×CONTEXT_REDS 次 reductions，一个调度器会根据所有调度器的工作负载，按优先级、按调度器计算一个迁移路径。迁移路径有三种值：

  1. cleared（清空）
  2. migrate to scheduler #（迁移到指定调度器）
  3. immigrate from scheduler #（从指定调度器迁入）

运作流程：

  • 进程就绪时（如收到消息或触发超时），通常被调度回它最后运行过的调度器（S1）。
  • 如果 S1 在该优先级上的迁移路径是 cleared，进程就留在 S1。
  • 如果路径设为"迁移到 S2"，且 S1、S2 的运行队列都不平衡，进程就被交给 S2。

平衡的计算：

  • 比较每个调度器某优先级的最大运行队列长度；
  • 每个调度器在自己的调度器循环每次迭代里更新一个计数器，记录最大队列长度；
  • 用这些信息计算平均最大队列长度（AMQL）。
Max
Run Q
Length
   5         o
             o
          o  o
Avg: 2.5 --------------
          o  o     o
   1      o  o     o

scheduler S1 S2 S3 S4

然后按最大队列长度排序：

Max
Run Q
Length
   5               o
                   o
                o  o
Avg: 2.5 --------------
             o  o  o
   1         o  o  o

scheduler S3 S4 S1 S2

          ^        ^
          |        |
         tix      fix

队列长度大于平均值的调度器（S1、S2）被标记为迁出（emigration）；最大队列长度小于平均值的调度器（S3、S4）被标记为迁入目标（immigration）。

用两个索引在排序后的调度器集合上循环：fix（迁入自）和 tix（迁出到）。每轮迭代，把 S[tix] 的迁入路径设为 S[fix]，把 S[fix] 的迁出路径设为 S[tix]。然后 tix 递增、fix 递减，直到两者都越过平衡点；若一个先到平衡点就先环绕。

示例：

  • 迭代 1：S2.emigrate_to = S3，S3.immigrate_from = S2
  • 迭代 2：S1.emigrate_to = S4，S4.immigrate_from = S1

到此完成。

实际上更复杂：调度器可能被下线（taken offline），迁移计划只对在线调度器做。而且如前所述，这是按优先级级别分别做的。

当进程要插入就绪队列、且存在从 S1 到 S2 的迁移路径时，调度器会先检查：S1 的运行队列是否大于 AMQL，且 S2 的运行队列是否小于平均值。只有当两个队列仍不平衡时，迁移才被允许。

有两个例外，即使队列平衡（或反向不平衡）也会强制迁移，并设置一个特殊的撤离标志（evacuation flag）来覆盖平衡测试：

  1. 调度器下线时——设置该标志确保没有新进程被调度到离线调度器；
  2. 调度器检测到某优先级没有进展时——比如某个 max 优先级进程永远可运行，导致 normal 优先级进程永远不被调度。此时会为该调度器的 normal 优先级队列设置撤离标志。

小结

Erlang 的调度器把协作式调度（进程在特定点主动让出）放在抢占式调度（从外部看是公平的、轮转的）之上，核心工具是 reduction 计数：每个函数调用计一个规约，用完就挂起。它用就绪队列 + 优先级 + 时间轮管理进程，用端口任务处理外部 IO，用任务窃取 + 迁移做负载均衡。整个设计让开发者无需手动 yield()，就能获得一个公平、响应、可并行的运行时。