编程语言底层之系统和并发

课程介绍

现代语言大部分会有 Runtime，类似在操作系统以外再抽象出一层虚拟机，它接管着很多东西，比如内存、垃圾回收、甚至包含现在的并发调度任务执行。内存管理、垃圾回收、并发调度是 Go 语言的 Runtime 中最核心的东西，本系列课程内容将深入剖析 Runtime 三大组件，内存分配器、垃圾回收器、Goroutine 调度。

相关联的系列达人课：《编程语言底层之数据结构》和《编程语言底层之函数执行》。

作者介绍

李永京，从事互联网后端系统开发，擅长高并发分布式系统，熟悉 Go、C、C#、Python 等语言。架构龙珠直播平台基础框架，开发过道具、任务、红包、直播、聊天、调度系统等。曾任职阿里妈妈，开发过移动广告 DMP、DSP、广告数据人群分析等。个人博客 积分排名前 30，300万 PV。

课程内容

导读：概述

引入

现在编程语言抽象化越来越剧烈，我们时刻提醒自己有上下两条分界线拘束着，下面的分界线称之为系统层面，上面的分界线称之为创意层面，系统层面偏向于基础研究，包括像操作系统、编译器和其他东西，而上面一层更多的是各种创意。我们大部分在中间，因为大部分人对于研究基础不感兴趣，往上创意层面非常需要灵感和天赋的，不是努力就能做到的，所以尽量扩展我们的层面越广阔越好。

系统层面上的各种各样的创新扩宽了整个世界，它给创意层面提供了更广阔的舞台，而创意层面除了把现在的东西发挥的很好以外还提供了各种各样的创意反过来促进底层的研究。现在很多科技在很早就出现在早期的科幻小说电影里慢慢的变成现实。系统层面的封装特别多，创意层面各种各样设计让大家使用起来越来越简单。

换句话说，对于中间层面的人来说可怕的在于表面上接触了越来越多的东西，实际上离底层和上层越来越远。一些语言把原来需要自己处理的东西做了一层包装 Runtime，造成了我们是很普通的使用者。科技越来越发展，我们甚至写的程序放在哪里怎么运行都不关心，服务器虚拟化调度越来越简单，甚至连服务器优化都不用管了。系统底层实际上用各种各样手段进一步的封装，把原来复杂的设计搞得越来越简单，所以对 Runtime 的了解是非常有必要的。

现代语言大部分会有 Runtime，类似在操作系统以外再抽象出一层虚拟机，它接管着很多东西，比如内存、垃圾回收、甚至包含现在的并发调度任务执行。内存管理、垃圾回收、并发调度是 Go 语言的 Runtime 中最核心的东西，这个系列深入剖析 Runtime 三大组件，内存分配器、垃圾回收器、Goroutine 调度。

内容介绍

现在用几句话概括这个系列的内容。

内存管理涉及两个核心问题，第一是快速分配，第二是适可而止。Go 语言基于 tcmalloc 实现的内存分配器，tcmalloc 就是 Google 开发的快速内存分配器，它本身就是基于并发设计的，目的是找到相对比较好的平衡，既有很高的性能同时内存消耗不会太夸张。Go 语言使用了 Heap、Central、Cache 三级机构实现分解锁，两级平衡，既照顾了快速分配同时又照顾了内存节约。

Go 语言垃圾回收器使用三色标记的方式扫描标记对象，使用写屏障模式实现并发标记和并发清理，使用控制器辅助回收一系列的措施做到垃圾回收。垃圾回收器只是一种辅助装置，它从来不是核心装置它只是辅助回收，它没有办法让程序变的很好，只不过现在不需要用代码时时刻刻去关心释放内存，但是它永远不可能让程序变的更好，因为它不够聪明。

Go 语言提供的 Goroutine 模型相对设计的相当不错的，Goroutine 本身就是基于并发设计的。如果有一个虚拟机的话，必须要有处理器，各种各样的运行的并发任务和具体执行机构线程，处理器的数量决定了并发的任务数量，通过相关的命令创建大量的任务。Goroutine 这样的 G、M、P 模型实际上就为了摆脱对操作系统层面上的依赖，不用考虑线程，不用考虑并发对于核的处理。

