内存模型

对于C/C++ 等语言来说，内存空间大致使用在

1. 栈区（stack）：又编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构的栈。

2. 堆区（heap）：一般是由程序员分配释放，若程序员不释放的话，程序结束时可能由OS回收，值得注意的是他与数据结构的堆是两回事.

3. 全局区（static）：也叫静态数据内存空间，存储全局变量和静态变量，全局变量和静态变量的存储是放一块的，初始化的全局变量和静态变量放一块区域，没有初始化的在相邻的另一块区域，程序结束后由系统释放。

4. 文字常量区(const)：常量字符串就是放在这里，程序结束后由系统释放。

5. 程序代码区：存放函数体的二进制代码。

堆中的对象对于Go 以及 Java 等编程语言来说由工程师和编译器共同管理，堆内存对象由内存分配器分配并由垃圾收集器 gc (garbage collection) 回收。

在多线程编程下，追求更高内存管理效率：更快的分配是主要目的。

• 引入虚拟内存后，让内存的并发访问问题的粒度从多进程级别，降低到多线程级别。
• 为线程预分配缓存需要进行1次系统调用，后续线程申请小内存时，从缓存分配，都是在用户态执行，没有系统调用，缩短了内存总体的分配和释放时间，
• 多个线程同时申请小内存时，从各自的缓存分配，访问的是不同的地址空间，无需加锁，把内存并发访问的粒度进一步降低

接下来介绍go的具体内存模型：

内存分配方法

• 线性分配器（Sequential Allocator，Bump Allocator）

  实现简单，直接在内存中维护一个指向可用地址的指针。其GC需要与具有拷贝特性的回收方法:标记压缩（Mark-Compact）、复制回收（Copying GC）和分代回收（Generational GC）等算法,所以像C、C++这样暴漏内存地址指针的无法使用。

• 空闲链表分配器（Free-List Allocator）

  大致分为以下四种策略：go使用的是第四种

  1. 首次适应（First-Fit）— 从链表头开始遍历，选择第一个大小大于申请内存的内存块；
  2. 循环首次适应（Next-Fit）— 从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块；
  3. 最优适应（Best-Fit）— 从链表头遍历整个链表，选择最合适的内存块；
  4. 隔离适应（Segregated-Fit）— 将内存分割成多个链表，每个链表中的内存块大小相同，申请内存时先找到满足条件的链表，再从链表中选择合适的内存块；举例：将内存分割成由 4、8、16、32 字节的内存块组成的链表，当我们向内存分配器申请 8 字节的内存时，它会在8字节链表中找到满足条件的空闲内存块并返回。隔离适应的分配策略减少了需要遍历的内存块数量，提高了内存分配的效率。

除此之外，go的内存分配器还借鉴了TCMalloc(毕竟都是google做的)的设计理念——使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略

1. Page：操作系统对内存管理以页为单位，TCMalloc也是这样，只不过TCMalloc里的Page大小与操作系统里的大小并不一定相等，而是倍数关系。《TCMalloc解密》里称x64下Page大小是8KB。
2. Span：一组连续的Page被称为Span，比如可以有2个页大小的Span，也可以有16页大小的Span，Span比Page高一个层级，是为了方便管理一定大小的内存区域，Span是TCMalloc中内存管理的基本单位。
3. ThreadCache：每个线程各自的Cache，一个Cache包含多个空闲内存块链表，每个链表连接的都是内存块，同一个链表上内存块的大小是相同的，也可以说按内存块大小，给内存块分了个类，这样可以根据申请的内存大小，快速从合适的链表选择空闲内存块。由于每个线程有自己的ThreadCache，所以ThreadCache访问是无锁的。
4. CentralCache：是所有线程共享的缓存，也是保存的空闲内存块链表，链表的数量与ThreadCache中链表数量相同，当ThreadCache内存块不足时，可以从CentralCache取，当ThreadCache内存块多时，可以放回CentralCache。由于CentralCache是共享的，所以它的访问是要加锁的。
5. PageHeap：PageHeap是堆内存的抽象，PageHeap存的也是若干链表，链表保存的是Span，当CentralCache没有内存的时，会从PageHeap取，把1个Span拆成若干内存块，添加到对应大小的链表中，当CentralCache内存多的时候，会放回PageHeap。如上图，分别是1页Page的Span链表，2页Page的Span链表等，最后是large span set，这个是用来保存中大对象的。毫无疑问，PageHeap也是要加锁的。

