内存区域划分，从高地址到低地址依次是

• 栈区：内存由系统控制开辟、释放。当系统的栈区大小不够分配时， 系统会提示栈溢出。存放时按照先入先出原则，从高地址向低地址扩展。
• 堆区：内存由程序控制开辟、释放。如果程序没有释放，在程序结束时，由系统释放。但是在程序运行时，会出现内存泄漏，内存溢出等问题。分配方式类似于链表。从低地址向高地址扩展。
• 全局静态区：全局变量、静态变量会存储在此区域。初始化的全局变量跟静态变量放在一片区域，未初始化的全局变量与静态变量放在相邻的另一片区域。程序结束后由系统释放。
• 文字常量区：在程序中使用的常量存储在此区域。程序结束后，由系统释放。
• 程序代码区： 存放函数体的二进制代码。

以上 全局静态区、文字常量区、程序代码区 在程序运行起来的时候就开辟好了
栈区由系统控制释放、开辟
垃圾回收机制主要就体现堆区的内存管理方面

基本概念

• GC：Garbage Collection。垃圾回收。
• Collector，用于进行垃圾回收的线程
• Mutators，应用程序的线程，可以修改 heap
• MS，mark-sweep 算法的简写
• MC，mark-compact 算法的简写
• RC，reference-counting 的简写
• liveness，一个对象的可到达性
• 引用关系图，由可到达对象引用形成的图结构
• locality，现代CPU在访问内存时，有多级缓存。缓存以 cache line （一般64字节）为最小操作单位，所以当访问内存中连续的数据时会比较高效，这称为 locality
• Roots，所有根对象，比如全局对象，stack 中的对象

一、手动垃圾回收

这个没什么好说的，c语言就需要手动垃圾回收

int *elements = malloc(10 * sizeof(int));
free(elements)

二、引用计数（Reference Counting）

• 为每个对象存储一个引用计数，新创建的对象，引用计数为1
• 当有一个新的指针指向这个对象时，引用计数加1
• 当某个指针不再指向这个对象时，引用计数减1
• 当引用计数为0时，将对象销毁，回收内存
  优点
  1.可以保证对象引用为0时立马得到清理，无不确定行
  2.大多数操作具有增量特性（incremental），GC 可与应用交替运行，不需要暂停应用即可完成回收功能
  3.可以用来优化运行时性能。比如函数式编程中所推崇的「 不可变数据结构 」的更新就能收益：运行时知道某个对象的引用为1，这时对这个对象进行修改，类似 str <-str+"a"，那么这个修改就可以在本地进行，而不必进行额外的 copy
  缺点
  1.无法解决循环引用。
  2.实现一个高效率的引用计数 GC 比较困难。每个对象需要额外的空间来存储其引用次数。在增加/减少对象的引用时，需要修改引用次数。修改引用次数对于栈上的赋值，影响是非常大的。因为之前只需要简单修改寄存器里面的值，现在需要一个原子操作（这涉及到加锁，会浪费几百个 CPU cycles）
  3.减少一个对象的引用计数时，会级联减少其引用对象的计数，这就可能造成同时删除过多的对象。在实现中一般会把要回收的对象放入一队列，当程序申请大小为 N 的内存时，从这个队列取出总体积不小于 N 的一个或多个对象将其回收。

采用这类 GC 的主流语言有：Python/PHP/ Perl /TCL/Objective-C。

三、追踪类（tracing）GC

3.1 MS算法：标记-清除（Mark-Sweep）

