一、前言
1.1 背景
记得去年组内的A系统遇到了一个线上问题，服务会周期性的出现耗时毛刺现象，同事经过长期的问题定位发现是由于Golang的垃圾回收机制导致的，原本对垃圾回收只是了解一个概念，但是了解过后发现原来垃圾回收里面有很多道道，下面我尝试着解开它的面貌。
1.2 什么是垃圾
程序在运行过程中，那些曾经申请在堆上存储，并且后续不再使用的对象，就是垃圾，我们需要把它所占用的内存释放掉。
1.3 谁在回收，为何要回收
这些垃圾是由系统帮忙回收吗？不是的，想想我们的垃圾是在堆上存储着，堆上的内存实际上是有用户程序进行管理的，自然垃圾要由用户程序进行回收，拿Golang来说，在程序进行启动的时候，会启动垃圾回收协程。那么自然的，由于堆上的内存是用户管理的，如果用户程序不主动回收，堆上的内存早晚被消耗一空。
1.4 垃圾回收的难点在哪
无论是哪种垃圾回收算法思想，都要做到两点：第一，要判断对象是否为垃圾。第二，垃圾对象的回收。标记清除类的算法，把这连个步骤完全的分开，造成STW（Stop The World），即为把整个用户的程序给挂起，这对在线服务来说实际上是致命的，为何要让垃圾回收与用户程序分开运行呢，合在一起跑不行吗？如果交叉在一起跑就会有新的问题才生，比如标记的过程中，有新的对象产生，标记的时候给落下了，那么回收节点会把这些新的对象直接给释放掉，这是不允许的，稍后我们会细说。由于STW是很多在线服务无法忍受的，所以后来人们基于这样的缺点发明了很多的垃圾回收算法，比如标记引用就是把垃圾回收程序“完美”的融合在了用户程序中，当然也有它自己的缺点，稍后说，最初版本的Golang采用的就是原始的标记清除，后来基于标记清除进行了改进，即我们稍后说的三色标记法，它的目的就是致力于减少STW时间。当然垃圾回收不只是关注STW时间，还有很多重要的指标需要我们关注，比如回收速度等等，基于这样的指标，人们提出了很多改进的方案，比如节点复制、分代收集。
二、堆与栈
记得之前写C++的时候，需要自己释放申请的内存，否则一不小心就搞的内存泄露了，而且只是模糊的知道new的内存是申请在堆上的，局部变量是存储在栈上，堆上的内存需要用户自己管理，栈上的则是系统管理。那么我们抛出几个问题： 1.为何堆上内存需要我们管理，而栈则不需要 2.堆与栈的本质是什么，二者又有什么区别 3.golang的协程又有什么不同 带着问题，我们一一道来。
2.1 Linux进程内存的布局
在了解堆与栈之前，我们先看下linux的进程是怎么使用物理内存的。 1.虚拟内存 想要完整的讲明白虚拟内存比较费劲，本文的目的是让读者从整体上明白虚拟内存的作用。我们带着问题来去解释虚拟内存会比较好一些： (1)为什么需要虚拟内存，它在解决什么问题？ 第一，在没有虚拟内存之前，所有的进程都是直接使用物理内存，这样是很危险的，某个进程一不小心就访问到了另外一个进程的数据，更严重一些，如果某个进程不小心修改了内核的内存数据，则会引起整个操作系统的崩溃。 其次，我们现在很多程序占用的内存很大，而我们的物理内存大小是有限的，比如你跑了10个进程就把内存占满了，你想再跑一个进程就无法实现了，这是现代操作系统无法接受的。 最后，进程直接使用物理内存对于连接器与加载器的设计要求更加复杂，归根结底是每个进程的地址空间是不定的，我们稍后细说。 (2)虚拟内存是如何解决的？ 什么是虚拟地址？ 我们的每个进程实际上都有一个完成的虚拟地址空间，32位的操作系统中，该虚拟地址空间是4G（好理解， 2^{32} 嘛），64位则有 2^{32} *4G的空间。 先给出一张图看一下，
在初期，CPU直接访问物理内存，而有了虚拟内存机制后，我们的CPU访问的地址都是虚拟地址，经过MMU地址翻译把虚拟地址转换为物理地址，然后再把对应的物理地址的数据传给CPU。总结一下几点来理解：
1).虚拟地址是如何转换到物理地址的呢，实际上在主存上存着一个映射表，每次进行地址转换的时候查询该表即可。
2).我们把虚拟地址空间划分为以页为单元，一般虚拟也大小在4KB-2MB之间，为了方便映射，我们的物理内存也是以页为单元进行管理，所以在1)中说的映射表的表项实际是页为单位。
3).其实我们的虚拟地址本质上把物理内存作为磁盘的高速缓存而已，也就是说我们的目标存储是磁盘，物理内存只是我们的缓存而已。它跟我们的CPU的目标地址是物理内存，只是把L1,L2,L3等作为高速缓存一样。
4).既然是缓存的概念，那么我们把虚拟内存中的虚拟页分为如图的三类：
未分配的：也就是说在虚拟内存上还未创建的页，不会占用磁盘空间，比如图中的虚拟页0和3。 缓存的：既然是缓存的，缓存是谁呢？我们刚才也说了是物理内存，所以这个缓存的代表的就是，在虚拟内存上已经创建页，并且还在物理内存上缓存着。比如图中的虚拟页1、4、6。 未缓存的：首先不在物理存储上，其次它是创建过的页，所以该页的内容只在磁盘上存储着。比如虚拟页2、5、7。
5).接下来我们看下，缓存命中的过程，不命中的过程，以及创建新的虚拟页的过程。
看上图，左边就是我们所说的映射表，首先我们看到虚拟地址空间的页在表中一一对应（通过固定的偏移量）。其次有一个有效位的概念，如果有效位为1就代表该页在物理内存中缓存着，右边一列的页号即为物理页号；如果有效位为0，则代表该也并未在物理内存缓存，但是如果右边一列为null，则代表，该虚拟页还未被创建，如果是一个非空页号，则是指向虚拟地址空间的页号。 接下来，我们看下CPU是如何访问到物理地址的： CPU想要读取某一个虚拟地址的内容，MMU根据虚拟地址定位到页表的索引，根据索引定位到对应的表项，如果该表项中的有效位为1，则直接读取右边的物理页号，找到对应的物理页读取内容即可，这就是所谓的页命中。如果标志为0，则代表该页并未命中缓存产生了缺页，则直接从虚拟地址所对应的磁盘中，把该页内容加载到物理内存中去，并且找到一个牺牲页，作为替换则会从物理内存中替换出去，如果该页被修改过，则会写回磁盘。当系统要分配一个新的虚拟页时，则会在磁盘上创建对应的虚拟页空间，更新映射表，指向该磁盘页。以上的三种操作都会相应的更新映射表。
6).疑问一：什么是系统颠簸？ 根据虚拟内存我们知道，进程在运行中实际上加载在物理内存中的数据只是少部分，但是它运行的还是很好，这要得益于我们的程序运行的局部性原理，所谓局部性原理指的是，我们的程序虽然总体使用的页面个数要很大甚至超过了物理内存的大小，但是在某一时刻，它的运行会只需要一小部分的活动页面上即可完成，我们把这部分的页面叫做工作集。但是如果我们的工作集的大小超出了我们的进程所占用的物理内存大小，可想而知，会不断的产生缺页，页面在磁盘与物理内存上换出换入。这就是我们的颠簸现象。
7).疑问二：每个进程占用的物理内存页数量是怎么确定的？ 我们知道进程运行中如果发生缺页，会在物理内存中寻找一个牺牲页，说明这个进程占用的物理内存页大小是有限制的，那么它占用的数量是如何确定呢？ 首先，给进程分配的物理页数有一个上限与下限，上限就是不能超过内存剩余的页数，下限比较有意思，我们来看看《操作系统概念》上是怎么解释的：一方面下限的目的是考虑性能问题，这个好理解些，但是另一方面，单个指令的完成需要的页数可能不止一个（间接引用导致的）,所以你分配的页数必须要保证一次指令的寻址操作，另外下限是给定的计算机结构定义的。 只有下限和上限还不够，我们来看看具体的页分配的策略。 算法有以下三种： 第一种：平均分配法，很简单，把物理页平均分配个每个进程，这种分配策略简单，但是没有考虑到每个进程需要的页数是不同的，所以我认为不太合理。 第二种：按照进程的大小来分配，也简单，按照比例来。 第三种：按照优先级来分配，优先级高的就分配的页数多一些。 按照是否可抢占来划分： 第一种：全局分配，它允许高优先级的进程去抢占其他进程的物理页，比如说进程发生缺页了，它把低优先级的进程的物理页给换出，然后加载自己的虚拟页。这种策略好处是，吞吐量高，但是坏处是进程无法控制自己的缺页率。 第二种：局部分配，跟第一种相反，不允许抢占其他进程的物理页，缺页率进程可以完全控制。
8).共享物理页 我们虽然为每个进程都创建了独立的虚拟内存，但是实际上多个进程的不同虚拟页面可以映射到相同的物理页面的，比如操作系统内核代码，比如进程公用的库等。这样避免了内存的浪费。
9).对于开发人员，我们能做什么？ 第一：尽量避免颠簸现象，如何避免呢？当系统中进程数量过大的时候，每个进程占用的物理内存就会变少，这样就会可能导致经常缺页，由于置换页很消耗性能，这时CPU利用率就会降低，但是操作系统会认为是进程数量少的原因导致的（看进程的调度原理），这时候会继续为系统加入新的进程，这时候会进入恶性循环。 怎么解决呢? 一方面通过获取每个进程使用物理页数的窗口，来近似得到进程需要的页数，如果页数大于物理页数，则说明需要减少进程数量，来使得进程获取足够多的物理页数来减轻颠簸。 另一方面，我们可以根据缺页频率的上下限来加入或者停止进程，什么原理呢？当警进程缺页的频率低的时候，说明它有太多了物理页了，我们要抢它点，怎么抢？加入新的进程，如果频率太高，我们给它多分配点物理页，但是如果这个时候没有可用的物理内存的时候，我们就暂停一个进程。 最后，我们的在设计程序的时候，也要考虑局部性。 而程序的局部性分为时间局部性与空间局部性： 时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。 空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。 关于空间局部性，我们引用网上的一个例子，如果我们的程序要遍历一个二维数组，采用如下两种方式：
我们知道二维数组在存储器中是按照行序为主序进行存储，所以fun_1具有良好的空间局部性，fun_2在访问元素的时候，每访问一个元素，就要跳过N个元素才能访问下一个。这种情况下没有良好的空间局部性。网上给出的遍历时间消耗如下： fun_1: 0.000624 seconds fun_2: 0.001193 seconds 看起来局部性影响还是很大的。 第二：我们是否可以通过调整操作系统的某些参数来适应我们的应用程序，比如页大小，比如每个进程的页分配的上下限等等。
(3)虚拟内存的好处 到这里我们大概已经明白了虚拟内存的优点了，我们再来总结下： 第一：给每个进程提供了一致的地址空间，每个进程都认为自己是在独占使用单机系统的存储资源，这其实是虚拟内存最大的作用。 第二：保护每个进程的地址空间不被其他进程破坏，隔离了进程的地址访问。 第三：根据缓存原理，上层存储是下层存储的缓存，虚拟内存把主存作为磁盘的高速缓存，在主存和磁盘之间根据需要来回传送数据，高效地使用了主存。 2.linux进程布局 我们已经知道linux为每个进程维护了一个虚拟地址空间，那么这个虚拟地址空间是怎么划分的呢，我们来看下
上面的图看着是不是很熟悉，在32位系统中，虚拟地址空间总共大小是4G，其中内核占用了1G，用户空间是3G，用户程序只能访问用户空间，不能访问内核空间。用户空间划分如下： (1)代码段，即存储当前运行的二进制代码。
(2)初始化过的数据(Data)，在程序运行初已经对变量进行初始化的数据。
(3)未初始化过的数据(BSS)，在程序运行初未对变量进行初始化的数据。
(4)文件映射区域，如动态库、共享内存等映射物理空间的内存，一般是mmap函数所分配的虚拟地址空间。
(5)堆 (Heap)，存储动态内存分配,需要程序员手工分配,手工释放。
(6)栈 (Stack)，存储局部、临时变量，函数调用时，存储函数的返回指针，用于控制函数的调用和返回。在程序块开始时自动分配内存,结束时自动释放内存，其操作方式类似于数据结构中的栈。 上面的内容大家都已经很熟，这里这是描述几个细节：
(1)上图的布局是32位操作系统的经典布局，这个布局在32位操作系统是有问题的，我们看到内存映射区域地址生长方向是向上，其开始地址就是堆的地址上限，这就造成我们的堆只有1G内存可用，内存映射区域一般我们用的比较少，这不就浪费了吗。于是引入了新版的32位系统的虚拟内存布局
这里实际上是把栈的最大值给限制了，内存映射区域从栈的下方开始，生长方向是从高地址空间到低地址空间，与堆对着生长，二者之间没有界限，为了确保栈与内存映射区域不发生冲突，二者之间设置了一个安全隙。
(2)64位系统又采用经典的内存布局，因为虚拟地址空间足够大了嘛，不存在内存不够用的情况，但是加上了随机的mmap起始地址，以防止溢出攻击。目前的x86-64架构CPU都遵循AMD的Canonical form, 即只有虚拟地址的最低48位才会在地址转换时被使用, 且任何虚拟地址的48位至63位必须与47位一致(sign extension). 也就是说, 总的虚拟地址空间为256TB( 248 ).
(3)我们看第一个32位的经典内存布局中，内核虚拟内存包含着内核的代码与数据结构，这些虚拟页是被映射到随意所有进程空想的物理页面的，这样节省了大量的物理内存。 (4)linux是如何管理这些区呢? linux给每个进程维护了一个任务结构task_struct，如果想要看源码的话，可以找这个文件/include/linux/sched.h，我们主要看下该结构体哪个地方是表示区域的。
看了这张图大概明白了,其中注意，每个区之间是有缝隙的，也就是说有些页实际是不属于任何区的,这些页不占用磁盘与物理内存，映射表也不用记录这些页，所以要访问这些地址的页是非法的。
(4)内存映射 我们之前说过虚拟内存其实就是把物理内存作为磁盘的缓存而已，我们把磁盘通过虚拟内存映射到物理内存上，那么这种根据根据映射到的磁盘的文件类型不同，分为两类： 第一：普通文件，这里注意一点，一个区域是映射到一个磁盘文件的，按照页区给文件切分，注意如果区域文件比文件大，则用二进制0填充区域剩下的部分。
第二：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。当CPU第一次引用这样一个区域内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页面，如果该页面被修改过，就先将它写回到硬盘，之后用二进制零覆盖牺牲页并更新页表，将这个页面标记为已缓存在内存中的。 注意：刚开始理解这句话的时候有些费劲，“之后用二进制零覆盖牺牲页并更新页表”，二进制零覆盖，这不是初始化第一次使用的页内存嘛！ 无论在那种情况，一旦虚拟页面被初始化，它就在一个就由内核维护的专门的交换文件之间换来换去，交换文件被称为交换空间(swap space)。
(5)开发人员怎么使用内存映射技术 看到刚才的linux的进程内存布局，其中的共享库的内存区域，其实也可以被用作内存映射文件，我们在程序中调用mmap()可以为文件分配虚拟内存。这种读取文件方式比传统的文件I/O要快很多，原因是每次进行IO操作,都要从用户态陷入内核态,由内核把数据从磁盘中读到内核缓冲区,再由内核缓冲区到用户缓冲区,如果没有buffer，读取都需要从用户态到内核态切换，而这种切换很耗时，所以，采用预读，减少IO次数，如果有buffer,根据局部性原理,就会一次多读数据,放到缓冲区中,减少了IO次数.
2.2 线程、进程、协程
终于把背景铺完了，进入正题。 在程序运行中，我们一般都只会关注栈和堆这两种内存区域： 进程的栈其实就我们刚才说的栈区，对其实就堆区，那么线程的也是有自己独立的栈的，但是线程是共享进程堆的，协程其实就是用户线程，其实也是一样，协程栈是各协程独立的，它们共享进程堆。 注意一点： 所谓的线程跟协程，其实就是线程模型1:1,还是N:M的区别。
2.3 进程栈、线程栈、协程栈
为什么会要说这几个栈呢？因为我有以下几个疑问：
1.为什么会有栈溢出
2.栈为何设置的那么小
3.都说堆需要用户程序管理，栈不需要，那栈是谁管理的，怎么管理的？
4.线程栈在哪开辟的空间，协程栈在哪开辟的空间？
5.为何golang的协程栈是动态增长的，有什么好处？ 这些疑问都是我看在堆与栈的区别的时候，慢慢发现的问题，我们一一道来。 我们先看如下代码
这是一个C++无限递归调用，我们知道这必然会引起栈溢出的，做这次测试的目的是用来判断我们的进程栈的大小是多少？（因为这是个单线程的进程）
我们看到现在使用的栈大小是203710244=8343552字节，一共是8148KB，我们在通过ulimit -s可以看到在Linux中线程栈的大小为8192。ok，我们看如下问题：
1.为何线程的最大限制是固定的，我想要更大栈内存怎么办？ 我们可以通过两种方式来解决这个问题，第一，我们可以日通过调整标准库给线程分配的内存大小，但是这里就有一个问题，就是每个线程的内存大小都将得到增大，这会无端的浪费很多的内存。着同样也是我们最初众多疑问中的其中"栈为何设置的那么小？"的答案。 第二，要注意一点，线程栈内存是在创建线程的时候已经确定好的，运行过程中是不能改变的。那么我们可以在创建内存的时候单独给这个线程申请一个大点的栈内存，看起来是完美的，但是很多时候我们是无法知道每个线程到底需要多少内存的，但是按需分配的思想还是很不错的，我们稍后会详细说golang的协程栈是如何解决这个问题的。
2.线程栈开辟的空间一定是在栈区吗，那么栈区到底是供谁用的呢？ 说实话，这个问题一直困扰着我，其实直到现在我还无法完全给出答案，我们来讨论下，以下内容只是我个人的理解，可能会有错误的地方（我尽量避免）。 首先，我们所谓的栈区与堆区都是我们的虚拟空间的一段连续地址而已，本质上并没有任何区别。所谓进程或者线程的栈的作用就是告诉内核线程，我的用户程序的一块连续地址，你运行的时候使用这块地址即可。 ok，我们继续探讨上述的问题。以下的操作都是在linux上进行，版本为Linux 2.6.32
\Rightarrow 我们先来看下创建线程的其中一种方法
首先，这是linux用的glibc创建的NPTL类型线程（NPTL类型线程与传统的linuxThread类型线程的区别，大家自行Google吧），我们看下，这里第二个参数为NULL，这就代表线程资源的分配交给了系统。 话不多说，看下源码吧
我们看到，创建线程的时候会判断是否传入了一个非空的attr，如果为NULL，则代表需要系统申请栈资源，稍后我们会具体说非空的情况。 ok，我们继续看ALLOCATE_STACK函数
看到这里我们知道它映射的是allocate_stack函数，ok我们找到 glibc/nptl/allocatestack.c
我们只保留了问题所关注的代码，看到过程如下，如果用户指定了栈空间，系统不需要为其分配，否则首先从栈缓存队列中取出一个大小够用的栈，如果没有取到合适的，才会为期申请栈内存，而且是通过mmap申请的。 ok,貌似还是没有确认我们的答案，mmap申请的内存是在哪呢？我们继续看mmap函数中有一个参数为MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK，看起来是标志位，其中一个标志MAP_STACK看起来跟栈有关，但是实际上这个标志还是被忽略的。看起来线索又断了。 回忆下我们在说虚拟内存的时候给出了一个进程虚拟内存地址布局图，内存映射区域是加在堆与栈的中间，并且跟栈区的地址增长方向相反，这里的mmap所开辟的空间应该是在这吧？我们来确认下。我们看下《linux/Unix系统编程手册》中的描述
“该图其实做了一些简化。特别是，线程栈的位置可能会与共享库和共享内存区域混杂在一起，这取决于创建线程、加载共享，以及映射共享内存的具体顺序。而且不同的linux发行版，线程栈地址也会有所不同。” 说实话我看这张图的时候，第一想法是：“线程栈开辟的空间是在栈区”，我们再看入下一张图
我们注意图中的一个细节，图中的内存映射区域的地址增长的方向是跟堆相反的，跟我们看到32位系统经典布局不一样，我们之前已经讨论过这个问题,实际上我的实验系统是64位系统，经过验证我发现是如上图的内存布局，我们现在实验验证下。 看如下的代码：
运行结果如下
首先我们看到我们成功创建了327651个线程,每个线程栈的大小为8M，一共2559.8G=2.49T，接下来创建线程都失败了，看起来是虚拟内存耗光了。接下来我们继续加料
看下运行结果
创建足够多的线程后，我们发现我们通过malloc申请内存的时候都失败了（第一次总是成功，不明白为什么），这说明什么？说明，我们的mmap申请的内存最后把堆也沾满了，这其实正好跟我们上面说的mmap的内存地址增长方向对应上了。为了更加验证，我们再加点料。
看如下的运行结果
我们在创建最大限度的线程后，再调用alloca申请内存，我们知道alloca申请的内存是在栈上开辟的。看到这里大家明白了，我们的mmap的地址增长方向是跟堆对向的。 最后，还有一个小的查看堆与栈空间的工具，看如下的代码
如果再多创建几个
ok，我们再看一种创建线程的方法
如代码所示，我们创建线程的栈是我们通过malloc来申请的，注意这里的线程栈需要我们手动的释放。 而且我们可以通过如下的方式来设置栈的大小
我们看到内存的分布就如同我们所说的，是在往堆的方向增长。
3.线程栈是如何管理的呢，资源如何释放呢？ 我们都知道C/C++中，在堆上申请的内存需要我们自己手动释放，而栈则需要。为何如此? 首先，栈内存的释放从两个角度去考虑，我们的局部变量和函数存储在栈上，函数完成后栈上的局部变量自动释放掉了。这个操作是如何实现的呢？ 实际上入栈出栈的操作是由编译器实现的，也就是说编译器在对代码编译的时候插入的汇编语言已经实现了局部变量的入栈出栈操作。 其次，我们要重点说的栈的释放，是指的我们的线程运行完毕后线程栈内存的释放是怎么做的呢？
以下内容为网络摘抄：
1)由谁释放？ 对于非 detach 的线程，这个问题答案十分明显，线程的栈区将由调用 Join 操作的线程来完成释放。但是对于 detach 线程，这个问题就不是那么清楚了。 没有其它线程来显式的释放栈区，那么这个栈区的释放只能交由线程自己来完成。也就是说，一个线程需要自己释放自己正在使用的栈内存块。这听上去就是胡扯嘛，正在用怎么能释放呢。但是仔细想一下，如果栈区没有使用了，那么线程已经结束，它更没办法去释放自己的栈内存了。这时就需要 Linux 内核的支持了。
2)怎么释放？ 事实上，线程释放自己的栈区也并非真正意义上的释放该内存块，而是将该内存块从 stack_used 移除，放入 stack_cache 链表中， 同时修改标志位，而将内存真正的释放操作推迟到其它线程中完成。释放过程被分为如下步骤：
（1） 将栈内存块从 stack_used 取下放入 stack_cache 列表中。
(2) 释放 stack_cache 中已结束线程的栈内存块。这里是否已结束是根据 pthread tid 位是否 被清零来业判断的。
(3) 线程结束时， 由内核清除标志位（tid）， 这一步骤是由内核完成的，当线程结束时，内核会自动将tid清零，这就意味着一旦 tid 被清零就意味着线程已经结束。需要注意：前两步是由线程完成，而每三步是由内核来完成的。 可以看出，针对自己的栈内存，每个线程只是将其放入 stack_cache 链表中，而该内存块真正的释放操作是由别的线程来完成的。所以会存在这样一个时间段，线程正在使用过程中却已经被放到 stack_cache 链表中了，而线程真正结束的标志是由 Linux 内核来完成的，只由 tid 被清零的栈内存才可能被真正的释放掉。
4.golang的协程栈有什么长什么样呢？ 我们linux的nptl的线程栈大小是固定的，这是不太合理的，golang的协程栈就是动态增长的，我们稍后会详细说，好处显而易见,不浪费内存资源。