浅谈协程

type

status

date

slug

summary

达夫设备

了解了协程的定义，就是实现问题了

来看一个 fib 协程


generator<int> fib() {
    int a = 1, b = 1;
    yield a;
    yield b;
    while(true) {
        int c = a + b;
        yield c;
        a = b;
        b = c;
    }
}

对 fib 进行调用，会返回斐波那契数列 1，1，2，3，5，8…

在 yield 时，协程被暂停，再次调用，协程被恢复

现在我们要实现类似的效果，核心无非两点，如何暂停和如何恢复

一种简单的协程实现是达夫设备，它是一个状态机，状态机上的状态对应每个 yield 的位置

首先通过 static 变量存储状态（也可以通过一个外部的协程结构体来在任意地方存储），接着，yield 时直接 return 返回控制权，调用时通过 switch + goto 跳转回之前的位置，也就是上次 yield 后的位置，这就恢复了状态：


int fib() {
    static int state = 0;
    static int a = 1;
    static int b = 1;
    static int c = 0;

    switch (state) {
        case 0:
            state = 1;
            goto s0;
        case 1:
            state = 2;
            goto s1;
        case 2:
            state = 3;
            goto s2;
        case 3:
            goto s3;
    }

s0:
    return a;
s1:
    return b;
s2:
    while(true) {
        c = a + b;
        return c;
        s3:
        a = b;
        b = c;
    }
}

扩展

有了基本的协程后，就可以谈谈其它语言中的 generator、async / await、goroutine / virtual thread 等实现了

对于 generator 和 async / await 模式，实际上和我们上面的实现是类似的，都是一个状态机。但它们通过编译器来生成了这堆繁琐的部分，作为语言的一个语法来提供，可以说是真正能用的协程。例如这样一段 Rust 的 generator 代码


#![feature(generators, generator_trait)]
use std::ops::Generator;

use std::pin::Pin;

fn main() {
    let mut gen = ||{
        yield 1;
        yield 2;
        yield 3;
        return 4;
    };

    let mut pin = Pin::new(&mut gen);
    for _ in 0..4 {
        println!("{:?}", pin.as_mut().resume(()));
        // Yielded(1)
        // Yielded(2)
        // Yielded(3)
        // Complete(4)
    }
}

编译器会生成类似这样的实现，和我们前面的达夫设备基本基本没区别：

剩下的一些，就基本属于是对协程的「扩展」了

首先就是所谓的调度器，前面 generator 的模式是没有调度的，或者说，是用户手动控制调度，自己决定何时运行哪个协程，而且这里调度一个协程，就是执行它这个函数。

而 async / await 模式就会有调度器，例如一个函数在 await 另一个 async 函数，此时如果该函数并没有执行完成，await 这里就需要等待，控制流会被切换出去（类似 generator 模式的 yield），调度器会进行调度

在设计更复杂的情况下，调度器的工作会多很多，例如如果不是采用 return 和直接 call 来转移所有权，那就可能需要通过直接跳转的方式（插入汇编或 setjmp/longjmp 等）来进行协程的所有权转移。以及可能有更复杂的调度策略决定运行哪一个协程

南京大学操作系统课程的其中一个实验就是实现这个程度的协程

M2: 协程库 (libco)

我们在《操作系统》课程中学习了线程：只需要 create 和 join 两个 API，我们就能创建和管理线程。我们也知道，线程的创建和执行需要操作系统的帮助：程序就是状态机，如果执行死循环，这个状态机就 “卡死” 了。那么，我们能在一个状态机内，实现多个状态机 (类似线程切换) 的效果吗？

https://jyywiki.cn/OS/2024/labs/M2.md

接着是一些协程设计上的问题。前面我们转移所有权的时候，yield 是定向地转移回所有权到 caller 上，因此可以用 return 实现。但更多场景是 yield 时协程 A 希望暂停自己的同时定向恢复协程 B 的运行，但又不希望 A 直接 call B（如果 B 也 call A，就会造成无限递归）。

一种实现是基于调度器的，称为非对称协程，A 返回到调度器，要求调度器 call B。这会带来一些性能损失，且不太能保证实时性

另一类是对称协程，需要一些特殊的指令，让 A 能够直接切换到 B，且 B 返回后直接回到了调度器，这个过程对调度器是不知情的，这种设计架空了调度器，实现上更加复杂，但性能更好更加灵活

设计上另外一个重要的区别是协程的栈帧，也就是有栈协程和无栈协程。前面实现的协程是无栈协程，它们两个的区别从概念上讲，只有是否保存完整栈帧。

从实现角度来看，无栈线程的「状态」只有局部变量，转移所有权的位置等，对于该协程来说都是固定的，所以每个无栈协程的帧通常是一个定制的结构体（当然编译器帮你实现了），这个结构体就直接代表了整个无栈协程的所有状态，例如前面 fib 的例子，它的这个结构体可能就是这样的


struct fib_state {
    int a;
    int b;
    int c;
    int state;
}

而有栈协程对于帧的保存，无论是哪个协程，都是直接申请一大块内存，将其作为函数的调用栈来使用，一切状态都保存在内部。从这个角度来讲，有栈协程更接近普通函数


struct co {
    byte stack[STACK_SIZE];
}

在使用上的一个重要区别是，有栈协程可以在任意处挂起，包括嵌套函数。而无栈协程不可以，因为它的帧结构只保存了它自己特定的那几个的状态，所以无法恢复到嵌套函数内部。这使得有栈协程在使用上和普通函数几乎没有区别，就像线程一样

实现上的差异这也体现出无栈协程更加紧凑，开销更小，因为它只保存了必要的状态。而有栈协程需要保存的状态更多，而且通常是有些浪费的（当然也可以让这个栈更小，但要考虑动态扩展的问题）

现在对于各种语言的协程实现就很清晰了，generator 和 async / await 就是编译器层面上实现的无栈协程，以语法糖的方式来提供。而 goroutine / virtual thread 等更类似线程，这是因为他们是有栈协程，还实现了抢占式的调度器来控制协程的执行，当然这里对于这种抢占式设计是不是协程也有不少争议，因为看起来他们从根本上就违背了协程的「协作式」这一想法