• mark，从 root 开始进行树遍历，每个访问的对象标注为「使用中」
• sweep，扫描整个内存区域，对于标注为「使用中」的对象去掉该标志，对于没有该标注的对象直接回收掉
  优点
  1.用以标注对象是否在使用中的flag 位一般放在引用变量里面，不需要额外的空间。
  2.较引用计数（Reference Counting） 性能更高
  缺点
  1.在进行 GC 期间，整个系统会被挂起（暂停，Stop-the-world），所以在一些实现中，会采用各种措施来减少这个暂停时间
  2.heap 容易出现碎片。实现中一般会进行 move 或 compact。（需要说明一点，所有 heap 回收机制都会这个问题）
  3.回收时间与 heap 大小成正比
  4.破坏引用本地性。其实还是因为碎片化导致的。（时间局部性是指，被引用一次的储存器位置，在接下来的时间会经常被引用，这样我们就说他有良好的时间局部性。空间局部性是指，被引用一次的储存器位置，在接下来的时间，他旁边的储存器位置也会被引用，这样我们就说他有良好的空间局部性）

3.2 优化MS算法 - 优化mark过程

在 mark 过程中，需要去标记（mark-bits）对象的 liveness，有两种方式来实现：

• 在每个对象的header部分（in-object mark-bit）
• 使用一个单独的 bitmap，每一位 bit 对应一个对象

两种方式各有利弊，需要结合具体场景进行分析。重点说一下bitmap：
对于 bitmap 来说，需要在 bit 位与 object 之间进行映射，这就要求 object 进行对齐，比如：heap 大小为 65536 字节，所有的对象以 16 字节对齐，那么堆内就有 4096 个地址可以作为对象的起始地址，与之对应需要 4096 个 bit 即 512 个字节。所以使sweep 操作更高效，这是由于 bitmap 结构紧凑，可以一次性加载到内存中，一次性进行多位的检测。

3.3 优化MS算法 - 优化sweep过程

MS 算法有以下两个特点：

• 某对象一旦被标为garbage，它永远都会是 garbage，不会被 mutator 再访问
• mutator 不能修改 mark-bit

基于以上两点，sweep 操作完全可以与 mutator 同时运行（parallel）的。
Lazy sweep 指的是把较为耗时（相对 mark 来说）的 sweep 操作放在 allocate 过程中，并且只在没有足够的空间时才去真正进行回收。
核心就是，把标记为待回收的内存块，放入一个队列中延迟回收。当需要开辟空间且内存不够时，根据需要开辟内存的空间大小，在待回收队列中释放内存。

Lazy Sweep 除了降低 sweep 阶段 mutator 的暂停时间外，还有以下优点：

• 更好的 locality。这是因为被回收的 block 会尽快地重新使用
• GC 复杂度只与可到达对象（即正在使用中的对象数）成正比
• 在大部分 heap 空间为空时效率最好

3.4 优化MS算法 - 碎片问题 - MC算法：标记-整理（Mark-Compact）

MC 算法与 MS 类似，先是一个 mark 过程标记可到达对象，这里取代 sweep 的是一个 compact，工作流程如下：

• 移动（relocate）可到达对象
• 更新指向可到达对象的指针

关于第一步中的安排策略，一般有如下三种选择：

• 任意（Arbitrary）。特点是快，但是空间局部性较差
• 线性（Linearising）。重新分配到附近有关系的（siblings/pointer/reference…）对象周边
• 滑动（Sliding）。所有活对象被滑动到 heap 的一端，保证原有顺序，这有利于改善 locality 的情况。这是现在采用较多的方案

对于采用 MC 的系统，allocate 过程就变得较为简单，只需要bump pointer 即可。
但是这类算法需要多次遍历对象，第一次遍历算出对象将要移动到的新位置，接下来的遍历来真正移动对象，并更新指针，所以MC相对MS要更耗时，这在 heap 较大时更为明显。

这里比较有名的是 Edward 的 Two-pointer 压缩算法。大致过程如下：

• 在 heap 两端各准备一指针，由外向内 scan 寻找可整理的对象
• 自顶向下的指针寻找可到达对象，自底向上的指针寻找 heap 中的“洞”来存放可到达对象

3.5 优化MC算法 - 效率问题 - Copying GC算法