Go 语言的 Channel 模型只能在进程内进行通讯，在各种各样的算法里面频繁的使用，显然比内存共享要花的代价大很多，但是它的抽象层面可以做到解耦。Channel 模型根本不需要对方是谁，只要约定好格式化数据放到某个通道里去，在通道上面与使用者无关，这实际上都是架构层面上的解耦。

同步模块中提供了互斥锁（Mutex）、读写锁（RWMutex）、条件锁（Cond）、信号量（Semaphore）、自旋锁（SpinLock）、原子操作（Atomic），平常开发中肯定会使用锁这样概念，为了数据竞争我们需要加个锁，他们有不同的性能差别，也就意味着不同的锁适合用在不同的场合。

内容大纲

系统模块（内存管理、垃圾回收、Goroutine 调度）：

• 自主实现内存管理
• 内存管理面临的问题
• Go 基于 tcmalloc 实现的内存分配器工作原理
• 如何释放物理内存
• 垃圾回收常用方式：引用计数、代龄、标记清理
• 垃圾回收何时启动？如何避免内存膨胀，避免影响性能
• Go 三色标记 + 写屏障模式如何实现并发标记和并发清理
• 控制器和辅助回收的作用
• Goroutine 调度 G、M、P 模型
• 如何创建 Goroutine
• 如何启动并发任务
• 调度器如何执行
• M/P 对应关系
• 分段栈的问题是什么
• 连续栈如何实现
• 连续栈回收
• 连续栈扩张问题演示
• 系统监控的用途
• 强制垃圾回收
• 释放物理内存
• 抢占调度
• 处理系统调用
• I/O 事件

并发模块（进程、线程、协程、通信、同步）：

• 进程、线程的区别
• 系统线程和用户线程的区别
• CPU 时间片分配方式
• 协程基本原理、优点和缺点
• 上下文切换以及对性能的影响
• 通道基本原理
• 同步通道和异步通道的区别
• Goroutine 资源泄漏
• 常见同步方式
• 互斥锁（Mutex）
• 读写锁（RWMutex）
• 条件锁（Cond）
• 信号量（Semaphore）
• 自旋锁（SpinLock）
• 原子操作（Atomic）
• 单核和多核指令是否原子
• 如何实现原子操作
• CAS（Compare-and-swap）
• 用原子操作实现自旋锁

第01课：内存管理

本节内容：

• 自主实现内存管理
• 内存管理面临的问题
• Go 基于 tcmalloc 实现的内存分配器工作原理
• 如何释放物理内存

自主实现内存管理

在 C 语言中直接调用malloc、free、new、delete系统调用由操作系统分配内存很简单，但是几乎所有的新语言都自主管理内存，为什么要自主管理内存？由操作系统管理内存有哪些问题？

C 语言中向操作系统申请或者释放内存需要做系统调用的，否则操作系统没有办法收到申请和释放的信号，向操作系统申请，操作系统需要在 mmu 建立映射，建立映射后给内存读写数据，自主管理内存肯定需要减少系统调用带来的系统消耗。

如果由操作系统管理的话可以避免每种语言都自己实现内存管理，操作系统为什么不管理呢？最主要原因是操作系统根本不知道怎么内存复用，对于操作系统来说，内存复用也就意味着内存不释放。操作系统上运行着各种各样的应用程序，不同语言对于内存使用方式也不一样，选择不同的操作系统，选择不同的编程语言，这里的变化都不好控制。当然有些专业的定制的操作系统，专门为某种事开发的操作系统最好的方案是所有事都管，比如像军事上的，把权限交给用户也就意味着风险失控。对于普通的操作系统来说，进程崩溃操作系统是不关心的，操作系统甚至主动把长期不用的线程或者进程干掉，就像我们做架构设计时候一样的，把职责分清楚。

