说明

前面有两篇文章我们聊了聊golang的协程调度算法。现在重新捡起来看看,真的是太皮毛了,羞愧,浅尝辄止的研究从来不是我的风格。

痛定思痛,从这里开始,我们深入深入再深入,直到将她扒光为止。

这篇文章可能会包含较多的个人思考,所以可能会有不少呓语,请忽略,如果你也能跟上我的节奏,那么你可能会很喜欢,否则,你可能觉得我是个神经病。

 

调度需要解决什么问题

前面有几篇文章大致介绍了golang协程调度的框架,主要的数据结构和流程等等。那我相信也假设你在阅读此文的时候在脑海中已经有了一些大致的印象。
OK,我帮你回顾下:

  1. golang的协程调度是非抢占性:除非某个协程自己主动放弃CPU(如进入系统调用);
  2. 协程与线程有别:他们之间是N:M的关系;
  3. 协程调度实现中抽象了G、M、P,G表示协程,M代表工作线程,P代表CPU,准确理解这三者非常关键。

上面的几点决定了Golang协程调度算法的轮廓,那么我们来看在这样的轮廓下如何实现一个高效的调度算法。
我们首先仔细思考下一个简单高效的调度算法需要解决哪些问题:

  1. 效率:协程响应时间
  2. 公平性:如何保证所有工作协程得到公平执行的机会;
  3. 容量:调度算法可扩展性,能支持的并发数,直接决定调度算法成败的指标

上面从大的方面提出了一个优秀的调度算法应该满足的特性,在满足每种特性的背后都充满了种种的挑战与权衡。接下来,我们深入golang,看看golang能否同时做到了这几点,看它如何处理每个细节。

怎么做

接下来我会从协程的生老病死来深挖,当然这里代表的意思是协程的创建、执行、调度、销毁等。

协程创建

golang创建一个协程异乎寻常地简单,go a()就创建一个协程去执行函数a。那我们看看go到底做了些什么?

go创建协程的入口是

G* runtime·newproc1(FuncVal *fn, byte *argp, int32 narg, int32 nret, void *callerpc)
{
    G *newg;
    P *p;
    int32 siz;
    ......
    // 获取当前g所在的p,从p中创建一个新g(newg)
    p = g->m->p;
    if((newg = gfget(p)) == nil) {
        ......    
    }
    ......
    // 设置Goroutine状态为Grunnable
    runtime·casgstatus(newg, Gdead,             
        Grunnable);
    .....
    // 新创建的g添加到run队列中
    // 这里的put也很有讲究,但我们暂时不管
    runqput(p, newg);
    ......
}

这里其实非常简单了,从创建新协程的父协程的P中分配一个新的g作为子协程,将其状态设置为Grunnable,添加到P所属的运行队列,万事大吉。
从上面简单的流程中我们可以得出如下结论:

  1. 每个G被创建出来后都会绑定至某个P(父协程所在的P);
  2. G被创建出来后的状态是可运行而非马上运行,至于什么时候执行取决于调度算法,可能立即,也可能被延后一段时间。
协程调度

协程的调度可能发生在很多场景下,我们一个个进行深入钻研。

系统调用

我们通过之前几篇文章的分析可以知道,在当前占据M的G陷入系统调用时,它需要让出当前执行的M,以便其他G可有被执行的机会,因为系统调用需要陷入内核态,可能占据时间比较长(N ms)。

其实这里说G让出M不对,因为该G仍然占有M,只是将该G对应的M从P中剥离出来,这样,P当前就没有任何M了,变成孤零零的一个存在,里面的G也没人去做了。当然调度器不会坐视不理。

我们这里所说的都比较抽象,那么让我们结合代码来看看到底怎么做吧。

看这个之前,让我们看看go是如何进入系统调用的,理解了这个让我们不会对后面所说的一些东西感到很陌生。

golang对操作系统的系统调用作了封装,专门提供了syscall这样的库让我们来调用系统调用。例如,Read系统调用实现如下:

