并发标记清除回收
JVM中从JDK 4正式引入并发回收，用于解决垃圾回收过程中停顿时间过长的问题。JVM的垃圾回收器通常采用分代设计，新生代和老生代采用不同的垃圾回收算法，在并发垃圾回收器中，新生代采用并行的复制算法，老生代采用并发的标记清除算法。
狭义上所说的并发回收（Concurrent-MarkSweep，CMS）仅仅指针对老生代的回收，而广义上所说的并发垃圾回收指的是新生代采用并行复制算法、老生代采用并发标记清除算法。本文使用广义上的概念。
到目前为止，CMS仍然是最成功的垃圾回收器，满足了大多数业务场景的需要。一方面，其本身存在设计上的特点，存在停顿时间偶发过长的情况、停顿时间不可控等问题。另外一方面，CMS在实现时为了能更好地满足停顿时间的需要，将并发粒度设计得非常细，例如老生代垃圾回收的某些阶段可以和Mutator并发运行，老生代垃圾回收可以和新生代垃圾回收并发运行，新生代垃圾回收还可以抢占老生代垃圾回收等，细粒度的并发设计会导致CMS实现的复杂性，所以CMS也是bug最多的垃圾回收器之一，在使用时存在崩溃的情况。基于以上原因，JVM引入了Garbage First的垃圾回收器用于替代CMS，从JDK 11开始，正式不推荐使用CMS，在JDK 14中CMS正式被移除。
鉴于目前生产环境中仍然以JDK 8为主，同时广大的程序员仍然使用CMS，另外，大家遇到的如V8（JavaScript虚拟机）、ART（AndroidRuntime）等其他虚拟机中的垃圾回收也都有并发标记清除的垃圾回收器实现，所以本章还是对CMS进行详细介绍。
内存管理
为了解决垃圾回收过程中应用存在较长停顿时间的问题，CMS在吸收分代串行回收的优点的同时改进了原有垃圾回收器的不足之处（在CMS之前JVM还引入了火车回收算法，但该算法很快被移除，所以本书没有进一步介绍它）。CMS也采用分代的垃圾回收，保证应用有较高的吞吐量。同时它还对串行的分代回收做了优化，主要表现如下：
1）对新生代采用了并行的复制算法，提高了新生代的回收效率。
2）对老生代采用了并发标记清除垃圾回收算法，在垃圾回收过程仅回收死亡对象，然后重用死亡对象的内存空间，故此老生代回收有较低的停顿时间。
3）因为老生代中不移动活跃对象，所以在垃圾回收完成后存在较多的内存碎片，在应用运行一段时间后，可能无法响应应用的分配请求，因此又引入Full GC，针对整个堆空间进行回收。
和串行回收相比，CMS整个堆的管理示意图如图4-1所示。
图4-1 CMS堆管理示意图
CMS也采用边界固定的分代实现。实际上CMS的设计者也发现针对堆空间的划分不容易，所以在设计之初希望能支持新生代和老生代边界自由移动，实现新生代和老生代大小的动态调整，但是该思想在CMS中并未实现。所以CMS仍然采用固定边界的堆空间划分方法，将整个堆空间划分为两个代：新生代和老生代。
1）新生代主要用于响应Mutator的分配请求。
2）老生代主要用于新生代垃圾回收时对象的晋升，同时也可以响应一些特殊的Mutator分配请求（例如当Mutator请求对象过大时，就直接分配在老生代中）。
对于新生代的内存分配管理方式采用和串行的垃圾回收中类似的方式，为每一个Mutator关联一个TLAB，用于响应Mutator的分配。
对于老生代，因为采用并发标记清除算法，所以内存的管理方式稍微复杂，采用的是复杂链表的方式管理空间内存。最为简单的链表一般通过指针来管理空闲内存块，如图4-2所示。
图4-2 简单链表式内存管理示意图
简单的链表管理把所有空闲的内存块放在一条链表中（图4-2中采用大小不同的图例表示内存块大小不同），导致简单的链表管理存在性能问题，当Mutator或者GC线程分配内存时，需要遍历整个链表才能找到一个大小“合适”的内存块（避免内存的浪费），所以性能极其低下。对于这种管理方式一个简单的优化是：将大小相同的内存块放在同一个链表中，也就是说老生代被划分为多个链表，每个链表仅仅管理同样大小的内存块。这样在分配时可以根据请求的大小直接找到对应的链表来获取内存，如图4-3所示。
图4-3 多条链表管理不同大小的空闲内存块
该优化部分解决了查找内存块的问题，但是Mutator请求的对象大小分布可能相当广泛，可能有十几字节，也可能有几十千字节或者兆字节，需要很多链表来保存不同大小的内存块。而多个链表也会在查找链表头时存在性能问题（定位到某一个大小的链表）。所以进一步的优化是将所有的链表形成一棵二叉树，树中的每一个节点都是一个链表头，每个链表管理一个相同大小的内存块，如图4-4所示（图中使用实线描述二叉树的结构，用虚线描述树节点关联的链表）。
针对内存的请求，先查找树的节点，然后再查找树节点管理的链表进行分配。但在实现中还有一些细节需要考虑，比如树形链表的管理方式，需要使用额外的指针来构建树或者链表。如果使用额外的内存来管理这些指针，将会浪费一定的内存，所以CMS又对树形链表的结构进一步优化，消除了这些额外指针的内存消耗。
另外还有一点，虽然使用树形链表的方式管理空闲内存提高了分配的效率，但是每一次分配需要先查找树中的节点，再查找链表，分配效率仍然低下。另外，当树中找不到合适大小的内存块时，还需要对树的节点进行拆分用于满足分配，效率就更为低下。特别是针对一个小对象来说，这样的分配效率会直接影响Mutator和GC线程的吞吐量，所以还需要进一步优化。一个自然而然的方式是针对小对象使用额外的缓存方式，即图4-3所示的多链表管理方式。
CMS的老生代采用的就是如图4-3和图4-4所示的复合管理方式。
图4-4 树形内存管理方式