所以在语言层面上去实现内存分配带来很多好处，第一减少系统调用带来的系统开销，第二自己实现内存复用体系，第三可以和垃圾回收器配合设计得非常精巧，垃圾回收器是回收内存，需要和内存分配器打交道，垃圾回收器不停的进化，内存分配器也要配合它不停的进化。换句话说，既然不使用操作系统的内存管理，操作系统提供的太原始了，那么我们应该怎么做呢？

内存管理面临的问题

简单的想象内存如何管理的，每个程序有一段用户地址空间 VA，它实际上会被映射到不同的部分，比如 .text 段、.data 段。我们使用mmap系统调用在用户地址空间上主动申请 1MB 大小内存空间，然后把 1MB 空间以8字节为单位分配相同大小的格子，每个格子都是8字节，使用链表把这些格子管理起来。需要使用内存的时候，最小单位是在 1-8 字节之间不需要分配，直接在链表上取一个出来直接使用，比如需要1字节空间，取8字节的空间格子，其他7字节就当作浪费掉，用完之后把内存重新放回到链表中去，接下来这段内存又可以被 1-8 字节使用，为什么说要把它切成8字节呢，很显然是一种策略是适用 1-8 字节的内存分配的复用。

如果不切成大小相等的格子会出现什么状态呢？比如一次切走了1字节，接下来切走3字节，接下来1字节放回来以后，后面空间还在用，除非下次正好用1字节，否则一直用不上，慢慢的切来切去，结果越切越小，最后会形成碎片化，没法管理。Java 语言和 C# 语言内存回收的时候可以把使用的内存全部压缩搬到左边，把右边一大块空出来。C 语言和 Go 语言支持指针，搬的话地址就发生变化，本来大的地址搬到左边去了变成小地址了，所以 C 语言和 Go 语言不能对内存做压缩处理，不能把一个对象随便挪一个位置，除非用户逻辑自己去改变指针。

内存分配最优化的方法是按照固定大小的方式分配，例如以 8 字节策略，就有 60 多种方式可以管理好几万种不同大小分配了，比如 8 字节、16 字节、32 字节，这样简化了内存管理和复用，规格1以 8 字节为单位切的格子，规格2以 16 字节为单位切的格子，以此类推，当分配的时候只需要计算出这个对象的 size，比如 11 字节，然后计算出需要对应的规格，比如规格2，直接在规格 2 上分配内存块就可以了，用完以后再放回规格 2，这样好处是内存复用会很方便，取内存和放回内存也很方便，还有这种规格大小的很难形成碎片化，因为很容易复用，所有内存都是有固定大小的。

实际如何来分配呢？我们逆向推导这个过程，比如需要做分配操作new(15)，先找到对应的规格，假如是 2 对应 16 字节大小，那么去规格 2 空间找有没有剩余可用的块，有的话直接拿出来，如果没有的话，看有没有大块的内存*块，如果有的话把它切成 16 字节大小的块，切完之后拿一块来用，没有大内存块就去向操作系统申请，一次申请 1M *块去切，尽管需要只是 16 字节但也申请 1M，申请后分配很多个 16 字节大小的格子，接下来所有分配内存都会从 16 字节格子上去取，这样就减少向操作系统申请的次数，这也是内存复用优化。还有种复用，假设在 16 字节格子切出 100 个，切出的内存都没有再用，就可以把 100 个格子整个内存块还原成*块，这个*块需要的时候可以切成 32 字节、64 字节、8 字节其他规格。

内存复用有两种体系，第一种是规格相同的复用，第二种是把切好的一整块大的内存块还原成*块，*块可以用来切成其他的单位。 很显然申请的 1M 内存可以有不同的复用方式。我们现在通过一种简单的策略知道内存管理简单的方式。无非是向操作系统申请一大块内存，用于减少向操作系统申请次数。申请一大块内存无非需要浪费很大内存空间，这里申请的是 VA 不是 PA，申请 1M 虚拟内存空间，操作系统肯定会及时返回，只有在写数据的时候才会去做 MMU 映射分配物理地址。

