第4章 调度器：React 的 CPU 调度算法

本章要点

• Scheduler 的设计哲学：为什么 React 要自己实现一个任务调度器
• 优先级模型：5 级优先级系统的设计与 Lane 模型的映射关系
• 时间切片（Time Slicing）的实现：shouldYield 与 5ms 时间窗口
• 任务队列的数据结构：小顶堆（Min Heap）的选择与实现
• MessageChannel vs requestIdleCallback：React 为何放弃了浏览器原生 API
• 从 scheduleCallback 到 performWorkUntilDeadline：一个任务的完整生命周期
• 延迟任务与过期机制：饥饿问题的解决方案

---

2018 年，React 团队做了一个在当时看来颇为大胆的决定——他们要在 JavaScript 中实现一个任务调度器。

这不是一个普通的任务队列。React 团队要实现的，是一个具备优先级抢占、时间切片、过期淘汰能力的调度器，它在概念上与操作系统内核中的 CPU 调度器极其相似。这个调度器最终以一个独立的 npm 包发布，名字简单直白：scheduler。

为什么 React 需要自己的调度器？答案藏在浏览器的运行模型里。

4.1 浏览器的单线程困境

一个线程，所有的事

浏览器的主线程是一个极其繁忙的执行环境。JavaScript 执行、DOM 操作、样式计算、布局、绘制、垃圾回收——所有这些任务都在同一个线程上顺序执行。浏览器通过事件循环（Event Loop）来协调这些工作：

// 浏览器事件循环的简化模型
function eventLoop() {
  while (true) {
    // 1. 从宏任务队列取出一个任务执行
    const task = macroTaskQueue.dequeue();
    if (task) task.run();

    // 2. 执行所有微任务
    while (microTaskQueue.length > 0) {
      microTaskQueue.dequeue().run();
    }

    // 3. 如果到了渲染时机（通常 16.67ms 一次）
    if (shouldRender()) {
      // 执行 requestAnimationFrame 回调
      runRAFCallbacks();
      // 样式计算 → 布局 → 绘制
      style();
      layout();
      paint();
    }

    // 4. 如果有空闲时间
    if (hasIdleTime()) {
      runIdleCallbacks(); // requestIdleCallback
    }
  }
}

问题在于：如果步骤 1 中的任务执行时间过长，步骤 3 的渲染就会被延迟，用户感知到的就是卡顿。而 React 的协调过程——对比新旧虚拟 DOM 树，计算需要更新的节点——恰恰是一个可能非常耗时的 JavaScript 任务。

requestIdleCallback：一个美好但不够用的 API

浏览器其实提供了一个看起来完美的 API——requestIdleCallback（rIC）。它允许开发者在浏览器空闲时执行低优先级的工作：

requestIdleCallback((deadline) => {
  // deadline.timeRemaining() 返回当前帧剩余的空闲时间
  while (deadline.timeRemaining() > 0 && hasWork()) {
    doWork();
  }
});

React 团队最初确实考虑过使用 rIC，但很快发现了它的几个致命问题：

1. 调用频率不可控：rIC 的调用时机完全由浏览器决定。在高负载场景下，rIC 可能被延迟到几百毫秒甚至更久才执行
2. 最大超时只有 50ms：即使在完全空闲的情况下，timeRemaining() 最多返回 50ms，这个限制是硬编码在规范中的
3. 兼容性问题：Safari 直到 2024 年仍未支持 rIC
4. 没有优先级概念：rIC 只有"空闲时执行"一种语义，无法区分"紧急更新"和"普通更新"

// React 早期基于 rIC 的原型（已废弃）
function workLoop(deadline: IdleDeadline) {
  while (nextUnitOfWork && deadline.timeRemaining() > 1) {
    nextUnitOfWork = performUnitOfWork(nextUnitOfWork);
  }

  if (nextUnitOfWork) {
    // 还有工作没做完，请求下一次空闲回调
    requestIdleCallback(workLoop);
    // ⚠️ 问题：不知道下次什么时候会被调用
    // ⚠️ 可能是 16ms 后，也可能是 200ms 后
  }
}

React 需要的是更精确、更可控的调度能力。于是，他们决定自己造一个。

4.2 Scheduler 的架构设计

独立包的设计决策

React 的调度器以 scheduler 这个独立 npm 包的形式存在，这个设计决策本身就值得讨论。为什么不把调度逻辑直接写在 react-reconciler 里？

react
├── react              // 核心 API（createElement, hooks 等）
├── react-dom          // DOM 渲染器
├── react-reconciler   // 协调器（Fiber 工作循环）
└── scheduler          // 调度器（独立包）

答案是通用性。React 团队最初的愿景是让 Scheduler 成为一个通用的浏览器任务调度库——不仅 React 可以用，任何需要在主线程上做任务调度的库都可以用。虽然这个愿景至今没有完全实现（Scheduler 仍然主要服务于 React 生态），但独立包的设计让它的边界非常清晰：

• Scheduler 只负责"何时执行"，不关心"执行什么"
• React Reconciler 负责"执行什么"，不关心"何时执行"

这种关注点分离（Separation of Concerns）让两个模块可以独立演进。

核心数据结构

Scheduler 内部维护两个任务队列：

// packages/scheduler/src/forks/Scheduler.js 的核心结构
// 存放已就绪的任务（按 sortIndex 排序，sortIndex = expirationTime）
var taskQueue: Array<Task> = [];
// 存放延迟任务（按 startTime 排序）
var timerQueue: Array<Task> = [];

// 任务节点的定义
interface Task {
  id: number;                  // 自增 ID，用于在 sortIndex 相同时保持插入顺序
  callback: SchedulerCallback; // 要执行的工作函数
  priorityLevel: PriorityLevel; // 优先级
  startTime: number;           // 开始时间（当前时间 + delay）
  expirationTime: number;      // 过期时间（startTime + timeout）
  sortIndex: number;           // 排序索引（taskQueue 中为 expirationTime，timerQueue 中为 startTime）
}

两个队列都使用小顶堆（Min Heap） 实现。为什么是小顶堆而不是普通数组？

// 如果用数组 + sort：
// 每次插入后排序：O(n log n)
// 取最小值：O(1)
// 总复杂度：O(n log n)

// 使用小顶堆：
// 插入：O(log n)  ✓ 更优
// 取最小值：O(1)
// 删除最小值：O(log n)
// 总复杂度：O(log n) ✓ 更优

React 实现了一个简洁的小顶堆：

// packages/scheduler/src/SchedulerMinHeap.js
type Heap<T extends Node> = Array<T>;
type Node = { id: number; sortIndex: number };

// 插入：将节点放到末尾，然后上浮
export function push<T extends Node>(heap: Heap<T>, node: T): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

// 查看堆顶（最小值）
export function peek<T extends Node>(heap: Heap<T>): T | null {
  return heap.length === 0 ? null : heap[0];
}

// 弹出堆顶，将末尾元素移到堆顶，然后下沉
export function pop<T extends Node>(heap: Heap<T>): T | null {
  if (heap.length === 0) return null;
  const first = heap[0];
  const last = heap.pop()!;
  if (last !== first) {
    heap[0] = last;
    siftDown(heap, last, 0);
  }
  return first;
}

function siftUp<T extends Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  while (index > 0) {
    const parentIndex = (index - 1) >>> 1; // 位运算取父节点
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // parent 比 node 大，交换
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      return; // 已满足堆性质
    }
  }
}

function compare(a: Node, b: Node): number {
  // 先比较 sortIndex，相同则比较 id（保持插入顺序）
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}