func Read(fd int, p []byte) (n int, err error) {
    n, err = read(fd, p)
    if raceenabled {
        if n > 0 {
            raceWriteRange(unsafe.Pointer(&p[0]), n)
        }
        if err == nil {
            raceAcquire(unsafe.Pointer(&ioSync))
        }
    }
    return
}
// 最终封装了Syscall
func read(fd int, p []byte) (n int, err error) {
    var _p0 unsafe.Pointer
    if len(p) > 0 {
        _p0 = unsafe.Pointer(&p[0])
    } else {
        _p0 = unsafe.Pointer(&_zero)
    }
    r0, _, e1 := Syscall(SYS_READ, uintptr(fd), uintptr(_p0), uintptr(len(p)))
    n = int(r0)
    if e1 != 0 {
        err = e1
    }
    return
}
// 我们只关心进入系统调用时调用的runtime·entersyscall
// 和退出时调用的runtime·exitsyscall
TEXT    ·Syscall(SB),NOSPLIT,$0-56
    CALL    runtime·entersyscall(SB)
    MOVQ    16(SP), DI
    MOVQ    24(SP), SI
    MOVQ    32(SP), DX
    MOVQ    $0, R10
    MOVQ    $0, R8
    MOVQ    $0, R9
    MOVQ    8(SP), AX   // syscall entry
    SYSCALL
    CMPQ    AX, $0xfffffffffffff001
    JLS ok
    MOVQ    $-1, 40(SP) // r1
    MOVQ    $0, 48(SP)  // r2
    NEGQ    AX
    MOVQ    AX, 56(SP)  // errno
    CALL    runtime·exitsyscall(SB)
    RET

我们并不关心系统调用到底怎么实现。我们只关心系统调用过程与调度器相关内容,因为golang自己接管系统调用,调度器便可以在进出系统调用时做一些你所不明白的优化,这里我要带你弄清楚调度器怎么做优化的。

进入系统调用前

我们前面说过,系统调用是一个相对耗时的过程。因此,一旦P中的某个G进入系统调用状态,也就意味着该P内的其他G可能会被阻塞,因没有M而无法得到执行(M被系统调用的那个死鬼占用着),这样我们必须得做点什么吧,这就是调度器在进入系统调用前call runtime·entersyscall的目的所在。

void
·entersyscall(int32 dummy)
{
    runtime·reentersyscall((uintptr)runtime·getcallerpc(&dummy), runtime·getcallersp(&dummy));
}

void
runtime·reentersyscall(uintptr pc, uintptr sp)
{
    void (*fn)(void);
    g->m->locks++;

    g->stackguard0 = StackPreempt;
    g->throwsplit = 1;

    // Leave SP around for GC and traceback.
    save(pc, sp);
    g->syscallsp = sp;
    g->syscallpc = pc;
    runtime·casgstatus(g, Grunning, Gsyscall);
    if(g->syscallsp < g->stack.lo || g->stack.hi < g->syscallsp)        
    {
        fn = entersyscall_bad;
        runtime·onM(&fn);
    }

    // 这个还不知道是啥意思
    if(runtime·atomicload(&runtime·sched.sysmonwait)) { 
        fn = entersyscall_sysmon;
        runtime·onM(&fn);
        save(pc, sp);
    }
    // 这里很关键:P的M已经陷入系统调用,于是P忍痛放弃该M
    // 但是请注意:m还指向p,即m还记得它原来服务的p,回来有用
    g->m->mcache = nil;
    g->m->p->m = nil;
    // P的状态变为Psyscall
    runtime·atomicstore(&g->m->p->status, Psyscall);
    if(runtime·sched.gcwaiting) {
        fn = entersyscall_gcwait;
        runtime·onM(&fn);
        save(pc, sp);
    }
    g->stackguard0 = StackPreempt;
    g->m->locks--;
}

上面与调度器相关的内容其实就是将P的M从P剥离出去,告诉调度器,我已经放弃M了,我不能饿着我的孩子们(G)。但是M内心还是记着P的,在系统调用返回后,M还尽量找回原来的P,至于P是不是另结新欢就得看情况了。

注意这时候P放弃了前妻M,但是还没有给孩子们找后妈,那么什么时候以及怎么样给孩子们找后妈呢?

从系统调用返回后

