purecpp - a cool open source modern c++ community

并发与异步执行流中的对象角色概述(一)

编辑时间：2022-08-29 13:57:03 作者：loop 0条评论

出自：purecpp.cn

地址： www.purecpp.cn

转载请注明出处！

# 并发与异步执行流中的对象角色概述(一)

`并发与异步执行流中的对象角色概述(一)`

[并发与异步执行流中的对象角色概述(二)](detail?id=2311)

[并发与异步执行流中的对象角色概述(三)](detail?id=2312)

在并发与异步编程中, 我们需要面对执行流的抽象问题。

- 并发编程的执行流问题既数据的依赖关系、任务的启动与同步
- 异步编程的执行流问题既异步过程的挂起与唤起、任务的调度

为完成对它们的抽象, 存在以下若干种用以描述执行流的实现手段。

- 同步调用
- 回调
- 有栈协程
- 无栈协程
- 任务图
- promise / future
- then

这些实现手段都能解决同样的问题, 但实现形式各不相同。为更加方便地理解和处理这类问题, 我们需要对其本质进行进一步的抽象。

---

## 前置概念

为对上述实现手段进行比较, 我们需要一个能够囊括上述所有技术细节的数学模型。我们知道计算机科学中的一切问题都可以被抽象为有限状态机模型。但由于我们需要考虑的是处于非实时操作系统下的用户态程序, 由于我们没有中断权限, 所以异步问题可能存在时序不确定性。这一限制使得我们在以往单线程情形下常用的单子状态机模型不再有效, 所以本文中我们首先需要重新确定异步并发编程下可抽象为单子状态机模型的前提条件适用范围。

### 有限状态机

假设有这样一台单核计算机, 它没有输入输出设备并且有时序, 同时它只运行在实模式。我们在这台计算机 boot 之后立即将它的时钟信号停掉, 不考虑 boot 过程本身, 那么此时我们获得了一个初状态。如果我们一直单步调试下去, 最终这台计算机一定会进入停机状态或是死循环。

对于这个过程中的每一个时序, 我们都可以将这个计算机的当前状态表示为一个整数 `S`。比如我们可以将所有寄存器和整个内存的所有数据按二进制位拼接起来, 就得到了这个整数 `S`。这种计算机到整数的一一映射是显然成立的。这是由于任何图灵机之间都可以互相模拟, 所以我们永远可以在一台图灵机里构造上述计算机的一个虚拟机, 之后 dump 它的内部状态, 即可得到这个特定状态的整数表示 `S`, 这个整数就是整个 dump 文件。

由于我们假设该计算机的存储空间是有限的, 那么这类计算机可以处于的状态数量则也是有限的。在这个前提假设下, 该计算机如果进入死循环, 则必会先后处于同一个状态两次以上。因为我们先前假设该计算机无输入, 所以一旦进入重复状态一次, 则必定会再发生无数次, 不会由于外部状态变化而跳出该死循环。现在我们把状态重复也作为一个停机条件, 那么现在我们的状态机就必定会在有限步计算之后停机了。

我们把这种计算机定义为 `无条件有限状态机`, 后文简称 `有限状态机` 或者 `状态机`。

我们可以把有限状态机的初状态记作 `S0`, 整个状态序列为 `{S0, S1, ..., Sn}`。状态的转移记作 `St+1 = f(St)`, 其中 `f(S)` 为状态转移函数(递推公式)。

当我们设计一个通用计算机硬件时, 我们就是在用逻辑电路搭建这个状态转移函数 `f(S)`, 它就是这个序列的递推公式。

### 执行流

我们定义上述状态序列 `{S0, S1, ..., Sn}` 为 `执行流`。

### 程序计数器 `pc`

#### 冯·诺依曼结构下的一般情况

