GAMES104：现代游戏引擎架构——面向数据编程与任务系统（上）

课程：GAMES104《现代游戏引擎：从入门到实践》
第 20 讲（上）：现代游戏引擎架构：面向数据编程与任务系统
本地视频时长：约 1 小时 16 分钟

一、本讲概览

现代 CPU 的性能增长越来越依赖多核，而不是单核频率无限提升。游戏引擎若仍把渲染、物理、动画、AI 和网络等工作串行塞进一条主线程，就无法充分利用硬件。

但把代码放进多个线程并不等于自动获得性能。并行程序还会面对：

线程创建与上下文切换开销。
共享数据竞争。
锁竞争、死锁与优先级反转。
编译器和 CPU 指令重排。
不同硬件平台的内存顺序差异。
固定线程负载不均。
任务依赖与等待造成的空闲核心。

本讲先建立并行编程的基础，再逐步引出游戏引擎的 Job System：

为什么多核时代必须显式考虑并行。
操作系统线程如何调度，以及上下文切换为何昂贵。
锁、原子操作、无锁算法和内存顺序解决什么问题。
固定多线程和 Fork-Join 模型为何仍不够灵活。
如何用任务图表达依赖。
如何用协程与 Fiber 保存轻量执行上下文。
如何用工作线程、任务队列和 Work Stealing 动态填满 CPU。

“面向数据编程”的完整展开主要留到下半部分；本部分重点是 Job System 所需的并发基础与调度架构。

二、学习目标

区分并发、并行、抢占式调度和协作式调度。
理解进程、线程、协程、Fiber 和 Job 的职责差异。
理解线程上下文切换与缓存失效为何昂贵。
掌握数据竞争、临界区、锁和死锁的基本概念。
理解原子 Load、Store、RMW、CAS 和 Fetch-Add。
区分 Blocking、Lock-Free 和 Wait-Free 的进展保证。
理解编译器重排、CPU 乱序执行与内存可见性问题。
认识固定多线程和 Fork-Join 的优点与瓶颈。
掌握任务图、依赖计数和就绪任务的基本模型。
区分有栈协程与无栈协程。
理解基于 Fiber 的 Job System 如何减少线程阻塞。
理解每核工作线程、全局队列、本地队列和 Work Stealing。

三、为什么现代引擎必须理解硬件与操作系统

高级语言中的一行代码最终要经过：

编译器优化和指令生成。
操作系统线程调度。
CPU 流水线、缓存与内存系统。
实际硬件平台执行。

所以“源码看起来按顺序执行”并不代表不同线程会按相同顺序观察到结果。高性能引擎不能只考虑算法的大 $O$ 复杂度，还必须考虑：

数据是否命中缓存。
工作是否能分配到多个核心。
线程是否频繁阻塞和切换。
同步是否形成串行瓶颈。
代码是否在不同 CPU 内存模型上保持正确。

游戏引擎位于应用、操作系统和硬件之间。越接近性能上限，越不能忽略下面两层。

四、从单核提速转向多核并行

过去可以期待新一代 CPU 自动让同一段串行代码运行得更快。随着功耗、散热和频率提升受限，处理器转向增加核心数量。

这带来一个根本变化：

硬件提供了更多并行执行单元，但软件必须暴露足够的独立工作，才能把这些执行单元用起来。

如果一帧中的所有工作存在一条长串依赖，即使机器有很多核心，也只能等待关键路径逐个完成。

假设程序中可并行比例为 $P$，使用 $N$ 个执行单元，Amdahl 定律给出的理论加速比为：

$$ S(N)

\frac{1} {(1-P)+\frac{P}{N}} $$

当 $N \to \infty$ 时：

$$ \lim_{N\to\infty} S(N)

\frac{1}{1-P} $$

因此，只要仍有一小段不可并行部分，它就会成为最终上限。Job System 的价值不仅是“开更多线程”，还包括缩短串行关键路径、减少等待和提高负载均衡。

五、并发与并行

1. 并发

并发表示多个任务在同一时间段内都在推进。单核 CPU 也可以通过快速切换任务形成并发。

2. 并行

并行表示多个任务在同一时刻真正运行在不同核心或硬件执行单元上。

3. 两者关系

并发是程序结构和调度问题。
并行是实际执行资源问题。
并发程序不一定并行执行。
并行程序通常需要先把工作组织成可并发任务。