垃圾回收

gc(garbage collection)在几乎所有的现代编程语言中，垃圾收集器都是一个复杂的系统，为了在不影响用户程序的情况下回收废弃的内存需要付出非常多的努力，Java 的垃圾收集机制是一个很好的例子，Java 8 中包含线性、并发、并行标记清除和 G1 四个垃圾收集器，想要理解它们的工作原理和实现细节需要花费很多的精力。

垃圾收集器将存储器视为一张有向可达图。图中的节点可以分为两组：一组称为根节点，对应于不在堆中的位置，这些位置可以是寄存器、栈中的变量，或者是虚拟存储器中读写数据区域的全局变量；另外一组称为堆节点，对应于堆中一个分配块，如下图：

当堆节点不可达时即可视为垃圾，因为已经访问不到了。

介绍几种基础的GC算法：

1. 引用计数：

   Objective-C 选择了自动引用计数（智能指针），即创建的堆空间维护一个计数器，每当有新的引用指向它就计数器加一。反之指向其的引用置空或指向其他对象计数器减一，减少至0则释放，实现动态回收内存空间。

   而其缺点是若存在对象的循环引用，无法释放这些对象。并且多个线程同时对引用计数进行增减时，引用计数的值可能会产生不一致的问题，必须使用并发控制机制解决这一问题，也是一个不小的开销。

2. 标记清除

   这个算法也称为Mark & Sweep算法，为McCarthy独创。它也是目前公认的最有效的GC方案。Mark&Sweep垃圾收集器由标记阶段和回收阶段组成，标记阶段标记出根节点所有可达的对节点，清除阶段释放每个未被标记的已分配块，其执行过程可以分成标记（Mark）和清除（Sweep）两个阶段：

   1. 标记阶段 — 从根对象出发查找并标记堆中所有存活的对象；
   2. 清除阶段 — 遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表；

   一般的地，块头部中空闲的低位中的一位用来表示这个块是否已经被标记了。通过Mark&Sweep算法动态申请内存时，先按需分配内存，当内存不足以分配时，从寄存器或者程序栈上的引用出发，遍历上述的有向可达图并作标记（标记阶段），然后再遍历一次内存空间，把所有没有标记的对象释放（清除阶段）。因此在收集垃圾时需要 中断正常程序STW (Stop the world) ，在程序涉及内存大、对象多的时候中断过程可能有点长。当然，收集器也可以作为一个独立线程不断地定时更新可达图和回收垃圾。

   该算法不像引用计数可对内存进行即时回收，但是它解决了引用计数的循环引用问题，因此有的语言把引用计数算法搭配Mark & Sweep 算法构成GC机制。

3. 节点复制

   Mark & Sweep算法的缺点是在分配大量对象时，且对象大都需要回收时，回收中断过程可能消耗很大。而节点复制算法则刚好相反，当需要回收的对象越多时，它的开销很小，而当大部分对象都不需要回收时，其开销反而很大。算法的基本思路是这样的：从根节点开始，被引用的对象都会被复制到一个新的存储区域中，而剩下的对象则是不再被引用的，即为垃圾，留在原来的存储区域。释放内存时，直接把原来的存储区域释放掉，继续维护新的存储区域即可。