由于实际电路实现过程中, 如果我们通过直接考察整个状态机的状态来决定下一步如何进行状态转移, 那么状态转移电路规模就太大了, 生物脑才有这个财力, 人工造物破费不起。于是便产生了冯·诺依曼结构这种妥协方案, 该实现中常常由一个 CPU 内的算数逻辑单元 (ALU) 作为状态转移函数的输入参数。ALU 是冯·诺依曼结构衍生出的状态摘要技术, 单个指令内寻址时的内存读写往往仅关心极少数几个 `word` 的内存子集, 如取指和寻址操作数影响到的内存子集。即使是作为内部状态的通用寄存器, 单个指令中也仅关心指令操作数指定的数个(一般至多2-3个)寄存器。冯·诺依曼结构中, 几乎总有一个特殊的寄存器, 既 `程序计数器` `pc` (如 x86/x64 架构中的 `eip` / `rip`), 用于承担 ALU 索引的功能。我们知道在工程实践中, 代码段往往是只读的, 一般鲜有主动读取代码段数据的需要, 这个工作往往由 `ALU` 自动完成, 通过对 `pc` 寻址, 以一次一条指令的方式装入不可见的 `指令寄存器` `ir`。在极端情况下, 除 `pc` 外的所有寄存器状态都可以被忽略, 我们依旧可以维持程序不进入 `undefined behaviour`。比如在跳转前将所有寄存器压栈, 返回后将所有寄存器弹栈, 即可达成这一点。

- **`pc` 是冯·诺依曼结构下唯一不可忽略的状态机摘要**

由于 `ALU` 模式是图灵机的一种具体实现, 该实现下我们可以方便地认为, 往往有 n 个 `pc` 就代表一个设备支持 n 个物理执行流, 既我们认为它可以同时处理 n 个有限状态机。

由于冯·诺依曼结构过于依赖 `pc`, 所以在讨论冯·诺依曼结构计算机时, 即使一个模拟的、逻辑上的执行流被挂起后, 其 `pc` 也必须被小心地保存起来, 所以绝大多数情况下, 我们都可以用 `pc` 指代一个执行流。如果它在程序计数器寄存器中, 则它是物理执行流, 如果已被拷贝到内存, 则它是已挂起的逻辑执行流, 如果被拷贝到外存(硬盘), 则它可能是系统休眠镜像内的持久化执行流状态快照。

#### 冯·诺依曼结构下的特殊情况

实际上, 段式权限控制是哈佛结构的特征, 这也是我们常常见到的情况。但这是当前主流的体系结构提供的模拟手段, 冯·诺依曼结构将代码视为数据的能力并未丢失。

只有在少数情况下, 程序才需要主动读写代码段的数据, 如调试器在下软件中断时, 需要将相应位置的机器指令改写成调试中断(如 int 3), 挂起恢复时则写回成原先的指令。又如部分病毒的 shellcode 也需要在代码段中搜索需要调用的非公开 api 地址, 或是在感染可执行文时通过修改代码段数据对程序挂钩子。

数学上, 冯·诺依曼结构比哈佛结构更一般, 所以上述两节的标题是对工程实践而非数学定义的描述。

***虽然客观存在, 但这些情况都不在本文的讨论范畴内, 本文将假设哈佛结构中的代码存储器总是只读的, 程序只主动读写哈佛结构中的数据存储器, `pc` 总是由 ALU 自动控制。***

### 操作系统级状态机抽象

如果我们武断地假设一个多任务计算机中每个状态机之间都能够严格地相互独立的话, 那么整个多任务系统是容易理解的。操作系统的主要功能就是让这种简单假设看起来仿佛成立, 既让计算机看起来有无限个物理核心, 可以同时持有无限个 `pc`, 既同时运行无限个状态机, 各个状态机又独享各自的地址空间。

但这也使得状态机间的通信要么通过系统调用, 要么隔着进程调度, 所以为了顾全效率, 我们往往要破坏这个状态机独立的假设。如在 `linux` 中获取系统时间时就并没有发生系统调用, 类似的只读的、时序依赖性弱的、单例的非敏感系统信息被 `linux` 操作系统通过 `mmap(...)` 映射到了用户态的某些分页上。

#### `linux` 时钟中断与 `syscall`

如果进程状态机从初始状态 `S0` 一直运行到停机状态 `Sn`, 那么操作系统就没有存在的意义了。实际上操作系统一般通过2类中断方式将运行着的状态机(既进程)当做数据来操作。第一类中断是外部中断, 如时钟中断。在触发此类中断后, 物理 `pc` 被强制跳转到中断处理程序入口点, 之前进程的 `pc` 一般被自动保存在了特定的特权寄存器内。

所以我们可以认为中断是一种特殊的跳转指令, 比一般的跳转指令额外做了一些默认操作, 这些额外操作在各个体系结构中存在一些差别。那么操作系统内核实际就是一个中断处理程序, 如果我们把上文中状态机的状态序列 `{S0, S1, ..., Sn}` 视为程序视角下的宿命, 那么操作系统的功能就是通过将不同状态机的宿命当做数据来操作, 来用单个物理 `pc` 完成对多个时间线的模拟。同时通过对状态快照的更改, 使得进程状态机可以在不同的宿命之间跳转, 既在相互平行的状态序列之间变轨。

