协程-无栈协程(上)

ronald7个月前职场2010

无栈协程

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

达夫设备

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

    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(带标签的语句)如下:

image-20211004130249653.png

    在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)通过静态局部对象记录上次执行时相关参数的信息;

    运行代码我们有:

[centos ~/test/label_test]$ ./main       
i:0
i:1
i:2
i:3
i:4

    通过运行结果,我们能看到,每次接口的执行实际都是从上次函数调用的中断的地方开始执行的,但是这样的代码并不能满足工业级的应用场景,因为:

    1)使用静态变量去保存函数的执行状态,使得这个接口是不可重入的

    2)我们也不能在每次写代码的时候去定义标签,指定跳转的位置

    3)使用标号去进行跳转会导致程序结构修改会牵涉大规模的代码改动

    ......

    虽然我们可以对上述进行优化和封装,但是在这我们并不准备过多赘述,后面我们则直接看一个开源的无栈协程库-protothread

    未完待续...

参考资料

        函数调用过程

        ucontext manual pages

        swapcontext() — Save and restore user context

        云风协程库源码

        编程沉思录——云风协程库源码分析

        编程沉思录——libco源码分析

        libco源码地址

        libco性能对比

        达夫设备

        Label As Values标签变量

        ucontext族函数的使用及原理分析

        FSTENV

        Intel x86 MXCSR Register

        SSE-维基百科

        libco源码注释版


相关文章

协程-有栈协程(coroutine)

协程-有栈协程(coroutine)

概述    后台架构的微服务化,原先的单体应用被按照功能模块切分为若干进程组承担,此种架构演化带来的收益诸如:单进程复杂度降低,代码维护成本降低发布影响范围缩小,发布灵活性提升计算资源更精准的分配... ...    但是这种架构带来的另外的变化就是,原先由单进程承载的事务,可能涉及几个甚至十几个进程;在这种情况下,采...

协程-无栈协程(下)

无栈协程库——protothread    ProtoThread源码如下所示:#define LC_INIT(s) s = 0; #define LC_RESUME(s) switch(s) { case 0: #define LC_SET(s)...

协程-有栈协程(libco)

协程-有栈协程(libco)

libco      还有一个广泛使用的协程库就是libco,libco是被由微信开发并大规模应用的协程库,自2013年起稳定运行于数万台微信后台机器上;具备以下特性:高性能,号称可以调度千万级协程在IO阻塞时,可以自动切换,利用hook技术+epoll事件循环实现阻塞逻辑IO化改造支持嵌套创建既支持共享栈模式也支持独立栈模式提供超时管...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。