关于golang的goroutine scheduler

前言

G：指的是Goroutine
M：工作线程或机器
P：处理器，用来执行Go代码的资源
每个M需要有一个关联P来执行Go代码，

当前scheduler的问题

当前goroutine scheduler限制使用go语言编写的并发程序可扩展性，特别是，高吞吐服务和并行计算程序方面。Vtocc服务在8核机器上CPU高达70%，而profile显示14%是花费在runtime.futex()这个地方。通常来说scheduler可能会禁止用户在性能优关的地方使用惯用细粒度的并发。

当前实现存在的问题

1. 单一的全局互斥锁(Sched.Lock)和中心式状态，全局互斥锁保护了所有goroutine的关联操作（创建、实现、重新调度等）
   2、Goroutine并不干涉其他的goroutine(G.nextG).同样工作线程经常也不干涉runnable goroutine在彼此之间，而这些可能会导致增加延迟和带来额外花费。每个M能够执行任意运行中的G,实际上M仅仅创建G。
   3、每个M内存缓存(M.mcache),与所有M关联的内存缓存和其他缓存(比如堆分配内存)，仅仅实在M运行go代码时才需要被分配(M在系统调用阻塞中是不需要分配内存缓存的)，在运行Go代码的M和所有M的内存比例最高达到1:100.这也导致资源浪费(每个MCache分配大小达到2M)及糟糕的数据存放位置
   4、频繁的blocking和unblocking，在系统调用时，工作线程会频繁阻塞和非阻塞，会带来额外的花费

scheduler 设计

Processors(处理器)

基本的思想是在运行引入P(Processors)的概念，并实现在Processor上实现抢夺式工作调度，而M表示操作系统线程，P表示执行Go代码时所需要的资源，当M执行Go代码时， 它会有对应关联的P。在M空闲或在进行系统调用时，是需要P的。GOMAXPROCES即为P，所有的P都会被存放到一个array中，这也是抢夺式工作模式的要求，对应的GOMAXPROCS的改变会带来停止/启动这个GC World来重新调整P的数组大小。在sched中的一些变量被分散并移到P中，M中的一些变量被移到P中，这些变量一般是与go代码活动执行有关的。

struct P{
    Lock；
    G *gfree；  // freelist, moved from sched
    G *ghead；// runnable, moved from sched
    G *gtail; 
    MCache *mcache;     // moved from M
    FixAlloc  *stackalloc;   // moved from M
    uint64  ncgocall;
    GCStats gcstates;
     // etc
     ...
};
P *allp;  // [GOMAXPROCS]
p *idlep; // lock-free list of idle P

说明：当一个M将要执行Go代码，必须从无锁空闲列表获取一个P。而当M完成Go代码执行，就需要将执行GO代码的P放入到该列表中，以便后续的操作使用。因此在M执行Go代码时，都必有一个与之关联的P。这种机制也取代了sched.atomic(mcpu/mcpumax)

调度scheduling

当新建一个G或已有的G重新运行，那么该G则将被推到当前P的运行goroutine列表中。在该P完成执行G，P则尝试从自己本地的运行goroutines列表pop一个G；若是本地列表为空，该P则会随机选择一个其他的P，并从选择的P本地运行goroutine列表获取一半的goroutine，这样就提升P资源的利用，提升效率。

系统调用/M parking和unparking

在M创建一个新的g时，在所有的M都不是很忙的情况下，必须能够确保有另外一个M来执行这个G。同样，当一个M正处于系统调用时，也必须确保有另外一个M来执行Go代码。
这里有两种选择，可以立即锁定或解锁M，也使用旋转。这里会存在必然的冲突在性能和消耗不必要的CPU时钟周期之间。通过使用旋转和消耗一定CPU时钟周期来实现，然而对于GOMAXPROCS=1的程序(命令行程序、app引擎等)是没有影响的。
关于旋转有两中类型：
(1)、一个关联P的空闲M通过自旋查找新的G
(2)、一个关联P的w/o M等待可用的P
类型(1)的空闲M在有类型(2)空闲M时并不会阻塞/锁定。常见的GOMAXPROCS旋转M基本上就在两种类型中。在一个新的G处于旋转状态或M在进行系统调用时甚至M从空闲转变为忙碌，都能确保至少有一个M是旋转的(或所有的P都处于忙碌状态)，同时这也确保了没有runnable的G以其他方式运行，并且也避免了同一时间过多的M进行block或unblock。一般来说旋转多半都是被动是由os调用sched_yield()来触发，但也可能存在些主动自旋转(循环消耗CPU)，这些是需要研究并进行调优的。

终止/死锁检查

在分布式系统中，终止/死锁检查存在很多的不确定性。通常的想法是通过是在所有的P都处于空闲状态下(全局空闲P原子计数器)，这允许进行更昂贵的检查涉及每个P状态的聚合。

LockOSThread

该功能并不是性能的关键
1、处于Locked的G则是不能进行runnable(状态=Gwaiting)，M立即将P返回到空闲列表(idle-list),并唤醒其他的M并阻塞
2、当处于Locked的G变成runnable并处于运行队列的头部，当前的M并不干涉自己对应的P和Locked G到Locked G相关的M上，并释放，最终当前M变为idle

空闲G

该功能也不是性能的关键
这里有一个全局的空闲G队列，一个M在多次尝试失败之后来检查该队列。

实现计划

最终的目标通过将整个项目分割成能够独立评估和提交的最小单元。
1、引入结构体P(目前为空)，实现allp/idlep容器(针对初学者来说idlep是一个互斥-受保护的)；分配一个P给对应的M来运行Go代码，全局的互斥和原子状态是保持不变的
2、移动G freelist给P
3、移动M到P
4、移动堆分配到P
5、移动ncgocall/gsstats到P
6、分散运行队列并实现抢夺式工作模式，清除G状态转换，仍处于全局互斥下
7、移除全局互斥，实现分布式终止检查：LockOSThread
8、实现旋转而不是blocking、unblocking
(该计划有可能会失败，有很多未被探索的细节)

进一步改善

1、尝试LIFO调度，将提高局部性能。然而，它仍然必须提供一定程度的公平性和优雅地处理生成goroutines
2、不要在goroutine首次运行时分配对应的G和stack；针对一个新建一个新的goroutine只需要callerpc、fn、narg、nret、args等6个命令。这也允许创建一些运行到完成的goroutine来显著的降低内存的占用
3、更好局部G-P过程尝试确保一个unblock的G到上次运行它的P上
4、更好的局部P-M尝试执行P在上次运行相同的M上
5、M创建限制，由于scheduler很容易每秒钟创建数千个M，直到OS拒绝创建更多的线程。M就必须立即创建直至k * GOMAXPROCS,在这以后新建M都是通过计数器来完成添加的

后记

GOMAXPROCS不会因为这些调整而消失。