本文将简要介绍游戏引擎中底层架构—任务系统的一些相关知识，包括：

• 并行编程基础；
• 游戏引擎并行架构；
• 任务系统；

并行编程基础

进程和线程

进程是运行中程序的实例，拥有独立的存储空间，由系统去管理。

线程是操作系统分配的最小执行单元，存在于进程中，共享存储空间。

在Windows系统中，线程比进程轻量很多；在Linux系统中，线程也可以做的轻量一些。

多任务模型

有了并行编程的执行者，还需要管理者来管理它们。常见的多任务模型有两种：抢占式多任务（Preemptive）和非抢占式多任务（Non-preemptive）。

抢占式多任务

由任务调度者负责管理，调度者决定什么时候中断任务1，继续任务2。

非抢占式多任务

由任务自己进行管理，更加灵活，但更考验程序员的多线程编程功底。

线程上下文切换

由于物理上存在的核就几个，虚拟化出来的线程却很多，因此在执行不同任务的期间常常会进行线程上下文切换，这个过程非常耗时：

因此，一个好的任务系统需要尽量减少线程上下文切换的次数。

多线程出现的问题

并行计算更加复杂，带来的问题也更多。例如线程之间的通信，依赖问题；竟态数据问题；编译指令重排问题等。

线程依赖问题

线程间可能存在依赖问题，例如线程A必须等待线程B执行完，获取到结果才能继续。最好将线程间的依赖去除，才能达到高效，例如蒙特卡洛多线程的同时采样，互不干扰。

竞态数据问题

竞态数据（Data Race）是多线程在同时读写一个变量，导致结果不符预期。

锁

解决它的一种方法就是用锁来保护读写操作，同时只能有一个线程获取锁，进而对受保护的资源进行修改。

锁是阻断式的，虽然锁的实现有很多，但仍有让程序无响应的死锁问题发生的可能，并且有性能上的损耗。

无锁编程

原子操作是无锁编程的一种，它受硬件支持，可以保证对某变量的读写操作是线程安全的。

比无锁编程更进阶的是无等待编程，它通过数学的方式让线程间几乎无等待地执行多任务：

编译指令重排问题

如果启用编译优化，编译器可能会将指令重排序，导致多线程环境中出现错误。

游戏引擎的并行编程架构

固定多线程

大多数引擎都采用这个架构，将每个模块分配一个线程，互不干扰。

但这样做导致每个线程的工作强度不均匀，可能会出现几个线程等一个线程工作完成的状况。并且由于分配的线程个数是写死的，导致在高配电脑上发挥不出性能（多余的核没用），在低配电脑上过于缓慢（线程上下文切换次数过多）。

动态线程分配

某一模块线程可以通过线程池来动态分配多个子线程，加快它的工作。

虽然在一定程度上提高了性能，但这样做仍然避免不了工作内容分配不均匀的问题。

这种架构的典型应用就是虚幻引擎，将主要模块分配给Named线程，然后通过分配Worker线程加快计算。

任务图架构

可以创建很多任务，设置好依赖关系，最后交给系统自动多核执行。

可以通过代码来构建：

任务系统 Job System

协程

协程是一种比线程更轻量的可执行上下文单元，可以通过在代码中调用相应函数实现协程的调度。

在一个线程内可存在多个协程，它们进行上下文切换的成本比线程间上下文切换的成本低多了，只是在程序中进行切换，而不会调用操作系统内核。协程因此也被称作“用户级线程”。

有栈协程

有栈协程中，每个协程都有自己独立的调用栈来存储状态，并可以从嵌套调用内部的任何地方挂起。

无栈协程

相对的，无栈协程没有自己独立的栈来保存状态，只能从顶层栈帧挂起，并保存函数体中具有自动存储时间的变量与临时变量。

和有栈协程相比，无栈协程的内存使用非常少，可以允许数百万甚至数十亿的协程同时运行。C++20中的协程构建块（不是库，得自行封装）就是无栈协程。

基于纤程的任务系统

纤程（Fiber）是有栈协程的一种具体实现方式，并由一个调度器来调度。对于线程中的各种子任务，可以将其各自分配一个纤程来执行。

为了减少线程上下文切换的次数，这个系统将线程都绑定到各自的核上，只让里面的纤程执行分配进来的任务。

该系统中存在一个调度器，这个调度器会根据各工作线程的状态（是否饱和）将任务进行适当分配。这些任务一般是LIFO（后进先出）的，因为任务就像树结构一样，从根节点可能还会派生出许多子任务，先完成这些子任务才能完成根节点的任务。

此外，使用调度器还有一个好处，当某个工作线程完成所有任务后，调度器会把其他线程中未完成的任务分配给它，不让它空闲。

任务之间会存在依赖现象，只需把当前任务挂起，执行完该任务依赖的其他任务后，再把该任务继续即可。

该系统的优点如下：

• 容易实现任务调度；
• 容易处理任务依赖；
• 每个任务的栈是独立的；
• 避免频繁的上下文切换；

该系统的缺点如下：

• C++本身不支持纤程；
• 在不同操作系统中的实现不同；
• 有一些限制，例如不能用thread_local；

参考资料

• GAMES104 (boomingtech.com)

待阅读的资料

Parallel Frameworks in Game Engine：

• GDC2015 - Parallelizing the Naughty Dog Engine Using Fibers：

  https://www.gdcvault.com/play/1022186/Parallelizing-the-Naughty-Dog-Engine

• GCAP 2016: Parallel Game Engine Design - Brooke Hodgman

  https://www.youtube.com/watch?v=JpmK0zu4Mts

• C++20: Building a Thread-Pool With Coroutines

  https://blog.eiler.eu/posts/20210512/

• Processes, threads, and coroutines https://subscription.packtpub.com/book/programming/9781788627160/1/ch01lvl1sec02/processes-threads-and-coroutines

• UE并发-TaskGraph的实现和用法

  https://zhuanlan.zhihu.com/p/398843895?utm_medium=social&utm_oi=1447486643037528064&utm_psn=1546525648855732224&utm_source=ZHShareTargetIDMore

• Unreal Engine 5.0 Documentation - Tasks System

  https://docs.unrealengine.com/5.0/en-US/tasks-systems-in-unreal-engine/

• UE4/UE5的TaskGraph

https://cloud.tencent.com/developer/article/1897046