libtask协程调度

libtask 是一个 c 实现的协程库, 里面通过一两千行代码就实现了协程调度, 延迟调度以及 channel 的功能, 实在很酷, 后面会根据代码来看具体的实现。它的作者 Russ Cox 同时也 golang 作者之一, 由此可以意淫可能 golang 的调度和实现有很多 libtask 的影子。

看完里面的实现后, 注释了一下, 有需要的可以参考:

https://github.com/git-hulk/libtask-annotation

一. 初识

在开始介绍源码实现之前,我们先对 libtask 有个简单理解。

scheduler

Schedulerlibtask 的调度器,不断从运行队列头部取出任务(协程), 如果有就切换到到这个协程运行,直到队列为空就退出。

这个调度器是不是很简单,就是一个队列处理器。

Note: libtask 代码里面把协程当作一个任务(task), 我们后面看代码 task 称呼为协程就好了。

二. 疑惑 & 答案

那么问题来了:

Q1: 如果当前执行的协程不主动让出 cpu, 不是要等到这个协程执行完?

A1: 这个是这样。

Q2: 当前协程是怎么出让 cpu 的?

A2: 这个在 libtask 的实现很简单, 直接把当前协程放到队尾,切换回调度。 因为调度器是从对头到队尾逐一调度,所以相当于让其他协程写执行。

三. 实现

协程在一些语言已经原生支持,对于协程虽然了解, 但没看到代码仍然感觉不踏实,所以有了下面的内容。

3.1) 例子

学习一个陌生的东西来说,个人第一反应还是先看看它是怎么使用的, 再了解怎么实现的,不然直奔代码往往觉得太抽象。当然天赋过人的另说。

#include <stdio.h>
#include <stdlib.h>                                                                                                                    
#include <unistd.h>
#include <task.h>

void
counttask1(void *arg)                                                                                                                  
{
    int i;
    for( i = 0; i < 5; i++) {                                                                                                          
        printf("task1: %d\n", i);                                                                                                      
        taskyield();                                                                                                                   
    }
}

void    
counttask2(void *arg)                                                                                                                  
{
    int i;
    for( i = 5; i < 10; i++) {                                                                                                         
        printf("task2: %d\n", i);                                                                                                      
        taskyield();                                                                                                                   
    }       
}

void    
taskmain(int argc, char **argv)                                                                                                        
{
    taskcreate(counttask1, NULL, 32768);                                                                                               
    taskcreate(counttask2, NULL, 32768);                                                                                               
}

这个例子的逻辑很简单, 在 taskmain 函数里创建两个协程, 结果是两个协程依次打印数值。

这个例子也顺带验证了我们上面提到那两个问题:

  1. libtask 添加协程,是直接放到队列尾部,调度器依次处理。
  2. 调用 yield 出让 cpu, 会放到运行协程队尾, 实现cpu 出让

3.2) 调度实现

看过上面代码, 问题很多的你,一定会问上面 c 代码为什么看起来入口是 taskmain, 而不是 main?

答案就在 task.c 里面, 为了防止贴代码占用太多空间, 我们只列出核心实现:


// 主协程 static void taskmainstart(void *v) { taskname("taskmain"); taskmain(taskargc, taskargv); } int main(int argc, char **argv) { ... // 创建一个主协程 taskcreate(taskmainstart, nil, mainstacksize); // 开始协程调度 taskscheduler(); ... }

可以看到 main 函数已经在 task.c 实现, 里面主要做了两件事情:

  1. taskcreate 创建一个协程, 处理函数就是调用 taskmainstart, 这个里面调用了 taskmain

  2. `askscheduler 开始进行协程调度

接着来看看 task.c 的 taskscheduler 是如何实现的:

static void
taskscheduler(void)
{
    ...
    for(;;){
        // 当前除了系统携程外没有其他协程, 退出
        if(taskcount == 0)
            exit(taskexitval);

        // 从队列头部开始处理
        t = taskrunqueue.head;
        if(t == nil){
            fprint(2, "no runnable tasks! %d tasks stalled\n", taskcount);
            exit(1);
        }
        // 从就绪队列里面去掉这个协程
        deltask(&taskrunqueue, t);
        t->ready = 0;

        // 协程调度计数 +1
        tasknswitch++;
        taskdebug("run %d (%s)", t->id, t->name);

        // 切换到刚拿到的协程
        contextswitch(&taskschedcontext, &t->context);

        taskrunning = nil;
        // 如果协程执行完毕,释放对应的结构数据
        if(t->exiting){
            // 系统协程不计数
            if(!t->system)
                taskcount--;

            // 把最后一个协程移动到退出协程的位置, 重复利用
            i = t->alltaskslot;
            alltask[i] = alltask[--nalltask];
            alltask[i]->alltaskslot = i;
            free(t);
        }
    }
}

我们看到调度函数进来开始就进入死循环, 然后开始从就绪协程队列头部处理协程, 直到没有协程可以处理就退出。

3.3) 梳理

我们分析过了核心代码之后, 再回来梳理一下刚才的例子:

main函数 --> 创建 taskmain 协程 --> taskscheduler 开始调度 --

--> 调度 taskmain协程, 调用 taskmain 添加用户协程 --> 调度用户协程 

--> 退出

task.c 里面还会有其他一些管理协程数据结构的函数,比较简单,这里不进行说明。有看不懂的地方,可以看看代码注释。

四. 上下文切换

除了实现逻辑外, 切换协程的核心函数是 getcontext, setcontext, makecontext, swapcontext, 这几个函数主要用来获取和修改当前线程的上下文信息。这些上下文信息实际上指的是一些寄存器, 如果 eip, esp, 告诉 cpu 执行代码的位置和堆栈的位置。

glibc 已经实现了这三个函数在 sysdeps/unix/sysv/linux/x86_64/ 目录下的 getcontext.c, makecontext.c 两个汇编文件, libtask 也实现了一个版本。

使用方法见 man(3) 手册.

五. 结束

libtask 只是跑在单核上面的简单调度器, 实现很简单。在实际一些多核调度的实现算法上, 比如像 golang, 会复杂很多。 国内的大牛 @云风 实现过一个更简单的版本, 只有 200 行代码, github地址

接下来还会继续介绍 libtask 的另外两个实现:

  1. 延时执行协程
  2. channel