1. 垃圾回收基本操作
1.1 标记可达对象（Marking Reachable Objects）
目前几乎所有的GC算法都是从标记存活对象开始的。如下图所示，GC算法会从GC Root开始，标记所有目前所有可达的对象。
1.1.1 GCRoots
GCRoots大致有如下几种:
当前执行函数的局部变量和输入参数
正在工作的线程
被加载类的静态块
JNI(Java Native Interface)引用
1.1.2 标记算法实现
标记算法的算法实现，可参考如下伪码：
Marking stack (linked list) = empty
Root.mark = 1
Push root onto marking stack (i.e., insert root at head of marking stack linked list using extra header word to hold the link)
While marking stack is not empty
Pop a block P off the marking stack
For every pointer Q in P’s data area
If Q.mark == 0
Q.mark = 1
Push Q onto marking stack
1.1.3 Card Marking
上述的朴素的标记算法并不适用于并发GC的情况。
并发标记操作在进行的过程中，如果一个对象及其子对象已经被标记，而此时用户线程操作这一对象，为其新引用了一个将要被回收的对象时，普通的标记算法可能无法标记到这一对象。但是Card Marking算法则可以利用将这一个块(Card)标记为为“脏块”(Dirty Card)的方式记录下这个块，等待GC Collector后续处理。
本节介绍的是最简单的Card Marking算法，更多的实现请查看Card Marking算法。
1.1.4 三色标记算法（Tri-color Marking Algorithm）
三色标记算法的数据结构中包含有三个集合：White Set, Black Set和Gray Set。
- 白色集合对象：需要被回收的对象。
- 黑色集合对象：没有对白色集合对象的外部引用，并且是GC Root可达的对象。这些对象将不会被回收。
- 灰色集合对象：集合中的对象全都是GC Root可达的对象，但是正在扫描或正在等待扫描其对“白色集合对象”的引用，这些对象也不会被回收，并且会在扫描结束之后被移入黑色集合。
在大多数算法实现中，黑色集合初始是空，灰色集合中保存有与GC Roots对象直连的所有老年代对象，白色集合中包含有其他对象。内存中的任意对象在任意时间都仅存在于这三个集合当中的一个。
算法步骤：
- 从灰色集合中取出一个对象放入黑色集合
- 遍历第1步取出的对象的所有白色集合对象引用，并将它们移入灰色集合。这保证了这个对象和它的引用对象都不会被GC
- 重复上述两步，直到灰色集合为空
由于非GC Root直接可达的节点都被加入到了White Set，并且对象只能从白色集合移动到灰色集合，从灰色集合移动到黑色集合，所以算法体现了一个重要特性-黑色集合中的对象不会引用到白色集合中的对象。这就保证了在灰色集合为空时，我们可以放心地释放白色空间中的对象。这被称作三色不变式（The Tri-color Invariant）。
1.2 移除不可达对象 (Removing Unused Objects)
1.2.1 清理(Sweep)
清理算法会遍历整个内存，释放(Free)掉内存区域中所有未被标记的对象，同时重置标记过的对象的标记位。标记-清理算法使用最简单
释放内存是由一个叫做free-list的数据结构来实现的，它会记录每一个空闲的空间地址和他的大小。维护这些free-lists会给创建对象的内存分配带来额外的开销。除此之外，这种方法还有另外一个缺点--可能存在有大量的空闲空间，但是却没有一个比较大的连续空闲空间（过多内存碎片），当内存中需要放入一个大对象时，系统将会分配内存失败。（OutOfMemoryError）
清理算法的代码实现可参考如下伪码:
Free list = empty
For every block P in the heap
If P.mark == 1
(P is an in-use block)
P.mark = 0
Else if block Q, the block immediately before block P, is a free block
(Coalesce P into Q)
Q.nWords = Q.nWords + P.nWords
Else
(P is a free block)
Append P to free list
1.2.2 整理(Compact)
整理步骤是将所有被标记的存活对象按顺序移动到内存的前部，它一般配合标记算法和清除算法一起使用（标记-清除-整理算法）。由于压缩的过程中清理了内存碎片，所以这个算法可以弥补标记-清除算法的短处。但是这个整理的步骤也会影响到算法的性能，因为算法需要把所有的对象拷贝到一块新的内存空间，同时还要改变他们的引用。
目前常用的整理算法分为两种，Table-based compaction和LISP2：
1.2.2.1 Table-based compaction
Table-based compaction算法是由Haddon和Waite在1967年提出来的。算法的特点是不需要额外的空间。
算法步骤：
- 第一步是用mark算法先将所有的存活对象标记出来。
- 第二步是遍历整个堆，将对象移动到最初的free空间中（向前移动），并且将对象的原始起始地址和移动的字节数记录在一个叫break table的数据结构中。（break table会不断的移动，使用的是unused空间）
- 第三步是对break table按照对象初始地址排序。排序时间复杂度O(n logn)，n是存活对象数。
- 第四步是修改移动过后的对象中的指针引用，如果引用指针个数总数为m，一次指针查找的复杂度是logn（二分查找），则算法复杂度为O(m logn)
详细信息可查看A compaction procedure for variable-length storage elements。（论文介绍了break table是如何通过移动来找到一块合适的unused空间）
1.2.2.2 LISP2算法
LIST2算法是一种时间复杂度与堆大小成正比的compact算法，目前被应用于ParallelScavenge算法中。
LISP2算法需要每一个对象都存在一个叫“forwarding pointer”的指针，它被用来临时保存对象在compact之后被移动到的位置。同时，LISP2算法在进行的过程中还需要用到两个全局的指针–free指针和live指针。其中，free指针用来指向当前空闲的区域，live指针用来指向当前操作的存活对象。
算法步骤：
- 计算对象移动后的位置：先让free指针和live指针都指向堆的头部，如果当前live指针指向了一个存活的（被标记的）对象，那么将free指针指向的值赋予live指针指向对象的forwarding pointer区域，然后将live指针和free指针的值都加上sizeof(current_obj)。如果live指针当前指向的不是一个存活对象，那么就逐步移动live指针，直到它指向了一个存活的对象为止。整个步骤结束于live指针指向了堆的结尾。
- 更新所有指针：与第一步一样，找出每一个存活对象，将这些对象里面的对象对应引用变量值修正为被引用对象的forwarding pointer值。
- 移动对象：还是需要找出所有存活对象，将对象的数据移动到forwarding pointer所指向的区域。
算法的伪代码如下：
Pass 1: Compute forwarding addresses
free = start of heap + size(header)
For each block P in the heap
If P.mark == 1
P.fwdAddr = free
free = free + P.nWords
Else
Q = block before P
If Q.mark == 0
(Coalesce P into Q)
Q.nWords = Q.nWords + P.nWords
Pass 2: Update pointers
root = (*root).fwdAddr
For each block P in the heap
If P.mark == 1
For each pointer Q in P’s data area
Q = (*Q).fwdAddr
Pass 3: Relocate blocks
For each block P in the heap
If P.mark == 1
P.mark = 0
Copy contents of P backwards so first word of P’s data area ends up at P.fwdAddr
(*free).nWords = Number of free words in the heap
这个算法一共要遍历三次堆，所以时间复杂度和堆空间的大小成正比。为O(m)，m为堆空间大小。
1.2.3 复制(Copy)
复制算法很像压缩算法，他们都会移动所有的存活对象并且修改对象内部引用的指针地址。而复制算法的不同之处则在于它会将这些对象移动到一个新的区域内。标记复制算法有一个非常大的优点--复制操作可以和标记操作在同一时间进行。它的缺点也很明显，他需要一个足够容纳一次GC后存活对象大小的内存区域。
复制算法的一种实现是Cheney算法，它是由C.J. Cheney在1970年在论文A nonrecursive list compacting algorithm提出的。
算法步骤：
主函数：
- 将roots对象加入tospace（调用Copy函数）。
- 将tospace看做一个Queue，从头至尾遍历存在的数据节点，针对数据节点中的每一个指针，调用Copy函数。
Copy函数：
- 如果该对象已经被移动到了tospace（对象中的forworded字段为1），那么直接返回对象在tospace中的首地址。
- 如果对象尚未移动，则将对象的数据移动到tospace，free指针后移对象的长度个单位，并且把对象的forwarded域置为1，最后返回移动后的地址。
算法实现（Cheney's algorithm）：
scan = fromspace
free = tospace
root = Copy (root)
While scan < free
Block P = *scan
For every pointer Q in P’s data area
Q = Copy (Q)
scan = scan + size(P)
Interchange roles of fromspace and tospace
function Copy
# To copy a block B located in the fromspace, returning its new address in the tospace:
If B.forwarded == 1
Return forwarding address from first word of B’s data area
Else
fwdaddr = free
Copy B’s contents to fwdaddr
free = free + size(B)
Store fwdaddr in first word of B’s data area
B.forwarded = 1
Return fwdaddr
注：
- 算法中forwarded字段位于Block Header中，值为1表示块已经被移动to space。
- forwarded=1标示块中数据区存放了fwdaddr，位于块数据区的第一个word中。
- 本算法遵循三色不变式
1.3 三种基本算法比较
上述的几种垃圾回收基本操作可以组成的三种算法：标记-清除，标记-整理和复制算法。它们的基本信息如下表所示。
| mark-sweep | mark-compact | copying | |
|---|---|---|---|
| 速度 | 中等 | 最慢 | 最快 |
| 空间开销 | 少（但会堆积碎片） | 少（不堆积碎片） | 通常需要活对象的2倍大小（不堆积碎片） |
| 移动对象？ | 否 | 是 | 是 |
关于时间开销：
- mark-sweep：mark阶段与活对象的数量成正比，sweep阶段与整堆大小成正比
- mark-compact：mark阶段与活对象的数量成正比，compact阶段与活对象的大小成正比
- copying：与活对象大小成正比
如果把mark、sweep、compact、copying这几种动作的耗时放在一起看，大致有这样的关系：
- compaction >= copying > marking > sweeping
- marking + sweeping > copying
虽然compactiont与copying都涉及移动对象，但取决于具体算法，compact可能要先计算一次对象的目标地址，然后修正指针，然后再移动对象；copying则可以把这几件事情合为一体来做，所以可以快一些。
另外还需要留意GC带来的开销不能只看collector的耗时，还得看allocator一侧的。如果能保证内存没碎片，分配就可以用pointer bumping方式，只有挪一个指针就完成了分配，非常快；而如果内存有碎片就得用freelist之类的方式管理，分配速度通常会慢一些。
在分代式假设中，年轻代中的对象在minor GC时的存活率应该很低，这样用copying算法就是最合算的，因为其时间开销与活对象的大小成正比，如果没多少活对象，它就非常快；而且young gen本身应该比较小，就算需要2倍空间也只会浪费不太多的空间。
而年老代被GC时对象存活率可能会很高，而且假定可用剩余空间不太多，这样copying算法就不太合适，于是更可能选用另两种算法，特别是不用移动对象的mark-sweep算法。
2. 对象分配算法
2.1 内存块存储结构
内存块的数据结构如下图所示，其中每一个区域的作用如下：
- Block Data Area：1. 这一块是用户程序所使用的内存；2. 大小可变，取决于用户程序一开始申请了多少空间；3. 块分配时，返回的指针指向的是- - Block Data Area的头部，用户程序也只能感受到Block Data Area中的内容。
- Block Header：1. 这一块内容是堆的内部程序锁使用的空间；2. 这一块大小是固定的；3. 用户程序无法感知到这一块内存。
- nWords：1. 内容是Block的大小（data area + header）；2. 块的最大大小被nWords的位(bit)数所约束，比如说24位的nWords可以支持的最大Block是16,777,215个Words（word大小自定义）
- Control bits：包含了垃圾回收时所需要用到的一些信息（比如标记信息）
2.2 单个空闲空间组织结构（One Big Free Space Organization）
2.2.1 堆结构
单个大空闲块的组织结构如下图所示，所有被使用的块都存放于堆的顶部，而未被使用的快则是被某一个块所控制。使用移动对象类型的垃圾回收算法（如mark-compact，copying）可以保证堆空间中的空闲空间总是以该结构的形式组织。
这种组织结构的优点：1. 对象分配速度快；2. 堆中没有内存碎片，可以分配更大的对象。
缺点：需要可以移动对象的垃圾回收算法（速度慢，对象需要移动，指针需要调整）
2.2.2 分配算法
这种单个空闲空间的堆空间分配内存非常简单，可以直接使用bump-the-pointer的算法，如下图，移动一下指针就完成了内存分配。
算法实现的伪代码如下，算法的时间复杂度是O(1)：
size(block) = n + size(header)
If free.nWords < size(block)
Failure (time for garbage collection!)
p = free
free = free + size(block)
free.nWords = p.nWords - size(block)
p.nWords = size(block)
return p
2.3 Free List组织结构
2.3.1 堆结构
Free List组织结构的对结构如下图所示，被使用的块和空闲的块在堆中是相互交错着排列的，另外一个要点就是空闲的块会被连接成一个叫做Free List的链表。
这种组织结构的优点：适用不需要移动对象的垃圾回收算法（对象回收速度更快，因为不需要移动被使用的对象，也不需要调整指针）
缺点：1. 分配算法更加复杂，耗时也更长；2. 存在有内存碎片，会限制分配对象的最大值
2.3.2 分配算法
Free List组织结构下存在有两种分配算法：First-Fit分配算法和Best-Fit分配算法。顾名思义，First-Fit分配算法就是在Free List中找出第一个适合分配的空间，而Best-Fit分配算法则是在Free List中找出最接近被分配对象大小的Free块，并将这个块分配给这个对象。这两种算法的伪代码如下所示：
First-Fit Allocation Algorithm
size(block) = n + size(header)
Scan free list for first block with nWords >= size(block)
If block not found
Failure (time for garbage collection!)
Else if free block nWords >= size(block) + threshold*
Split into a free block and an in-use block
Free block nWords = Free block nWords - size(block)
In-use block nWords = size(block)
Return pointer to in-use block
Else
Unlink block from free list
Return pointer to block
*Threshold must be at least size(header) + 1 to leave room for header and link
Threshold can be set higher to combat fragmentation
Best-Fit Allocation Algorithm
size(block) = n + size(header)
Scan free list for smallest block with nWords >= size(block)
If block not found
Failure (time for garbage collection!)
Else if free block nWords >= size(block) + threshold*
Split into a free block and an in-use block
Free block nWords = Free block nWords - size(block)
In-use block nWords = size(block)
Return pointer to in-use block
Else
Unlink block from free list
Return pointer to block
*Threshold must be at least size(header) + 1 to leave room for header and link
Threshold can be set higher to combat fragmentation
2.4 分配逻辑
- 当堆中的空闲块不够新申请空间的大小时，将会进行一次垃圾回收，然后在尝试分配
- 如果空间还是不够，则会尝试增大堆的大小，然后再尝试分配
- 最后如果空间还是不够，则会抛出OutOfMemoryError
3. CMS算法
CMS算法是JVM中老年代常用的垃圾回收算法，全称是Concurrent Mark Sweep算法，即并发标记-清除算法。算法的执行步骤如下图所示，共有六个步骤。
3.1 初始标记(Initial Mark)：
CMS算法中两个会触发Stop the World事件中的一个，这个阶段会标记所有与GC Roots直接相关联的对象，以及被存活的青年代对象所直接引用的对象。
3.2 并发标记(Concurrent Mark)：
并发标记，顾名思义，它是并发的执行标记任务的，这也就意味着GC在运行的过程中用户的应用线程并不会停止工作。该阶段GC收集器会从第一步“初始标记”中所标记出来的对象开始逐步遍历这些对象（与GCRoot直接相连或与存活的青年代对象直接相关联的对象）的所引用的对象，并将这些被引用的对象加上标记。
需要注意的是，这一步中，会漏掉一下老年代的存活对象，这是因为在并发的过程中，用户应用线程可能会对老年代的对象产生引用上的改变。某一些被改变的标记可能会被遗漏。
3.3 并发预清理(Concurrent Preclean)：
并发预清理是Java1.5被加入进来的。主要目的是减少重标记（Remark）步骤Stop-the-World的时间。这一步同样也是并发的，不会停止用户应用线程。在前面的并发标记中，一些引用被改变了。当某一块块（Card）中的对象引用发生改变时，JVM会标记这个空间为“脏块”（Dirty Card）。
在预清理阶段，JVM根据之前记录的这些“脏对象”重新标记了他们新的可达对象。这一步结束后空间重新进入clean状态。另外，一些必要的最终重标记之前的准备步骤也会在这一步做好。
预清理步骤将会不断重复一直到Eden区的占用量达到某个指定的阈值。设定这个阈值作为结束条件的原因主要是为了防止YoungGC产生的Stop-the-World和下一阶段的Remark同时产生，导致系统产生一个更长的停滞。设定了这个阈值之后基本可以保证Remark阶段可以在两次YoungGC之间进行。
3.4 重标记(Remark):
这是CMS算法中第二个会触发Stop-the-World事件的步骤，由于前一步是一个并发的步骤，预清理的速度可能会赶不上用户应用对对象改变的速度，所以需要一个Stop-the-World的暂停来完整的标记所有对象结束整个标记阶段。
通常CMS会在年轻代为空时来运行重标记阶段，以此避免一个接一个的Stop-the-World阶段。
3.5 并发清理(Concurrent Sweep):
这一阶段程序并发地工作，目的是移除所有不用的对象，并且重新声明内存空间的归属等候将来使用。
3.6 并发清理(Concurrent Reset):
并发地重置所有算法需要的内部数据结构，为下一次GC做准备。
3.7 CMS算法注意事项:
3.7.1 Concurrent Mode Failures
当CMS算法在并发的过程中堆空间无法满足用户程序对新空间的需求时，Stop-the-World的Full GC就会被触发，这就是Concurrent Mode Failures，这通常会造成一个长时间停顿。这种情况通常是因为老年代没有足够的空间供青年代对象promote。（包括没有足够的连续空间）
3.7.2 CMS相关JVM参数
- -XX:+UseConcMarkSweepGC：激活CMS收集器，默认情况下使用ParNew + CMS + Serial Old的收集器组合进行内存回收，Serial Old作为CMS出现“Concurrent Mode Failure”失败后的后备收集器使用。
- -XX:CMSInitiatingOccupancyFraction={x}：在老年代的空间被占用{x}%时，调用CMS算法对老年代进行垃圾回收。
- -XX:CMSFullGCsBeforeCompaction={x}：在进行了{x}次CMS算法之后，对老年代进行一次compaction
- -XX:+CMSPermGenSweepingEnabled & -XX:+CMSClassUnloadingEnabled：让CMS默认遍历永久代（Perm区）
- -XX:ParallelCMSThreads={x}：设置CMS算法中并行线程的数量为{x}。（默认启动(CPU数量+3) / 4个线程。）
- -XX:+ExplicitGCInvokesConcurrent：用户程序中可能出现利用System.gc()触发系统Full GC（将会stop-the-world），利用这个参数可以指定System.gc()直接调用CMS算法做GC。
- -XX:+DisableExplicitGC：该参数直接让JVM忽略用户程序中的System.gc()
4. 参考资料
- GC算法基础及实现：https://plumbr.eu/handbook/what-is-garbage-collection
- Oracle文档：https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/toc.html
- CMS算法：http://insightfullogic.com/2013/May/07/garbage-collection-java-3/
- GC Tuning: https://plumbr.eu/handbook/gc-tuning-measuring
- 三色标记： https://en.wikipedia.org/wiki/Tracing_garbage_collection#Tri-color_marking
- 内存管理wiki： http://www.memorymanagement.org/glossary/
- Rednaxelafx’s Blog: http://rednaxelafx.iteye.com/blog/362738
- rit GC资料：https://www.cs.rit.edu/~ark/lectures/gc/index.html
- memory barrier: https://www.kernel.org/doc/Documentation/memory-barriers.txt