游戏引擎的 Job System 先把大系统拆成可调度的细粒度任务，再由工作线程把它们映射到多个 CPU 核心。

六、易并行与非易并行问题

1. 易并行问题

若任务之间几乎没有依赖和通信，可以直接切分。例如：

对独立粒子做更新。
对多个对象做包围盒计算。
对大量动画骨骼或实例执行相同变换。
Monte Carlo 样本计算。

这类工作只需分配输入范围，最后合并结果。

2. 非易并行问题

若任务之间需要频繁交换数据或等待前置结果，并行化难度显著提高。例如：

物理接触会把多个刚体连接成约束岛。
动画结果可能依赖角色状态与 IK 输入。
渲染 Pass 之间存在资源读写依赖。
Gameplay 系统可能同时修改同一实体。

这类问题的关键不是创建线程，而是识别：

哪些数据可独占写入。
哪些数据只读共享。
哪些阶段必须建立同步点。
哪些依赖可以重构或延迟。

七、抢占式与协作式多任务

1. 抢占式调度

操作系统调度器可以在任意调度点中断当前线程，并切换到另一线程。

特点：

线程不需要主动让出 CPU。
操作系统决定执行顺序和时间片。
能防止单个普通线程永久占用核心。
切换时机对应用层通常不可预测。

2. 协作式调度

任务运行到明确位置后主动 Yield，把控制权交给调度器或其他任务。

特点：

切换发生在程序允许的位置。
应用可以维护更轻量的执行上下文。
若任务长时间不 Yield，其他任务可能饥饿。
协程与 Fiber 常使用协作式切换。

3. Job System 的组合

现代 Job System 通常同时使用：

少量操作系统工作线程，由 OS 抢占调度到 CPU 核心。
大量 Job 或 Fiber，由引擎自己的调度器协作式管理。

这让引擎在不创建海量 OS 线程的前提下，维护大量可暂停和恢复的工作。

八、进程、线程、协程、Fiber 与 Job

概念	谁调度	是否拥有执行上下文	主要作用
进程	操作系统	地址空间、资源和至少一个线程	隔离应用
线程	操作系统	寄存器、栈、线程状态	在 CPU 上实际执行
协程	应用程序	取决于有栈或无栈实现	协作式暂停与恢复
Fiber	应用调度器	通常有独立栈和寄存器上下文	承载可切换 Job
Job	Job Scheduler	通常不直接等同于 OS 线程	描述一小段可调度工作

需要牢记：

线程是执行资源。
Fiber 是用户态执行上下文。
Job 是待完成的工作描述。
Job 可以在不同时间由不同工作线程推进。

把 Job 永久绑定到某一线程，会重新退化为固定线程架构。

九、线程上下文切换

线程被切出时，系统需要保存并恢复：

CPU 寄存器。
指令指针。
栈指针。
调度状态。
与操作系统相关的线程信息。

上下文切换可能还包含用户态与内核态切换。更隐蔽的成本来自缓存：

新线程需要的数据可能不在当前核心缓存中。
原线程的热点数据可能被替换。
跨核迁移会增加缓存一致性流量。
分支预测器和 TLB 的有效状态可能下降。

可以把一次任务的有效执行比例近似写为：

$$ \eta

\frac{T_{\text{work}}} {T_{\text{work}} +T_{\text{schedule}} +T_{\text{sync}} +T_{\text{cache}}} $$

任务过细时，调度和同步成本会吞掉并行收益；任务过粗时，又会导致负载不均和核心空闲。

十、共享状态与数据竞争

当多个线程并发访问同一内存位置，并且至少有一个线程执行写操作，而程序又没有建立正确同步，就会发生数据竞争。

例如两个线程同时对计数器执行“读取、加一、写回”：

线程 A 读取旧值 $x$。
线程 B 也读取旧值 $x$。
A 写入 $x+1$。
B 写入 $x+1$。

两次增加最终只生效一次。

避免数据竞争的主要思路：

不共享：每个 Job 写入独立数据。
不可变：并发阶段只读取共享数据。
分阶段：读写阶段通过依赖明确分离。
单一写者：某份状态只由一个系统或任务拥有。
同步保护：确实需要共享写时使用锁或原子操作。

最便宜的同步通常是根本不共享可变数据。

十一、锁与临界区

锁保证同一时刻只有一个线程进入临界区。

基本结构是：

获取锁。
访问共享资源。
释放锁。

