最近看到有人讨论stackless python，看到有部分讲协程在python中的实现，结合Linux的相关知识我这里小结一下。

从函数的角度看，

协程避免了传统的函数调用栈，几乎可以无限递归。

从线程的角度看，

协程没有上下文切换，几乎可以无线并发；

协程在用户态进行显式的任务调度，可以把异步操作转换成同步操作，也意味着无需额外的加锁。

所谓的“微线程”、纤程、协程，甚至用户态线程，都可以理解为一码事，只是实现和概念的区别。

调用栈

我们传统上理解的函数，概念上也叫做子例程，是通过调用栈来传递调用关系的。协程则是比子例程更一般化的概念。子例程的调用是LIFO，它的启动位置是唯一入口，且只能返回一次；而协程允许有多个入口，且可以返回多次(yield)，你可以在特定的地方暂停和重新执行它。

上下文切换

上下文切换最早是指进程的上下文切换(context switch)，它发生在内核态。内核调度器会对每个CPU上执行的进程进行调度(scheduling))，以保证每个进程都能分到CPU时间片。当一个进程的时间片用完，或被中断后，内核将保存该进程的运行状态(即上下文)，将其存入运行队列(run queue)，同时让新的进程占用CPU。进程的上下文切换包括内存地址空间、内核态堆栈和硬件上下文(CPU寄存器)的切换，所以代价很高(具体参阅UTLK进程一章)。

由于进程切换开销大，所以设计了线程。Linux 2.6内核的clone()系统调用已经支持创建内核级线程，且发布了内核线程库pthread。在同一进程内的线程可以共享进程的地址空间，线程仅需要维护自己的寄存器、栈和线程相关的变量。不过内核线程的调度仍然需要由内核完成，这需要进行用户态和内核态的模式切换，至少包括堆栈和内存映射的切换。而且，不同进程之间的线程切换，有可能会还会导致进程切换，所以代价还是不小。

而协程始终运行在一个线程之内，完全没有上下文切换，因为它的上下文是维护在用户态开辟的一块内存里，而它的任务调度是在代码里显式处理的。目前Linux上可选用的纤程库是GNU Portable Threads(Pth)。

任务调度

进程、线程和协程的设计，都是为了并发任务能够更好的利用CPU资源，他们最大的区别即在于对CPU的使用上(任务调度)：如前文所述，进程和线程的任务调度由内核控制，是抢占式的；而协程的任务调度在用户态完成，需要在代码里显式的把CPU交给其他协程，是协作式的。

由于我们可以在用户态调度协程任务，所以，我们可以把一组互相依赖的任务设计成协程。这样，当一个协程任务完成之后，可以手动进行任务调度，把自己挂起(yield)，切换到另外一个协程执行。这样，由于我们可以控制程序主动让出资源，很多情况下将不需要对资源加锁。

示例

最后，引用一个stackless里的例子，文中给了个python的写法，我照猫画虎写了个c风格的：

#include <stdio.h>

void ping();

void pong();

void ping(){

printf("ping\n");

pong();

}

void pong(){

printf("pong\n");

ping();

}

int main(int argc, char *argv[]){

ping();

return 0;

}

很明显，这是一个循环调用，运行后很快就会把调用栈耗尽，抛出Segmental Fault。 但是，我们可以用协程的风格把它修改一下，主要是试一下ucontext.h里的这几个函数，据说Pth也是用它们实现的：

#include <ucontext.h>

#include <stdio.h>

#define MAX_COUNT (1<<30)

static ucontext_t uc[3];

static int count = 0;

void ping();

void pong();

void ping(){

while(count < MAX_COUNT){

printf("ping %d\n", ++count);

// yield to pong

swapcontext(&uc[1], &uc[2]);

}

}

void pong(){

while(count < MAX_COUNT){

printf("pong %d\n", ++count);

// yield to ping

swapcontext(&uc[2], &uc[1]);

}

}

int main(int argc, char *argv[]){

char st1[8192];

char st2[8192];

// initialize context

getcontext( &uc[1] );

getcontext( &uc[2] );

uc[1].uc_link = &uc[0];

uc[1].uc_stack.ss_sp = st1;

uc[1].uc_stack.ss_size = sizeof st1;

makecontext (&uc[1], ping, 0);

uc[2].uc_link = &uc[0];

uc[2].uc_stack.ss_sp = st2;

uc[2].uc_stack.ss_size = sizeof st2;

makecontext (&uc[2], pong, 0);

// start ping-pong

swapcontext(&uc[0], &uc[1]);

return 0;

}

