协程

在常用的并发模型中多线程、多进程、分布式是最普遍的，不过近些年来逐渐有一些语言以first-class或者library的形式提供对基于协程的并发模型的支持。其中比较典型的有Scheme、Lua、Python、Perl、Go等以first-class的方式提供对协程的支持。那到底协程有什么魅力使得它赢得一些人的青睐。

更容易理解的编程模型

生产-消费

相比于传统的多线程和线程锁构建的生产-消费者模型，协程可以提供更文明礼让、更优雅的实现方式(snippet1)：

状态机

传统的状态机中总是需要一些共享的状态变量去跟踪状态，每次进入状态机都是从入口重新开始，而协程可以将需要的共享变量局部化打包在一个闭包(closure)中，而且每次进入状态机也勿须从入口重新开始，可以直接从上次挂起的地方开始。

generator

generator是用来简便生成iterator的手段，它是一种特性受限的协程。

异步I/O

进行过异步I/O或者事件驱动模型编程的程序员对callback应该很熟悉，这种编程模型需要将执行逻辑顺序的代码强行拆分成多个片段(通常是多个函数)，这个过程大多数人应该都会觉得反感，有lambda的语言会稍微好受一些，但对C这类语言来讲简直就是梦魇。

而协程的出现可以很大程度上解决这个问题，它允许我们以“同步”方式调用I/O阻塞接口，从而使得代码的编写与同步调用的代码几无二异，这样再也不用写那么多callback。

更容易理解的并发模型

与多线程、多进程等并发模型不同，协程依靠user-space调度，而线程、进程则是依靠kernel来进行调度。线程、进程间切换都需要从用户态进入内核态，而协程的切换完全是在用户态完成，且不像线程进行抢占式调度，协程是非抢占式的调度。通常多个运行在同一调度器中的协程运行在一个线程内，这也消除掉了多线程同步等带来的编程复杂性。同一时刻同一调度器中的协程只有一个会处于运行状态，这一点很容易从前言得出。

一个通常的误解是协程不能利用CPU的多核心，通过利用多个线程多个调度器，协程也是可以用到CPU多核心性能的。

协程的定义

协程最早的描述是由Melvin Conway于1958给出“subroutines who act as the master program”(与主程序行为类似的子例程)，此后他又在博士论文中给出了如下定义：

· the values of data local to a coroutine persist between successive calls(协程的局部数据在后续调用中始终保持)

· the execution of a coroutine is suspended as control leaves it, only to carry on where it left off when control re-enters the coroutine at some later stage(当控制流程离开时，协程的执行被挂起，此后控制流程再次进入这个协程时，这个协程只应从上次离开挂起的地方继续)。

一些实现

setjmp/longjmp

大多数程序员应该或多或少接触过C编程语言，不过对于setjmp/longjmp可能印象不会太深刻，因为这对接口的“邪恶”程度比goto有过之而无不及，以至于大多数教程都只会出于完整性的考虑介绍goto并顺带介绍setjmp/longjmp，然后就会像香烟包装上的“吸烟有害健康”一样忠告我们不要使用它们。

实际上在许多项目中都会使用到这对接口，不过大多数情况下项目的架构人员都会将它隐藏起来提供一种高层的功能，比如做异常机制。那这对接口怎么实现协程？要弄明白这个问题我们得再次审视这对接口的功能。

goto作为一个关键字可以用来在一个函数体内做任意跳转，而setjmp/longjmp却可以在整个程序内做任意跳转。这意味着goto不能处理函数堆栈，而setjmp/longjmp可以在函数堆栈间跳转，而函数堆栈是在程序被“实例化”为进程后才建立起来的，所以goto在编译期即可确定跳转上下文，而setjmp/longjmp则必须在运行时才能确定跳转上下文。

来看一段示例代码(snippet2):

编译后运行，不出意外地会得到输出:

101

