调度器学习

zengfan · · 1350 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

概要

本文从几个角度入手,描述和学习调度器原理

  • 讲解调度器的基本概念
  • go语言的作者实现的C的协程库 libtask 源码分析,以理解协程的原理
  • golang的调度器原理

任务调度概念

任务与任务控制块(TCB)

linux中称为进程控制块(PCB),即包含任务相关的数据结构,包含任务执行过程中的所有信息。

  • 任务的名字 task name
  • 任务的ID task id
  • 任务的状态 task status
  • 任务的优先级 task priority
  • 任务的上下文(寄存器、堆栈指针、程序计数器(PC) ) task context

任务状态

  • 运行态:获得cpu
  • 等待态:需要资源才能继续运行
  • 就绪态:获得资源,等待运行
image
image

ps: 上图中从运行态进入就绪态,还有可能是 运行态的任务主动放弃cpu

任务队列

  • 就绪队列:从运行态和等待态进入就绪态的任务,进入就绪队列尾; 从就绪态进入运行态,从就绪队列头取任务,进入运行态
  • 等待队列:运行态任务,等待资源时,进入等待队列尾;等待队列的任务,就绪了以后,从等待队列中取出来,放入就绪队列中。

调度算法

按照是否有优先级,调度算法主要可分为

  • 1、基于优先级的可抢占式调度

    如果出现具有更高优先级的任务处于就绪状态,将当前任务停止运行,把cpu的控制权交给高优先级任务。

  • 2、时间片轮转调度

    各个任务按照先入先出原则排成一个队列,新任务入队尾,调度时选队首。

  • 3、轮询,直到 ①任务执行完毕 ②任务主动放弃cpu ③ 任务IO操作阻塞

协程调度 libtask

对于协程调度,我们主要关心两个问题:

  • 怎么调度?
  • 什么时候调度?

协程特点

  • 一个线程中模拟多个协程并发执行
  • 没有优先级、非抢占式调度:任务不能主动抢占时间片
  • 每个协程都有自己的堆栈和局部变量
  • 采用轮询的调度方式

协程task结构体

struct Task
{
    char    name[256];      // 任务名
    char    state[256];     // 任务状态 
    Task    *next;
    Task    *prev;
    Task    *allnext;
    Task    *allprev;
    Context context;        //任务上下文
    uvlong  alarmtime;
    uint    id;             //任务ID
    uchar   *stk;           //任务栈
    uint    stksize;        //任务栈大小
    int exiting;
    int alltaskslot;
    int system;
    int ready;
    void    (*startfn)(void*);  //函数指针,指向本任务的业务函数
    void    *startarg;          //函数参数
    void    *udata;
};

可以看到,协程的结构体包含的数据,基本与TCB一致。

调度器与上下文切换

static void
taskscheduler(void)
{
    int i;
    Task *t;

    taskdebug("scheduler enter");
    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;   //将该任务设置成非就绪
        taskrunning = t; 
        tasknswitch++;   
        taskdebug("run %d (%s)", t->id, t->name);
        contextswitch(&taskschedcontext, &t->context);  
        //将调度器当前上下文保存在全局taskschedcontext, 
        然后切换到就绪队列队头任务t的上下文
//print("back in scheduler\n");
        taskrunning = nil;
        if(t->exiting){
            if(!t->system)
                taskcount--;
            i = t->alltaskslot;
            alltask[i] = alltask[--nalltask];
            alltask[i]->alltaskslot = i;
            free(t);
        }
    }
}

image
image

以上是一个调度器的实现,画了个图表示调度器一次for循环的运行流程(其中③④⑤⑥⑦具体细节代码可以看调度点那一节)如果要从一个协程切换到另一个协程,执行顺序按上图中的③④⑤⑥⑦①②

上述过程基本表示了协程调度的流程,即每次做协程切换时,都会先切换到调度器,再从调度器切换到下一个协程。

而整个过程对于协程库使用者来说,是透明的,在使用者看来,就是从一个协程切换到了另外一个协程。

任务切换时机(调度点)

在每一个调度点上,任务都会调用contextswitch()函数切换上下文,切换到调度器上,然后调度器再切换到就绪队列下一个任务。

  • 单个任务执行完毕