MC 算法虽然能解决内存碎片问题，但是需要多次遍历heap空间，这会导致较大性能损耗，Copying GC 采用空间换时间的方式来提升性能。
这类 GC 并不会真正去“回收”不可到达对象，而是会把所有可到达对象移动到一个区域，heap 中剩余的空间就是可用的了（因为这里面都是垃圾）。这里并没有进行 sweep/compact，而是用 scavenging（净化） 来描述回收这一过程。

Copying GC 典型的代表半空间回收器（semispace collector）。其工作过程是这样的：

• heap 被分成2份相邻的空间（semispace）：fromspace 与 tospace
• 在程序运行时，只有 fromspace 会被使用（分配新对象）
• 在 fromspace 没有足够空间容纳新对象时，程序会被挂起，然后把 fromspace 的可到达对象拷贝到 tospace
• 在拷贝完成时，之前的2个空间交换身份，tospace 成了新一轮的 fromspace

Cheney 算法是用来解决如何遍历引用关系图，将之移动到 tospace 的算法，其步骤如下：

1. 所有可直接到达的对象组成一队列，作为宽度优先遍历的起点，同时有两个辅助指针：scan 指针指向起始位置，free 指针指向末尾
2. 通过移动 scan 来依次遍历队列，当 scan 的对象存在指向 fromspace 中对象的指针时，把被指向的对象添加到队列末端，同时更新指针，使之指向新对象；
3. 更新 free 使之始终指向初始时队列末尾所指的那个对象，重复步骤2
4. 当 scan 移动到初始时队列末尾所指的那个对象时，即scan与free指向同一对象时，算法结束。

如果按照上述算法操作，会把被指向多次的对象复制多次(类似于引用计数为N，同一个可触达对象在队列中有多份)，所以在拷贝对象到 tospace 时，会在原始版本的对象上记录一个重定向指针（forwarding pointer），来标明这个对象已经被复制过了，并且告知新对象的位置；后面 scan 对象时，如果发现具有重定向指针的对象时就会跳过复制操作，直接更新指针就可以了。

3.6 优化Copying算法 - 空间问题 - Non-Copying Implicit GC算法

通过上述描述，不难发现Copying GC 一最大缺点在于所需空间翻倍，不过现如今内存已经普遍较大，这个问题不是很严重。
其次，复制的效率与可到达对象成正比，如果每次 GC 时可到达对象占用的空间接近semispace空间，那么只能通过降低 GC 频率减少 GC 对程序的影响。如何降低 GC 频率呢？答案就是加大 semispace 空间，这样程序就需要更多的时间来填满它。

Non-Copying Implicit GC从 Copying GC 衍化而来，核心是，semispace 不必是物理上分割的空间，可以用两个用双向链表来表示，一般称为 ：from-set 与 to-set。为了实现这种策略，需要在每个对象上多加以下两个信息：

• 两个指针，用来形成链表
• 一个flag，标明属于哪个集合

当 from-set 耗尽时，只需遍历 from-set，把其中的可到达对象插入到 to-set，然后改变flag即可，复制操作变成了链表指针操作。这类 GC 的优势除了不用进行真正的拷贝外，还有下面两处优点：

• 语言级别的指针不需要改变了（因为对象没动），这对编译器的要求更小了
• 如果一个对象不含有指针，那么就没必要 scan 了
  缺点当然也比较明显：
• 每个对象需要而外的空间
• 碎片问题又回来了

所以这类 GC 虽然是 Copying GC 的优化，但也只适用于某些特定的场景。

通过上面的介绍，觉得最重要的就是要分清一个算法的优势与劣势，软件工程里面没有「银弹」，都是有取舍的。

上面对 MS 算法的优化，基本都是在 sweep 阶段，mark 阶段没怎么改进。
但 mark 阶段会导致应用程序挂起，也就是常说的：stop-the-world（STW），这严重影响了 Tracing GC 的应用场景。

3.7 增量式 GC 思路（Incremental Collection）