4. 分代回收

   以上三种基本算法各有各的优缺点，也各自有许多改进的方案。通过对这三种方式的融合，出现了一些更加高级的方式。而高级GC技术中最重要的一种为分代回收。它的基本思路是这样的：程序中存在大量的这样的对象，它们被分配出来之后很快就会被释放，但如果一个对象分配后相当长的一段时间内都没有被回收，那么极有可能它的生命周期很长，尝试收集它是无用功。为了让GC变得更高效，我们应该对刚诞生不久的对象进行重点扫描，这样就可以回收大部分的垃圾。为了达到这个目的，我们需要依据对象的”年龄“进行分代，刚刚生成不久的对象划分为新生代，而存在时间长的对象划分为老生代，根据实现方式的不同，可以划分为多个代。

   一种回收的实现策略可以是：首先从根开始进行一次常规扫描，扫描过程中如果遇到老生代对象则不进行递归扫描，这样可大大减少扫描次数。这个过程可使用标记清除算法或者复制收集算法。然后，把扫描后残留下来的对象划分到老生代，若是采用标记清除算法，则应该在对象上设置某个标志位标志其年龄；若是采用复制收集，则只需要把新的存储区域内对象设置为老生代就可以了。而实际的实现上，分代回收算法的方案五花八门，常常会融合几种基本算法。

go的垃圾回收

为了高效的标记对象缩短stw时间，go使用三色标记法（标记清除的一种改良）来做；

三色对象定义：

• 白色对象 — 潜在的垃圾，其内存可能会被垃圾收集器回收；

• 黑色对象 — 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；

• 灰色对象 — 活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；

在垃圾收集器开始工作时，垃圾收集的根对象会被标记成灰色，其他对象标记为白色，垃圾收集器只会从灰色对象集合中取出对象开始扫描，当灰色集合中不存在任何对象时，标记阶段就会结束。

三色标记垃圾收集器的工作原理很简单，我们可以将其归纳成以下几个步骤：

1. 从灰色对象的集合队列中选择一个灰色对象并将其标记成黑色并进行步骤2；
2. 将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收；
3. 重复上述两个步骤直到对象图中不存在灰色对象；

垃圾收集器一旦开始执行就会浪费大量的计算资源，为了减少应用程序暂停的最长时间和垃圾收集的总暂停时间，我们会使用下面的策略优化现代的垃圾收集器：

• 增量垃圾收集 — 增量地标记和清除垃圾，降低应用程序暂停的最长时间；

  增量式（Incremental）的垃圾收集是减少程序最长暂停时间的一种方案，它可以将原本时间较长的暂停时间切分成多个更小的 GC 时间片，虽然从垃圾收集开始到结束的时间更长了，但是这也减少了应用程序暂停的最大时间：

• 并发垃圾收集 — 利用多核的计算资源，在用户程序执行时并发标记和清除垃圾；

  并发（Concurrent）的垃圾收集不仅能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启读写屏障、利用多核优势与用户程序并行执行，并发垃圾收集器确实能够减少垃圾收集对应用程序的影响：

因为增量和并发两种方式都可以与用户程序交替运行，使用并发或增量执行，有可能会生成悬挂指针——即不该被回收的对象被回收了。所以我们需要使用屏障技术保证垃圾收集的正确性；与此同时，应用程序也不能等到内存溢出时触发垃圾收集，因为当内存不足时，应用程序已经无法分配内存，这与直接暂停程序没有什么区别，增量和并发的垃圾收集需要提前触发并在内存不足前完成整个循环，避免程序的长时间暂停。

内存屏障技术是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束，目前多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作。

想要在并发或者增量的标记算法中保证正确性，我们需要达成以下两种三色不变性（Tri-color invariant）中的一种：

• 强三色不变性 — 黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；
• 弱三色不变性 — 黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径

垃圾收集中的屏障技术更像是一个钩子方法，它是在用户程序读取对象、创建新对象以及更新对象指针时执行的一段代码，根据操作类型的不同，我们可以将它们分成读屏障（Read barrier）和写屏障（Write barrier）两种，因为读屏障需要在读操作中加入代码片段，对用户程序的性能影响很大，所以编程语言往往都会采用写屏障保证三色不变性。