一、       Golang简介

1.1概述

Golang语言是Google公司开发的新一代编程语言，简称Go语言，Go 是有表达力、简洁、清晰和有效率的。它的并行机制使其很容易编写多核和网络应用，而新奇的类型系统允许构建有弹性的模块化程序。 Go 编译到机器码非常快速，同时具有便利的垃圾回收和强大的运行时反射。而他最广为人知的特性便是语言层面上对多核编程的支持，他有简单的关键字go来实现并行，就像下面这样：

Go的并行单元并不是传统意义上的线程，线程切换需要很大的上下文，这种切换消耗了大量CPU时间，而Go采用更轻量的协程（goroutine）来处理，大大提高了并行度，被称为“最并行的语言”。最近引起容器技术浪潮的Docker就是Go写的。由于GC穿插在goroutine之中，但是本篇文章并不讨论GC相关内容，故略过GC，主要讨论goroutine的调度问题。本文针对的go版本是截止2016年6月29日最新的Go1.7。

1.2与其他并发模型的对比

Python等解释性语言采用的是多进程并发模型，进程的上下文是最大的，所以切换耗费巨大，同时由于多进程通信只能用socket通讯，或者专门设置共享内存，给编程带来了极大的困扰与不便；

C++等语言通常会采用多线程并发模型，相比进程，线程的上下文要小很多，而且多个线程之间本来就是共享内存的，所以编程相比要轻松很多。但是线程的启动和销毁，切换依然要耗费大量CPU时间；

于是出现了线程池技术，将线程先储存起来，保持一定的数量，来避免频繁开启/关闭线程的时间消耗，但是这种初级的技术存在一些问题，比如有线程一直被IO阻塞，这样的话这个线程一直占据着坑位，导致后面的任务排不到队，拿不到线程来执行；

而Go的并发较为复杂，Go采用了更轻量的数据结构来代替线程，这种数据结构相比线程更轻量，他有自己的栈，切换起来更快。然而真正执行并发的还是线程，Go通过调度器将goroutine调度到线程中执行，并适时地释放和创建新的线程，并且当一个正在运行的goroutine进入阻塞（常见场景就是等待IO）时，将其脱离占用的线程，将其他准备好运行的goroutine放在该线程上执行。通过较为复杂的调度手段，使得整个系统获得极高的并行度同时又不耗费大量的CPU资源。

1.3 Goroutine的特点

Goroutine的引入是为了方便高并发程序的编写。一个Goroutine在进行阻塞操作（比如系统调用）时，会把当前线程中的其他Goroutine移交到其他线程中继续执行，从而避免了整个程序的阻塞。

由于Golang引入了垃圾回收（gc），在执行gc时就要求Goroutine是停止的。通过自己实现调度器，就可以方便的实现该功能。 通过多个Goroutine来实现并发程序，既有异步IO的优势，又具有多线程、多进程编写程序的便利性。

引入Goroutine，也意味着引入了极大的复杂性。一个Goroutine既要包含要执行的代码，又要包含用于执行该代码的栈和PC、SP指针。

既然每个Goroutine都有自己的栈，那么在创建Goroutine时，就要同时创建对应的栈。Goroutine在执行时，栈空间会不停增长。栈通常是连续增长的，由于每个进程中的各个线程共享虚拟内存空间，当有多个线程时，就需要为每个线程分配不同起始地址的栈。这就需要在分配栈之前先预估每个线程栈的大小。如果线程数量非常多，就很容易栈溢出。

为了解决这个问题，就有了Split Stacks 技术：创建栈时，只分配一块比较小的内存，如果进行某次函数调用导致栈空间不足时，就会在其他地方分配一块新的栈空间。新的空间不需要和老的栈空间连续。函数调用的参数会拷贝到新的栈空间中，接下来的函数执行都在新栈空间中进行。

Golang的栈管理方式与此类似，但是为了更高的效率，使用了连续栈（ Golang连续栈） 实现方式也是先分配一块固定大小的栈，在栈空间不足时，分配一块更大的栈，并把旧的栈全部拷贝到新栈中。这样避免了Split Stacks方法可能导致的频繁内存分配和释放。

Goroutine的执行是可以被抢占的。如果一个Goroutine一直占用CPU，长时间没有被调度过，就会被runtime抢占掉，把CPU时间交给其他Goroutine。

二、       具体实现

2.1概念：

M：指go中的工作者线程，是真正执行代码的单元；

P：是一种调度goroutine的上下文，goroutine依赖于P进行调度，P是真正的并行单元；

G：即goroutine，是go语言中的一段代码（以一个函数的形式展现），最小的并行单元；

P必须绑定在M上才能运行，M必须绑定了P才能运行，而一般情况下，最多有MAXPROCS（通常等于CPU数量）个P，但是可能有很多个M，真正运行的只有绑定了M的P，所以P是真正的并行单元。

 

每个P有一个自己的runnableG队列，可以从里面拿出一个G来运行，同时也有一个全局的runnable G队列，G通过P依附在M上面执行。不单独使用全局的runnable G队列的原因是，分布式的队列有利于减小临界区大小，想一想多个线程同时请求可用的G的时候，如果只有全局的资源，那么这个全局的锁会导致多少线程一直在等待。

 

但是如果一个正在执行的G进入了阻塞，典型的例子就是等待IO，那么他和它所在的M会在那边等待，而上下文P会传递到其他可用的M上面，这样这个阻塞就不会影响程序的并行度。