增量式（incremental）GC 顾名思义，允许 collector 分多个小批次执行，每次造成的 mutator 停顿都很小，达到近似实时的效果。
引用计数类 GC 本身就具有增量式特性，但由于其算法自身的缺陷与效率问题，一般不会采用。而追踪类 GC 实现增量式的难点在于：
这是一个并发问题，collector 线程与 mutator 线程同时去读/写一些共享的数据结构（引用关系图），这就要求把它加锁保护起来。
在 GC 期间，对 mutator 改变「引用关系图」的保守度（conservatism）是增量式 GC 一大特性。如果 mutator 在 collector 遍历某对象后将其释放（floating garbage），那么这个对象在本次 GC 不会被回收，但在下一轮 GC 开始时会被回收。
这种弱一致性（relaxed consistency）是允许的，因为它不会对程序逻辑造成影响，只是延迟了垃圾对象的回收，而且一致性越弱，遍历算法的实现就可以更灵活。

三色标记（tricolor marking）抽象屏蔽了 GC 实现的算法（MS/Copying）、遍历策略（宽度优先/深度优先）等细节，具体来说是在 GC 遍历引用关系图时，对象会被标为三种颜色：

• 黑色black，表明对象被 collector 访问过，属于可到达对象
• 灰色gray，也表明对象被访问过，但是它的子节点还没有被 scan 到
• 白色white，表明没有被访问到，如果在本轮遍历结束时还是白色，那么就会被收回

对于 MS 来说，设置标记位就是着色的过程：有 mark-bit 的即为黑色。对 Copying GC 来说，把对象从 fromspace 移动到 tospace 就是着色过程：在 fromspace 中不可到达的对象为白色，被移动到 tospace 的对象为黑色。
对于增量式 GC 来说，需要在黑白之间有个中间状态来记录「那些之前被 collector 标记黑色，后来又被 mutator 改变的对象」，这就是灰色的作用。

对于 MS（3.2） 来说，灰色对象是用于协助遍历 queue 里面的对象，
对于 Copying GC 来说，灰色对象就是那些在 fromspace 中还没被 scan 的对象，
如果采用 Cheney 的宽度优先遍历算法，那么就是 scan 与 free 指针之间的对象。

增加的中间状态灰色要求 mutator 不会把黑色对象直接指向白色对象（这称为三色不变性 tri-color invariant），collector 就能够认为黑色对象不需要在 scan，只需要遍历灰色对象即可。但这可能存在违法三色不变性的情况。
违法三色不变性的情况简单来说，
就是有三层节点，第一层节点被scan过，且第二层节点全都可访问，此时第一层节点被着色为黑色，第二层节点被着色为灰色。
因为并发，mutator此时做了修改，把第一层节点直接指向第三层的节点，第二层的节点不再指向第三层节点
scan继续访问第二层节点，将第二层节点置位黑色，第三层节点因为此时不再连接第二层节点，故依旧为白色。第一层节点因为已经scan过为黑色，所以在此轮中不会再次被scan，第三层节点依旧为白色。
当遍历结束，虽然第三层节点依旧被第一层节点连接，可依旧会因为是白色而导致被释放。

为了解决上面的违法三色不变性的问题，一般有两类方式来协调 mutator 与 collector 的行为：

• 读屏障（read barrier），它会禁止 mutator 访问白色对象，当检测到 mutator 即将要访问白色对象时，collector 会立刻访问该对象并将之标为灰色。由于 mutator 不能访问指向白色对象的指针，也就无法使黑色对象指向它们了
• 写屏障（write barrier），它会记录下 mutator 新增的由黑色–>白色对象的指针，并把该对象标为灰色，这样 collector 就又能访问有问题的对象了

读/写屏障本质是一些同步操作——在 mutator 进行某些操作前，它必须激活 collector 进行一些操作。
如果没有特殊的硬件支持，写屏障一般来说效率要高于读屏障，因为heap 指针的读操作要多于写操作。

