顺序员真的有须要把GC算法好好于一遍，由于它是进大厂必备的

tzwwtz

GC算法概述
最先的GC算法能够追溯到20世纪60年代，但到目前为止，GC的根本算法没有太多的翻新，能够分为复制算法（Copying GC）、标志革除（MarkSweep GC）和标志紧缩（Mark-Compact GC）。近年推出的GC算法也都是在根底算法上针对一些场景进行优化，所以十分有须要了解根底的GC算法。
复制算法
复制算法是把堆空间分为两个部份，分别称为From Space（From空间）和To Space（To空间）。其中From空间用于运用的内存调配，To空间用于履行GC时活泼对象的转移。GC履行时From空间中的活泼对象都会转移到To空间中，GC实现后From和To替换，From空间中残余尚未使用的空间持续用于运用的内存调配，To空间用于下一次GC活泼对象转移。上面经过示用意演示。假定对象标志如图2-4所示。


图2-4 复制算法履行前内存空间形态
复制算法履行之后，内存示用意如图2-5所示。


图2-5 复制算法履行后内存空间形态
复制算法的特征能够总结为：
1）复制实现后，To空间中的对象是根据堆空间的内存程序调配的，也就是说复制实现后，To空间不存在内存碎片的问题。
2）复制实现后，From空间和To空间替换，运用顺序新的对象都调配在From空间残余的空间中（图2-5为了演示复制进程，没有将From和To替换）。
因为复制算法波及对象的挪动，因此必需存储对象挪动先后的地位瓜葛（确保对象只转移一次），在复制算法中当对象转移胜利后，通常把转移后的地址保留在对象头中，当再次转移相反对象时能够经过对象头的信息获取转移后的对象，无须再次转移，这也象征着复制算法除了转移对象之外，还需求在原对象转移胜利后在原对象的对象头中设置对象转移后的地址。能够想象，当多线程并行履行复制算法时，需求斟酌同步，避免多个线程同时转移一个对象，通常使用无锁的原子指令来包管对象仅能胜利转移一次。
复制算法通常只需求遍历From空间一次就能实现一切活泼对象的转移，所以对象的标志和转移一次性实现。因为转移中需求遍历活泼对象的成员变量，因此算法完成中需求一个额定的数据构造保留待遍历的对象，固然这个额定的数据构造能够是队列或者栈。Cheney提出的复制算法借助To空间而不需求额定的数据构造，该算法在前面具体引见。
此外，复制算法还有一个最大的问题：空间利用率不敷高。如图2-4和图2-5所示，空间利用率只要50%。为理解决空间利用率的问题，JVM对复制算法进行了优化，设置了3个分区，分别是Eden、Survivor 0（简称S0）和Survivor 1（简称S1）。在新的优化完成中，Eden用于新对象的调配，S0和S1存储复制算法时标志活泼对象。这个优化的依据是，运用顺序调配的对象很快就会死亡，在GC回收时活泼对象占比个别都很小，所以不需求将一半空间用于对象的转移，只需使用很少的空间用于对象的转移，S0和S1加起来通常小于全部空间的20%就可以保留转移后的对象。上面演示一下新的优化算法的履行进程。
新调配的对象都放在Eden区，S0和S1分别是两个存活区。复制算法第一次履行前S0和S1都为空，在复制算法履行后，Eden和S0外面的活泼对象都放入S1区，如图2-6所示。


图2-6 复制算法第一次履行
回收后运用顺序持续运转并发生渣滓，在复制算法第二次履行前Eden和S1都有活着的对象，在复制算法履行后，Eden和S1外面活着的对象都被放入S0区，如图2-7所示。


图2-7 复制算法第二次履行
虽然优化后的算法能够进步内存的利用率，然而带来了额定的繁杂性。
例如，S0可能无奈存储一切活泼对象的状况（这在规范的半代回收中不会泛起，活泼对象不成能超过使用空间的最大值）。通常有两种办法处置S0溢出的状况：使用额定的预留空间保留溢出的对象，这部份空间需求预留；静态调剂S0和S1的大小，包管S0和S1在GC履行时知足对象转移的需求，这象征着Eden、S0/S1的界限其实不固定，在完成时需求额定处置。这两种办法在JVM中均有体现。此外JVM完成了分代算法，在某一个代中履行复制算法时，假如泛起S0或S1溢出，则能够跨代使用其余代的内存。
标志革除算法
复制算法的空间利用率无限，但效力较高，而且GC履行进程包孕了紧缩，所以不存在内存碎片化问题。此外一种GC算法是标志革除，关于内存的办理能够使用链表的形式，当运用需求内存时从链表中获取一块闲暇空间并使用，当GC履行时首先遍历全部空间中一切的活泼对象，而后再次遍历内存空间，将空间中一切非活泼对象释放并参加闲暇链表中。以图2-4的内存形态为例，标志革除算法履行完结后的示用意如图2-8所示。