从系统调用返回后,也要告诉调度器,因为需要调度器做一些事情,根据前面系统调用的实现,具体实现是:

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;
    // 判断能否快速找到归属
    if(exitsyscallfast()) {
        g->m->p->syscalltick++;
        // We need to cas the status and scan before resuming...
        runtime·casgstatus(g, Gsyscall, Grunning);
        g->syscallsp = (uintptr)nil;
        g->m->locks--;
        if(g->preempt) {
            g->stackguard0 = StackPreempt;
        } else {
            g->stackguard0 = g->stack.lo + StackGuard;
        }
        g->throwsplit = 0;
        return;
    }
    g->m->locks--;

    // Call the scheduler.
    // 如果m回来发现P已经有别人服务了,那只能将自己挂起
    // 等着服务别人。
    fn = exitsyscall0;
    runtime·mcall(&fn);
    ......
}

static bool
exitsyscallfast(void)
{
    void (*fn)(void);
    if(runtime·sched.stopwait) {
        g->m->p = nil;
        return false;
    }

    // 如果之前附属的p尚未被其他m服务
    // 尝试绑定至原来的p
    if(g->m->p && g->m->p->status == Psyscall && runtime·cas(&g->m->p->status, Psyscall, Prunning)) {
        g->m->mcache = g->m->p->mcache;
        g->m->p->m = g->m;
        return true;
    }
    // Try to get any other idle P.
    // 否则从空闲p列表中随便捞一个出来
    g->m->p = nil;
    if(runtime·sched.pidle) {
        fn = exitsyscallfast_pidle;
        runtime·onM(&fn);
        if(g->m->scalararg[0]) {
            g->m->scalararg[0] = 0;
            return true;
        }
    }
    return false;
}

G从系统调用返回的过程,其实就是失足妇女找男人的逻辑:

  1. 首先看看能否回到当初爱人的怀抱,找到当初被我抛弃的男人,我这里还存着它的名片,家庭住址什么的我都还知道;
  2. 如果爱人受不了寂寞和抚养孩子的压力已经变节(P的状态不再是Psyscall),那我就随便找个单身待解救男人从了也行;
  3. 如果上面的1、2都找不到,那也没办法,男人都死绝了,老娘只好另想他法。

以上过程其实就是exitsyscallfast()的主要流程,用怀孕了的失足妇女找男人再合适不过。
一个女人由于年轻不懂事失足,抛家弃子(家是P,子是P的G)。当浪子回头后,意欲寻回从前的夫君,只能有两种可能:

  1. 等了很久已然心灰意冷的夫君在家人的安排下另娶他人;
  2. 痴情的夫君已然和嗷嗷待哺的孩子们依然在等待她的归回。

当然第二种的结局比较圆满,这个女人从此死心塌地守着这个家,于是p->m又回来了,孩子们(g)又可以继续活下去了。
第一种就比较难办了,女人(m)心灰意冷,将产下的儿子(陷入系统调用的g)交于他人(全局g的运行队列)抚养,远走他乡,从此接收命运的安排(参与调度,以后可能服务于别的p)。
对于第二种可能性,只能说女人的命运比较悲惨了:

static void
exitsyscall0(G *gp)
{
    P *p;
    runtime·casgstatus(gp, Gsyscall, Grunnable);
    dropg();
    runtime·lock(&runtime·sched.lock);
    // 这里m再次尝试为自己找个归宿p
    p = pidleget();
    // 将m的g随意找个P安置进去,自己不管了
    // 如果没找到,放入全局的运行队列中
    if(p == nil)
        globrunqput(gp);
    else if(runtime·atomicload(&runtime·sched.sysmonwait)) {
        runtime·atomicstore(&runtime·sched.sysmonwait, 0);
        runtime·notewakeup(&runtime·sched.sysmonnote);
    }
    runtime·unlock(&runtime·sched.lock);
    // 如果找到了p,那么占有p,并且开始执行p内的g,永不回头
    if(p) {
        acquirep(p);
        execute(gp);  // Never returns.
    }
    // 这个g是?
    if(g->m->lockedg) {
        // Wait until another thread schedules gp and so m again.
        stoplockedm();
        execute(gp);  // Never returns.
    }
    // 找了一圈还是没找到,释放掉m当前执行环境,m不再做事
    // stopm会暂停当前m直到其找到了可运行的P为止
    // 找到以后进入schedule,为什么需要schedule?
    stopm();
    // m从sleep中返回以后,就需要调度找到一个g去执行
    // 这就是调用schedule的目的所在
    schedule();  // Never returns.
}