Go 基于 Tcmalloc 实现的内存分配器工作原理

Heap 机构的职责

上面介绍的是内存管理流程，Go 语言 Runtime 具体怎么管理的呢？首先操作系统有很大的内存空间，这个空间称之为堆 Heap，我们向操作系统申请大量的内存空间，有大有小，称之为*块，最小的*块是 1M，Heap 中很多*块，*块怎么管理起来呢？*块的管理方式很简单，对于内存来说它的分类方式两种方式，一个按照字节来分，这种分类方式太琐碎了，比如 1 字节、3 字节，数量太多不方便管理，最好的方式按照页为单位，内存块有多少页，申请*块时候说这块内存有多少页，操作系统管理内存的单位是页，一页可能有 8K、4K、2K，假设以 8K 为单位称之为 1 页，我们把所有为 1 页的*块放在一个链表里，把 2 页的*块放在 2 页的链表中，以此类推，这样把规格 1、规格 2 这样的链表建立数组。例如向堆上申请*块，要 2 页的，很简单，从数组以 2 为下标，找到链表，从链表里取一个就可以了，换句话说，向堆释放一个*块，它有多少页就放到哪个链表中去。

很显然，对于规格的数组有个预值，超过一个限度的*块，比如 100M 以上的*块，可能说 100M 以上的*块本来就很少，那么是 100M、101M、1000M 也好全部放在一起，我们管这些*块称之为大对象，上面规格的*块称之为小对象。实际在程序中小对象的数量是最多的，因为大多数分配内存都是在 1K 以下，起码都是在几页之内的，大对象数量非常的少，没有必要把大对象管理的非常复杂，比如说超过一定大小的来区分大对象还是小对象，每种语言对于这个大小都有预值。所有小对象以数组下标为单位，挂在链表数组里面去，所有大对象挂在单独的链表上去。

对于堆来说，无非就做两种事情，第一种事情是申请*块，首先从链表中去找，找到大小合适的，找不着的话，从大对象链表去找，可能涉及到比如申请 10 页大小的*块，但是 1-9 都没有了，那么只能找一个比 10 大的或者等于 10 的，就是说 1-10 没找到只能从 11 找，11 没有从 12 找，如果从 12 找到到*块，申请的是 10 页，但是当前*块是 12 页，剩下 2 页浪费太严重，怎么办？把 2 页切下来，10 页的拿走，2 页的放到 2 的数组里。所以当从堆里拿内存的时候，可能会对内存做切割处理，因为可能正好没有大小合适的，那没有 10 页怎么不向操作系统申请 10 页？有一大堆 12 页搁在那不用去向操作系统申请干嘛，把的空闲内存尽可能用起来，用完了才会向操作系统申请，同样的当*块归还给 Heap 的时候，这个*块最好方式做合并处理，为什么要合并，10 页和 2 页在两个地方，现在要 12 页怎么办？10 页不合适 2 页不合适只能向操作系统申请？最好方式把 10 页回收的时候把 10 页和 2 页合并为 12 页，12 页就可以适应 12 种变化，无非是要么正好要么接着切，所以向堆去取内存的时候，一种是多的地方要切出来，释放的时候尽可能合并成大块，因为大块可以适应不同的变化。我们现在大概知道 Heap 是用来干嘛的，堆是用来管理大块的*块，大块*块以页为单位划分到不同的地方。

Central 机构的职责

接下来*块需要有地方分配，所以需要一大堆门店，建门店有讲究了，一种方式是每个门店里有各种*块，比如 1 页、2 页的，这样话会造成很多问题，一是各种规格的用户请求拥挤过来会造成排队堵死，二是要考虑每种*块什么时候准备并且准备多少数量。换句话说，有很多这样的门店，用户请求也不知道应该去哪家，最好的方式怎么做呢？每种门店只提供一种规格的*块，比如 1 页的、2 页的、以此类推，用户请求需要什么样的规格的*块就去什么样的门店，这样也不会造成拥堵，如果说同一时间内要 1 页的用户请求多，那就排队，1 页和 2 页的申请快速分流，这是很简单的分布式做法。这样锁就分散了，不同规格放到一个地方不管取什么规格内存块都得上锁，我们把这种机构称之为 Central。