这时候，ping pong的循环调用并不依赖于调用栈，所以也就不会有调用栈溢出的风险了。而且手工调度协程，静态变量也可以无锁访问。不过manual上说getcontext, setcontext, makecontext, swapcontext这系列函数并没有被posix接受，为了兼容性考虑，推荐使用pthread库……我想大概一般能够用coroutine解决的问题，用pthread也能解决，至多就是多加一些锁呗。而如果要使用coroutine的话，代码编写者必须自己理清所有的调度逻辑，可能容易滋生bug，就跟setjmp和longjump似的，虽然威力强大，但一般人不推荐 :)

协程实现的基础

协程可以认为是一种用户态的线程，与系统提供的线程不同点是，它需要主动让出CPU时间，而不是由系统进行调度，即控制权在程序员手上。

既然看成是用户态线程，那必然要求程序员自己进行各个协程的调度，这样就必须提供一种机制供编写协程的人将当前协程挂起，即保存协程运行场景的一些数据，调度器在其他协程挂起时再将此协程运行场景的数据恢复，以便继续运行。这里我们将协程运行场景的数据称为上下文。

在linux里，有getcontext和swapcontext等接口来获取当前的上下文数据和切换上下文。那如果没有提供相应的接口，又该如何来实现呢？

其实说到底，保存下上文数据，不外乎就是保存下当前运行的栈空间的数据，还有cpu各个寄存器相应的值。只要我们能够将其保存下来，在特定的时刻恢复回去就可以了。

有人用c提供的接口setjmp和longjmp来实现协程的切换和恢复，但这里要介绍另外一种方式，即用汇编来保存/恢复cpu寄存器的值。

用汇编的方式依赖于特定的平台，这里举例的是i386 32位的*nix平台。

在开始贴代码前，要先说一个概念–栈帧。

ia32程序用程序栈来支持过程调用。机器用栈来传递过程参数、存储返回信息、保存寄存器用于以后恢复，以及本地存储。为单个过程分配的那部分栈称为栈帧。下图描绘了linux下栈帧的通用结构。栈帧的最顶端以两个指针界定，寄存器%ebp为帧指针，而寄存器%esp为栈指针。当程序执行时，栈指针可以移动，因此大多数信息的访问都是相对于帧指针的。

栈帧结构

这里我们可以看到，在调用一个函数前，都会先将各个参数、调用者在被调用函数返回时执行的下一条指令的地址–返回地址压栈，被调用函数在开始前会将%ebp的值保存，然后将当前%esp的值赋予%ebp。弄明白帧指针和栈指针的作用，以及返回地址等如何通过%ebp来获取的话，对下面保存当前上下文的汇编代码理解比较有帮助。

struct mcontext {

/*

* The first 20 fields must match the definition of

* sigcontext. So that we can support sigcontext

* and ucontext_t at the same time.

*/

int mc_onstack; /* XXX - sigcontext compat. */

int mc_gs;

int mc_fs;

int mc_es;

int mc_ds;

int mc_edi;

int mc_esi;

int mc_ebp;

int mc_isp;

int mc_ebx;

int mc_edx;

int mc_ecx;

int mc_eax;

int mc_trapno;

int mc_err;

int mc_eip;

int mc_cs;

int mc_eflags;

int mc_esp; /* machine state */

int mc_ss;

int mc_fpregs[28]; /* env87 + fpacc87 + u_long */

int __spare__[17];

};

struct ucontext {

/*

* Keep the order of the first two fields. Also,

* keep them the first two fields in the structure.

* This way we can have a union with struct

* sigcontext and ucontext_t. This allows us to

* support them both at the same time.

* note: the union is not defined, though.

*/

sigset_t uc_sigmask;

mcontext_t uc_mcontext;

struct __ucontext *uc_link;

stack_t uc_stack;

int __spare__[8];

};

struct mcontext {

/*

* The first 20 fields must match the definition of

* sigcontext. So that we can support sigcontext

* and ucontext_t at the same time.

*/

int mc_onstack; /* XXX - sigcontext compat. */

int mc_gs;

int mc_fs;

int mc_es;

int mc_ds;

int mc_edi;

int mc_esi;

int mc_ebp;

int mc_isp;

int mc_ebx;

int mc_edx;

int mc_ecx;

int mc_eax;

int mc_trapno;

int mc_err;

int mc_eip;

int mc_cs;

int mc_eflags;

int mc_esp; /* machine state */

int mc_ss;

int mc_fpregs[28]; /* env87 + fpacc87 + u_long */

int __spare__[17];

};

