雨润年华

电子DIY爱好者的家园

ProtoThreads的原理,分析及应用

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

不依赖任何库(包括C标准库和OS,是的,可以在bootloader里使用它),甚至本身都算不上个“库”,事实上整个实现都只有.h文件。
充上一条,.h文件共也只有5个而已,总共的有效行数也就100数量级(版本1.4)。
接着补充,那些行中大部分也都是宏定义,所以使用该库导致程序的膨胀基本可以忽略不计。
每个协程的内存开销只有一个指针那么大。
说实话,这种形式的所谓“库”的最佳使用方式,是去参考其源代码然后直接借鉴到自己的程序中。这么点代码就能实现协程的功能,其原理也就一层窗户纸。事实上Protothreads使用了两种方式来实现协程,你可以选择其中一种方式:

用switch语句来实现。
用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              协程间通信(信号量)的实现

  源码包中的 example-buffer.c 包含了可运行的完整示例,我就不全部贴了。整体框架就是一个 asymmetric coroutines,包括一个主协程 driver_thread和两个子协程 producer 和 consumer ,其实不用多说大家也懂的,代码非常清晰直观。我们完全可以通过单线程实现一个简单的事件处理需求,你可以任意添加数十万个协程,几乎不会引起任何额外的系统开销和资源占用。唯一需要留意的地方就是没有一个局部变量,因为 protothreads 是 stackless 的,但这不是问题,首先我们已经假定运行环境是单线程的,其次在一个简化的需求下也用不了多少“局部变量”。如果在协程出让时需要保存一些额外的状态量,像迭代生成器,只要数目和大小都是确定并且可控的话,自行扩展协程上下文结构体即可。

  当然这不是说 protothreads 是万能的,它只是贡献了一种模型,你要使用它首先就得学会适应它。下面列举一些 protothreads 的使用限制:

· 由于协程是stackless的,尽量不要使用局部变量,除非该变量对于协程状态是无关紧要的,同理可推,协程所在的代码是不可重入的。

· 如果协程使用 switch-case 原语封装的组件,那么禁止在实际应用中使用 switch-case 语句,除非用 GNU C 语法中的标签指针替代。

· 一个协程内部可以调用其它例程,比如库函数或系统调用,但必须保证该例程是非阻塞的,否则所在线程内的所有协程都将被阻塞。毕竟线程才是执行的最小单位,协程不过是按“时间片轮度”的例程而已。

  官网上还例举了更多实例,都非常实用。另外,一个叫 Craig Graham 的工程师扩展了 pt.h,使得 protothreads 支持 sleep/wake/kill 等操作,文件在此 graham-pt.h。

本原创文章未经允许不得转载 | 当前页面:雨润年华 » ProtoThreads的原理,分析及应用

评论