电子大神的日记本,供应链专家的功夫茶盘,在这里记录、分享与共鸣。

登录以开始

最轻量级的C协程库:Protothreads

文/Lych

协程的好处不用再多说,作为与函数调用/返回相对的概念,它使我们思考问题的方式经历一场变革。现在我们关注的是C,由于C本身的特质,将协程引入其中将会是一 个挑战。无数先驱已经为这个目标抛了头颅洒了热血,于是我们有了libtask之类。而这里提到的,是一个堪称最轻量级的协程实现:Protothreads(主页:http://www.sics.se/~adam/pt/)。所谓最轻量级,就是说,功能已经不能再精简了,几乎就是原语级别的。——确实,这种最简带来了一些使用上的繁琐不便,但在打退堂鼓之前,先来看看它的优点吧:

  1. 不依赖任何库(包括C标准库和OS,是的,可以在bootloader里使用它),甚至本身都算不上个“库”,事实上整个实现都只有.h文件。
  2. 充上一条,.h文件共也只有5个而已,总共的有效行数也就100数量级(版本1.4)。
  3. 接着补充,那些行中大部分也都是宏定义,所以使用该库导致程序的膨胀基本可以忽略不计。
  4. 每个协程的内存开销只有一个指针那么大。

说实话,这种形式的所谓“库”的最佳使用方式,是去参考其源代码然后直接借鉴到自己的程序中。这么点代码就能实现协程的功能,其原理也就一层窗户纸。事实上Protothreads使用了两种方式来实现协程,你可以选择其中一种方式:

  1. 用switch语句来实现。
  2. 用GCC扩展语法来实现。

前者通用性好但低效,使用起来也有更多不便,后者相反。默认是前者,本人倾向于后者(后者MinGW也支持的),这归咎于用惯了GCC,而且后者从思想上确实更加简明,没有trick的意味。这里的原理叙述也以后者为主。

这个如洪水猛兽般的“扩展语法”,其实就是:可以把label地址保存到变量。label就是goto的那个label,就是那个人人喊打的goto。如下:

begin:
    printf("This is a message\n");
    /* goto begin; -- 我们本来应该这么用 */
    void *p = &&begin;
    goto *p;

&&不是取地址又取地址^_^而是扩展语法,这个运算符用于label,表示取其在代码段中的地址,就是说获得一个指针。指向代码段的指针,第一反应是函数指针,但这个不是,因为它并不指向一个函数的入口,而是指向其腹部。这种指针类型C中是不存在的,GCC也不想把事情搞大,整出个新数据类型来,于是用void *通吃了。这样这个值就可以当普通数据一样摆弄来摆弄去,最后靠goto *p,来从其他任何地方跳到这个地址来执行。

或许还记得,C的goto是不能跨越函数边界的,从理论角度这叫确保了单入单出的结构化编程,从底层实现角度,则保证了栈帧不混乱,即:如果goto到另一个函数的代码段中,但另一个函数的栈帧并没有准备好,栈顶还是当前函数的栈帧,那么目的函数在访问局部数据时候就会发生混乱。这种原来不可能发生的混乱,在这种扩展语法的支持下成为了可能。这是需要注意的一点,在使用扩展的goto语句的时候也要注意不要越过函数边界(当然,如果你BT到了解栈帧协议并试图手工建立栈帧的话,就当我没说^_^)。

Protothreads库对协程的实现,说来也简单,且看一个协程函数的示意:

int foo(struct pt *p) {
    PT_BEGIN(p);
    ……        /* 代码段1 */
    PT_YIELD(p);
    ……        /* 代码段2 */
    PT_END(p);
}

这个函数,在每次重入这个协程的时候都要被调用,靠这些PT_开头的宏,函数可以确定每次被调用时应该执行函数体的哪一部分。比如调用两次foo的话,第一次会执行代码段1,第二次则执行代码段2。原理如下:

结构体struct pt其实只有一个void *型成员,就是传说中那“一个指针的开销”,每个协程都有个对应的此物。该指针在初始化的时候被置NULL(由另一个宏PT_INIT在别处完成),在foo函数中,PT_BEGIN会检查这个指针,若是NULL,则表明是第一次启动该协程,什么也不做。接下来遇到了PT_YIELD,即协程挂起原语。此宏内部定义一个label,并立即将该label保存进pt结构体中。这样,此处可能有多种方式进入,一是顺序执行到此,二是从别处goto过来。这所谓别处,其实就在PT_BEGIN。如果它检查到pt不为空,则立即goto过去。现在PT_YIELD根据到达此处的方式做进一步判断,如果是自然执行到此,该挂起了,则立即reeturn出函数。否则,则是刚刚重入回来,继续执行下边的代码段2。这个判断是如何进行的?——靠一个标志位,PT_BEGIN每次被调用都首先置一个标志,而PT_YIELD则在label之前清除这个标志。这样,在label之后,PT_YIELD就可以据此判断,若标志没了,则是自然执行到此,若标志存在,则是从PT_BEGIN处goto过来的。——说穿了,就是setjmp的一个超轻量级版。

至于PT_END,其作用除了清除pt指针以外,主要是为了返回协程的状态。实际上PT_YIELD中的return也是带值的,之所以foo函数要声明为int,就是为了每次调用foo都能得到该协程当前的状态,是挂起了、结束了,还是中途退出了等等。
应该注意到了一点,就是既然每次重入协程都要重新调用foo函数,则说明foo函数中留不下任何状态,如果定义局部变量,则其内容都会丢失。嗯……这就是我指的“繁琐与不便”的主要所在吧,你需要让一切协程状态都以外部变量的形式存在,典型做法是封装成一个结构体,作为该函数的第二个参数。嗯,毕竟,C是接近底层的语言,让它自动背着你创建好多变量的副本,或者好多个协程局部的堆栈,还是不如你自己精确掌控对每块内存的使用,不是吗?毕竟不能用脚本语言的眼光来看C ^_^

现在,用这种方式创建了好多协程,那么接下来用一个简单的方式让它们运转起来,这个轮转调度简单得难以置信:

while (1) {
    foo1(p1);
    foo2(p2);
    ...
    foon(pn);
}

这就是调度器的主循环,只需要往复依次调用每个协程的入口函数即可。

以上叙述了Protothreads库的核心内容,实际上该库还包含了动态协程建立、协程间通信等设施,对于一个如此单薄的库来说,还是相当令人惊喜的。最后为了再次强调其单薄,在此列举一下其所有的头文件:

        lc-addrlabels.h        用GCC语法扩展实现的协程基础
        lc-switch.h            用switch语句实现的协程基础
        lc.h                  该文件存在的意义仅仅为了选择以上两者之一
        pt.h                 基于lc.h的协程设施的真正实现
        pt-sem.h               协程间通信(信号量)的实现
博主
mydows@gmail.com
mydows's Blog
mydows
点击跳转