Go runtime的调度器:在了解Go的运行时的scheduler之前,需要先了解为什么需要它,因为我们可能会想,OS内核不是已经有一个线程scheduler了嘛?熟悉POSIX API的人都知道,POSIX的方案在很大程度上是对Unix process进场模型的一个逻辑描述和扩展,两者有很多相似的地方。 Thread有自己的信号掩码,CPU affinity等。但是很多特征对于Go程序来说都是累赘。 尤其是context上下文切换的耗时。另一个原因是Go的垃圾回收需要所有的goroutine停止,使得内存在一个一致的状态。垃圾回收的时间点是不确定的,如果依靠OS自身的scheduler来调度,那么会有大量的线程需要停止工作。 单独的开发一个GO得调度器,可以是其知道在什么时候内存状态是一致的,也就是说,当开始垃圾回收时,运行时只需要为当时正在CPU核上运行的那个线程等待即可,而不是等待所有的线程。用户空间线程和内核空间线程之间的映射关系有:N:1,1:1和M:NN:1是说,多个(N)用户线程始终在一个内核线程上跑,context上下文切换确实很快,但是无法真正的利用多核。1:1是说,一个用户线程就只在一个内核线程上跑,这时可以利用多核,但是上下文switch很慢。M:N是说, 多个goroutine在多个内核线程上跑,这个看似可以集齐上面两者的优势,但是无疑增加了调度的难度。
Go的调度器内部有三个重要的结构:M,P,G
M:代表真正的内核OS线程,和POSIX里的thread差不多,真正干活的人G:代表一个goroutine,它有自己的栈,instruction pointer和其他信息(正在等待的channel等等),用于调度。P:代表调度的上下文,可以把它看做一个局部的调度器,使go代码在一个线程上跑,它是实现从N:1到N:M映射的关键。
有2个物理线程M,每一个M都拥有一个context(P),每一个也都有一个正在运行的goroutine。P的数量可以通过GOMAXPROCS()来设置,它其实也就代表了真正的并发度,即有多少个goroutine可以同时运行。图中灰色的那些goroutine并没有运行,而是出于ready的就绪态,正在等待被调度。P维护着这个队列(称之为runqueue),Go语言里,启动一个goroutine很容易:go function 就行,所以每有一个go语句被执行,runqueue队列就在其末尾加入一个goroutine,在下一个调度点,就从runqueue中取出(如何决定取哪个goroutine?)一个goroutine执行。为何要维护多个上下文P?因为当一个OS线程被阻塞时,P可以转而投奔另一个OS线程!图中看到,当一个OS线程M0陷入阻塞时,P转而在OS线程M1上运行。调度器保证有足够的线程来运行所以的context P。M1可能是被创建,或者从线程缓存中取出。当MO返回时,它必须尝试取得一个context P来运行goroutine,一般情况下,它会从其他的OS线程那里steal偷一个context过来,如果没有偷到的话,它就把goroutine放在一个global runqueue里,然后自己就去睡大觉了(放入线程缓存里)。Contexts们也会周期性的检查global runqueue,否则global runqueue上的goroutine永远无法执行。
另一种情况是P所分配的任务G很快就执行完了(分配不均),这就导致了一个上下文P闲着没事儿干而系统却任然忙碌。但是如果global runqueue没有任务G了,那么P就不得不从其他的上下文P那里拿一些G来执行。一般来说,如果上下文P从其他的上下文P那里要偷一个任务的话,一般就’偷’run queue的一半,这就确保了每个OS线程都能充分的使用。1. 操作系统与运行库对于普通的电脑用户来说,能理解应用程序是运行在操作系统之上就足够了,可对于开发者,我们还需要了解我们写的程序是如何在操作系统之上运行起来的,操作系统如何为应用程序提供服务,这样我们才能分清楚哪些服务是操作系统提供的,而哪些服务是由我们所使用的语言的运行库提供的。除了内存管理、文件管理、进程管理、外设管理等等内部模块以外,操作系统还提供了许多外部接口供应用程序使用,这些接口就是所谓的“系统调用”。从DOS时代开始,系统调用就是通过软中断的形式来提供,也就是著名的INT 21,程序把需要调用的功能编号放入AH寄存器,把参数放入其他指定的寄存器,然后调用INT 21,中断返回后,程序从指定的寄存器(通常是AL)里取得返回值。这样的做法一直到奔腾2也就是P6出来之前都没有变,譬如windows通过INT 2E提供系统调用,Linux则是INT 80,只不过后来的寄存器比以前大一些,而且可能再多一层跳转表查询。后来,Intel和AMD分别提供了效率更高的SYSENTER/SYSEXIT和SYSCALL/SYSRET指令来代替之前的中断方式,略过了耗时的特权级别检查以及寄存器压栈出栈的操作,直接完成从RING 3代码段到RING 0代码段的转换。系统调用都提供什么功能呢?用操作系统的名字加上对应的中断编号到谷歌上一查就可以得到完整的列表 (Windows, Linux),这个列表就是操作系统和应用程序之间沟通的协议,如果需要超出此协议的功能,我们就只能在自己的代码里去实现,譬如,对于内存管理,操作系统只提供进程级别的内存段的管理,譬如Windows的virtualmemory系列,或是Linux的brk,操作系统不会去在乎应用程序如何为新建对象分配内存,或是如何做垃圾回收,这些都需要应用程序自己去实现。如果超出此协议的功能无法自己实现,那我们就说该操作系统不支持该功能,举个例子,Linux在2.6之前是不支持多线程的,无论如何在程序里模拟,我们都无法做出多个可以同时运行的并符合POSIX 1003.1c语义标准的调度单元。可是,我们写程序并不需要去调用中断或是SYSCALL指令,这是因为操作系统提供了一层封装,在Windows上,它是NTDLL.DLL,也就是常说的Native API,我们不但不需要去直接调用INT 2E或SYSCALL,准确的说,我们不能直接去调用INT 2E或SYSCALL,因为Windows并没有公开其调用规范,直接使用INT 2E或SYSCALL无法保证未来的兼容性。在Linux上则没有这个问题,系统调用的列表都是公开的,而且Linus非常看重兼容性,不会去做任何更改,glibc里甚至专门提供了syscall(2)来方便用户直接用编号调用,不过,为了解决glibc和内核之间不同版本兼容性带来的麻烦,以及为了提高某些调用的效率(譬如__NR_ gettimeofday),Linux上还是对部分系统调用做了一层封装,就是VDSO (早期叫linux-gate.so)。可是,我们写程序也很少直接调用NTDLL或者VDSO,而是通过更上一层的封装,这一层处理了参数准备和返回值格式转换、以及出错处理和错误代码转换,这就是我们所使用语言的运行库,对于C语言,Linux上是glibc,Windows上是kernel32(或调用msvcrt),对于其他语言,譬如Java,则是JRE,这些“其他语言”的运行库通常最终还是调用glibc或kernel32。“运行库”这个词其实不止包括用于和编译后的目标执行程序进行链接的库文件,也包括了脚本语言或字节码解释型语言的运行环境,譬如Python,C#的CLR,Java的JRE。对系统调用的封装只是运行库的很小一部分功能,运行库通常还提供了诸如字符串处理、数学计算、常用数据结构容器等等不需要操作系统支持的功能,同时,运行库也会对操作系统支持的功能提供更易用更高级的封装,譬如带缓存和格式的IO、线程池。所以,在我们说“某某语言新增了某某功能”的时候,通常是这么几种可能:
struct chan {
bool ready,
int data
};int read (struct chan *c) {
while (1) {
if (c->ready) {
c->ready = false;
return c->data;
} else {
schedule();
}
}
}void write (struct chan *c, int i) {
while (1) {
if (c->ready) {
schedule();
} else {
c->data = i;
c->ready = true;
schedule(); // optional
return;
}
}
}
很显然,如果是多线程的话,我们需要通过线程库或系统调用提供的同步机制来保护对这个结构体内数据的访问。以上就是最简化的一个并发框架的设计考虑,在我们实际开发工作中遇到的并发框架可能由于语言和运行库的不同而有所不同,在功能和易用性上也可能各有取舍,但底层的原理都是殊途同归。譬如,glic里的getcontext/setcontext/swapcontext系列库函数可以方便的用来保存和恢复任务执行状态;Windows提供了Fiber系列的SDK API;这二者都不是系统调用,getcontext和setcontext的man page虽然是在section 2,但那只是SVR4时的历史遗留问题,其实现代码是在glibc而不是kernel;CreateFiber是在kernel32里提供的,NTDLL里并没有对应的NtCreateFiber。在其他语言里,我们所谓的“任务”更多时候被称为“协程”,也就是Coroutine。譬如C++里最常用的是Boost.Coroutine;Java因为有一层字节码解释,比较麻烦,但也有支持协程的JVM补丁,或是动态修改字节码以支持协程的项目;PHP和Python的generator和yield其实已经是协程的支持,在此之上可以封装出更通用的协程接口和调度;另外还有原生支持协程的Erlang等,笔者不懂,就不说了,具体可参见Wikipedia的页面:http://en.wikipedia.org/wiki/Coroutine由于保存和恢复任务执行状态需要访问CPU寄存器,所以相关的运行库也都会列出所支持的CPU列表。从操作系统层面提供协程以及其并行调度的,好像只有OS X和iOS的Grand Central Dispatch,其大部分功能也是在运行库里实现的。5. goroutineGo语言通过goroutine提供了目前为止所有(我所了解的)语言里对于并发编程的最清晰最直接的支持,Go语言的文档里对其特性也描述的非常全面甚至超过了,在这里,基于我们上面的系统知识介绍,列举一下goroutine的特性,算是小结:(1) goroutine是Go语言运行库的功能,不是操作系统提供的功能,goroutine不是用线程实现的。具体可参见Go语言源码里的pkg/runtime/proc.c(2) goroutine就是一段代码,一个函数入口,以及在堆上为其分配的一个堆栈。所以它非常廉价,我们可以很轻松的创建上万个goroutine,但它们并不是被操作系统所调度执行(3) 除了被系统调用阻塞的线程外,Go运行库最多会启动$GOMAXPROCS个线程来运行goroutine(4) goroutine是协作式调度的,如果goroutine会执行很长时间,而且不是通过等待读取或写入channel的数据来同步的话,就需要主动调用Gosched()来让出CPU(5) 和所有其他并发框架里的协程一样,goroutine里所谓“无锁”的优点只在单线程下有效,如果$GOMAXPROCS > 1并且协程间需要通信,Go运行库会负责加锁保护数据,这也是为什么sieve.go这样的例子在多CPU多线程时反而更慢的原因(6) Web等服务端程序要处理的请求从本质上来讲是并行处理的问题,每个请求基本独立,互不依赖,几乎没有数据交互,这不是一个并发编程的模型,而并发编程框架只是解决了其语义表述的复杂性,并不是从根本上提高处理的效率,也许是并发连接和并发编程的英文都是concurrent吧,很容易产生“并发编程框架和coroutine可以高效处理大量并发连接”的误解。(7) Go语言运行库封装了异步IO,所以可以写出貌似并发数很多的服务端,可即使我们通过调整$GOMAXPROCS来充分利用多核CPU并行处理,其效率也不如我们利用IO事件驱动设计的、按照事务类型划分好合适比例的线程池。在响应时间上,协作式调度是硬伤。(8) goroutine最大的价值是其实现了并发协程和实际并行执行的线程的映射以及动态扩展,随着其运行库的不断发展和完善,其性能一定会越来越好,尤其是在CPU核数越来越多的未来,终有一天我们会为了代码的简洁和可维护性而放弃那一点点性能的差别。