setjmp(jb)的返回值被判断了两次，第一次为0，调用了foo，第二次在foo中调用longjmp(jb, 101)将101带回给sjret，打印出这个值。尽管跨越了main到boo再到foo的调用栈，longjmp还是直接把我们带回到了setjmp(jb)的地方，这正是setjmp/longjmp的“邪恶”之处，它才不管作用域、内存堆、调用栈这些的，它就是这么任性。

到这里让我们联想一下协程的定义，在子例程中suspend，resume子例程时从上次suspend的地方继续执行，我们对snippet2进行一些改造(snippet3)：

编译后运行，不出意外地会得到:

101

102

是时候发挥我们的想象力了，现在假设我们可以并且已经对snippet2的代码进行了精心的封装，使它看起来不像上面那么糟心。

我们分析下snippet2的流程：

在20行处setjmp(jb1)，此时返回值为0，调用boo，进入foo函数，在7行处setjmp(jb2)，此时返回值为0，执行longjmp(jb1, 101)，foo函数被suspend，回到main函数，21行处setjmp(jb1)此时返回值被置为101，打印出来。

26行处setjmp(jb1)，此时返回值为0，执行28行longjmp(jb2, -1)，再次进入foo函数，7行处setjmp(jb2)此时返回值被置为-1，执行10行处longjmp(jb1, 102)，foo函数再次被suspend，回到main函数，27行处setjmp(jb1)，此时返回值被置为102，打印出来（值得注意的是代码中setjmp都是只执行了一次，而具有两次不同的返回值，且两次都从返回处开始执行）。

这个过程与协程的定义是不是相符呢？但这一切的发生还是有点玄妙，setjmp/longjmp到底做了什么？我们需要挖掘更多的细节。

让我们得到snippet2的汇编代码(本文的环境是一个i386的linux gcc4.8.4)：

objdump -d snippet2 > snippet2.dump

看看main函数：

figure 1

gdb跟入：

figure 2

可以看到在代码0x80484d1处，$0x804a100(就是jb1的内存地址)被推入当前栈顶寄存器(esp)指向的内存地址，然后call 8048350<_setjmp@plt>，一个事实就是call指令会将pc(eip)推入调用者的栈，这一点我们可以在gdb中跟进setjmp看到：

figure 3

其中0x080484dd就是figure1中mov %eax, 0x1c(%esp)的指令地址。再看看setjmp到底做了什么(snippet4)：

可见setjmp就是将几个重要的寄存器的内容保存了下来，包括调用处的ebp(栈基址)/esp(栈顶址)，它并没有拷贝整个栈，意思就是说如果用一个函数封装setjmp这将会是一件愚蠢的事情，等到这个函数调用返回时它的栈都会被丢弃。安全且正确的做法是使得setjmp到longjmp之间的调用栈都是连续的。

值得注意的是movl 0(%esp), %ecx和xorl %eax, %eax，前者将调用处的pc(eip)(这里就是0x080484dd)保存到ecx，后者将eax置为0。看到figure1中0x080484dd处，就是将寄存器eax的值放入到esp+0x1c的内存处(函数栈的生长是顺着地址减小的方向)，后面则将esp+0x1c内存处的值与0比较，这正是我们在main中做的比较。可以猜想longjmp就是将setjmp记录的这些寄存器值还原，将指定的一个值存入eax，然后整个程序的流程再次回到0x08048dd处。

且看看longjmp(snippet5)：

至此setjmp/longjmp的实现细节已暴露无遗。我们也了解到setjmp/longjmp所做的保存策略，对于一个真正可用的协程肯定是不够的，所以我们还需要做很多封装。

达夫设备