锁能提供清晰的互斥语义，但正确使用仍需满足：

所有访问者使用同一同步协议。
锁必须在所有退出路径上释放。
临界区尽可能短。
持锁期间避免阻塞 I/O 或等待其他任务。
锁顺序保持一致。

1. 锁竞争

如果锁空闲，获取成本可能较低；一旦多个线程争用：

线程可能自旋浪费核心。
线程可能休眠并触发上下文切换。
共享缓存行在核心之间来回转移。
并行区域会退化为串行队列。

2. 粗粒度与细粒度

粗粒度锁：简单，但并发度低。
细粒度锁：并发度高，但更难维护，死锁风险更大。

优化前应先测量争用时间和临界区长度，而不是机械地增加更多锁。

十二、锁的典型问题

1. 死锁

线程 A 持有锁 $L_1$ 并等待 $L_2$；线程 B 持有 $L_2$ 并等待 $L_1$，形成循环等待。

常见预防方式：

规定全局锁顺序。
避免持有多个锁。
缩小临界区。
使用超时或可取消等待。
通过任务依赖和数据所有权代替嵌套锁。

2. 异常退出导致资源无法释放

若持锁线程异常退出或遗漏解锁，其他线程可能永久等待。应使用作用域管理资源，让锁的生命周期与对象生命周期绑定。

3. 优先级反转

高优先级线程等待低优先级线程持有的锁；此时中优先级线程又不断抢占低优先级线程，导致高优先级线程间接被长期阻塞。

可使用优先级继承、缩短持锁时间或减少跨优先级共享锁来缓解。

4. 阻塞传播

一个锁等待可能沿任务依赖链向上游传播，最终让多个工作线程全部休眠。Job System 因此倾向于让等待中的 Job 让出 Fiber，而不是让整个工作线程阻塞。

十三、原子操作

原子操作在其他线程看来不可分割。常见类别包括：

1. Atomic Load

从共享内存读取一个原子对象。

2. Atomic Store

向共享内存写入一个原子对象。

3. Read-Modify-Write

把“读取旧值、计算新值、写回”作为一个原子步骤执行，例如：

Test-and-Set。
Compare-and-Swap。
Fetch-and-Add。
Exchange。

原子性只保证该操作不会被其他线程看到一半，并不自动保证整个算法正确，也不自动给所有内存访问建立所需顺序。

十四、Compare-and-Swap

CAS 接收三个概念参数：

地址 $p$。
期望值 $e$。
新值 $d$。

其语义可表示为：

$$ CAS(p,e,d)

\begin{cases} \text{success}, & *p=e,\ \text{并令 } *p\leftarrow d \ \text{failure}, & *p\neq e \end{cases} $$

无锁算法通常采用循环：

读取旧状态。
基于旧状态构造新状态。
用 CAS 尝试提交。
若失败，说明其他线程已更新，重新读取并重试。

CAS 适合小范围状态更新，但竞争激烈时可能不断失败重试。复杂结构还需处理对象生命周期和 ABA 问题。

十五、Blocking、Lock-Free 与 Wait-Free

1. Blocking

某个线程持有锁时，其他线程可能被阻塞。若持锁线程暂停或异常，整体进度也可能停止。

2. Lock-Free

系统整体保证持续前进：即使某个线程反复失败，也至少有其他线程能完成操作。

这不保证每个线程都在有限步骤内成功，个别线程仍可能饥饿。

3. Wait-Free

每个线程都保证在有限步骤内完成操作，进展保证强于 Lock-Free，实现也更困难。

关系可以理解为：

$$ \text{Wait-Free} \subset \text{Lock-Free} \subset \text{Non-Blocking} $$

“无锁”不等于“没有等待成本”，也不等于“一定比锁快”。在低竞争或临界区很短时，简单锁可能更清晰、更高效。

十六、指令重排为什么危险

编译器和 CPU 都可能在不改变单线程可观察结果的前提下重排指令，以提高吞吐。

假设线程 A 按源码顺序执行：

$$ data \leftarrow 42 $$

$$ ready \leftarrow true $$

线程 B 等待 $ready$ 后读取 $data$。若没有正确同步：

编译器可能调整访问顺序。
CPU 可能乱序执行。
Store Buffer 可能延迟对其他核心可见。
线程 B 可能看到 $ready=true$，却仍看到旧的 $data$。

单线程语义没有被破坏，但跨线程观察结果已经不符合程序员直觉。