3.8 分代式 GC 思路（Generational Collection）

增量式 GC 是对 mark 阶段的一大优化，可以极大避免 STW 的影响。分代式 GC 根据对象生命周期（后面称为 age）的特点来优化 GC，降低其性能消耗。
虽然对象的生命周期因应用而异，但对于大多数应用来说，80% 的对象在创建不久即会成为垃圾。因此，针对不同 age 的对象「划分不同区域，采用不同的回收策略」也就不难理解了。
对于 Copying GC 来说，需要在两个 semispace 间移动对象，如果移动对象较大，就会对程序造成较大影响，而分代就能解决这个问题。简单情况下可以分为两个代：younger、older。

younger 用于分配新对象，在这里的对象经过几轮 GC 后会移动到 older。younger 与 older 相比空间要小，且 GC 发生更频繁。

分代算法的首要的问题是「如何在不回收 older 的同时安全的回收 younger 里面的对象」
由于引用关系图是全局的属性，older 里面的对象也必须考虑的。比如 younger 里面的一对象只被 older 里面的对象引用了，如何保证 GC 不会错误的回收这个对象呢？

避免上述问题的一个方法是采用写屏障（write barrier），在 mutator 进行指针存储时，进行一些额外的操作（bookkeeping）。写屏障的主要目的是保证所有由 older-->younger 的指针在进行 younger 内的 GC 时被考虑在内，并且作为 root set 进行 copy 遍历。需要注意的是，这里的写屏障与增量式 GC 同样具有一定的保守性。这是由于所有由 older-->younger 的指针都会被当作 root set，但在 older 内的对象是否存活在进行下一次 older GC 前是不可知的，这也就造成了一些 floating garbage，不过这在现实中并不是不能接受的。

第二个问题是「如何在不回收 younger 的同时安全的回收 older 里面的对象」。为了独立回收 older，通过记录所有由 younger-->older 的指针也是可行的，不过这会比较消耗性能。因为在大多数情况下，由 younger-->older 的指针数目要远大于 older-->younger 的，这是符合程序运行规律的——创建一个新对象，将至指向一个老对象。

即便不记录 younger-->older 的指针，也可以在不回收 younger 的前提下回收 older，只不过这时会把 younger 里面的所有对象作为 root set。尽管这样遍历的时间会与 younger 里面的对象数目成正比，但考虑到 younger 内对象数量一般都要小于 older 的，而且遍历操作的消耗要远小于 copying，所以这也是一种可以接受的方式。

除了上面交叉引用的问题，对于一个分代的 GC 来说，还需要考虑下面几个方面：

• 提升策略（advancement policy）。在一个代内的对象经过多少次 GC 会晋级到下一个代
• 堆组织（heap organization）。在代与代之间或者一个代内，heap 空间如何组织可以保证高的 locality 与 缓存命中率
• 代之间的交叉引用（intergenerational references）。采用哪种方式来记录这些指针最好？dirty bit or indirect table

提升策略
最简单的提升策略是在每次 GC 遍历时，把 live 的对象移动到下一代去。这样的优势有：

• 实现简单，不需要去区分一个代内不同对象的 age。对于 copying GC 来说，只需要用一块连续的区域表示即可，不需要 semispace，也不需要额外的 header 来保存 age 信息
• 可以尽快的把大对象提升到 GC 频率比较小的下一代中去

当然，这样做的问题也比较明显，可能会把一些 age 较小的对象移动到下一代中去，导致下一代被更快的填满，所以一般会让 younger 里面的对象停留一次，即第二次 GC 时才去提升，当然这时就需要记录对象的 age 了。

至于是不是需要停留两次，这个就不好说了，这个和应用也比较相关。一般来说，如果代分的少，比如2个，那么会倾向多停留几次，减慢 older 被填满的速度；如果代的数目大于2，那么就倾向于快速提升，因为这些对象很有可能在中间的某个代就会死亡，不会到达最终的 older。