**在本文中, 我们常常会将状态机的挂起与恢复视作状态机的停机和初始化, 后启动的状态机以前者的末状态作为自己的初状态。**

前者从初始化到停机的状态序列为 `{S0, S1, ..., Sn}`, 令后者的初状态 `S'0 = Sn`, 则有后者的状态序列为 `{S'0, S'1, ..., S'm-n} = {Sn, Sn+1, ..., Sm}`。假设我们扮演操作系统, 用户进程通过 `syscall` 主动将自己挂起, 挂起期间如果我们在后者的初状态 `S'0` 上改动32个二进制位, 我们就通过 `syscall` 向该进程返回了一个 `int32 value`。该改动可以视作令 `S'0 = mix(Sn, value)`, 也就是使得挂起恢复时状态机的初状态从 `Sn` 变轨到 `mix(Sn, value)`, `mix(S, R)` 定义为向程序状态机 `S`, 写入或返回 `R`。

显然对于这个改动过程, 我们可以将其看做程序状态机对操作系统状态机的读操作, 或是后者对前者的写操作。当然在传统的有状态转移条件的有限状态机模型中, 这种读操作一般被抽象为 `输入序列`, 但该传统抽象根本不足以描述当今计算机的工业实现。首先如果我们要描述外部中断, 则我们状态机的状态拓扑中, 每个节点都必须可以转移到中断状态。因为用户态程序没有关中断的权限, 所以每条机器指令的下一条指令都是可能分叉的。但显然这种数学抽象相当冗余, 因为中断的执行过程大同小异, 而且我们不关心, 希望它在逻辑上不可见。同时, 如果要用一般的有限状态机模型描述简单的程序挂起, 我们就会发现, 在用户态视角下, 我们并无法给出程序恢复的条件, 因为挂起时我们的程序状态机不再进行状态转移。如果我们将计算机整体(包括内核执行时间)视作状态机, 又反而从抽象回到了具体, 导致与本文的动机背道而驰了。所以我们采用了 `无条件有限状态机` 模型, 而对于 `条件状态转移` 的情况, 我们视其为特殊情况, 以 `停机 - 修改末状态 - 形成初状态 - 启动` 的方式处理。虽然条件状态转移在数十年前打孔纸带的古董计算机上状态机的多数情况, 但在当代计算机中, `I/O` 指令不但在所有指令中所占比例极低, 同时必定会被封装在中断(包括 `syscall`)内。在中断例程对 `I/O` 的处理过程中, 用户态程序是被切切实实地停机挂起的, 所以采取这种抽象方式自然而然。

由于 `条件状态转移` 被单独孤立出来, 我们的状态机模型的拓扑结构可以保证总是一条直链, 不带任何分支结构, 因为分支的方向需要通过条件来确定。注意这指的是状态机的状态分支, 而非程序中的 `if(x)` 等语句或者汇编中的 `jnz` 等指令, 因为在无输入的情况下, 状态机执行的第 N 条指令的逻辑分支是可以被提前确定的。在初状态和转移规则固定后, 这些计算是可重复的, 因果固定的。**本文中我们将这些直链形态的状态转移拓扑称为状态机的 `执行流`, 将 `停机 - 修改末状态 - 形成初状态 - 启动` 的行为称为 `变轨`**。同步等待的 `syscall`, 亦或是异步调度的 `co_await`, 本质上都是程序状态机主动停机并约定由外部进行 `变轨` 的过程。`变轨` 过程中包括停机状态的保存, 状态的修改, 以及以此为初状态的新状态机的再启动。

一般操作系统的外部中断处理程序在例程的一开始就把各个寄存器逐个保存到内存中预留的一个结构体内, 且这个结构体一般被设计成进程内存地址空间的一部分, 但对进程本身不可见。由于进程的状态机基本可以被表示为 `寄存器 + 内存`, 那么经过这样一种执行上下文封存之后, 整个进程的当前状态就可以被表示为若干个内存页了, 进一步可以通过按位拼接等手段被抽象地表示为上文所述的一个整数。当然当要挂起该进程时, 操作系统不会真的把整个状态机序列化保存, 其只需永远以引用的方式访问内存, 这样一旦需要切换内存, 只需切换其引用即可, 这些内存引用就是页表。