十七、内存顺序与可见性

并发正确性需要回答两类问题：

原子性：操作会不会被撕裂或丢失。
顺序性：一个线程何时能看到另一个线程的其他写入。

常见内存顺序概念：

Relaxed：只保证原子操作本身，不建立额外跨变量顺序。
Acquire：之后的读写不能移动到该操作之前。
Release：之前的读写不能移动到该操作之后。
Acquire-Release：同时承担获取与发布语义。
Sequentially Consistent：提供更强的全局顺序直觉。

典型发布模式是：

生产者先写数据，再以 Release 方式写入就绪标记。
消费者以 Acquire 方式读取就绪标记，再访问数据。

若 Acquire 读到了对应的 Release 值，就建立 Happens-Before 关系，消费者能够看到生产者在 Release 之前的写入。

不同 CPU 的差异

x86 通常提供相对强的内存顺序；ARM 等平台允许更多重排。只在一台机器上“跑了很久没出错”不能证明并发代码正确。

正确做法是使用语言定义的原子和内存序，而不是依赖特定编译器、CPU 或调试构建中的偶然行为。

十八、固定多线程架构

早期或结构简单的引擎常为不同模块分配固定线程：

渲染线程。
模拟线程。
Gameplay 逻辑线程。
网络线程。

优点：

设计直观。
模块边界清晰。
实现成本相对低。
每类线程可采用专门循环。

问题：

不同模块每帧工作量不同。
某线程忙碌时，其他核心可能空闲。
模块间等待形成流水线气泡。
难以随核心数量自动伸缩。
长任务会拖慢该线程上的全部后续工作。

固定线程把“系统”绑定到“执行资源”，限制了动态调度能力。

十九、Fork-Join 与线程池

Fork-Join 把一段可并行工作拆成多个子任务：

Fork：创建或提交子任务。
多个工作线程并行执行。
Join：等待所有子任务完成。
恢复后续阶段。

线程池避免每次 Fork 都创建和销毁 OS 线程。它适合：

批量动画更新。
并行遍历实体。
分块粒子模拟。
可独立处理的数据数组。

局限：

Join 是显式同步点。
子任务耗时不均会留下尾部空闲。
嵌套 Fork-Join 容易让工作线程互相等待。
复杂系统依赖难以只用一层 Fork-Join 表达。

任务图把多个 Fork-Join 阶段推广为一般依赖网络。

二十、任务图

任务图通常是有向无环图 DAG：

$$ G=(V,E) $$

其中：

节点 $V$ 表示 Job。
有向边 $E$ 表示前置依赖。
图中不能存在循环依赖。

若任务 $v$ 的前置集合为 $Pred(v)$，其未完成依赖计数可表示为：

$$ d(v)

\left| \left{ u\in Pred(v) \mid u\text{ 尚未完成} \right} \right| $$

当：

$$ d(v)=0 $$

任务进入 Ready 状态，可以被调度。

每个任务完成后，调度器遍历它的后继节点并减少依赖计数；计数降为零的后继任务进入就绪队列。

二十一、为什么任务图适合游戏引擎

一帧可以抽象为若干任务：

角色输入完成后才能推进 Gameplay。
动画采样后才能计算蒙皮。
可见性结果完成后才能生成渲染命令。
物理模拟完成后才能读取最终位姿。
多个子任务完成后才能提交帧结果。

任务图让系统只声明“必须先发生什么”，而不强制指定“在哪个线程执行”。

这样调度器可以：

在依赖满足时立即执行任务。
把任务分配给任意空闲工作线程。
根据平台核心数自动扩展。
在等待时执行其他可运行任务。

任务图中最长的依赖链是关键路径。增加核心只能压缩并行支路，不能越过关键路径下限。

二十二、任务粒度

任务粒度决定 Job System 的实际效率。

任务过粗

并行度不足。
单个长任务形成尾部延迟。
工作窃取难以平衡。
某核心繁忙时其他核心提前空闲。

任务过细

创建和入队成本变高。
原子操作和队列竞争增加。
依赖图节点数量膨胀。
调度开销超过有效工作。

可用一个简单判断：

$$ T_{\text{job}} \gg T_{\text{enqueue}} +T_{\text{dequeue}} +T_{\text{dependency}} $$

其中 $T_{\text{job}}$ 应明显大于任务调度和依赖维护成本。

实际引擎常采用批处理：一个 Job 处理一段连续数据，而不是一个实体创建一个 Job。