堆组织
分代式 GC 需要对不同 age 的对象采取不同的处理方式，所以在 GC 遍历时，必须能够判断当前对象属于哪个代，写屏障也需要这个信息来识别 older-->younger 指针。

• 对于 copying GC 来说，一般是把不同 age 的对象放在不同的连续区域内，这样一个对象的代就能够从内存地址推断出来了。也有一些系统不采用连续地址，而是采用由 page number of object-->generation 的表来辅助判断。
• 对于 non-copying GC，一般是存放在 header 内

Subareas in Copying
分代式 copying GC 一般会把 generation 分为几个子区域，比如 semispace，通过来回的移动对象让它们一直处于当前代中。如果一个代内只有一个区域，那么每次 GC 时都需要把对象提升到下一代（没有可移动的地方）。
但是 semispace 的 locality 比较差，一个代的内存只有一半可以使用，且来回需要移动。

Ungar 在其论文《Generation Scavenging》 中提出一个解决方法：
一个代内除了两个 semispace 外，还有第三个区域，这里称为Third。在 Third 内分配新对象，在 GC 时，Third 内 live 对象与 semispace 中的一个对象会复制到 semispace 中的另一个去，GC 结束时 Third 会被清空，用于再次分配对象。这样就能够与只有一个区域的代类似的 locality 了。
（第三个区域即为java中的Eden，伊甸园区域。将新生代分为Eden，FromSpace，ToSpace等几个区域）

最后一个代（oldest generation，后面称为 oldest）在一些系统中有特殊处理。比如，在 Lisp Machine 中，每次 GC 后，大多数代都会被清空，并将其内对象拷贝到下一代去，但是 oldest 后面没有可用代了，因此 oldest 内会被分为 semispace。另一个优化是分配一个特殊的区域，称为 static space，用来分配 system data & compiled code 等这些基本不会变的数据，这个区域基本不会有 GC，即为永久代。

在一些基于 Ungar 的 Generation Scavenging 的系统中，把 oldest 分为一个区域，在这个区域使用 mark-compact 算法。使用一个区域可以提高内存利用率，MC 虽然比 copying 算法成本更高，但对于 oldest 来说减少换页（page fault）也是有价值的。

交叉引用

上面已经介绍的，older-->younger 的交叉引用是由写屏障来保障的。对于某些系统（如 Lisp，指针存储指令占全部指令的1%），这个写屏障的成本对分代式 GC 来说非常严重，因此写屏障的策略就十分重要了。

常见的策略的核心思路有两个

• 使用 entry table 或 Remembered Sets 记录交叉引用的指针对象，这种方式成本比较高
• 使用虚拟内存页保存交叉引用的对象，GC 时只需要对虚拟内存页进行扫描即可

3.9 实例：Java 的垃圾回收原理

java的垃圾回收分为三个区域
新生代 老年代 永久代

java的垃圾回收

GC流程：

• 一个对象实例化时 先去看伊甸园有没有足够的空间
• 如果有 不进行垃圾回收 ,对象直接在伊甸园存储.
• 如果伊甸园内存已满,会进行一次minor gc
• 然后再进行判断伊甸园中的内存是否足够
• 如果不足 则去看存活区的内存是否足够.
• 如果内存足够,把伊甸园部分活跃对象保存在存活区,然后把对象保存在伊甸园.
• 如果内存不足,向老年代发送请求,查询老年代的内存是否足够
• 如果老年代内存足够,将部分存活区的活跃对象存入老年代.然后把伊甸园的活跃对象放入存活区,对象依旧保存在伊甸园.
• 如果老年代内存不足,会进行一次full gc,之后老年代会再进行判断 内存是否足够,如果足够 同上.
• 如果不足 会抛出OutOfMemoryError.

参考链接：
http://ju.outofmemory.cn/entry/358715
https://liujiacai.net/blog/2018/07/08/mark-sweep/