??學(xué)習(xí)JVM的垃圾回收，離不開的是追蹤式垃圾回收算法，現(xiàn)有的主流Java虛擬機都采用的是追蹤式回收算法。對比于引用計數(shù)式垃圾收集，追蹤式垃圾回收算法都是采用的間接式的回收策略，也就是這種策略并非直接尋找垃圾本身，而是先尋找哪些對象存活，然后反過來判斷其余所有的對象為垃圾對象。追蹤式回收算法本身包括標記-清除(Mark-Sweep)、標記-復(fù)制(Mark-Copy)、標記-整理(Mark-Compact)這三種回收策略，在真正的回收器上，一定是根據(jù)對象的不同情況進行分區(qū)或者分代，針對不同的區(qū)域采取不同的回收策略，針對這些情況，有許多的相關(guān)基礎(chǔ)概念展現(xiàn)出來。

追蹤回收算法回收策略

追蹤式回收算法本身包括標記-清除(Mark-Sweep)、標記-復(fù)制(Mark-Copy)、標記-整理(Mark-Compact)這三種回收策略，這三種策略都有一個共通之處，那就是標記(Mark)，關(guān)于這個標記的過程在上一篇文章(JVM學(xué)習(xí)-GC之判斷對象存活)有講過，就是里面的可達性分析算法，本篇文章將不再做多余概述。

標記-清除(Mark-Sweep)算法

標記-清除(Mark-Sweep)算法是一種典型的非移動式回收算法，是所有追蹤式回收算法的基礎(chǔ)，其他的算法都是針對標記-清除(Mark-Sweep)算法的缺點改進而來。

原理

??在標記過程完成之后，將未標記的對象進行回收。

優(yōu)缺點

??優(yōu)點：
????1. 標記-清除(Mark-Sweep)算法的吞吐量（吞吐量就是處理器用于運行用戶代碼的時間與處理器總消耗時間的比值，吞吐量 = 運行用戶代碼時間 / (運行用戶代碼時間 + 運行垃圾收集時間)）較高；
????2. 標記-清除(Mark-Sweep)算法對空間的利用率比較高，既不需要像標記-復(fù)制(Mark-Copy)算法劃出多余的空間來進行復(fù)制對象，也不需要像引用計數(shù)算法為每個對象設(shè)置引用計數(shù)器；
??缺點：
????1. 標記-清除(Mark-Sweep)算法的執(zhí)行效率不太穩(wěn)定；
????2. 標記-清除(Mark-Sweep)算法在清除的過程中會產(chǎn)生大量的碎片化空間，空間的碎片化太多，會導(dǎo)致程序在運行時分配對象的時候，無法找到足夠大的連續(xù)空間，導(dǎo)致提前進行另一次垃圾收集；

標記-復(fù)制(Mark-Copy)算法

標記-復(fù)制(Mark-Copy)算法簡稱為復(fù)制算法，為了解決標記-清除(Mark-Sweep)算法面對大量可回收對象時，執(zhí)行效率低的問題。

半?yún)^(qū)復(fù)制原理

??基本的復(fù)制回收器會將堆劃分稱為兩個大小相等的半?yún)^(qū)，分別是來源空間和目標空間。每次在程序運行時，只用其中的來源空間來進行對象的內(nèi)存分配，當來源空間的內(nèi)存不足時，進行垃圾回收，交換兩個半?yún)^(qū)的角色，然后將存活的對象移到另一個半?yún)^(qū)的一端，最后將垃圾回收的半?yún)^(qū)內(nèi)存清零。

半?yún)^(qū)復(fù)制優(yōu)缺點

??優(yōu)點：
????1. 半?yún)^(qū)復(fù)制提升了垃圾回收的效率；
????2. 半?yún)^(qū)復(fù)制減少了碎片化空間的誕生；
??缺點：
????1. 半?yún)^(qū)復(fù)制將原來的可用內(nèi)存減少了一半；

Appel式回收原理