二十三、协程

普通函数调用只会从入口执行到返回；协程可以：

执行到 Yield。
保存恢复所需状态。
把控制权交给调度器。
之后从暂停点继续。

协程由应用层管理，切换通常不需要进入内核，因此比 OS 线程切换轻量。

但协程本身不等于并行：

同一线程上的多个协程只是协作式并发。
只有当协程承载的 Job 被分配到多个工作线程时，才会并行执行。

二十四、有栈协程

有栈协程拥有独立运行栈。Yield 时会保留：

调用链。
栈帧。
局部变量。
返回地址。
必要寄存器状态。

优点：

可以在嵌套函数深处 Yield。
编程形式接近普通同步函数。
恢复后局部变量自然保留。

代价：

每个协程需要栈空间。
上下文切换需要保存更多状态。
栈大小、溢出检测和跨平台实现更复杂。

二十五、无栈协程

无栈协程没有独立运行栈。编译器或运行时把恢复状态显式保存到协程对象中，行为近似状态机。

优点：

不需要为每个协程预留独立栈。
切换状态较少。
大量协程时内存成本更可控。

限制：

通常只能在协程函数自身的指定位置挂起。
普通子函数不能随意跨调用栈 Yield。
需要显式保存恢复所需的局部状态。

维度	有栈协程	无栈协程
独立栈	有	无
嵌套函数内 Yield	可以	通常不可以
内存开销	较高	较低
切换状态	较多	较少
编程直觉	接近同步代码	接近状态机

二十六、Fiber-Based Job System

Fiber 可以看成由调度器管理的有栈协作式执行上下文。

典型结构包括：

与 CPU 核心数量接近的工作线程。
数量更多的 Fiber 池。
大量细粒度 Job。
负责依赖、队列和唤醒的调度器。

执行关系是：

工作线程从队列中取得 Job。
Job 在某个 Fiber 上运行。
Job 等待依赖时，当前 Fiber 被挂起。
工作线程切换到另一个可运行 Fiber。
依赖满足后，原 Fiber 重新进入可运行队列。

关键收益是：

Job 等待时只挂起 Fiber，不必阻塞宝贵的 OS 工作线程。

二十七、每个核心一个工作线程

为了减少 OS 线程间切换，Job System 常让工作线程数接近可用硬件核心数，并尽量保持线程与核心的稳定关系。

优点：

减少同一核心上多个工作线程的抢占。
降低线程上下文切换。
提高缓存局部性。
让调度器更容易估计并行容量。

但这不是绝对规则：

操作系统和其他进程仍需核心时间。
同时多线程 SMT 的逻辑核心不等同于完整物理核心。
I/O 密集型任务可能需要不同策略。
主线程、渲染提交线程等可能需要预留资源。

线程数量应根据平台、任务类型和实测数据配置。

二十八、任务队列

Job Scheduler 常同时维护：

全局任务队列：外部线程提交任务，所有 Worker 可访问。
Worker 本地队列：工作线程优先处理自己生成的任务。
等待集合：依赖未满足或 Fiber 已挂起的任务。

全局队列便于统一提交，但所有线程频繁竞争同一队列会形成热点。本地队列能减少共享访问并改善缓存局部性。

二十九、FIFO 与 LIFO

1. FIFO

先进入队列的任务先执行。

优点：

公平。
等待时间容易理解。
适合独立任务流。

2. LIFO

后提交的任务优先执行。

在树状任务依赖中，LIFO 有助于深度优先推进刚刚产生的子任务：

子任务所需数据可能仍在缓存中。
尽快完成子树可以更快解除父任务等待。
临时创建并立即等待的任务能较快完成。

调度器可以在本地队列使用 LIFO，在窃取时从另一端取较旧任务，从而兼顾局部性与负载均衡。

三十、Work Stealing

每个 Worker 维护本地双端队列：

Worker 自己从一端取任务。
空闲 Worker 从其他队列的另一端窃取任务。

基本流程：

优先执行本地任务。
本地队列为空时检查全局队列。
仍无任务时选择其他 Worker。
从目标队列窃取可运行 Job。
无任何工作时短暂等待或休眠。

Work Stealing 的作用是动态平衡不可预测的任务耗时。它不需要中央调度器持续精确分配每个 Job。

为什么从另一端窃取