struct ucontext {

/*

* Keep the order of the first two fields. Also,

* keep them the first two fields in the structure.

* This way we can have a union with struct

* sigcontext and ucontext_t. This allows us to

* support them both at the same time.

* note: the union is not defined, though.

*/

sigset_t uc_sigmask;

mcontext_t uc_mcontext;

struct __ucontext *uc_link;

stack_t uc_stack;

int __spare__[8];

};

ucontext结构体主要关心的为uc_mcontext和uc_stack这两个成员，其中uc_stack指向一段内存，这段内存做为协程的运行栈；而uc_context为mcontext类型，各个成员保存着CPU同名的寄存器值。

int getmcontext(mcontext_t*);/*保存当前上下文的声明*/

/*保存当前上下文的汇编实现*/

.globl GET

GET:

movl 4(%esp), %eax

movl %fs, 8(%eax)

movl %es, 12(%eax)

movl %ds, 16(%eax)

movl %ss, 76(%eax)

movl %edi, 20(%eax)

movl %esi, 24(%eax)

movl %ebp, 28(%eax)

movl %ebx, 36(%eax)

movl %edx, 40(%eax)

movl %ecx, 44(%eax)

movl $1, 48(%eax) /* %eax */

movl (%esp), %ecx /* %eip */

movl %ecx, 60(%eax)

leal 4(%esp), %ecx /* %esp */

movl %ecx, 72(%eax)

movl 44(%eax), %ecx /* restore %ecx */

movl $0, %eax

ret

/*保存当前上下文的汇编实现*/

.globl GET

GET:

movl 4(%esp), %eax

movl %fs, 8(%eax)

movl %es, 12(%eax)

movl %ds, 16(%eax)

movl %ss, 76(%eax)

movl %edi, 20(%eax)

movl %esi, 24(%eax)

movl %ebp, 28(%eax)

movl %ebx, 36(%eax)

movl %edx, 40(%eax)

movl %ecx, 44(%eax)

movl $1, 48(%eax) /* %eax */

movl (%esp), %ecx /* %eip */

movl %ecx, 60(%eax)

leal 4(%esp), %ecx /* %esp */

movl %ecx, 72(%eax)

movl 44(%eax), %ecx /* restore %ecx */

movl $0, %eax

ret

上述分别是保存上下文的C接口声明和汇编实现。根据第4行汇编代码可以看出，GET函数所需要的参数值被保存到%eax，之所以根据4(%esp)来寻址，是因为这时候栈指针指向的是保存返回地址的内存地址。接着将各个寄存器的值保存到参数值指向的mcontext结构体，结合下struct mcontext以及代码里的移位看就可以了，这里就不多说了。唯一比较难理解的可能就是%eip寄存器值的获取了。由于这时候要保存的是调用GET函数的过程的上下文，这时候%eip寄存器保存的并不是调用GET函数过程的下一条指令的值，GET函数栈帧的返回地址才是调用GET函数过程返回后应该往下执行的下一条指令，因此可以看到上面汇编代码18行是将栈指针指向内存保存的值做为%eip的值保存起来。

.globl SET

SET:

movl 4(%esp), %eax

movl 8(%eax), %fs

movl 12(%eax), %es

movl 16(%eax), %ds

movl 76(%eax), %ss

movl 20(%eax), %edi

movl 24(%eax), %esi

movl 28(%eax), %ebp

movl 36(%eax), %ebx

movl 40(%eax), %edx

movl 44(%eax), %ecx

movl 72(%eax), %esp

pushl 60(%eax) /* new %eip */

movl 48(%eax), %eax

ret

.globl SET

SET:

movl 4(%esp), %eax

movl 8(%eax), %fs

movl 12(%eax), %es

movl 16(%eax), %ds

movl 76(%eax), %ss

movl 20(%eax), %edi

movl 24(%eax), %esi

movl 28(%eax), %ebp

movl 36(%eax), %ebx

movl 40(%eax), %edx

movl 44(%eax), %ecx

movl 72(%eax), %esp

pushl 60(%eax) /* new %eip */

movl 48(%eax), %eax

ret

