为什么要要读 golang 的源码

大家都知道 golang 1.5 是一个里程碑版本,因为这个版本实现了 golang 的自举,也就是说 golang 整个语言的运行时用自己 golang 来实现了,除了少量的汇编语言,实现自举充分说明了 golang 的稳定性。所以我读 golang 的源码的源码不仅能够学习 golang 语言,还能学习到 google 的对 golang 的设计,学习 golang 能够将汇编,编译原理,链接,操作系统 这四个方面的知识连成一个整体,对自己本身系统知识的了解和熟悉也能有较大的提升。

golang 的精髓包含两个方面

  • golang 的内存管理和垃圾回收
  • golang 的协程序调度

golang 在语言层面就实现了协程的支持,这样能大大减轻程序员在并发编程上的心智负担。很好的驾驭了多核云时代。使用 golang 实现的明星项目就不少了,

  • 容器相关docker,kubernetes
  • etcd/consul
  • 数据库相关:influxdb,TiDB
  • 区块链技术:fabric,chain

更加详细的信息可以戳 这里 基本上当前热门和有趣的项目大部分都是 golang 开发的,可以说我们正在经历一个基础设施有 c 到 golang 重写的过程中。

Golang 语言运行时有两个皇冠上的明珠,其一为内存管理和垃圾收集,内存管理是基于 google tcmalloc 算法实现的,其二就是 golang 的 goroutine 设计和调度。我们这次先分析 golang 的 goroutine 和调度器。

现代操作系统的调度

cpu 中一些基本的概念

我们先来看看现代计算机的一般结构

CPU调度

注意上图中的一些重要的组件

  • pc: 程序计数器,主要标示下一条指令的位置,同时注意 pc 不能通过普通命令如:mov 等来改变这个,只能通过 jmp, call/ret, int 这些命令来修改它
  • 由于寄存器是有限的,当 cpu 完成指令时,需要的输入或者输出超出了寄存器的个数时,必需配合内存来工作,这时需要时使用栈标示寄存器
  • 由于外设是通过 int 中断来和 cpu 通讯,或者程序内存错误如除 0 等,这些情况都会修改标志寄存器

线程(Thread)

  1. 系统内核态,更轻量的进程
  2. 由系统内核进行调度
  3. 同一进程的多个线程可共享资源

线程的出现解决了两个问题,一个是GUI出现后急切需要并发机制来保证用户界面的响应。第二是互联网发展后带来的多用户问题。最早的CGI程序很简单,将通过脚本将原来单机版的程序包装在一个进程里,来一个用户就启动一个进程。但明显这样承载不了多少用户,并且如果进程间需要共享资源还得通过进程间的通信机制,线程的出现缓解了这个问题。

线程的使用比较简单,如果你觉得这块代码需要并发,就把它放在单独的线程里执行,由系统负责调度,具体什么时候使用线程,要用多少个线程,由调用方决定,但定义方并不清楚调用方会如何使用自己的代码,很多并发问题都是因为误用导致的,比如Go中的map以及Java的HashMap都不是并发安全的,误用在多线程环境就会导致问题。另外也带来复杂度:

  1. 竞态条件(race conditions) 如果每个任务都是独立的,不需要共享任何资源,那线程也就非常简单。但世界往往是复杂的,总有一些资源需要共享,比如前面的例子,开发人员和市场人员同时需要和CEO商量一个方案,这时候CEO就成了竞态条件。
  2. 依赖关系以及执行顺序 如果线程之间的任务有依赖关系,需要等待以及通知机制来进行协调。比如前面的例子,如果产品和CEO讨论的方案依赖于市场和CEO讨论的方案,这时候就需要协调机制保证顺序。

为了解决上述问题,我们引入了许多复杂机制来保证:

  • Mutex(Lock) (Go里的sync包, Java的concurrent包)通过互斥量来保护数据,但有了锁,明显就降低了并发度。
  • semaphore 通过信号量来控制并发度或者作为线程间信号(signal)通知。
  • volatile Java专门引入了volatile关键词来,来降低只读情况下的锁的使用。
  • compare-and-swap 通过硬件提供的CAS机制保证原子性(atomic),也是降低锁的成本的机制。

如果说上面两个问题只是增加了复杂度,我们通过深入学习,严谨的CodeReview,全面的并发测试(比如Go语言中单元测试的时候加上-race参数),一定程度上能解决(当然这个也是有争议的,有论文认为当前的大多数并发程序没出问题只是并发度不够,如果CPU核数继续增加,程序运行的时间更长,很难保证不出问题)。但最让人头痛的还是下面这个问题:

