垃圾收集算法
在文章 生存还是死亡？？中，提到了两种判断对象是否存活的方法：「引用计数算法」和「可达性分析算法」
由于引用计数算法在主流 Java 虚拟机中均未涉及，所以本篇文章介绍的所有算法都是基于「可达性分析」的
分代收集理论
当前商业虚拟机的垃圾收集器，大多数都遵循了「分代收集」的理论进行设计。虽然称之为理论，但其实质是一套符合大多数程序运行实际情况的经验法则，它建立在两个分代假说之上：
- 弱分代假说：绝大多数对象都是朝生夕灭的
- 强分代假说：熬过越多次垃圾收集过程的对象越难以消亡
这两个分代假说共同奠定了多款常用的垃圾收集器的一致设计原则：收集器应该将 Java 堆划分出不同的区域，然后将回收对象依据其年龄 (年龄即对象熬过垃圾收集过程的次数) 分配到不同的区域之中存储
如果一个区域中大多数对象都是朝生夕灭，难以熬过垃圾收集过程的话，那么把它们集中放在一起，每次回收时只关注如何保留少量存活而不是去标记那些大量将要被回收的对象，就能以较低代价回收到大量空间
如果剩下的都是难以消亡的对象，那把它们集中放在一块，虚拟机便可以使用较低的频率来回收这个区域
对两个特点不同的区域分别采用不同的收集策略，这就同时兼顾了垃圾收集的时间开销和内存的空间有效利用
我们为上述两个区域取了很生动形象的名字：「新生代 (Young Generation)」和「老年代 (Old Generation)」。在新生代中，每次垃圾收集时都发现有大批对象死去；而每次回收后存活的少量对象，将会逐步晋升到老年代中存放
不仅为区域取了相应的名字，而且还为不同的垃圾收集策略取了相应的名字，为了避免产生混淆，这里统一定义：
部分收集 (Partial GC)：不是完整收集整个 Java 堆的垃圾收集，其中又分为：
- 新生代收集 (Minor/Young GC)：只是对新生代的垃圾收集
- 老年代收集 (Major/Old GC)：只是对老年代的垃圾收集。目前只有 CMS 收集器会有单独收集老年代的行为；另外 Major GC 说法有点混淆，需要根据上下文区分到底是老年代收集还是整堆收集
- 混合收集 (Mixed GC)：对整个新生代以及部分老年代的垃圾收集。目前只有 G1 收集器会有这种行为
整堆收集 (Full GC)：收集整个 Java 堆和方法区的垃圾收集
虽然分代收集有一些好处，但它存在一个问题：对象不是孤立的，对象之间会存在跨代引用，该问题在前文 生存还是死亡？？提到过
出现这个问题的本质就是：新生代中的对象完全有可能被老年代所引用，为了找出新生代中存活的对象，不得不在固定的 GC Roots 之外，再额外遍历整个老年代中所有对象来确保可达性分析结果的正确性
这无疑会为内存回收带来很大的性能负担，为了解决这个问题，就需要对分代理论添加第三条经验法则：
- 跨代引用假设：跨代引用相对于同代引用来说仅占极少数
这一条是可根据前面两条推出的隐含结论：存在相互引用关系的两个对象，是应该倾向于同时生存或者同时消亡的
举个例子，如果某个新生代对象存在跨代引用，由于老年代对象难以消亡，该引用会使得新生代对象在收集时同样得以存活，进而在年龄增长之后晋升到老年代中，这时跨代引用也随即被消除了
根据这条假说，我们就不应再为了少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用，只需在新生代上建立一个全局的数据结构 (记忆集 Remenbered Set)
这个结构把老年代划分为若干小块，标示出老年代哪一块内存会存在跨代引用。此后当发生 Minor GC 时，只有包含了跨代引用的小块内存里的对象才会被加入到 GC Roots 进行扫描
虽然这种方法需要在对象改变引用关系 (如：将自己或者某个属性赋值) 时维护记录数据结构的正确性，会增加一些运行时的开销，但比起收集时扫描整个老年代来说仍是划算的
标记-清除算法
这个算法如它的名字一样，先「标记」后「清除」。可以标记已死的对象，然后把标记的对象清除 (引用计算算法)；也可以反过来，标记存活的对象，然后把未标记的对象清除 (可达性分析算法)
判断对象死亡还是存活，在文章 生存还是死亡？？中已经介绍过，有两种算法：「引用计算算法」和「可达性分析算法」。当前主流的商用程序语言 (Java，C#，Lisp) 的内存管理子系统都是通过「可达性分析算法」来判定对象是否存活的！！
「标记-清除算法」的执行过程如下图所示：
这个算法也是最基础的收集算法，因为后续的收集算法大多都是以「标记-清除算法」为基础，对其缺点进行改进而得到的
它的缺点主要有两个：
- 执行效率不稳定。如果 Java 堆中包含大量对象，而且其中大部分是需要回收的，这时必须进行大量的标记和清除动作，导致标记和清除两个过程的执行效率都随对象的数量增长而降低
- 内存空间碎片化。标记、清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致当以后在程序运行过程中需要分配较大对象时无法找到足够的连续内存而不得不提前触发另一次 GC 动作
标记-复制算法
「标记-复制算法」常被简称为复制算法。为了解决「标记-清除算法」面对大量可回收对象时执行效率低的问题 (第一个缺点)，提出了一种「半区复制」的垃圾收集算法
它将可用内存按容量分为大小相等的两块，每次只使用其中的一块。当这一块内存用完了，就将还存活的对象复制到另外一块上面，然后再把已使用过的内存空间一次性清理掉
「标记-复制算法」的执行过程如下图所示：
如果内存中多数对象都是存活的，这种算法将会产生大量的内存间复制的开销；但对于多数对象都是可回收的情况，算法需要复制的就是占少数的存活对象，而且每次都是针对整个半区进行内存回收，分配内存时也就不用考虑有空间碎片的复杂情况，只要移动堆顶指针，按顺序分配即可
优点：
- 不存在内存碎片的问题
- 没有标记的过程，直接枚举 GC Roots，若可达，则复制；实现简单、运行高效
缺点：
- 可用内存缩小为原来的一半，浪费空间
- 复制意味着对象移动，需要维护对象引用之间的关系，时间开销增加
- 在对象存活率较高时就要进行较多的复制操作，效率将会降低 (如：老年代)
现在的商用 Java 虚拟机大多都优先采用了这种收集算法去回收新生代，新生代中绝大多数对象都是朝生夕灭的，有研究表明：新生代中的对象有 98% 熬不过第一轮收集。因此并不用按照 1 : 1 的比例来划分新生代的内存空间
Andrew Appel 针对具备朝生夕灭特点的对象，提出一种更优化的半区复制分代策略，现在称为 Appel 式回收。Appel 式回收的具体做法如下：
- 首先把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间，其比例默认为 8 : 1 : 1，每次分配对象只使用 Eden 和其中一块 Survivor 空间上
- 发生垃圾收集 (Minor GC) 时，将 Eden 和 Survivor 中仍然存活的对象一次性复制到另外一块 Survivor 空间上，然后直接清理掉 Eden 和已用过的那块 Survivor 空间
当然，没有人能保证每次都只有 10% 的幸存对象，如果某一次的幸存对象超过了 10%，那么 Survivor 空间就存放不下
因此 Appel 式回收还有一个充当罕见情况的「逃生门」的安全设计，当 Survivor 空间不足以容纳一次 Minor GC 之后存活的对象时，就需要依赖其它内存区域 (老年代) 进行分配担保
换句话来说：如果另外一块 Survivor 空间没有足够空间存放上一次新生代收集下来的存活对象，这些对象便将通过分配担保机制直接进入老年代
下面用图来简单展示一下这个过程：关于「内存分配与回收策略」的更多细节，可见 对象的创建
标记-整理算法
「标记-复制算法」适合存活对象较少的区域，如朝生夕灭的年轻代；对于像老年代这种区域，对象都是难以消亡的，再使用「标记-复制算法」的话，效率将会降低
更关键的，如果不想浪费 50% 的内存，就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都 100% 存活的极端情况。在老年代中，触发担保的概率更大，所以老年代一般不直接选用这种算法
针对老年代对象的死亡特点，提出一种基于「标记-清除算法」的「标记-整理算法」，它们俩唯一的区别为是否整理了内存碎片 (这也是「标记-清除算法」的缺点，存在大量内存碎片)
「标记-整理算法」的标记过程与「标记-清除算法」一样，但后续过程不是直接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存
「标记-整理算法」的执行过程如下图所示：
是否移动回收后的存活对象是一项优缺点并存的风险决策：
- 如果移动存活对象，会给垃圾收集过程造成负担 (老年代存活对象多，移动对象并更新所有引用这些对象的地方是一种极为负重的行为，而且必须 STW (Stop The World))
- 如果不移动对象，导致存在大量内存碎片，给新对象分配内存时需要依赖更为复杂的机制 (如：分区空闲分配链表)，也为内存访问带来了负担
总结一下：如果移动，则回收内存时更复杂；如果不移动，则分配访问时更复杂
但由于内存分配和访问相比于垃圾收集的频率要高得多，所以移动的性价比更高 (但仍然需要用一种辩证的态度去看待)
另外，还有一种「和稀泥式」解决方案可以不在内存分配和访问上增加太大的额外负担：让虚拟机平时多数时间都采用「标记-清除算法」，暂时容忍内存碎片的存在，直到内存空间的碎片化程度已经大到影响对象的分配时，再采用「标记-整理算法」收集一次，以获得规整的内存空间
写在后面
👇👇👇👇👇👇👇👇👇👇👇👇