任务执行完以后,切换回调度器,销毁该任务。

  • 业务代码主动要求切换,即主动出让执行权
void
taskswitch(void)
{
    needstack(0);
    //保存当前任务上下文,切换至调度器上下文。
    contextswitch(&taskrunning->context, &taskschedcontext);   
}

void
taskready(Task *t)
{
    t->ready = 1;
    addtask(&taskrunqueue, t);   //将该任务入队尾
}

int
taskyield(void)
{
    int n;
    
    n = tasknswitch;
    taskready(taskrunning);    //将该任务入队尾
    taskstate("yield");       //改状态
    taskswitch();     //切换上下文
    return tasknswitch - n - 1;    //判断此时就绪队列中是否只有fdtask一个任务
}

这个协程库没有时间片轮转机制,所以大部分任务可能都会主动调用taskyield主动让出执行权。

整个过程,其实就是前一节图中的③④⑤⑥⑦,所以,taskyield会重新激活taskscheduler()函数,从调度器的contextswitch()的下一行继续执行。

  • IO阻塞
void
fdwait(int fd, int rw)
{
    int bits;

    if(!startedfdtask){                 
    //确保系统中只有一个fdtask,且是在第一次出现IO操作时创建的。
        startedfdtask = 1;              
        taskcreate(fdtask, 0, 32768);
    }

    if(npollfd >= MAXFD){
        fprint(2, "too many poll file descriptors\n");
        abort();
    }
    
    taskstate("fdwait for %s", rw=='r' ? "read" : rw=='w' ? "write" : "error");
    bits = 0;
    switch(rw){
    case 'r':
        bits |= POLLIN;
        break;
    case 'w':
        bits |= POLLOUT;
        break;
    }

    polltask[npollfd] = taskrunning;
    pollfd[npollfd].fd = fd;                        //将本fd加入到pollfd数组
    pollfd[npollfd].events = bits;
    pollfd[npollfd].revents = 0;
    npollfd++;
    taskswitch();                                   //上下文切换到调度器
}

如果运行态的任务,遇到IO阻塞,会调用void fdwait(int fd, int rw) 函数,这个函数主要调用taskswitch(),即做上下文切换,但是不将此任务加入就绪队列,而是直接加入
pollfd数组,到后面fdtask任务再判断是否将该任务加入就绪队列。(具体见fdwait函数的注释)

从等待态到就绪态的过程:

void
fdtask(void *v)

