无栈协程(上)

原创

王鹏程1990

发布于 2023-03-09 20:50:32

5240

发布于 2023-03-09 20:50:32

无栈协程

有栈协程是基于函数切换上下文恢复的思路实现被中断协程的继续执行，但是这个上下文里面有返回地址，即下一条指令的地址，所以当程序发生改动重新编译生成，指令地址有可能发生改变，这种对于需要重新编译生成发布的发布场景支持并不友好，会因为程序指令地址的变化导致协程执行流的错乱。这时另外一种不基于上下文恢复的协程机制提供了一种新的思路。

达夫设备

在比较早期的时候，有一种程序的优化机制叫做循环展开，所谓循环展开是通过将循环进行部分展开，既减少了指令数，又充分调用执行单元的并行处理的能力；这是一种牺牲程序尺寸换取程序执行速度的优化机制，现在我们很少用到这种机制，一个是编译器帮我们做了这种优化，一个是我们现在执行单元处理速度快，很少遇到这样的性能问题。

1983年，一个叫Tom Duff的程序员利用这种方式实时播放动画的代码段进行了优化，优化前如下所示：

send(to, from, count)
	register short *to, *from;
	register count;
	{
		do
			*to = *from++;
		while(--count>0);
	}

这是一段常见的存储器之间的复制操作，当时性能瓶颈出现在这段代码位置处，而达夫基于汇编语言常用的，“在复制时最小化判断数和分支数”的基本思想，将上面代码改写成如下形式：

send(to, from, count)
register short *to, *from;
register count;
{
	register n = (count + 7) / 8;
	switch (count % 8) {
	case 0: do { *to = *from++;
	case 7:	*to = *from++;
	case 6:	*to = *from++;
	case 5:	*to = *from++;
	case 4:	*to = *from++;
	case 3:    *to = *from++;
	case 2:    *to = *from++;
	case 1:    *to = *from++;
	     } while (--n > 0);
	}
}

看起来是不是很奇怪，没关系，变换一下你们就认识了：

send(to, from, count)
register short *to, *from;
register count;
{
    register n = (count + 7) / 8;
    switch (count % 8) {
        case 0: *to = *from++;
        case 7: *to = *from++;
        case 6: *to = *from++;
        case 5: *to = *from++;
        case 4: *to = *from++;
        case 3: *to = *from++;
        case 2: *to = *from++;
        case 1: *to = *from++;
    }
    while (--n > 0) {
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
    }
}

代码本身并不复杂，但对于我们来说更加关注的是，switch和do-while语句的嵌套写法，为什么程序可以这样写？

关于switch语句

在编程实践中，switch里面的condition-state命中一个条件之后，就会找到一个case向下运行，直到遇到一个break，这个过程可能会跨越多个case，这就是switch的“掉落”特性；事实上经常有很多bug都是因为这种掉落特性引发的，所以我们的编程实践都推荐每个case过后，都有一对大括号来包裹程序块并用break进行收尾。如下所示：

int function() {
    switch(condition-state){
        case state1: {
              statement-1;
              break;
        }
        case state2: {
              statement-2;
              break;
        }
        ... ...
        default: {
              statement-n;
        }
    }
}

但是实际我们查阅C17草案，我们可以看到case语句实际属于labeled statement（带标签的语句）如下:

在C语言中，switch实际上是一个转移表，而case则是一个标签——用于给一个或者一组指令进行命名，而标签本身并不会改变指令的控制流，而只是提供了一个程序的执行位置；基于此，形成无栈协程一个朴素的思想：是否我们可以通过给指令打标签的方式，告诉下一次指令需要从哪个标签开始执行，其中需要的变量我们存起来就好了？这样既解决了上下文切换很多不必要的操作，也解决了程序修改后指令地址改变导致的无法恢复的问题。

无栈协程的Demo实现

一个协程库要解决以下几个问题：

1）如何在协程阻塞调用时归还执行权限？

2）如何选择合适的协程进行调度？

3）如何把执行权限交给被调度的协程？

4）如何让被调度的协程从被中断的地方继续执行？

在前面讨论中，可以认为协程是一个函数的调用，那么协程的恢复无非是从调用中断处继续执行，而对于无栈协程不需要进行上下文恢复，则核心是通过存储标签保证下次调度能从预期的地方继续执行，那么就有：

1）针对问题一，当协程阻塞等待时，直接保存下一步返回时，所想执行指令的位置的标签，然后直接return，则实现了执行权限交还给主调方；

2）针对问题二，主调方拿到执行权限之后，可以根据自己策略去进行调度，这个协程库提供相应接口支持即可；

3）针对问题三，因为协程被认为是一次函数调用，则执行权限交给对应被调度协程本质上调用协程的接口即可，即通过接口调用实现执行权限的传递；

4）如何实现中断指令流的继续，执行流程的恢复包括两个部分，一个是局部变量的值的恢复，一个是从被中断的位置处继续执行。针对前者，我们可以将函数内局部变量全部迁出来用全局结构缓存，在调度到协程时通过参数形式传递进去，对于后者我们可以通过标签记录下函数中断位置的标签，并且通过switch-case找到中断的部分继续下去，于是有如下demo代码片段：

int function(void) {
    static int state = 0;
    static int i = 0;
    switch(state){
        case 0: goto LABEL0;
        case 1: goto LABEL1;
        case 2: goto LABEL2;
    }
    LABEL0:
    for(i=0;i<10;++i){
        state = 1;
        return i;
        LABEL1:
        state = 2;
        i+=1;
        return i;
        LABEL2:
        state = 3;
    }
}

int main() {
    int i =function();
    printf("i:%d\n",i);
    i = function();
    printf("i:%d\n",i);
    i = function();
    printf("i:%d\n",i);
    i = function();
    printf("i:%d\n",i);
    i = function();
    printf("i:%d\n",i);
    return 0;
}

分析代码，我们有：

1）function函数通过标签被划分为三个部分；

2）function函数通过静态局部对象state记录程序执行到哪一步了；

3）通过静态局部对象记录上次执行时相关参数的信息；

运行代码我们有：