系统里到底需要多少线程?

这个问题我们先从硬件资源入手,考虑下线程的成本:

  • 内存(线程的栈空间)
    每个线程都需要一个栈(Stack)空间来保存挂起(suspending)时的状态。Java的栈空间(64位VM)默认是1024k,不算别的内存,只是栈空间,启动1024个线程就要1G内存。虽然可以用-Xss参数控制,但由于线程是本质上也是进程,系统假定是要长期运行的,栈空间太小会导致稍复杂的递归调用(比如复杂点的正则表达式匹配)导致栈溢出。所以调整参数治标不治本。

  • 调度成本(context-switch)
    我在个人电脑上做的一个非严格测试,模拟两个线程互相唤醒轮流挂起,线程切换成本大约6000纳秒/次。这个还没考虑栈空间大小的影响。国外一篇论文专门分析线程切换的成本,基本上得出的结论是切换成本和栈空间使用大小直接相关。

  • CPU使用率
    我们搞并发最主要的一个目标就是我们有了多核,想提高CPU利用率,最大限度的压榨硬件资源,从这个角度考虑,我们应该用多少线程呢?

这个我们可以通过一个公式计算出来,100/(15+5)*4=20,用20个线程最合适。但一方面网络的时间不是固定的,另外一方面,如果考虑到其他瓶颈资源呢?比如锁,比如数据库连接池,就会更复杂。

作为一个1岁多孩子的父亲,认为这个问题的难度好比你要写个给孩子喂饭的程序,需要考虑『给孩子喂多少饭合适?』,这个问题有以下回答以及策略:

  • 孩子不吃了就好了(但孩子贪玩,不吃了可能是想去玩了)
  • 孩子吃饱了就好了(废话,你怎么知道孩子吃饱了?孩子又不会说话)
  • 逐渐增量,长期观察,然后计算一个平均值(这可能是我们调整线程常用的策略,但增量增加到多少合适呢?)
  • 孩子吃吐了就别喂了(如果用逐渐增量的模式,通过外部观察,可能会到达这个边界条件。系统性能如果因为线程的增加倒退了,就别增加线程了)
  • 没控制好边界,把孩子给给撑坏了 (这熊爸爸也太恐怖了。但调整线程的时候往往不小心可能就把系统搞挂了)

通过这个例子我们可以看出,从外部系统来观察,或者以经验的方式进行计算,都是非常困难的。于是结论是:

让孩子会说话,吃饱了自己说,自己学会吃饭,自管理是最佳方案。

然并卵,计算机不会自己说话,如何自管理?

但我们从以上的讨论可以得出一个结论:

  • 线程的成本较高(内存,调度)不可能大规模创建
  • 应该由语言或者框架动态解决这个问题

kernel 是如何调度线程的

在Linux中,线程是由进程来实现,线程就是轻量级进程( lightweight process ),因此在Linux中,线程的调度是按照进程的调度方式来进行调度的,也就是说线程是调度单元。Linux这样实现的线程的好处的之一是:线程调度直接使用进程调度就可以了,没必要再搞一个进程内的线程调度器。

在Linux中,调度器是基于线程的调度策略(scheduling policy)和静态调度优先级(static scheduling priority)来决定那个线程来运行。

对于下面三种调度策略SCHED_OTHER, SCHED_IDLE, SCHED_BATCH,其调度优先级sched_priority是不起作用的,即可以看成其调度优先级为0;调度策略SCHED_FIFO和SCHED_RR是实时策略,他们的调度值范围是1到99,数值越大优先级越高,另外实时调度策略的线程总是比前面三种通常的调度策略优先级更高。