达夫设备(Duff's device)由Tom Duff在1983年发现，它本意用来手工做循环展开(loop unrolling)(然而在如今的编译技术下它已经没什么卵用了)。但在协程的研究中，它还有卵用。

问题的背景是这样的，达夫要将16位的单元组拷贝到一个内存映射输出寄存器，他的第一版的代码看起来像这样(snippet6)：

然后他想到如果count总是能被8整除的话，可以将这段循环展开成如下模样(snippet7)：

这么做是因为循环展开后可以减少CPU流水线中条件分支(conditional branching)预测带来的负作用。但是这么做并不能处理count不能被8整除的情况，于是他将代码再次进行了改进(snippet8)：

第一眼看到这段代码要是觉得它能通过编译，那要么是C写得不够多，要么是对C编译器十分了解了。

这段代码的精妙之处在于switch进行匹配之后可以直接进入到do...while循环的内部任一语句开始循环。这使得我们从任何结构处挂起、再次进入成为可能。我们借此构造一个类似python3中range的接口(snippet9)：

编译并运行，不出意外我们将得到如下输出：

0 2 4 6 8

这里range函数的行为和协程的定义是相符的，与上例一样，要将达夫设备变成一个真正可用的协程还需要做更多的封装，此例中比如range函数的可重入，栈的保存等，引用2展示了一个完整可用的实现。

System/V context control

在操作系统的领域有两个比较知名的系统级“协程”接口族，一个是Microsoft Windows®的纤程(fiber)，一个是POSIX的用户上下文(ucontext)。由于一些复杂的原因，本文选择ucontext介绍。

ucontext本来是System/V的API，后来加入到了POSIX标准。这个接口族包含有四个接口，它们的签名如下：

其中的ucontext_t在GNU C Library实现中内存布局如下：

接口1用来初始化一个context，接口2用来将一个context和一个函数绑定，接口3用来切换到一个context，接口4用来切换到一个context，并保存当前的context。在引用3中有对以上接口和数据类型的详细说明。

借由ucontext构造一个“奇怪”的python3中的range函数(snippet10)：

编译运行，不出意外我们将得到如下输出:

0 2 4 6 8

显而易见的是这离一个真正可用的协程也还需要一些封装，在引用8中即有一例展示了云风大神基于ucontext封装的一个非对称(asymmetric)协程库。

协程的分类

对称(symmetric)与非对称(asymmetric)

协程依控制转移机制分为对称与非对称，对称协程中所有的协程都只有一种控制转移语义，即将控制转移至其他协程，此中的协程在这种机制下都是对称的。而非对称协程中调用者协程与被调用协程处于不对称的地位，和函数调用一样，被调用协程挂起之后控制总是会转移到调用者协程。

在理论上已经证明对称协程与非对称协程有着同等的表达能力(见引用4)，但实际应用中非对称协程更加友好。

栈式(stackful)与非栈式

协程依挂起与恢复的深度分为栈式与非栈式，栈式协程可以在嵌套调用中挂起并恢复，而非栈式协程只能在同级调用中挂起并恢复，典型如python的

上示为一个类似python中xrange的generator function，如果我们想让gfrange每次通过一个嵌套函数来挂起是办不到的(snippet12)：

我们必须且只能在gfrange这个函数体中使用yield(snippet13)：

可见python的generator function实际上是一种非对称非栈式协程。

引用

1.谈一谈setjmp/longjmp(http://blog.lucode.net/skills/talk-about-setjmp-and-longjmp.html)

2.Coroutines in C(http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html)

3.System/V contexts(http://www.gnu.org/software/libc/manual/html_node/System-V-contexts.html)

4.Revisiting Coroutines(http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf)

5.Duff's device(https://en.wikipedia.org/wiki/Duff%27s_device)

6.Loop unrolling(https://en.wikipedia.org/wiki/Loop_unrolling)

7.branch(https://en.wikipedia.org/wiki/Branch_(computer_science))

8.a cloudwu's asymmetric-coroutine(https://github.com/cloudwu/coroutine)

尾声

友情提示：引用1中的示例代码还是有问题的，在main函数中setjmp(ctx)并不能平衡env的栈。

关于协程的话题远不止这些，很多“文章”的深度和广度也远胜本文，期以本文为匣中三尺水，且为山路荡平荆棘。

本文作者：胡震国（点融黑帮），技术部工程师。爱玩游戏，偏爱RPG，仙剑和古剑的脑残粉。