??Appel式回收是針對標準ML提出的一種自適應(yīng)分代策略，在ML語言中，一次回收完成通常只有不到2%的對象能夠存活，Appel式回收正式針對這一種情況而設(shè)計的策略。Appel式回收策略將空間分為三個：老年代、復(fù)制保留區(qū)、新生代，在HotSpot虛擬機中的實現(xiàn)中新生代收集器將新生代變成Eden空間，將復(fù)制保留區(qū)變成兩塊較小的Survivor空間，在程序運行中每次分配內(nèi)存只使用Eden和其中一塊Survivor空間，在發(fā)生垃圾收集時，將存活的對象復(fù)制到保留的那一塊Survivor上，另外兩塊空間直接清零（在HotSpot虛擬機中Eden和Survivor的比例為8:1）。
??當Survivor空間不足以容納一次Minor GC之后，就需要依賴其他內(nèi)存區(qū)域（大部分時候是老年代）進行分配擔(dān)保，這些沒有足夠空間存放的對象直接進入其他區(qū)域。

Appel式回收優(yōu)缺點

??優(yōu)點：
????1. Appel式回收可以為復(fù)制保留區(qū)的大小進行動態(tài)調(diào)節(jié)；
??缺點：
????1. 必須要有其他空間進行空間擔(dān)保；

標記-整理(Mark-Compact)算法

??在標記-清除(Mark-Sweep)算法這種非移動式回收算法中最大的問題就是會產(chǎn)生碎片化的空間，而標記-整理(Mark-Compact)算法正是為了降低內(nèi)存碎片化提出來的解決策略。

原理

??在標記之后，把所有標記的對象都移到內(nèi)存空間的一端，然后直接把邊界之外的內(nèi)存清零。

優(yōu)缺點

??優(yōu)點：
????1. 減少了內(nèi)存碎片化；
????1. 在對象大量存活的情況下，效率要高于復(fù)制算法；
??缺點：
????1. 整理(Compact)過程繁瑣，在大多數(shù)算法下需要多次遍歷內(nèi)存，STW(Stop The World)時間比清理(Sweep)時間長；

關(guān)于標記-整理(Mark-Compact)算法吞吐量的個人理解：在算法上標記-整理(Mark-Compact)算法一般需要多次遍歷堆的過程，所以標記-整理(Mark-Compact)算法上的吞吐量是不如標記-清除(Mark-Sweep)算法的吞吐量的，但是對于整個系統(tǒng)來說標記-清除(Mark-Sweep)算法是屬于不移動回收算法，不移動回收算法有一個明顯的缺點就是在分配內(nèi)存時更加復(fù)雜，對于大量的碎片化空間就只能通過其他分配空間手段（比如：分區(qū)空閑分配鏈表）來解決，而分配內(nèi)存是程序運行過程中最頻繁的操作，所以在系統(tǒng)的吞吐量上標記-整理(Mark-Compact)算法上的吞吐量是優(yōu)于標記-清除(Mark-Sweep)算法的吞吐量的。

三色算法

在標記過程中，三色算法是所有賦值器和回收器遵守的不變式。

三色算法原理

??在遍歷對象圖的過程中，回收器把是否訪問過的對象根據(jù)“是否訪問過”來把所有對象標記成三種顏色。

• 白色：對象尚未被回收器訪問到，在回收周期的開始階段，所有的對象都是白色，在回收周期結(jié)束的時候，所有白色對象都是不可達對象。
• 灰色：表示對象已經(jīng)被回收器掃描過，但是對象上還有一個或者多個引用沒有進行掃描。
• 黑色：對象已經(jīng)被回收器掃描過，并且所有的引用已經(jīng)被掃描。黑色對象永遠不可能直接指向白色對象，也永遠不會被回收器再次掃描，除非顏色變化。

??回收器從白色根節(jié)點出發(fā)，逐步把對象圖的對象變成灰色再到黑色，當全部遍歷完成后所有可達的節(jié)點變成黑色，不可達的節(jié)點依舊是白色。

對象丟失問題

??當在同時產(chǎn)生下面兩個條件時，會產(chǎn)生對象丟失問題