图2-8 标志革除算法履行完结后的内存示用意
标志革除算法的内存使用率相对于来讲较高，然而还有一些详细状况需求进一步剖析。因为标志革除算法使用链表的形式调配内存，因此需求斟酌调配的效力及内存调配时内存碎片化的状况。详细来讲，空间链表中寄放尚未使用或者曾经释放的内存块，这些内存块的大小其实不相反。从闲暇链表中申请内存块时，需求遍历链表找到一个内存块。此外，因为链表中内存块大小不相反，因此可能没有和申请大小同样的内存块，此时需求找到一个比申请内存大的内存块能力知足运用的需求，这就需求额定的管制战略，是找到一个和申请内存尽量接近（best-fit）的内存块，仍是找一个最大（worstfit）的内存块，或者是第一个知足需要（first-fit）的内存块？不同战略致使调配时的碎片化状况有所不同。
除了斟酌调配效力和调配时内存碎片化的状况，还需求斟酌回收的状况。特别是回收时闲暇内存的合并，是不是允许相邻的空间内存块合并？合并需求破费额定的时间，同时也会影响内存的碎片化。
在JVM中并发标志革除采取了该算法，为进步调配效力使用了多条链表及树形链表，调配战略使用best-fit办法，回收时提供了5种战略并辅以预测模型管制闲暇内存块的合并。更多细节参考第4章。
标志紧缩算法
标志革除算法的内存利用率虽然对比高，然而有一个首要的缺陷：内存碎片化重大。内存碎片化可能会致使无奈知足运用大内存块的需要。此外一种GC算法是标志紧缩算法，其实质是就地紧缩内存空间，而不是像复制算法那样需求一个额定的空间。算法能够分为下列4步：
1）遍历内存空间，标志内存空间的活泼对象。
2）遍历内存空间，计算一切活泼对象紧缩后的地位，“紧缩后”是指假如遇到死亡对象，则间接将其掩盖。
3）遍历内存空间，更新一切活泼对象成员变量紧缩后的地位。
4）遍历内存空间，挪动一切活泼对象到第二步计算好的地位，此时因为对象外部的成员变量曾经实现更新，因此挪动对象后一切的援用瓜葛都是正确的。
在一些完成中，第二步和第三步能够借助额定的数据构造合并成一步。
整体来讲，标志紧缩算法需求遍历3～4次内存空间，虽然内存利用率更高，而且GC履行后不存在内存碎片的问题，然而由于屡次遍历内存空间，故算法的履行效力不高。
依然以图2-4的内存形态为例，标志紧缩算法履行完结后的示用意如图2-9所示。


图2-9 标志紧缩算法履行后内存示用意
因为标志紧缩算法履行效力不高，因此通常作为GC的兜底算法。标志紧缩在JVM中也有多种完成，分别是串行完成、并行完成。在第3～5章中都会引见标志紧缩算法。
分代回收
3种GC算法各有优缺陷，实际中需求按照需要选择不同的完成。除此之外还能够将内存空间划分红多个区域，每个区域采取一种或者多种算法协调办理。这个思绪来自人们对运用顺序运转时的视察和剖析。按照钻研发现，大少数运用运转时候配的内存很快会被使用，而后就释放，这象征着为这样的对象划分一块内存空间，而后使用复制算法效力会很高，由于对象的生命周期很短，在GC履行时大少数对象都曾经死亡，只需求标志/复制大量的对象就能实现内存回收。古代渣滓回收完成中都会按照对象的生命周期划分将内存划分红多个代进行办理，最多见的是将内存划分为两个代：重生代和老生代，其中重生代次要用于运用顺序对象的调配，个别采取复制算法进行办理；老生代存储重生代履行GC后依然存活的对象，个别采取标志革除算法办理。
基于对象生命周期办理，有弱分代实践假定和强分代实践假定两种：
1）弱分代实践假定：假设对象调配内存后很快使用，而且使用后很快就再也不使用（内存能够释放）。
2）强分代实践假定：假设对象长时间存活后，将来此类对象还将长时间存活。
基于弱分代实践将内存办理划分红多个空间进行办理，基于强分代实践能够优化GC履行的效力，不回收辨认的长时间存活对象，从而放慢GC的履行效力。
值得一提的是，目前弱分代实践在初级言语中广泛失掉证明和认可，然而关于强分代实践只在一些场景中合用。目前弱分代实践和强分代实践在JVM中均有体现。
虽然分代回收的思想十分简略，但完成中有许多细节需求斟酌，例如在内存分代当前，分代界限是不是能够调剂？之内存划分为两个代为例，最简略的完成是界限固定，如图2-10所示。


图2-10 界限固定的分代划分
界限固定的分代回收算法完成简略，能够经过固定界限疾速判别对象处于哪一个空间，办理代际援用也对比简略。然而界限固定的分代办法需求JVM使用者提前设定好每个代的大小，这关于JVM使用者来讲其实不容易，实际使用中可能需求使用者不停调剂界限，以便内存代的划分和内存使用形式统一。
一种很天然的优化是将界限设计为浮动的，浮动能够解决使用者需求分代划分的问题，由JVM按照顺序使用内存的状况自动调剂内存代的划分。界限浮动的示用意如图2-十一所示。


图2-十一 界限浮动的分代划分
界限浮动后能够放大重生代也能够扩张重生代，个别来讲放大重生代会致使GC的进展时间增加、吞吐量增加，如图2-十二所示。而扩张重生代会致使GC的进展时间减少、吞吐量减少，如图2-13所示。


图2-十二 界限浮动之放大重生代


图2-13 界限浮动之扩张重生代
浮动界限对JVM使用者很敌对，然而回收算法的完成难度减少了得多。在JVM中一切的渣滓回收器完成中只要一款完成了界限浮动，但该功用由于存在一些bug，已在JDK 15中被移除，对于如何完成界限浮动将在前面具体引见。
除了代际界限划分的问题，在分代中还需求斟酌分代的大小、代际援用办理等问题。这些问题将在后续详细渣滓回收器的完成中引见。
本文给大家讲授的内容是Java虚构机和渣滓回收根底常识：GC算法概述
下篇文章给大家讲授的内容是JVM中渣滓回收相干的根本常识：GC的根感激大家的反对！