Cache 机构的职责

接下来就是具体的用户请求，当用户请求 1 页*块就去 1 号门店去申请，需要 2 页*块就去 2 号门店申请。用户请求会关联一个缓存 Cache，这个缓存是以规格大小来保存，为什么要建立缓存呢？因为这个用户请求可以绑定到当前执行线程 Thread 上去，根据相同的理论，当一个算法频繁的执行，可能会使用相同规格的内存块，比如说 for 循环或者频繁执行一个函数的时候，这种内存分配实际上是很有规律性的。

假设一个函数执行时候会使用 1、3、5 页这样规格的内存块，频繁的执行时候 1、3、5 页就会频繁的分配，换句话说这个用户请求就会频繁的去 1 号、3 号、5 号门店申请*块，这种频繁的操作很显然会影响程序性能，最好的方式是需要 1 页的时候一次性拿回 10 个 1 页，需要 3 页的时候一次性拿回 10 个 3 页，这样去 1 号门店、3 号门店本来要去 20 次，在门口需要去抢 20 次锁，现在每次拿 10 个去两次就可以了，1 号门店去一次、3 号门店去一次。因为 Central 做一次分流，Cache 一次拿回更多的*块做了第二次分流，减少同一个 Central 里大量拥挤的行为。

有这样的场景，高峰期时候去门店，前面很多请求需要排很长的队，如果每次去都申请很多的话，就不用太长时间排队了，这个门店实际上就被分流了，这是第二次分流。还有和线程绑定了之后，它从 Cache 中取内存块时候不需要加锁，因为每个 Cache 是和 Thread 是绑定的，所以实际上是一次lock-free无锁处理，Thread 从它绑定的 Cache 分配和释放内存块操作都是针对 Cache 做操作。Central 级是需要加锁的，Heap 级也是需要加锁的，因为有一堆请求都要往里面去挤。但是 Cache 级不需要加锁的，就是 Cache 每次去 Central 取 10 个加一次锁，接下来用这 10 个时候不需要加锁，因为每个 Cache 是同 Thread 绑定的，除非 Cache 拿回的 10 个全部用完了继续去门店时候才会去加锁，所以这地方用三级机构分解锁。

所以现在的流程是分配内存时候，首先检查 Cache 里有没有，如果有的话直接返回，如果没有的话去检查应该去哪个门店，从门店取回一批，一批是 10 个，Go 语言在初始化时候建立一个静态表，通过这个表查出来到底需要多少个，这个数字基于大量的统计得到的，有些语言根据程序运行期动态调整这个数字。从 Central 里面去取，如果 Central 正好有这样的资源，那就拿回来，如果 Central 没有，它就去 Heap 中去取大块*块，切回，如果 Heap 没有多余的*块，去操作系统 OS 申请。

接下来带来的问题是 Cache 上会积累了大量的可用资源，比如 1 号拿回 10 个，但是每次操作只使用 1 个操作完放回去，剩下 9 个长时间不用，这样浪费很严重，谁来触发回收操作呢？由 GC 来触发的，它把 9 个收回退回 Central 以后可以交给别的线程来用，这是第一级平衡。

还有可能某段时间都频繁使用 2 号 Central，会造成一段时间 Central 会产生大量的内存，如果 Central 存在大量挤压，它会找出相对完整的大块，把它退还给 Heap，Heap 会把这些内存切成别的规格的内存在不同的 Central 之间做平衡，这样内存块才不会有大量的闲置浪费。这就涉及到两级平衡，一个是 Cache 不能有大量的积累，尽可能归还 Central，第二级是不同的 Central 之间的平衡，有可能 Central 有大量的闲散资源，把这些闲散资源交还给 Heap，Heap 可以把这些资源分配给 1 号 Central 或者 3 号 Central。