所有者通常从队列一端处理最新子任务，以保持深度优先和缓存局部性；窃取者从另一端取得较老、通常粒度更大的任务，减少双方操作同一位置的冲突。

三十一、等待、唤醒与帮助执行

传统写法在等待子任务时阻塞线程；Job System 更希望工作线程继续做有用工作。

可采用：

Fiber Yield：挂起当前执行上下文。
Help-While-Waiting：等待者主动执行其他 Ready Job。
Continuation：依赖满足后自动排入后继任务。
Counter/Event：多个子任务完成后把计数降到零并唤醒等待者。

若任务 $J$ 等待 $k$ 个子任务，可维护计数器：

$$ C_J(0)=k $$

每个子任务完成后：

$$ C_J \leftarrow C_J-1 $$

当：

$$ C_J=0 $$

任务 $J$ 恢复执行。

计数更新必须是原子的，任务注册与完成之间还需避免丢失唤醒。

三十二、Job System 的优势

任务可以按依赖自动调度。
工作不再永久绑定特定线程。
空闲核心可通过 Work Stealing 获取任务。
Fiber 等待不会阻塞整个工作线程。
任务拥有独立执行上下文，写法接近同步代码。
工作线程数量可按硬件平台调整。
更容易把动画、物理、渲染准备和 Gameplay 统一到一套调度框架。

三十三、Job System 的代价

Fiber 并非所有 C++ 平台都原生统一支持。
Fiber 上下文切换和栈管理需要平台相关实现。
调试调用栈和复现竞态更困难。
Job 可能在线程之间迁移，不能随意依赖线程局部存储。
任务图、队列和依赖计数本身有开销。
任务过细会被调度成本反噬。
任务过粗又无法充分利用核心。
不正确的内存序和生命周期管理会产生低概率错误。

Job System 不是“自动并行化一切”的魔法层。它要求上层系统以清晰的数据访问和依赖关系提交工作。

三十四、Job 与数据设计的关系

Job System 能否高效，最终取决于数据组织。

如果每个 Job 都会：

访问大量随机对象。
修改共享全局状态。
持有多个锁。
追踪深层指针关系。

那么调度器再先进，也会被缓存未命中和同步等待限制。

理想任务更接近：

输入范围明确。
只读数据与输出数据分离。
批量处理连续内存。
写入区域互不重叠。
依赖在提交时就能声明。

这正是 Job System 与面向数据编程连接起来的原因：数据布局决定缓存效率，也决定工作能否安全拆分。

三十五、常见错误与改进

1. 一个系统永久绑定一个线程

结果：最慢系统决定整帧耗时，其他核心无法帮助。

改进：把系统内部工作拆成 Job，只保留必要的专用线程。

2. 每个小对象创建一个 Job

结果：队列、依赖和原子操作开销超过有效计算。

改进：批量处理连续对象，根据测量调整 Grain Size。

3. Job 内长时间持锁

结果：工作线程或 Fiber 大量等待，吞吐下降。

改进：明确数据所有权，缩小写集，用依赖边代替运行时抢锁。

4. 等待 Job 时阻塞工作线程

结果：线程池可能全部等待，系统即使存在 Ready Job 也无人执行。

改进：挂起 Fiber，或在等待期间帮助执行其他任务。

5. 认为 Atomic 就等于线程安全

结果：单个变量读写不撕裂，但多变量不变量和顺序关系仍可能被破坏。

改进：明确算法所需的原子性范围和 Happens-Before 关系。

6. 默认所有 CPU 都像 x86

结果：代码在弱内存序平台上出现难以复现的错误。

改进：依赖 C++ 内存模型和明确的 Acquire/Release，而不是硬件偶然保证。

7. 用 Volatile 代替同步

结果：可能抑制部分编译器优化，却不能提供完整原子性和跨线程顺序保证。

改进：使用语言定义的 Atomic、锁或同步原语。

8. 任务图中形成循环

结果：依赖计数永远无法归零，相关任务全部无法执行。

改进：提交时检测 DAG 合法性，并输出可视化依赖链。

9. 滥用线程局部存储

结果：Job 在不同工作线程恢复后读到不同的 Thread Local 状态。

改进：把 Job 所需状态放入 Job/Fiber 上下文，或明确限制任务迁移。

三十六、调试与性能分析

1. 正确性信息

Job ID、父任务和依赖列表。
创建、入队、开始、挂起、恢复和完成事件。
当前 Fiber 与工作线程映射。
锁持有者和等待者。
原子操作失败重试次数。
依赖计数变化。