fdtask任务,用于监听所有处于阻塞状态的pollfd

    for(;;){
        /* let everyone else run */
        while(taskyield() > 0)
            ;
        /* we're the only one runnable - poll for i/o */

调用taskyield,即每次一进fdtask任务,就会做进程切换,将fdtask切换到末尾,然后调度就绪队列头部,如果发现就绪队列中只有fdtask一个任务,跳出while循环,执行poll:

if(poll(pollfd, npollfd, ms) < 0){
            if(errno == EINTR)
                continue;
            fprint(2, "poll: %s\n", strerror(errno));
            taskexitall(0);
        }

pollfd中有读写事件的fd,将fd[i]对应的polltask[i]加入就绪队列,fd[i]与polltask[i]一一对应。

/* wake up the guys who deserve it */
        for(i=0; i<npollfd; i++){
            while(i < npollfd && pollfd[i].revents){
                taskready(polltask[i]);             //加入就绪队列
                --npollfd;
                pollfd[i] = pollfd[npollfd];
                polltask[i] = polltask[npollfd];
            }
        }

taskready(polltask[i]); 加入就绪队列。

等待态并不是一个任务队列,而是一个存多个fd的pollfd数组,然后当有IO操作,会创建一个fdtask任务,加入队尾,用IO复用操作poll或者epoll去轮询这个数组,
当所有的任务都执行完以后,判断出此时就绪队列中只有fdtask一个任务,才将可以进行读写的fd加入到就绪队列队尾,继续以上操作。

再举个例子:

image
image

与Reactor模式对比,虽然都是用了IO复用poll/epoll,但是Reactor用的是基于回调的异步方式,而
协程通过就绪队列这一层中间层,不需要注册回调函数,用跟其他普通任务相同的方式处理IO事件。

对使用者来讲,协程这种同步编程方式更加好理解,而且不需要维护各种回调。

goroutine调度器

通过分析libtask的部分源码,我们已经得知两个问题:1.怎么调度 2.什么时候调度

线程模型

  • N:1模型,N个用户空间线程在1个内核空间线程上运行。优势是上下文切换非常快但是无法利用多核系统的优点。
  • 1:1模型,1个内核空间线程运行一个用户空间线程。这种充分利用了多核系统的优势但是上下文切换非常慢,因为每一次调度都会在用户态和内核态之间切换。(POSIX线程模型(pthread),Java)
  • M:N模型, 每个用户线程对应多个内核空间线程,同时也可以一个内核空间线程对应多个用户空间线程。Go打算采用这种模型,使用任意个内核模型管理任意个goroutine。这样结合了以上两种模型的优点,但缺点就是调度的复杂性。

下面看看golang的协程调度

  • M:一个用户空间线程,同时对应一个内核线程,类似posix pthread
  • P:代表运行的上下文环境, 也就是我们上一节实现的调度器,一个调度器也会对应一个就绪队列
  • G:goroutine,即协程

M和P和G的关系:

image
image
  • 一个内核线程M一次只能选择一个调度器P,但是每次选择哪个是不确定的

比如:调度器P1对应的就绪队列中没有就绪任务,M选择P1白白浪费资源,于是会选择就绪任务多的P2、P3等

再比如: 调度器P1对应的就绪队列中的就绪任务已经执行完成了,M会重新选择任务多的P2、P3等

  • 一个调度器P可以调度多个协程G,这跟libtask的原理是一样的。

我们分析的libtask,其实就是P与G的关系,M总是1,即并没有考虑多核的情况。

需要搞清楚的几个问题

M和P的数量如何确定?或者说何时会创建M和P?

1、P的数量:

  • 由启动时环境变量$GOMAXPROCS或者是由runtime的方法GOMAXPROCS()决定(默认是1)。这意味着在程序执行的任意时刻都只有$GOMAXPROCS个goroutine在同时运行。

2、M的数量:

  • go语言本身的限制:go程序启动时,会设置M的最大数量,默认10000.但是内核很难支持这么多的线程数,所以这个限制可以忽略。
  • runtime/debug中的SetMaxThreads函数,设置M的最大数量
  • 一个M阻塞了,会创建新的M。

M与P的数量没有绝对关系,一个M阻塞,P就会去创建或者切换另一个M,所以,即使P的默认数量是1,也有可能会创建很多个M出来。

3、P何时创建:在确定了P的最大数量n后,运行时系统会根据这个数量创建n个P。

4、M何时创建:没有足够的M来关联P并运行其中的可运行的G。比如所有的M此时都阻塞住了,而P中还有很多就绪任务,就会去寻找空闲的M,而没有空闲的,就会去创建新的M。

M选择哪一个P关联?

  • M会选择导致此M被创建的那个P关联。

什么时候会切换P与M的关联关系?

当M因系统调用而阻塞时(M上运行的G进入了系统调用的时候),M与P会分开,如果此时P的就绪队列中还有任务,
P就会去关联一个空闲的M,或者创建一个M进行关联。(也就是说go不是像libtask一样处理IO阻塞的?不确定。)

就绪的G如何选择进入哪个P的就绪队列?

  • 默认情况下:因为P的默认数量是1(M不一定是1),所以如果我们不改变GOMAXPROCS,无论我们在程序中用go语句创建多少个goroutine,它们都只会被塞入同一个P的就绪队列中。
  • 有多个P的情况下:如果修改了GOMAXPROCS或者调用了runtime.GOMAXPROCS,运行时系统会把所有的G均匀的分布在各个P的就绪队列中。

后来的G进入哪个P,具体的算法还没有看到

如何保证每个P的就绪队列中都会有G

如果一个P的就绪队列所有任务都执行完了,那么P会尝试从其他P的就绪队列中取出一部分到自己的就绪队列中,以保证每个P的就绪队列都有任务可以执行。

上面只是简单的讲了M、P、G的关系,如果还要继续深入,感觉只能看代码细节了


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:zengfan

查看原文:调度器学习

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1350 次点击  
加入收藏 微博
5 回复  |  直到 2018-06-14 09:21:30
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传