• 賦值器插入了一條或者多條從黑色對象到白色對象的新引用；
• 賦值器刪除了全部從灰色對象到該白色對象的直接或者間接引用。

弱三色不變式和強三色不變式

弱三色不變式和強三色不變式是為了解決對象丟失的。

• 弱三色不變式：所有被黑色引用的白色對象都會被灰色保護（灰色保護：白色對象直接或間接被灰色對象引用）。弱三色不變式打破了對象丟失條件的條件二。
• 強三色不變式：不存在黑色對象指向白色對象的指針。強三色不變式打破了對象丟失條件的條件一。

并發(fā)時三色問題的解決方案

增量更新

??增量更新要破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關(guān)系的時候，就將這個新插入的引用記錄下來，等并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關(guān)系中的黑色對象為根，重新掃描一次。

原始快照(SATB)

??原始快照(SATB)要破壞第二個條件，當灰色對象要刪除指向白色對象的引用關(guān)系的時候，就要將這個要刪除的引用記錄下來，在并發(fā)掃描結(jié)束之后，再將這些引用記錄過的引用關(guān)系中的灰色對象為根，重新掃描一次。

GC的實現(xiàn)方式

在追蹤式垃圾收集算法里面最先開始的就是用可達性分析算法標記(Mark)對象，在可達性分析算法里面第一步就是確定根節(jié)點集合(Root Set)，而如何確定根節(jié)點集合(Root Set)，就影響了GC的實現(xiàn)方式。

保守式GC

??如果JVM選擇不記錄內(nèi)存中每個數(shù)據(jù)的類型，那么JVM就無法區(qū)分內(nèi)存里某個位置上的數(shù)據(jù)到底應(yīng)該解讀為引用類型還是其他數(shù)據(jù)類型。這種條件下，實現(xiàn)出來的GC就會是“保守式GC(Conservative GC)”。在進行GC的時候，JVM開始從一些已知位置（例如說JVM棧）開始掃描內(nèi)存，掃描的時候每看到一個數(shù)字就看看它“像不像是一個指向GC堆中的指針”，判斷的方式類似于上下邊界的檢查，對其檢查等。

半保守式GC

??JVM可以選擇在棧上不記錄類型信息，而在對象上記錄類型信息。這樣的話，掃描棧的時候仍然會和保守式GC(Conservative GC)的過程一樣，但掃描到GC堆內(nèi)的對象時因為對象帶有足夠類型信息了，JVM就能夠準確判斷出在該對象內(nèi)什么位置的數(shù)據(jù)是引用類型了。這種是“半保守式GC”，也稱為“根上保守(ConserVative With Respect To The Roots)”。

準確式GC

??“準確式GC”所謂的準確，關(guān)鍵就是“類型”，也就是說給定某個位置上的某塊數(shù)據(jù)，要能知道它的準確類型是什么，這樣才可以合理地解讀數(shù)據(jù)的含義；GC所關(guān)心的含義就是“這塊數(shù)據(jù)是不是指針”，這塊數(shù)據(jù)不僅僅是GC堆內(nèi)對象上的數(shù)據(jù)，包括活動記錄（棧+寄存器）里的數(shù)據(jù)。

分代收集理論相關(guān)

追蹤式垃圾收集算法在少量垃圾回收的時候效率非常高效，特別是復(fù)制回收算法。但是長壽對象的存在會影響到回收回收的效率，這個時候就通過分區(qū)，使長壽的數(shù)據(jù)都堆積在一邊，這樣對年輕的數(shù)據(jù)使用復(fù)制回收算法就可以大大提升效率。在真實的商用垃圾回收大部分都采用了分代理論，哪怕G1回收器作為全區(qū)域回收器，在區(qū)域里面依舊用到了分代概念。

分代收集理論

分代收集理論建立在兩個分代假說之上：

• 弱分代假說：大多數(shù)對象都是朝生夕滅的。這個假說已經(jīng)在不同的編程語言和編程范式中得到證實；
• 強分代假說：越長壽的對象越不容易死亡。這個假說證據(jù)稍顯不足，但是卻依舊給大對象回收處理有一定的意義。

