TAOCP 学习记录 (2) - 协程? 管道? 纤程?

今天读了 The Art of Computer Programming (TAOCP) 第一卷的协程部分, 感觉很有意思, 用这篇博客记录一下.

“小兄弟” Subroutine

首先先提一下协程 (Coroutine) 的小兄弟, Subroutine. Subroutine 这个词虽然并不常用, 但是它的概念相信大家都非常熟悉. 我们经常会使用它的有微妙差异的”同义词”, 比如函数 (Function), 方法 (Method) 等等.

在 Subroutine 的语境里, 我们常常会有一个 Main Routine, 这个主流程包含了整个流程框架, 在执行任务的过程中, 调用各种 Subroutine 来执行任务的细节. 所以, routines (不管是 main 还是 sub) 的调用关系构成了一个不对等的层级结构.

“平等”的 Coroutine

和 Subroutine 不太一样的是, Coroutine 之间是比较”平等”的, 这个平等体现在哪里呢? 对 Coroutine 有一点了解的朋友 (i.e. 从前的我) 可能会说, Coroutine 之间会互相调用, 没有一个 Main Routine 的概念. 其实这还没有说到点子上, 毕竟 A, B 两个函数互相调用这种情况也是经常出现的.

我们在回想一下, Routine A 在调用另一个 Routine B 的时候, A 和 B 的一个重要差别在于, B 执行完之后, A 会继续执行. A 的执行周期包含了 B, 我们会说 B 函数返回 (return) 了, B 存在在世界上的证据 (e.g. 栈桢, 寄存器) 被某个黑暗力量吞噬了.

反观 Coroutine 之间的调用则不同. Coroutine 没有返回的概念, 它们只会友好地让对方从上次暂停的地方 (上下文) 继续执行. 每个 Coroutine 的上下文都会保存的好好的, 直到时间再一次给它机会.

Coroutine 在 MIX 中的实现

MIX 是 TAOCP 中使用的一种虚拟的机器. MIXAL 是为它定制的机器语言. 在 MIXMIXAL 中实现 Coroutine 非常简单, 只需要几行.

# LABEL      OP       OPERAND

# Main Routine
             JMP    CO1_E
    CO1     STJ      CO2X
   CO1X      JMP    CO1_E
    CO2     STJ      CO1X
   CO2X      JMP    CO2_E
   
# Coroutine 1
  CO1_E
#  Do something
             JMP      CO2
#  Do something

# Coroutine 2
  CO2_E
#  Do something
             JMP      CO1
#  Do something

MIXAL 简介

MIXAL 比较容易理解. LABEL 这一列是助记符, 用来表示这一行代码的地址; OP 这一列是操作符; OPERAND 这一列是操作数.

JMP 指令和 x86 的汇编语言中的跳转类似, 会从指定的地方取指令, 继续执行. 注意在 MIX 中, 这个指令还会把本来应该执行的下一条指定地址存到一个指定的寄存器 J 中.

STJ 指令则是将寄存器 J 中的值保存到指定地址.

Coroutine 的实现解释

在对 MIXAL 有了一定了解之后, Coroutine 的实现就很好理解了. 实际上我们为每一个 Coroutine 定义了三个入口, 下面用 Coroutine 1 来举例子.

CO1_E 物理起始入口, 是这个 Coroutine 实际代码的开始位置.
CO1 表面的代理入口, 除了 Main Routine 调用外, 所有其他地方的调用都应该使用这个入口.
CO1X 继续入口, 它负责从 Coroutine 上次暂停的位置之后继续执行.

从上面的代码我们可以看到

Main Routine 通过 JMP CO1_E 首次调用了 Coroutine 1
Coroutine 1 执行完一部分之后执行 JMP CO2 来调用 Coroutine 2.
CO2 这一行会先通过 STJ CO1X 来将寄存器 J 中的值保存到 CO1X. 用于上一次 JMP就是 Coroutine 1 中执行的, J 中保存的值就是 Coroutine 1 继续执行的话要运行的第一行代码.
CO2这一行执行完之后, 会执行下面的 JMP CO2_E 来执行 Coroutine 2 的逻辑. Coroutine 2 执行完一部分之后又运行 JMP CO1 来让 Coroutine 1 来继续执行.
在CO1像步骤 3 中那样暂存完 Coroutine 2 的下一步的代码地址之后, CO1X 这行的代码虽然看上去是 JMO CO1_E, 实际上已经被步骤 3 修改了. 它会继续执行 CO1未完成的使命.

到这里, Coroutine 就已经实现了.

代码即数据

这里很有意思的一点是, 在步骤 3 中, 我们动态的修改了代码. 这是因为代码实际也是数据.

当然, 允许随意修改 “代码” 有时候不是很安全. 现代的内核会给内存加上 flag 表示这个段内存能不能被执行. 不过这个想法很厉害.

和 Coroutine 相似的概念

管道

Coroutine 和 *nix 系统中的管道实际上有点像. 比如这个例子

1	cat data \| seq ...

上面这条指令中的各个部分可以类比成一个协程. 第一个协程获取到一定数据后交给第二个协程, 这样依次类推.

Spark / Java Stream

既然和管道相似, 那么 Spark 这中类型的模型好像也有那么几分相像之处.

Multi-Pass

Multi-Pass 程序就是先对原数据执行一个 pass, 获得一份数据, 然后在对这个数据执行下一个 pass, 不断继续下去直到完成. 听上去和 Map-Reduce 有点像.

N 个 Coroutine 构成的程序, 大部分情况下都可以转化成 N-Pass 的程序. 这样转化的好处是更容易理解, 坏处是每个 Pass 的结果都得全量记录下来.

当然, 也不是所有情况都能互相转化的. 如果 Coroutine 之间需要非单向通讯, 比如两个 coroutine 下象棋, 就不能转化成 2-Pass 的代码. 反过来看, 如果一个 pass 需要依赖上一个 pass 的全量结果, 也不能转化成 coroutine. 就好像 Spark 遇到 groupBy 这样的运算子, 也是需要 shuffle 一下的.

纤程

说了这么多协程, 我们再简单聊聊纤程 (Fiber) 到底是个啥. 纤程简而言之就是用户态的线程, 它没有操作系统线程这么高的上下文切换以及内存的开销, 所以可以同时创建很多个.

我个人感觉 Golang 中的 goroutine 实际上是纤程 (虽然它的名字和 coroutine 长得很像), 因为 goroutine 之间并没有显式地将 CPU 移交给对方, 而是由调度器负责为 goroutine 分配对应的物理线程. goroutine 之间使用 channel 同步/通讯是代码层面上的实现.

瞎扯

目录