数据结构

Golang中实现协程调度算法的主要有以下三个数据结构,正是这三个结构加上一些算法构成了golang的协程调度算法,当然,这些数据结构也是在不断进化的,保不准未来又会加入其他结构来提升调度器性能。

Golang协程调度算法分析(二)

其中:

M: 代表操作系统线程,也就是我们经常理解的线程,是真正参与OS调度的单元,每个goroutine,只有依附于某个M方可真正地执行;
G: 代表协程,也就是我们经常滥用的Goroutine;
P: 协程调度器的基本调度单元:每个G的容身之所,连接G和M的桥梁。

理解调度器的关键是理解P的作用:它是实现M:N调度的关键结构,也是在golang1.1版本中才引入了,解决了1.0中的全局调度队列带来的可扩展性问题。
1). 每个G都必须依附于某个P;
2). 每个M想运行的时候,必须先获取一个P,再执行P中的G;
3). 每个P维护可运行G队列,避免了全局G队列带来的锁竞争问题,提高了调度器的可扩展性;
4). 如果一个M在执行G的时候进入了syscall,那么该M就被占据了,与其关联的P此时就游离出来,可被同样处于idle状态的M获取到,进而P内的G得到继续执行的机会;
5). go中可通过GOMAXPROCS()来设置P的数量,一般建议设置成系统核数即可,P的数量也代表了当前活跃的M数(因进入syscall而block的M不计算在内)。

struct G {
    ......
}
struct  M
{
    ......
    G*  curg;   // current running goroutine
    P*  p;      // attached P for executing Go code (nil if not executing Go code)
    ......
}

struct P
{
    ......
    M*  m;  // back-link to associated M (nil if idle)
    ......
    // Queue of runnable goroutines.
    uint32  runqhead;
    uint32  runqtail;
    G*  runq[256];

    // Available G's (status == Gdead)
    G*  gfree;
    ......
};

调度算法

正常情况下,调度器的运行状态图应该是下面这样的:

Golang协程调度算法分析(二)

 

发生系统调用

加入当前运行的goroutine进入了系统调用,那状态可能变成下面这样:

 

Golang协程调度算法分析(二)

 

由于当前P的壮丁M0被block在G0协程的系统调用中,所以P不得不重新抓个壮丁M1去执行它的goroutine。
当G0从系统调用中返回以后,为了继续执行接下来的代码,还必须得找(偷)个依靠P,如果找不到,它将自己添加到全局的可运行goroutine队列中,等待后续被调度执行。

void
runtime·reentersyscall(uintptr pc, uintptr sp)
{
    ......
    // 将p从M中剥离出来
    g->m->mcache = nil;
    g->m->p->m = nil;
    ......
}

entersyscall 和 entersyscallblock

在runtime中进入系统调用可能有这两种方式进入系统调用。我们下面就来说下这两种方式的区别:

entersyscall:

将m的MCache置为空,并将m->p->m置为空,表示进入系统调用后结构体M是不需要MCache的,并且P也被剥离了,将P的状态设置为PSyscall

entersyscallblock:

entersyscallblock,它会告诉提示这个系统调用是会阻塞的,因此会有一点点区别。它调用的releasephandoffp
releasep将P和M完全分离,使p->m为空,m->p也为空,剥离m->mcache,并将P的状态设置为Pidle。注意这里的区别,在非阻塞的系统调用entersyscall中只是设置成Psyscall,并且也没有将m->p置为空。
handoffp切换P。将P从处于syscall或者locked的M中,切换出来交给其它M。每个P中是挂了一个可执行的G的队列的,如果这个队列不为空,即如果P中还有G需要执行,则调用startm让P与某个M绑定后立刻去执行,否则将P挂到idlep队列中。

总结:

  1. 两个P的状态不同,一个是PSyscall,另外一个是Pidle;
  2. 前者的M仍然指向P,系统调用返回以后可直接找到P,而后者则将M和P彻底分开,返回以后,该M可能以后就会去执行其他P上的G了。

exitsyscall

出系统调用时会调用到runtime·exitsyscall,这个函数跟进系统调用做相反的操作。它会先检查当前m的P和它状态,如果P不空且状态为Psyscall,则说明是从一个非阻塞的系统调用中返回的,这时是仍然有CPU可用的。因此将p->m设置为当前m,将p的mcache放回到m,恢复g的状态为Grunning。否则,它是从一个阻塞的系统调用中返回的,因此之前m的P已经完全被剥离了。这时会查看调用中是否还有idle的P,如果有,则将它与当前的M绑定。

如果从一个阻塞的系统调用中出来,并且出来的这一时刻又没有idle的P了,要怎么办呢?这种情况代码当前的goroutine无法继续运行了,调度器会将它的状态设置为Grunnable,将它挂到全局的就绪G队列中,然后停止当前m并调用schedule函数。

void
·exitsyscall(int32 dummy)
{
    void (*fn)(G*);

    g->m->locks++;  // see comment in entersyscall

    if(runtime·getcallersp(&dummy) > g->syscallsp)
        runtime·throw("exitsyscall: syscall frame is no longer valid");

    g->waitsince = 0;
    // 如果是从快速系统调用中返回,这时候M的P还在,将G状态设置未Grunning
    if(exitsyscallfast()) {
        // There's a cpu for us, so we can run.
        g->m->p->syscalltick++;
        // We need to cas the status and scan before resuming...
        runtime·casgstatus(g, Gsyscall, Grunning);

        // Garbage collector isn't running (since we are),
        // so okay to clear syscallsp.
        g->syscallsp = (uintptr)nil;
        g->m->locks--;
        if(g->preempt) {
            // restore the preemption request in case we've cleared it in newstack
            g->stackguard0 = StackPreempt;
        } else {
            // otherwise restore the real stackguard, we've spoiled it in entersyscall/entersyscallblock
            g->stackguard0 = g->stack.lo + StackGuard;
        }
        g->throwsplit = 0;
        return;
    }

    g->m->locks--;

    // Call the scheduler.
    fn = exitsyscall0;

偷盗算法

这个算法为了解决各个P之间goroutine数不均衡问题:由于各种原因,各个P之间的goroutine数量可能存在不均衡现象:这个现象导致的后果就是:可能某个P内还有一堆活等着去做,但是某个P内没啥任务,导致效率低下。为了解决这个问题,go调度器引入了偷盗算法:当某个P内无可运行goroutine时,会从其他的P内偷一些goroutine来做,如下图所示:

Golang协程调度算法分析(二)

 

  1. 是不是阻塞的syscall会产生一个阻塞的系统线程. 然后分离的P会找一个新的线程来执行.那么如果有很多block的syscall, 是不是会产生大量的block系统线程?