任何时候内存管理都会涉及两个核心问题，第一个快速分配，比如实现lock-free，减少锁，因为 Central 肯定会被很多 Cache 共享的，取数据必须要排队或者加锁处理，Heap 是被不同的 Central 共享的，都会加锁。第二个不能有太多的浪费行为需要适可而止，分配的是 VA 地址，但是写过数据了，PA 还在，除非还给操作系统，有可能会占用大量的资源，所以尽可能在内存复用方面做到平衡，平衡既要在快速分配中进行操作，快速操作也就意味着用批处理代替单次处理，我们很多时候用批处理代替单次处理实现性能提升，但是批处理很显然会浪费大量的资源，在另一端我们要做节约，所以一是实现批处理来实现快速的性能，一是实现内存节约避免快速消耗，需要在中间找到平衡点。

很显然，Go 语言使用了三级机构既照顾了快速分配同时又照顾了内存节约，所以它从一开始就是基于并发设计的一种内存分配模型。因为 Go 语言内存分配模型就是基于 tcmalloc。tcmalloc 本身就是 Google 开发的快速内存分配器，它本身就是基于并发设计的，这个原理在这个地方找到相对比较好的平衡，既有很高的性能同时内存消耗不会太夸张。

如何释放物理内存

比如程序上午 10:00 访问高峰，可能各种原因分配大量的内存，下午 13:00 时候访问低峰，大量的内存会堆在 Heap 上，因为 Central 有大量的资源都会退还给 Heap，这样会涉及到内存释放，需要把大量的 Heap 还给操作系统，一种方式彻底告诉操作系统内存不用了可以释放了，这种释放是 VA 和 PA 全部释放掉，这种方式就会造成地址空间形成很多空洞，下次这些空洞很难复用，这种释放算法不太合理。

Go 语言怎么做呢？不释放 VA，把 VA 挂在 Heap 上，只是向操作系统提个建议，某一段 VA 暂时不用，可以解除 VA 和 PA 的 mmu 映射，操作系统可能会触发两种行为，第一种行为操作系统物理内存的确不够用有大量的换入换出操作，就解除，第二种操作系统觉得物理内存挺大的，就搁那，但是知道了这段 PA 空间不可用了，在 Heap 中并没有把 VA 释放掉，下次分配正好用到当时解除的 VA，有可能会引发两种行为，第一种是 PA 映射没有解除直接拿过来用，第二种是 PA 被解除掉了会引发操作系统缺页异常，操作系统就会补上这段物理内存，这个过程对用户空间来说是不可见的，这样在用户空间觉得这段内存根本没有释放过，因为用户空间看到的永远是 VA，VA 上某段内存可能存在也可能不存在，它是否存在对用户逻辑来说根本不关心，这地方实际上是操作系统来管理，操作系统通过 mmu 建立映射，这会造成 64 位 VA 地址空间非常的大，只要申请就不释放，下次重复使用，只不过重复使用会补上。现在内存管理在 64 位下简单的多，无非 VA 用就用了，就不释放。Windows 操作系统没有建议解除，只能说全部释放掉。

tcmalloc、jemalloc、supper 三种常见内存分配器，很多应用都是基于前两种，比如 Redis 使用前两种替换系统调用的内存分配提升性能。编译 MySQL 时候建议使用前两种内存分配器。实现原理在大的层面上有些类似，细节处理上有些区别，选择一种做深入了解有助于对内存分配有深入认识，另外可以看出来在 64 位系统下很多东西被简化了，还有对于物理内存释放，我们经常看到释放了大量的内存但是物理内存 RSS 一直没有下去就是操作系统也扮演着一些角色。

第02课：垃圾回收常用方式

第03课：Go 语言垃圾回收实现

第04课：Goroutine 调度

第05课：连续栈

第06课：系统监控

第07课：进程、线程

第08课：协程和上下文切换

第09课：通道

第10课：Goroutine 架构设计

第11课：常见同步方式

第12课：原子操作

阅读全文: http://gitbook.cn/gitchat/column/5a7a80975a8e2a1cf2e2a955