话说到这里,其实这个m当前没有运行的价值了(无法找到p运行它),那么我们就将她挂起,直到被其他人唤醒。
m被挂起调用的函数是stopm()

// Stops execution of the current m until new work is available.
// Returns with acquired P.
static void stopm(void)
{
    if(g->m->locks)
        runtime·throw("stopm holding locks");
    if(g->m->p)
        runtime·throw("stopm holding p");
    if(g->m->spinning) {
        g->m->spinning = false;
        runtime·xadd(&runtime·sched.nmspinning, -1);
    }
retry:
    runtime·lock(&runtime·sched.lock);
    // 将m插入到空闲m队列中,统一管理
    mput(g->m);
    runtime·unlock(&runtime·sched.lock);
    // 在这里被挂起,阻塞在m->park上,位于lock_futex.go    
    runtime·notesleep(&g->m->park);
    // 从挂起被唤醒后开始执行
    runtime·noteclear(&g->m->park);
    if(g->m->helpgc) {
        runtime·gchelper();
        g->m->helpgc = 0;
        g->m->mcache = nil;
        goto retry;
    }
    // m->nextp是什么?
    acquirep(g->m->nextp);
    g->m->nextp = nil;
}

那么说到这里,其实很多事情都一目了然,当一个m从系统调用返回后,通过各种方式想找到可以托付的p,找前夫—>找闲汉,求之不得最终只能将自己挂起,等待下次系统中有空闲的P的时候被唤醒。

陷入系统调用的P的管理

前面我们重点讲了一个m是如何陷入系统调用和如何返回的心酸之路。我们忽略了p的感情,因为他才是真正的受害者,它被剥夺了m,从此无人理会它嗷嗷待哺的孩子们(g),并且状态还被变成了Psyscall,相当于贴上了屌丝标签,别无他法,只能等待陷入系统调用的m返回,再续前缘。
当然,这样做是不合理的,因为如果m进入系统调用后乐不思蜀,那P的孩子们都得饿死,这在现实社会中可以发生,但在数字世界里是决不允许的。
OK,组织绝对不会忽略这种情况的,于是,保姆(管家)出现了,它就是sysmon线程,这是一个特殊的m,专门监控系统状态。
sysmon周期性醒来,并且遍历所有的p,如果发现有Psyscall状态的p并且已经处于该状态超过一定时间了,那就不管那个负心的前妻,再次p安排一个m,这样p内的任务又可以得到处理了。

func sysmon() {
    ......
    retake(now);
    ......
}

我们只摘取了sysmon中与P处理相关的代码分析:

static uint32
retake(int64 now)
{
    uint32 i, s, n;
    int64 t;
    P *p;
    Pdesc *pd;

    n = 0;
    // 遍历所有的P,根据其状态作相应处理,我们只关注Psyscall
    for(i = 0; i < runtime·gomaxprocs; i++) {
        p = runtime·allp[i];
        if(p==nil)
            continue;
        pd = &pdesc[i];
        s = p->status;
        if(s == Psyscall) {
            t = p->syscalltick;
            if(pd->syscalltick != t) {
                pd->syscalltick = t;
                pd->syscallwhen = now;
                continue;
            }

            if(p->runqhead == p->runqtail &&
             runtime·atomicload(&runtime·sched.nmspinning) + runtime·atomicload(&runtime·sched.npidle) > 0 &&
                pd->syscallwhen + 10*1000*1000 > now)
                continue;
            incidlelocked(-1);
            // 因为需要将P重新安排m,所以状态转化为Pidle
            if(runtime·cas(&p->status, s, Pidle)) {
                n++;
                handoffp(p);
            }
            incidlelocked(1);

找到了处于Psyscall状态的P后,继续判断它等待的时间是否已经太长,如果是这样,就准备抛弃原来的还陷入syscall的m,调用handoff(p),开始为p准备新生活。

我们接下来仔细分析下p是怎么过上新生活的,handoffp无非就是找一个新的m,将m与该p绑定,接下来将由m继续执行该p内的g。

参考资料

  1. golang抢占式调度:http://goo.gl/7s2c8p