第二类中断则是内部中断, 它来自 CPU 内部, 既陷阱门。它指在 CPU 处于特定状态时触发的中断。陷阱门一般又细分为两类, 既 `中断指令` 及 `异常`。上文中我们提到中断的主要功能是造成 `pc` 的强制跳转, 这两类内部中断刚好对应无条件跳转和条件跳转。如读内存指令一般情况下就不是一个跳转指令, 但当读不可读内存地址时, 它就变成了跳转指令, 同时切换 CPU 特权级。异常中断就是一种广义上的条件跳转, 其跳转目的地址是操作系统异常处理例程。`syscall` 或调试中断之类的指令则是无条件跳转, 用以提供操作系统和进程之间的进行主动通信功能。操作系统在中断处理程序中将进程状态机上下文保存好后, 直接读进程状态, 则可以知道进程想要调用何种系统功能, 因为系统调用的编号和参数都是该状态的一部分(一般用寄存器传递), 它们与整个进程的状态机一同被挂起到了程序的当前状态快照中。操作系统只需直接改动状态快照, 本质上就是改动了进程的状态整数 `S`, 其结果就是将进程状态机从一个状态序列强行切换到了另一个状态序列, 操作系统正是以该种方式与进程通信的。期间操作系统自身状态机的当前状态也被有目的地更改, 如创建 `fd`, 销毁其他进程, 与设备通信等。

![fsm](static/06f9595ea179460eb80c9978ed9f6ad7.png "系统调用的变轨等价")

上图中4种情况分别为:

- 1. *一般状态序列*
- 2. *将 syscall 表示为一般状态转移*
- 3. *将 syscall 等价表示成了一次变轨*
- 4. *将 fork 系统调用表示成了分叉变轨*

不难发现, 如果采用基本的状态机模型, 则状态转移要么必须考虑外部输入, 要么需要将内核态完全纳入状态机状态之中。如果采用 `变轨` 抽象, 则可以完全隔离外部状态。代价是红色箭头处状态机进行了特殊的状态转移, 由于状态转移函数不再是 `f(x)`, 所以可以认为其是停机后再以新的初状态重启了。被 `g(x)` 和 `h(x)` 隐藏起来的过程, 一般需要保证可以被状态机视作是原子的。

#### `linux execve`

`execve` 系统调用的功能就是将一个进程的状态机置为初始状态 `S0`, 这个初始状态保存于一个 `elf` 文件中。虽然这个操作往往被描述为 `启动一个进程`, 但注意实际上 `pc` 的数量并没有变化。`linux` 下的 `shell` 在启动新进程时要么先 `fork` 要么先 `clone`, 之后再用 `exec` 系列系统调用重置子进程。其第一个操作增加了一个 `pc`, 但第二个操作 `execve` 没有增加 `pc`。

如果我们采取前文中的抽象习惯, 将所有 `syscall` 视作状态机先停机, 将末状态更改后作为新状态新建状态机, 那么 `execve` 就变得极其容易理解了。它最自然最理所应当, 直接把一个文件地址传递给操作系统, 告诉操作系统 “新状态机照着这个初始化” 就完事了。而一般的 `syscall` 则在数学上是 `execve` 的一个特殊情况, 既不对状态机做这种大开大合的 `变轨`, 而是仅根据调用前的末状态修改一个 `eax / rax` 之类的寄存器当做返回值, 或是再改动一些指定的缓冲区, 但保留调用前状态机的大部分状态数据。

几乎所有系统调用数学上都是在帮助状态机在原本不可达的平行状态序列之间变轨, 各系统调用之间唯一的区别就是往哪条轨道上跳以及跳多远。一般的 `syscall` 就变几个字节, `execve` 则变的面目全非。一般情况下 `syscall` 后的新状态机初始状态和调用前状态机的末状态只有些许区别。过大的变动没有意义, 实际应用中用户态程序当然不希望一次系统调用就导致自己的程序面目全非。虽然本文中我们将 `syscall` 前后两个状态序列视作两个独立的状态机, 但其间基本必定存在因果联系, 不会完全独立。因此即使是 `execve` 这种以投胎转世为目的的系统调用, 也会保留前世的一些记忆, 如大部分 `process attributes` 以及没有设置 `FD_CLOEXEC` 标志的 `fd`。`shell` 就是靠这些免疫孟婆汤的 `fd` 实现了管道功能。