至于恢复上下文的SET函数，要说的就是它是如何来改变%eip寄存器的值。根据上面第17行的汇编代码，它只是将新的%eip的值压栈而已，并不是直接赋予ip寄存器。我们这里再看一下当执行到ret后会怎么样。ret可以等效于这句指令–pop %eip。当SET函数返回后即将刚刚压栈的新的%eip的值恢复到ip寄存器当中去了。

使用汇编实现的GET和SET函数，实际上就可以进行上下文的保存和恢复了。但是要实现协程这还不够，协程跟线程一样，都是提供一个函数做为入口，那我们还需要为协程构建好调用其函数入口的准备，即参数压栈，栈指针的指向，还有返回地址的保存等。

void makecontext(ucontext_t *ucp, void (*func)(void), int argc, ...)

{

int *sp;

sp = (int*)ucp->uc_stack.ss_sp+ucp->uc_stack.ss_size/4;

sp -= argc;

sp = (void*)((uintptr_t)sp - (uintptr_t)sp%16); /* 16-align for OS X */

memmove(sp, &argc+1, argc*sizeof(int));

*--sp = 0; /* return address */

ucp->uc_mcontext.mc_eip = (long)func;

ucp->uc_mcontext.mc_esp = (int)sp;

}

void makecontext(ucontext_t *ucp, void (*func)(void), int argc, ...)

{

int *sp;

sp = (int*)ucp->uc_stack.ss_sp+ucp->uc_stack.ss_size/4;

sp -= argc;

sp = (void*)((uintptr_t)sp - (uintptr_t)sp%16); /* 16-align for OS X */

memmove(sp, &argc+1, argc*sizeof(int));

*--sp = 0; /* return address */

ucp->uc_mcontext.mc_eip = (long)func;

ucp->uc_mcontext.mc_esp = (int)sp;

}

第6到第9行实现了用户指定参数的入栈，第11行将返回地址指定为0.实际上linux实现的makecontext接口会根据ucontext结构体uc_link指向的值来进行设定，可以让其返回到另外一个协程继续执行。

12、13行分别设定了ip寄存器和栈指针的值，这就指定了协程开始运行的指令地址和所使用的栈空间。

makecontext函数的调用往往会伴随着SET函数的调用，由于makecontext已经指定好用户传进来的函数入口地址和栈空间的起始地址了，而SET函数返回后就会开始执行用户指定的函数了，协程开始了。

就一个简单实现的语言来说，如果有并发需求，像之前说的直接使用宿主环境的线程，加上必要的调度控制即可实现需求，但如果要求比较高，触发到上篇讲的线程和单线程异步的相关缺陷，一个较普遍的解决办法是采用用户态并发，即对于os内核来说，进程只有一个或少数几个线程，而对于源语言来说，接口和使用线程别无二致，由虚拟机实现对这些“线程”的调度，虚拟机的实现则可以一定程度简化、优化调度算法和内存占用，从而达到高并发高效率的目的。这个过程中一般使用到协程技术

协程这个概念是1963年提出来的，最早的出发点并不是针对并发（那时候的os应该还没有线程），而是另一种编程模式，相对子例程而言。子例程通俗说就是函数，现在我们写程序，已经习惯了函数的调用是在栈中，有调用者和被调用者的区别，还有递归调用，而协程模型中，各协程虽然看上去是一个函数，但彼此之间是对等的，没有谁调用谁的关系；子例程的调用由于是一个栈结构，则需要严格按照后进先出的方式来调用和返回，而协程的生命周期则是自由的，按照实际需要来结束（返回）

如果查阅一些资料，可能会看到说另一个区别是，协程是一个多入口多出口的子例程，但这个入口和出口跟一般子例程还是有区别，一般子例程是“调用”和“返回”，而一个协程的出入更合适的说法是“切换”，举个简单的生产者-消费者的例子（代码摘自wiki）：

var q := new queue

生产者协程：

loop

while q is not full

create some new items

add the items to q

yield to consume

消费者协程：

loop

while q is not empty

remove some items from q

use the items

yield to produce

这里的yield表示切换协程，生产者和消费者都是一个无限loop，生产者往队列q里面尽可能增加新任务，然后切换到消费者执行，消费者处理完q里面所有任务后，切换回生产者执行，可以拿这个例子和函数调用、线程并发比较下：