??這兩個假說共同奠定了多款常用的垃圾收集器的一致設(shè)計原則：收集器應(yīng)該將堆劃分出不同區(qū)域，然后將回收對象依據(jù)年齡分配到不同的區(qū)域之中。

??除此之外新生代對象完全可以由老年代對象引用，如果產(chǎn)生這種引用，就需要遍歷整個老年代來確定可達性分析的準確性，這樣對內(nèi)存回收帶來極大的性能負擔(dān)，所以引出了另一條假說

• 跨代引用假說：跨代引用對比與同代引用來說僅占極少數(shù)。

記憶集(Remembered Set)和卡表(Card Table)

??對于跨代引用來說，目前解決的方式就是記憶集和卡表。記憶集(Remembered Set)是一種抽象概念，而卡表(Card Table)可以是記憶集(Remembered Set)的一種實現(xiàn)方式。
??記憶集(Remembered Set)是在實現(xiàn)部分垃圾收集(partial GC)時用于記錄從非收集部分指向收集部分的指針的集合的抽象數(shù)據(jù)結(jié)構(gòu)。
??1. 記錄精度（其實無論是remembered set還是card table，記錄精度都有很大的選擇余地）：

• 字粒度：每個記錄精確到一個機器字(Word)。該字包含有跨代指針。
• 對象粒度：每個記錄精確到一個對象。該對象里有字段含有跨代指針。
• 卡(card)粒度：每個記錄精確到一大塊內(nèi)存區(qū)域。該區(qū)域內(nèi)有對象含有跨代指針。

??(還有許多類型的顆粒度，可以自己想象)

??2. 數(shù)據(jù)結(jié)構(gòu)
??記憶集(Remembered Set)：使用指針（對象指針或者字指針）的數(shù)據(jù)來實現(xiàn)，例如

struct RememberedSet {  
  Object* data[MAX_REMEMBEREDSET_SIZE];  
}; 

卡表(Card Table)：使用字節(jié)數(shù)組來實現(xiàn)卡(card)的記錄，每個卡(card)對應(yīng)該數(shù)組里的一個bit或一個byte，例如

struct CardTable {  
  byte table[MAX_CARDTABLE_SIZE];  
};  

字節(jié)數(shù)組卡表的每一個元素都對應(yīng)著其標識的內(nèi)存區(qū)域中一塊特定大小的內(nèi)存塊，這個內(nèi)存塊被稱作“卡頁”(Card Page)，一般來說卡頁大小都是以2的N次冪的字節(jié)數(shù)。一個卡頁的內(nèi)存中通常不止包含一個對象，只要卡頁中有一個或者多個對象的字段存在著跨代指針，那就將對應(yīng)的卡表的數(shù)組元素的標識變成1，稱為這個元素變臟，沒有則標識為0。在垃圾收集過程中只要篩選出來變臟的元素，把變臟的元素加入根節(jié)點集合(Root Set)一并掃描。

對象的年齡

在JVM的HotSpot虛擬機中，對象的年齡放置在對象頭中，每當對象經(jīng)歷熬過一次回收，年齡加一，最大15。
對象分配規(guī)則和晉升老年代規(guī)則：

1. 對象優(yōu)先在Eden分配
2. 大對象直接進入老年代
3. 長期存活對象進入老年代
4. 動態(tài)對象年齡判斷（虛擬機并不是總是要求對象年齡需要達到規(guī)定的晉升年齡(MaxTenuringThreshold)才能晉升到老年代的，如果在Survivor空間中相同年齡所有對象大小的總和大于Survivor空間的一半，年齡大于或等于該年齡的對象就可以直接進入老年代，無須等到MaxTenuringThreshold中要求的年齡）
5. 空間分配擔(dān)保

本文采用《深入理解Java虛擬機》和《The Garbage Collection Handbook》以及RednaxelaFX大佬的文章進行參考以及學(xué)習(xí)