#### `linux fork`

`fork` 的主要功能是使操作系统内 `pc` 数量 `+1`。`linux` 将这个系统调用设计为复制整个进程状态机, 但这并不是必要的。`windows` 里就没有这个系统调用或者它的类似功能, 但其核心功能 `pc` 数量 `+1` 是所有现代操作系统都支持的, 既创建进程或线程。

`fork` 后的两个新状态机都经过了 `变轨`, 其整个状态机中唯一不同的几个字节就只有 `fork` 系统调用的返回值。

`windows` 中的 `CreateProcess` api 则兼顾了 `fork` 和 `execve` 的功能, 既 `pc` `+1` 和完全 `变轨`, 却没有提供 `fork` 这种单纯的 `pc` `+1` 的功能。`fork` 虽然在逻辑上更加清晰, 但是在内核中却需要额外的复杂实现(`copy-on-write`、假只读等)。

#### `linux join / exit`

使得 `pc` 数量 `-1`, 和前者是对偶操作。

```plain
     @fork                   @join       @exit
S 0 - S 1 - S 2 - S 3 - S 4 - S 5 - S 6 - S 7
          \                 /
            S'2 - S'3 - S'4
#pc = 1     #pc = 2           #pc = 1         #pc = 0
```

#### `linux yield` 类调用

如 `nanosleep` 或者 `wait` 相关使得进程挂起的系统调用, 其本质是进程将其 `pc` 主动让渡给操作系统, 再由操作系统保证未来归还该 `pc`。

#### 分时复用图灵完备性

对于图灵机而言, 由于多个图灵机的组合也是图灵机, 又因为图灵机可以模拟任何其他图灵机, 所以单个图灵机可以模拟多个图灵机的组合。要在冯·诺依曼结构下实现这一功能, 我们往往需要对物理 `pc` 进行分时复用, 这在80x86到奔腾时代的多任务操作系统中是物理上不可避免的。由于进程内部也是图灵完备的, 所以在进程内部我们也可以实现这类模拟。软件虚拟机就是一个很好的例子, 协程与线程池也是为此而设计的。

简而言之, 在操作系统层面, 页表中的所有进程分页和处理器寄存器状态快照共同组成了程序状态机的整体状态描述。而程序计数器 `pc` 和页表都是为快速操作这个抽象状态机所做的实现优化。其优化手段并不特殊, 如 `fork` 系统调用后所进行的内存分页 `copy-on-write` 优化, 一些操作系统分页分配过程中的 `append-only` 优化, 进程调度和缺页中断设计中的惰性执行优化等都是软件设计中常见的技巧。

**我们把 `syscall` 当做进程状态机的一次停机和启动, 是为了更容易地对协程模式和回调模式建立统一的抽象。**

如果我们将时间片长度设置为无穷大, 则系统只在用户进程主动挂起时才发生调度。部分实时操作系统和批处理操作系统就基于这种设计, 这种假设有助于帮助我们剥离由时钟中断驱动的被动调度所产生的复杂性, 从而在内核态调度和用户态调度之间建立更一般的对应联系。

通过前文我们知道 `execve` 并不特殊, 其数学本质同普通的立即返回一个值的 `syscall` 如 `read` 等无任何区别。由此我们可以将进程内的异步并发技术与上述状态机概念做一些形式上的对应。

- 异步回调对应 `execve`, `execve` 通过 `elf` 文件显式指定新状态机的初状态, 异步回调则通过回调函数指定新状态机的初状态。
- `co_await` 对应一般 `syscall`, `syscall` 通过系统调用前的末状态指定新状态机的初状态, `co_await` 则通过 `std::coroutine_handle` 指定新状态机的初状态。

当调度器在建立新状态机时对初状态稍作修改, 状态机就跳到了本无法自主到达的平行状态序列。这种状态序列的变轨就是状态机与 `外部` 的 `通信`。

`外部` 在计算机科学中往往是一个笼统的概念。但考虑了分时复用的图灵完备性, 则可以严格定义 `外部`。既当一个状态机通过分时复用模拟多个子状态机时, 前者则为后者的 `外部`。当一个子状态机需要 `通信` 时, 一定是因为他的内部状态转移不足以产生其需要的信息, 其希望自身状态被 “意外” 地改变。这种 “意外” 只能通过使其原本的状态转移函数暂时失效来达成, 既通过 `变轨` 达成。

---

[后篇](detail?id=2311)

来说两句吧