Protothreads 详解

Protothreads 是一个 C 语言的极简协程库，实现了无栈非对称协程。

概念

极简

寥寥 100 行代码，就用两种方式实现了协程 yield / resume ，并以此为基础实现了信号量同步机制。

无栈

无栈协程，也称为共享栈协程，在同一个调度器上运行的协程使用调度器的栈作为调用栈；
有栈协程，也称为独立栈协程，每个协程创建时分配一定的内存作为协程栈，有一定内存浪费和 OOM 风险，协程切换时性能比共享栈慢一些。

非对称协程

对称协程，每个协程的地位是平等的，调度器可以直接切换到任意协程；
非对称协程，协程返回后必然切换到其创建者协程。

前置知识

switch 的另类用法

以下代码是合法的吗？

#include <stdio.h>

int main()
{
    int code = 1;

    switch (code) {
    case 0:
        return -1;
    case 1:
        for (int i = 0; i < 2; i++) {
    case 2:
            printf("i=%d\n", i);
        }
    }

    return 0;
}

简而言之，switch case 中的代码可以是“不完整”的吗？

既然这么问了，那答案也呼之欲出了：可以！

以上代码可以通过编译并输出

i=0
i=1

用 goto 替换 switch

以下代码和上一节的代码等效

#include <stdio.h>

int main()
{
    void *s = &&def;
    goto *s;

abc:
    return -1;
def:
    for (int i = 0; i < 2; i++) {
ghi:
        printf("i=%d\n", i);
    }

    return 0;
}

惊不惊喜？意不意外？

没想到 goto 和 label 竟然还有这种用法， && 除了在 C++ 里表示 move 语义，竟然还能在 C 里表示对 label 的引用！

实现

Yield / Resume

Protothreads 用 swtch /或 goto 实现了 yield /和 resume。

假设我们有两个需要并行运行的函数 thread1 和 thread2 ，我们用变量的设置模拟它们的交互

int loop_count = 10;
int thread1_continue = 0;
int thread2_continue = 0;

void
thread1() {
    while (1) {

        // TODO: yield and wait until thread1_continue = 1;

        thread1_continue = 0;
        thread2_continue = 1;
    }
}

void
thread2() {
    while (1) {
        thread1_continue = 1;

        // TODO: yield and wait until thread2_continue = 1;

        thread2_continue = 0;
    }
}

并行情况下，thread2 和 thread1 会通过变量设置交互运行（忽略线程缓存可见性问题和原子问题），直到运行次数达到 loop_count 退出。

怎么让两个函数在同一个线程中运行呢？

核心诀窍就是等待的时候不能阻塞线程，要返回“调度器”。

Protothreads 中的调度器简单粗暴：最外层套一个 while 死循环

while (1) {
  thread1();
  thread2();
}

那 yield / resume 的实现也呼之欲出了：yield 直接 return，需要 resume 就用 switch 跳过 return

int
thread1(int *status) {
    switch (*status) {
    case 0:
        while (1) {

            // yield and wait until thread1_continue = 1;
            if (thread1_continue != 1) {
                return PT_WAITING;
            }
            *status = 1;
    case 1:

            thread1_continue = 0;
            thread2_continue = 1;
            break;
        }
    }
    return PT_ENDED;
}

使用 status 作为参数配合 switch 来进行 resume；
每次完成一次可能的 wait 代码就会重置 status 的值；
如果需要 wait 就通过返回值表明在 wait 状态，实现 yield 语义。

这个例子的完整代码如下

#include <stdio.h>

#define PT_WAITING 0
#define PT_EXITED  1
#define PT_ENDED   2
#define PT_YIELDED 3

int thread1_continue = 0;
int thread2_continue = 0;

int
thread1(int *status) {
    switch (*status) {
    case 0:
        while (1) {

            // yield and wait until thread1_continue = 1;
            if (thread1_continue != 1) {
                return PT_WAITING;
            }
            *status = 1;
    case 1:

            thread1_continue = 0;
            thread2_continue = 1;
            break;
        }
    }
    return PT_ENDED;
}

int
thread2(int *status) {
    switch (*status) {
    case 0:
        while (1) {
            thread1_continue = 1;

            // yield and wait until thread2_continue = 1;
            if (thread2_continue != 1) {
                return PT_WAITING;
            }
            *status = 1;
    case 1:
            thread2_continue = 0;
            break;
        }
    }
    return PT_ENDED;
}

int main()
{
    int status1 = 0;
    int status2 = 0;

    while (1) {
        int ret1 = thread1(&status1);
        int ret2 = thread2(&status2);
        if (ret1 == PT_ENDED && ret2 == PT_ENDED) {
            break;
        }
    }
    return 0;
}

信号量

信号量就是一个计数器，在上文已经实现了 wait_until 语义的情况下，很容易实现信号量机制

直接搬运 Protothreads 的代码即可

#include "pt.h"

struct pt_sem {
  unsigned int count;
};

#define PT_SEM_INIT(s, c) (s)->count = c

#define PT_SEM_WAIT(pt, s)  \
do {                        \
  PT_WAIT_UNTIL(pt, (s)->count > 0);        \
  --(s)->count;             \
} while(0)

#define PT_SEM_SIGNAL(pt, s) ++(s)->count

其他

核心内容就是以上提到的部分，剩下的就是封装成宏，大家可以自行下载浏览代码，并无难点。

问题

resume 时的上下文

在 Protothreads 的实现中，resume 实际是重新运行函数，没有保存上下文变量，这会在一些场景下出错。

简单的，比如把 while(1) 换成 for (int i = 0; i < loop_count; i++) ，在 resume 后是 i 被重置为 0，无法正确运行得到结果。

如果要实现这个功能，需要把上下文声明并保存到参数 pt 中。