通常,调度器会为每个可能的调度优先级(sched_priority value)维护一个可运行的线程列表,并且是以最高静态优先级列表头部的线程作为下次调度的线程。所有的调度都是抢占式的:如果一个具有更高静态优先级的线程转换为可以运行了,那么当前运行的线程会被强制进入其等待的队列中。下面介绍几种常见的调度策略:

  • SCHED_OTHER:该策略是是默认的Linux分时调度(time-sharing scheduling)策略,它是Linux线程默认的调度策略。SCHED_OTHER策略的静态优先级总是为0,对于该策略列表上的线程,调度器是基于动态优先级(dynamic priority)来调度的,动态优先级是跟nice中相关(nice值可以由接口nice, setpriority,sched_setattr来设置),该值会随着线程的运行时间而动态改变,以确保所有具有SCHED_OTHER策略的线程公平运行。在Linux上,nice值的范围是-20到+19,默认值为0;nice值越大则优先级越低,相比高nice值(低优先级)的进程,低nice值(高优先级)的进程可以获得更多的处理器时间。使用命令ps -el查看系统的进程列表,其中NI列就是进程对应的nice值;使用top命令,看到的NI列也是nice值。运行命令的时候可用nice –n xx cmd来调整cmd任务的nice值,xx的范围是-20~19之间。

  • SCHED_FIFO:先入先出调度策略(First in-first out scheduling)。该策略简单的说就是一旦线程占用cpu则一直运行,一直运行直到有更高优先级任务到达或自己放弃。

  • SCHED_RR:时间片轮转调度(Round-robin scheduling)。该策略是SCHED_FIFO基础上改进来的,他给每个线程增加了一个时间片限制,当时间片用完后,系统将把该线程置于队列末尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。使用top命令,如果PR列的值为RT,则说明该进程采用的是实时策略,即调度策略是SCHED_FIFO或者为SCHED_RR,而对于非实时调度策略(比如SCHED_OTHER)的进程,该列的值是NI+20,以供Linux内核使用。

Goroutine 介绍

使用过 go 语言的同学都知道在 go 中实现一个 goroutine 是非常简单的,只需要使用关键字 go 就能运行一个 goroutine,那到底 goroutine 是什么?又是如何是实现的呢?这篇文章先试图讲清楚这两个问题,至于之后的具体实现和源码分析,我们随后写 blog 来阐述。

goroutine 翻译为 协程 字面意思是协同的程序?确实如此,就是协同的工作的程序。

咱们先看看协同的是啥,就是说有多个 goroutine 时,可以大家一起协同工作,那程序指啥呢?指的就是协同工作的内容了,咱们现在程序是运行在 cpu 上,所以就是一段 cpu 指令,对应就是咱们程序中的代码,因为咱们程序的代码分为 code data,就是 code 也就是咱们具体写的各个函数,因为咱们的 function 进过编译器编译后生成的咱可执行文件的 text segment,即 cpu 可执行的执行。

为什么需要协程

coroutine本质上是一种轻量级的thread,它的开销会比使用thread少很多。多个coroutine可以按照次序在一个thread里面执行,一个coroutine如果处于block状态,可以交出执行权,让其他的coroutine继续执行。

非阻塞I/O模型协程(Coroutines)使得开发者可以采用阻塞式的开发风格,却能够实现非阻塞I/O的效果隐式事件调度,

简单来说:协程十分轻量,可以在一个进程中执行有数以十万计的协程,依旧保持高性能。

goroutine 的一个主要特性就是它们的消耗;创建它们的初始内存成本很低廉(与需要 1 至 8MB 内存的传统 POSIX 线程形成鲜明对比)以及根据需要动态增长和缩减占用的资源。这使得 goroutine 会从 4096 字节的初始栈内存占用开始按需增长或缩减内存占用,而无需担心资源的耗尽。

实现 Goroutine 需要解决的问题

在上文中我讲了程序是啥,那么咱们这节就来看看要让 goroutine run 起来需要解决的问题有哪些?

  • code 运行起来后在电脑中最关键的数据有什么
  • 咱们的 goroutine 运行在操作系统上面临的问题有哪些
  • 咱们自身解决了上面的问题后,是不是引入新的问题

第一问题就得我们了解电脑的结构和运行是的原理,现代电脑都是 冯诺曼 体系的,而今天要回答这个问题,我们先得了解两个重要的组件,cpu 和 内存。有这些基础的同学都知道,cpu 和内存有几个重要的概念,寄存器 和 stack。 寄存器是 cpu 运行的重要组件可以和 cpu 来交换数据,而寄存是有限的,但是内存就要大的多,所以又变化而来了 stack 来和 cpu 交换数据。

  • 当单个 goroutine 结束后,调度器如何调度下个 goroutine
  • 当 goroutine 中存在系统调用并且系统调用阻塞了后,将会被 kernel 将这个线程挂起来,这样调度器就失去了调度当机会这样当情况怎么处理
  • 若是采用新启动一个线程来调度,大规模当网络程序如何处理
  • 当两个 goroutine 有交换数据当需求时,如何实现生产者和消费者当问题。