2.2 框架图

2.3具体函数

goroutine调度器的代码在/src/runtime/proc.go中，一些比较关键的函数分析如下。

1.     schedule函数

schedule函数在runtime需要进行调度时执行，为当前的P寻找一个可以运行的G并执行它，寻找顺序如下：

1） 调用runqget函数来从P自己的runnable G队列中得到一个可以执行的G；

2） 如果1）失败，则调用findrunnable函数去寻找一个可以执行的G；

3） 如果2）也没有得到可以执行的G，那么结束调度，从上次的现场继续执行。

2.     findrunnable函数

findrunnable函数负责给一个P寻找可以执行的G，它的寻找顺序如下：

1） 调用runqget函数来从P自己的runnable G队列中得到一个可以执行的G；

2） 如果1）失败，调用globrunqget函数从全局runnableG队列中得到一个可以执行的G；

3） 如果2）失败，调用netpoll（非阻塞）函数取一个异步回调的G；

4） 如果3）失败，尝试从其他P那里偷取一半数量的G过来；

5） 如果4）失败，再次调用globrunqget函数从全局runnableG队列中得到一个可以执行的G；

6） 如果5）失败，调用netpoll（阻塞）函数取一个异步回调的G；

7） 如果6）仍然没有取到G，那么调用stopm函数停止这个M。

3.     newproc函数

newproc函数负责创建一个可以运行的G并将其放在当前的P的runnable G队列中，它是类似”go func() { … }”语句真正被编译器翻译后的调用，核心代码在newproc1函数。这个函数执行顺序如下：

1） 获得当前的G所在的 P，然后从free G队列中取出一个G；

2） 如果1）取到则对这个G进行参数配置，否则新建一个G；

3） 将G加入P的runnable G队列。

4.     goexit0函数

goexit函数是当G退出时调用的。这个函数对G进行一些设置后，将它放入free G列表中，供以后复用，之后调用schedule函数调度。

5.     handoffp函数

handoffp函数将P从系统调用或阻塞的M中传递出去，如果P还有runnable G队列，那么新开一个M，调用startm函数，新开的M不空旋。

6.     startm函数

startm函数调度一个M或者必要时创建一个M来运行指定的P。

7.     entersyscall_handoff函数

entersyscall_handoff函数用来在goroutine进入系统调用（可能会阻塞）时将P传递出去。

8.     sysmon函数

sysmon函数是Go runtime启动时创建的，负责监控所有goroutine的状态，判断是否需要GC，进行netpoll等操作。sysmon函数中会调用retake函数进行抢占式调度。

9.     retake函数

retake函数是实现抢占式调度的关键，它的实现步骤如下：

1） 遍历所有P，如果该P处于系统调用中且阻塞，则调用handoffp将其移交其他M；

2）    如果该P处于运行状态，且上次调度的时间超过了一定的阈值，那么就调用preemptone函数这将导致该 P 中正在执行的 G 进行下一次函数调用时，导致栈空间检查失败。进而触发morestack()（汇编代码，位于asm_XXX.s中）然后进行一连串的函数调用，主要的调用过程如下：morestack()（汇编代码）-> newstack() -> gopreempt_m() -> goschedImpl() ->schedule()在goschedImpl()函数中，会通过调用dropg()将 G 与 M 解除绑定；再调用globrunqput()将 G 加入全局runnable队列中。最后调用schedule() 来为当前 P 设置新的可执行的 G 。

三、          小结

Go语言由于存在自己的runtime，使得goroutine的实现相对简单，笔者曾尝试在C++11中实现类似功能，但是保护现场的抢占式调度和G被阻塞后传递给其他Thread的调用很难实现，毕竟Go的所有调用都经过了runtime，这么想来，C#、VB之类的语言实现起来应该容易一点。笔者在C++11中实现的goroutine不支持抢占式调度和阻塞后传递的功能，所以仅仅和直接使用std::thread进行多线程操作进行了对比，工作函数为计算密集的操作，下面是效果对比图（项目地址在https://github.com/InsZVA/cppgo）：

 

可以看到笔者的库启动时间更短（goroutine比线程轻量），执行到最高峰的时候也给系统OS空出了一个线程，而且用时也要短于多线程模型。相比大多数并行设计模型，Go比较优势的设计就是P上下文这个概念的出现，如果只有G和M的对应关系，那么当G阻塞在IO上的时候，M是没有实际在工作的，这样造成了资源的闲置，而且，没有了P，那么所有G的列表都放在全局，这样导致临界区太大，对多核调度造成极大影响。而goroutine在使用上面的特点，感觉既可以用来做密集的多核计算，又可以做高并发的IO应用，做IO应用的时候，写起来感觉和对程序员最友好的同步阻塞一样，而实际上由于runtime的调度，底层是以同步非阻塞的方式在运行（即IO多路复用），虽然达不到nodejs这样异步非阻塞的并发程度，但也接近。而且相比nodejs，go可以更好地利用多核做计算，由于是静态编译，可以在很早的时候发现程序的错误。这门语言还处于蓬勃发展中，也属于开源语言，有兴趣可以保持持续关注。

四、          参考资料

Golang代码仓库：https://github.com/golang/go

《ScalableGo Schedule》：https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y\_kqxDv3I3XMw/edit

《GoPreemptive Scheduler》：https://docs.google.com/document/d/1ETuA2IOmnaQ4j81AtTGT40Y4\_Jr6\_IDASEKg0t0dBR8/edit