2. 性能信息

每个 Job 的运行时间。
Worker 忙碌率和空闲时间。
队列长度。
Work Stealing 次数与成功率。
全局队列竞争时间。
Fiber 切换次数。
锁等待和上下文切换时间。
关键路径长度。

3. 调度轨迹视图

并行问题很难仅靠平均值判断。时间线应显示：

每个核心或工作线程正在执行哪个 Job。
哪些任务因依赖等待。
哪些核心存在空洞。
哪个长尾任务拖延帧结束。
任务在哪些线程之间迁移。

真正的优化目标不是让任务数量最多，而是缩短帧的关键路径并减少核心空闲。

三十七、设计原则

先设计数据所有权，再设计线程同步。
尽量让 Job 处理独立、连续的数据范围。
线程是执行资源，Job 是工作，不要永久绑定二者。
用显式依赖表达先后关系，少用运行时抢锁。
工作线程数量接近实际并行容量，不盲目增加线程。
等待依赖时让出 Fiber，不阻塞整个 Worker。
任务粒度必须显著大于调度成本。
本地队列优先保证局部性，Work Stealing 负责动态均衡。
原子性、可见性和顺序性是三个不同问题。
Lock-Free 描述整体进展，不保证单个线程永不饥饿。
内存序必须基于语言标准，而不是平台经验。
任务图必须保持无环，并能观察关键路径。
Job 不应隐式依赖固定线程和 Thread Local 状态。
调度框架只能暴露并行机会，最终收益仍由数据布局决定。
所有并行优化都必须用真实帧时间、争用和核心利用率验证。

三十八、核心术语

术语	含义
Concurrency	多个任务在同一时间段内推进
Parallelism	多个任务同一时刻在不同执行单元运行
Preemption	调度器强制中断当前任务
Yield	任务主动让出执行权
Context Switch	保存一个执行上下文并恢复另一个
Critical Section	需要互斥访问的代码区域
Data Race	未同步的并发访问中至少有一个写操作
Atomic Operation	对其他线程呈现为不可分割的操作
CAS	比较当前值并在相等时交换
Lock-Free	系统整体保证持续取得进展
Wait-Free	每个参与者都保证有限步完成
Memory Ordering	不同内存操作对线程可观察的顺序约束
Task Graph	用 DAG 表达任务与依赖
Coroutine	应用管理的可暂停、恢复执行过程
Fiber	常带独立栈、由用户态调度的执行上下文
Job	可由调度器分配给 Worker 的工作单元
Work Stealing	空闲 Worker 从其他 Worker 队列获取任务
Critical Path	决定图整体完成时间的最长依赖链

三十九、复习要点

多核增加的是并行执行资源，串行程序不会自动获得线性加速。
Amdahl 定律说明不可并行部分决定最终加速上限。
并发是任务结构，并行是实际同时执行。
抢占式线程由 OS 调度；协程和 Fiber 多由应用协作式调度。
线程上下文切换成本不仅是保存寄存器，还包括缓存和内核切换。
最有效的同步往往是避免共享可变数据。
锁简单但可能引发竞争、死锁、阻塞传播和优先级反转。
原子操作是无锁算法基础，但原子变量不等于整个算法线程安全。
Lock-Free 保证系统整体前进；Wait-Free 保证每个线程有限步完成。
编译器和 CPU 都可能重排指令，跨线程通信必须建立正确内存顺序。
Acquire/Release 可建立数据发布与消费之间的 Happens-Before 关系。
固定多线程容易实现，却难以应对每帧变化的负载。
Fork-Join 适合数据并行，任务图能表达更一般的系统依赖。
Job System 把工作与线程解耦，让任意空闲核心处理 Ready Job。
协程提供轻量暂停与恢复；有栈协程更灵活，无栈协程更节省内存。
Fiber-Based Job System 在 Job 等待时挂起 Fiber，而不是阻塞 Worker。
每核少量 Worker 减少 OS 线程切换，本地队列提高数据局部性。
Work Stealing 让空闲 Worker 动态获取其他队列中的工作。
任务过粗会负载不均，任务过细会被调度开销反噬。
Job System 的最终效率依赖清晰的数据访问模式和缓存友好布局。

四十、参考资料

GAMES104 第 20 讲（上）：现代游戏引擎架构——面向数据编程与任务系统（Bilibili）