如果采用函数调用的方式，上述代码直接改yield切换为调用是行不通的，因为函数调用必须有调用者和被调用者，如果produce里面调用了consume，consume里面又去调用produce，则无限递归，因此必须考虑实际情况，consume作为produce的子例程，produce的yield改为call，consume的yield改为return，这样形成一个从属关系即可，毕竟是要先produce才能consume。函数调用和协程的另一个区别是，虽然每次函数调用都有自己的局部环境，但随着return切换，局部环境会销毁，而协程的局部环境是跟协程的生命周期走的，实际上上面这段代码在一个不支持协程的语言里面实现的时候，相当于建立两个协程的数据环境，yield则是直接goto到对应代码执行

协程和线程很类似，事实上很多时候协程被认为是用户态调度的线程，这个说法勉强也算对，但由于协程出现早，如果咬文嚼字的话不应该用线程来描述协程，应该说线程是协程的替代品。考虑上面的例子，如果用线程实现就非常简单了，比如yield改为sleep一段时间，主动放弃cpu，os会帮我们在两个线程切换，或者如果q是一个内核对象，则对q的出入操作可以由os来阻塞调度，这样代码就能进一步简化了

从这个角度说，协程在程序中的实现跟线程在os中的实现是很类似的，一个协程包含一个自己的数据环境（对应线程的栈环境），执行代码（对应线程的入口函数），声明周期（线程入口函数的调用和返回）。线程调度依赖os，协程则可以自己调度，但是，要实现自己调度需要一个非常自由的goto（线程调度实际也是切换上下文环境后直接jmp），而在基于函数调用模式的语言中实现协程，还是跟线程的os一样使用一个中央调度器。或许唯一的区别是，线程的标准调度是被硬件强行中断的，而协程是自己交出控制权

和函数，线程类比，则一个协程的“多入口多出口”也能很好的理解，比如如下协程代码：

func f():

for i from 1 to 10:

return i

如果f是个函数，则上面这段代码就相当于return 1，但如果是协程，则依次调用f的时候，会返回1到10，也就是说每次return会返回给调用者当前的i，同时当前执行状态也被保留，下次调用时从上次的状态继续，显然这是一个状态机，因此协程可以用一个对象实现（python代码）：

class F:

def __init__(self):

self.i = 1

def __call__(self):

if self.i > 10:

raise CrEnded()

ret = self.i

self.i += 1

return ret

f = F()

while True:

try:

print f()

except CrEnded:

break

f是一个状态机，重载它的()运算（__call__），就能像上面一样反复调用了，协程最终结束后，再调用会抛出CrEnded异常，当然也可以有其他类型的表示结束的方法。python中的协程（generator生成器）实际就是类似这样实现的

而如果用线程来实现这个例子，由于线程是os调度的，要想f受控运行，需要通过通讯来控制：

func f():

for i from 1 to 10:

recv_from_queue()

send_to_queue(i)

f在一个线程执行，通过一个queue和外界通讯，每recv到一个请求，就将i send回去。换句话说，线程的多入口多出口是通过通讯和阻塞实现的

协程通过自己主动yield放弃执行来调度，一个协程本质就是一个自动机，虽然对一个自动机而言，整个流程是比较清晰的，但是如果业务比较复杂，手工写自动机也是比较繁琐的，比如说，我们要从若干数据库和表中分别读取一个用户的各种信息，组成一个总信息结构，每个信息的读取可能阻塞的，则需要多次yield，用协程：

user = User(id)

trans = get_info_a(user.id) //提交info a的请求

yield trans

user.info_a = trans.result

... //其他info

这里为了写清楚一些，get_info_a提交请求后返回一个事务对象trans，然后将trans在切换时以“返回值”的形式返回，当结果回来时，外部控制代码填写trans.result，然后继续执行。当然完全不必这么麻烦，python直接用这种语法：

user.info_a = yield get_info_a(user.id)

...

提交请求并yield返回trans，yield本身是个表达式，其值为继续执行时传入的参数

这样一来，就可以在协程很方便的写同步代码了，但是，外部代码依然要自己实现为异步的，仅仅是协程的自动机代码写起来紧凑而已，不至于像单线程异步那样凌乱。而更严重的问题是，如果我要实现函数调用，比如一个函数a调用b，a的其他地方和b都可能阻塞，那么改成协程的话，就不得不建立a和b两个协程，它俩还是对等的，这样写代码还是比较麻烦，至少不符合现在流行的线程+函数的习惯了

发布时间: 9年前【代码相关】115人已围观【返回】【回到顶端】

转载：个人转载请注明文章出处 "www.itarticle.cc-IT技术类文章收集&分享"。

很赞哦！ (1)