第二个问题:

  • 我们运行在用户态,是没有中断或系统调用这样的机制来打断代码执行的,那么,一旦我们的 schedule()代码把控制权交给了任务的代码,我们下次的调度在什么时候发生?答案是,不会发生,只有靠任务主动调用 schedule(),我们才有机会进行调度,所以,这里的任务不能像线程一样依赖内核调度从而毫无顾忌的执行,我们的任务里一定要显式的调用 schedule(),这就是所谓的协作式(cooperative)调度。(虽然我们可以通过注册信号处理函数来模拟内核里的时钟中断并取得控制权,可问题在于,信号处理函数是由内核调用的,在其结束的时候,内核重新获得控制权,随后返回用户态并继续沿着信号发生时被中断的代码路径执行,从而我们无法在信号处理函数内进行任务切换)

  • 堆栈。和内核调度线程的原理一样,我们也需要为每个任务单独分配堆栈,并且把其堆栈信息保存在任务属性里,在任务切换时也保存或恢复当前的SS:ESP。任务堆栈的空间可以是在当前线程的堆栈上分配,也可以是在堆上分配,但通常是在堆上分配比较好:几乎没有大小或任务总数的限制、堆栈大小可以动态扩展(gcc有split stack,但太复杂了)、便于把任务切换到其他线程。

Metadata 组织

既然是协作式的,那我们就得知道怎么样来协作,协作的隐含的一个意思就是可调度,既然要可调度,就得又调度的依据即数据,应为没有数据就没有调度的依据,而一般调度数据是通过埋点收集起来,goroutine 也不例外,通过自身 runtime 的数据来组织这些需要的数据。

通过上一节的说明我们大概知道了一个程序要运行起来几个重要的状态信息

  • 寄存器的相关状态,如 PC,SP,Flag 等
  • 程序运行起来后的 stack 状态

这两个数据是 goroutine 能调度运行的关键

syscall 和 network 的问题

goroutine 程序也是运行在操作系统系统之上,那么操作系统上的进程或者线程都是受操作系统管控的,我们知道和操作系统通讯只有两个方式一个中断,如 io,设备的中断,一个系统调用,其实这也是利用的中断。当操作系统陷入中断时就陷入内核这时,不是在用户态了,也就不受用户的管控,如果这是因为一个长时间的 io,操作系统会将这个线程或者进程调度让出,这是 golang 用户台的调度也就没有机会运行了。对于 network stack 上问题就更加突出,应为使用 golang 大都是网络程序,有着成千上万的网络链接。解决上面的两个 golang 主要使用了两个方式

  • 监控 syscall,若是耗时的系统调用使用单独的线程服务
  • 使用非阻塞的方式,在 network stack 使用的 epoll/kqueue 非阻塞网络技术

goroutine 之间的数据同步问题

引入 goroutine 时,当两个或者多个 goroutine 需要通讯时,如生产者和消费这样的场景是很常见,当消费者向生产者要数据时,生产者的数据还没有准备好,这是就应该让消费者挂起来,反正亦然。对于者问题,golang 使用 channel 来解决

CSP并发模型

CSP 描述这样一种并发模型:多个Process 使用一个 Channel 进行通信, 这个 Channel 连结的 Process 通常是匿名的,消息传递通常是同步的(有别于 Actor Model)。

CSP模型是上个世纪七十年代提出的,用于描述两个独立的并发实体通过共享的通讯 channel(管道)进行通信的并发模型。 CSP中channel是第一类对象,它不关注发送消息的实体,而关注与发送消息时使用的channel。

Golang 就是借用CSP模型的一些概念为之实现并发进行理论支持,其实从实际上出发,go语言并没有,完全实现了CSP模型的所有理论, 仅仅是借用了 process和channel这两个概念。process是在go语言上的表现就是 goroutine 是实际并发执行的实体,每个实体之间是通过channel通讯来实现数据共享。

Golang中使用 CSP中 channel 这个概念。channel 是被单独创建并且可以在进程之间传递,它的通信模式类似于 boss-worker 模式的,一个实体通过将消息发送到channel 中,然后又监听这个 channel 的实体处理,两个实体之间是匿名的,这个就实现实体中间的解耦,其中 channel 是同步的一个消息被发送到 channel 中,最终是一定要被另外的实体消费掉的,在实现原理上其实是一个阻塞的消息队列。

Goroutine 是实际并发执行的实体,它底层是使用协程(coroutine)实现并发,coroutine是一种运行在用户态的用户线程,类似于 greenthread,go底层选择使用coroutine的出发点是因为,它具有以下特点:

  • 用户空间 避免了内核态和用户态的切换导致的成本
  • 可以由语言和框架层进行调度
  • 更小的栈空间允许创建大量的实例

参考