5.1 调度器相关数据结构

Go的调度的实现，涉及到几个重要的数据结构。运行时库用这几个数据结构来实现goroutine的调度，管理goroutine和物理线程的运行。这些数据结构分别是结构体G，结构体M，结构体P，以及Sched结构体。前三个的定义在文件runtime/runtime.h中，而Sched的定义在runtime/proc.c中。Go语言的调度相关实现也是在文件proc.c中。

结构体G

G是goroutine的缩写，相当于操作系统中的进程控制块，在这里就是goroutine的控制结构，是对goroutine的抽象。其中包括goid是这个goroutine的ID，status是这个goroutine的状态，如Gidle,Grunnable,Grunning,Gsyscall,Gwaiting,Gdead等。

struct G
{
    uintptr stackguard; // 分段栈的可用空间下界
    uintptr stackbase;  // 分段栈的栈基址
    Gobuf   sched;      //进程切换时，利用sched域来保存上下文
    uintptr stack0;
    FuncVal*    fnstart;        // goroutine运行的函数
    void*   param;      // 用于传递参数，睡眠时其它goroutine设置param，唤醒时此goroutine可以获取
    int16   status;     // 状态Gidle,Grunnable,Grunning,Gsyscall,Gwaiting,Gdead
    int64   goid;       // goroutine的id号
    G*  schedlink;
    M*  m;      // for debuggers, but offset not hard-coded
    M*  lockedm;    // G被锁定只能在这个m上运行
    uintptr gopc;   // 创建这个goroutine的go表达式的pc
    ...
};

结构体G中的部分域如上所示。可以看到，其中包含了栈信息stackbase和stackguard，有运行的函数信息fnstart。这些就足够成为一个可执行的单元了，只要得到CPU就可以运行。

goroutine切换时，上下文信息保存在结构体的sched域中。goroutine是轻量级的线程或者称为协程，切换时并不必陷入到操作系统内核中，所以保存过程很轻量。看一下结构体G中的Gobuf，其实只保存了当前栈指针，程序计数器，以及goroutine自身。

struct Gobuf
{
    // The offsets of these fields are known to (hard-coded in) libmach.
    uintptr sp;
    byte*   pc;
    G*  g;
    ...
};

记录g是为了恢复当前goroutine的结构体G指针，运行时库中使用了一个常驻的寄存器extern register G* g，这个是当前goroutine的结构体G的指针。这样做是为了快速地访问goroutine中的信息，比如，Go的栈的实现并没有使用%ebp寄存器，不过这可以通过g->stackbase快速得到。"extern register"是由6c，8c等实现的一个特殊的存储。在ARM上它是实际的寄存器；其它平台是由段寄存器进行索引的线程本地存储的一个槽位。在linux系统中，对g和m使用的分别是0(GS)和4(GS)。需要注意的是，链接器还会根据特定操作系统改变编译器的输出，例如，6l/linux下会将0(GS)重写为-16(FS)。每个链接到Go程序的C文件都必须包含runtime.h头文件，这样C编译器知道避免使用专用的寄存器。

结构体M

M是machine的缩写，是对机器的抽象，每个m都是对应到一条操作系统的物理线程。M必须关联了P才可以执行Go代码，但是当它处理阻塞或者系统调用中时，可以不需要关联P。

struct M
{
    G*  g0;     // 带有调度栈的goroutine
    G*  gsignal;    // signal-handling G 处理信号的goroutine
    void    (*mstartfn)(void);
    G*  curg;       // M中当前运行的goroutine
    P*  p;      // 关联P以执行Go代码 (如果没有执行Go代码则P为nil)
    P*  nextp;
    int32   id;
    int32   mallocing; //状态
    int32   throwing;
    int32   gcing;
    int32   locks;
    int32   helpgc;     //不为0表示此m在做帮忙gc。helpgc等于n只是一个编号
    bool    blockingsyscall;
    bool    spinning;
    Note    park;
    M*  alllink;    // 这个域用于链接allm
    M*  schedlink;
    MCache  *mcache;
    G*  lockedg;
    M*  nextwaitm;  // next M waiting for lock
    GCStats gcstats;
    ...
};

这里也是截取结构体M中的部分域。和G类似，M中也有alllink域将所有的M放在allm链表中。lockedg是某些情况下，G锁定在这个M中运行而不会切换到其它M中去。M中还有一个MCache，是当前M的内存的缓存。M也和G一样有一个常驻寄存器变量，代表当前的M。同时存在多个M，表示同时存在多个物理线程。

结构体M中有两个G是需要关注一下的，一个是curg，代表结构体M当前绑定的结构体G。另一个是g0，是带有调度栈的goroutine，这是一个比较特殊的goroutine。普通的goroutine的栈是在堆上分配的可增长的栈，而g0的栈是M对应的线程的栈。所有调度相关的代码，会先切换到该goroutine的栈中再执行。

结构体P

Go1.1中新加入的一个数据结构，它是Processor的缩写。结构体P的加入是为了提高Go程序的并发度，实现更好的调度。M代表OS线程。P代表Go代码执行时需要的资源。当M执行Go代码时，它需要关联一个P，当M为idle或者在系统调用中时，它也需要P。有刚好GOMAXPROCS个P。所有的P被组织为一个数组，在P上实现了工作流窃取的调度器。

struct P
{
    Lock;
    uint32  status;  // Pidle或Prunning等
    P*  link;
    uint32  schedtick;   // 每次调度时将它加一
    M*  m;  // 链接到它关联的M (nil if idle)
    MCache* mcache;

    G*  runq[256];
    int32   runqhead;
    int32   runqtail;

    // Available G's (status == Gdead)
    G*  gfree;
    int32   gfreecnt;
    byte    pad[64];
};

结构体P中也有相应的状态：

Pidle,
Prunning,
Psyscall,
Pgcstop,
Pdead,

注意，跟G不同的是，P不存在waiting状态。MCache被移到了P中，但是在结构体M中也还保留着。在P中有一个Grunnable的goroutine队列，这是一个P的局部队列。当P执行Go代码时，它会优先从自己的这个局部队列中取，这时可以不用加锁，提高了并发度。如果发现这个队列空了，则去其它P的队列中拿一半过来，这样实现工作流窃取的调度。这种情况下是需要给调用器加锁的。

Sched

Sched是调度实现中使用的数据结构，该结构体的定义在文件proc.c中。

struct Sched {
    Lock;

    uint64  goidgen;

    M*  midle;   // idle m's waiting for work
    int32   nmidle;  // number of idle m's waiting for work
    int32   nmidlelocked; // number of locked m's waiting for work
    int3    mcount;  // number of m's that have been created
    int32   maxmcount;  // maximum number of m's allowed (or die)

    P*  pidle;  // idle P's
    uint32  npidle;  //idle P的数量
    uint32  nmspinning;

    // Global runnable queue.
    G*  runqhead;
    G*  runqtail;
    int32   runqsize;

    // Global cache of dead G's.
    Lock    gflock;
    G*  gfree;

    int32   stopwait;
    Note    stopnote;
    uint32  sysmonwait;
    Note    sysmonnote;
    uint64  lastpoll;

    int32   profilehz;  // cpu profiling rate
}

大多数需要的信息都已放在了结构体M、G和P中，Sched结构体只是一个壳。可以看到，其中有M的idle队列，P的idle队列，以及一个全局的就绪的G队列。Sched结构体中的Lock是非常必须的，如果M或P等做一些非局部的操作，它们一般需要先锁住调度器。

5.1 调度器相关数据结构

结构体G

结构体M

结构体P

Sched

links