垃圾回收算法：清除、压缩、复制
可达性分析提供了一种有效的方式，来标记哪些对象死亡，哪些对象还存活。然而，确定哪些对象死亡可以被回收，只是垃圾回收的第一步， 这个过程通常被称为标记（Mark）。接下来，需要一种方法来回收这些死亡对象占用的内存，以便这些内存可以被重新使用。这就是垃圾回收算法的任务。
垃圾回收算法描述了如何有效地回收垃圾对象的内存，同时尽量减少对程序执行的影响。
清除
清除（Sweep）算法的主要操作是将不再活跃的对象的内存标记为可用，并将这些内存信息记录在一个叫做空闲列表（Free List）的数据结构中。当程序需要实例化新的对象时，内存管理模块会从空闲列表中找到可用的内存空间，分配给新对象。
清除算法的主要缺点是可能导致内存碎片化。因为在堆内存中，对象的存储必须是连续的，可能会出现总的空闲内存充足，但无法找到足够大的连续内存空间来存储新的对象的情况。
另一个缺点是清除策略的内存分配效率较低。如果内存是连续的空间，可以通过简单的指针运算，比如指针加法（Pointer Bumping），快速分配内存。但对于清除算法中的空闲列表，需要逐一检查列表中的每一项，找到足够大的空闲内存来存储新的对象，这个过程相对耗时
image
压缩
压缩（Compact）算法的主要操作是将所有存活的对象移动至内存的一端，使这些对象在内存中连续排列，并更新所有指向这些对象的引用。这样，所有未被标记的对象都被挤压到内存的另一端，可以一次性回收。
压缩算法的优点是可以避免内存碎片，因为所有活动对象在压缩时都被紧凑排列。此外，这种算法不需要额外的内存空间，因为所有操作都在原地完成。
然而，压缩算法也有缺点。首先，压缩可能改变对象在内存中的位置，可能影响程序性能。其次，如果活动对象占据了大部分内存，压缩过程可能会非常耗时。
image
复制
复制（Copy）算法的主要操作是将所有活动的对象复制到内存的另一部分（通常称为to-space），并更新所有指向这些对象的引用。复制后，原来的内存区域（即from-space）中的所有对象都被视为垃圾，可以一次性回收。
复制算法的优势在于避免内存碎片，因为所有活动对象在复制时都被紧凑排列。此外，由于只处理活动对象，所以当大部分内存被垃圾对象占据时，此算法效率高。
然而，复制算法也有缺点。首先，它需要额外内存空间存放复制的对象。其次，复制过程可能改变对象在内存中的位置，可能影响程序性能。
image
并发标记：与时间赛跑的追踪游戏
标记阶段是所有追踪式垃圾回收算法的共同特征，这个阶段会随着堆变大而等比例增加停顿时间，其影响就会波及几乎所有的垃圾回收过程，同理可知，如果能够削减这部分停顿时间的话，那收益也将会是系统性的。
为了解决原始标记阶段带来的长时间停顿，多数现代的追踪式垃圾回收算法都会实现三色标记（Tri-color Marking）算法的变种以缩短停顿的时间。三色标记算法将程序中的对象分成白色、黑色和灰色三类。
1）白色对象：不活动对象，没有被其他对象引用，或者从根节点开始无法到达的对象；
2）灰色对象：活动对象，被其他对象引用，或者从根节点开始可以到达的对象。但是，这些对象引用的对象还没有被检查；
3）黑色对象：活动对象，从根节点开始可以到达的对象，而且这些对象引用的对象都已经被检查过了。
image
在垃圾回收过程中，首先将所有对象标记为白色，然后从根节点开始，将可达的对象标记为灰色，然后逐步将灰色对象标记为黑色，并将它们引用的对象标记为灰色。这个过程一直持续到所有活动对象都被标记为黑色，所有不活动对象都被标记为白色。
image
三色标记算法在并发环境下可能会出现问题，这个问题被称为“并发标记的漏标问题”。如下图所示的三色标记过程中，用户程序重新建立了从A对象到D对象的引用，但是因为程序中已经不存在灰色对象了，导致D对象本应被标记为灰色，而被错误地标记为白色，从而在垃圾回收时被错误地回收。
image
为了解决这个问题，可以使用写屏障（Write Barrier）技术。写屏障像是一个钩子方法，当一个对象的引用被修改时，会触发执行一段指令代码，将这个对象重新标记为灰色，以确保不会错过任何需要被标记的对象。这样，就可以在并发环境下正确地进行垃圾回收。
image
增量更新（Incremental Update）和快照在写时复制（Snapshot At The Beginning, SATB）都是垃圾回收中的写屏障技术，但是，它们在处理方式上有所不同。
1）增量更新：写屏障被触发时，如果一个黑色对象引用了一个白色对象，那么这个白色对象会被立即标记为灰色。
2）快照在写时复制：写屏障被触发时，会记录下被修改的引用，而不是立即修改对象的颜色。然后在并发标记结束时，根据这些记录，重新标记那些被错误地标记为非活动对象。
