网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

golang调度器学习

2020-06-10 03:07:25 admin 594

# 概要

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

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

# 任务调度概念

## 任务与任务控制块（TCB）

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

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

## 任务状态

* 运行态：获得cpu
  * 等待态：需要资源才能继续运行
  * 就绪态：获得资源，等待运行

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

以上是一个调度器的实现，画了个图表示调度器一次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

与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

* 一个内核线程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的关系，如果还要继续深入，感觉只能看代码细节了

转载文章，原文链接： golang调度器学习

关键字词golang 调度

分享到：

上一篇：如何在docker中进行gdb调试

下一篇：Golang处理JSON（二）--- 解码

如需留言，请登录，没有账号？请注册

0 条评论 0 人参与

网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

golang调度器学习

admin 1年前

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

网站首页 返回列表 像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

golang调度器学习

admin 官方 1年前

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

网站首页返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

admin 1年前