垃圾收集原理依據(jù)及要點 [ 文末中獎名單 ]

分代收集理論

理論支撐：

• 弱分代假說(Weak Generational Hypothesis):絕大多數(shù)對象都是朝生夕滅的。

• 強分代假說(Strong Generational Hypothesis):熬過越多次垃圾收集過程的對象就越難以消亡。

• 跨代引用假說(Intergenerational Reference Hypothesis):跨代引用相對于同代引用來說僅占極少數(shù)。

跨代引用假說的具體解決辦法是：在新生代上建立一個全局的數(shù)據(jù)結(jié)構(gòu)(該結(jié)構(gòu)被稱為“記憶集”，Remembered Set)，這個結(jié)構(gòu)把老年代劃分成若干小塊，標(biāo)識出老年代的哪一塊內(nèi)存會存在跨代引用。此后當(dāng)發(fā)生Minor GC時，只有包含了跨代引用的小塊內(nèi)存里的對象才會被加入到GC Roots進(jìn)行掃描。

 

各類收集名稱

• 部分收集(Partial GC):指目標(biāo)不是完整收集整個Java堆的垃圾收集，其中又分為:

• 新生代收集(Minor GC/Young GC):指目標(biāo)只是新生代的垃圾收集。

• 老年代收集(Major GC/Old GC):指目標(biāo)只是老年代的垃圾收集。目前只有CMS收集器會有單獨收集老年代的行為。另外請注意“Major GC”這個說法現(xiàn)在有點混淆，在不同資料上常有不同所指，讀者需按上下文區(qū)分到底是指老年代的收集還是整堆收集。

• 混合收集(Mixed GC):指目標(biāo)是收集整個新生代以及部分老年代的垃圾收集。目前只有G1收集器會有這種行為。

• 整堆收集(Full GC):收集整個Java堆和方法區(qū)的垃圾收集。

 

標(biāo)記-清除算法

算法分為“標(biāo)記”和“清除”兩個階段:首先標(biāo)記出所有需要回收的對象，在標(biāo)記完成后，統(tǒng)一回收掉所有被標(biāo)記的對象。標(biāo)記過程就是對象是否屬于垃圾的判定過程。它是最基礎(chǔ)的收集算法，后續(xù)的收集算法大多都是以標(biāo)記-清除算法為基礎(chǔ)，對其缺點進(jìn)行改進(jìn)而得到的。

它的主要缺點有兩個：

• 第一個是執(zhí)行效率不穩(wěn)定，如果Java堆中包含大量對象，而且其中大部分是需要被回收的，這時必須進(jìn)行大量標(biāo)記和清除的動作，導(dǎo)致標(biāo)記和清除兩個過程的執(zhí)行效率都隨對象數(shù)量增長而降低;

• 第二個是內(nèi)存空間的碎片化問題，標(biāo)記、清除之后會產(chǎn)生大量不連續(xù)的內(nèi)存碎片，空間碎片太多可能會導(dǎo)致當(dāng)以后在程序運行過程中需要分配較大對象時無法找到足夠的連續(xù)內(nèi)存而不得不提前觸發(fā)另一次垃圾收集動作。

 

標(biāo)記-復(fù)制算法

為了解決標(biāo)記-清除算法面對大量可回收對象時執(zhí)行效率低的問題，它將可用內(nèi)存按容量劃分為大小相等的兩塊，每次只使用其中的一塊。當(dāng)這一塊的內(nèi)存用完了，就將還存活著的對象復(fù)制到另外一塊上面，然后再把已使用過的內(nèi)存空間一次清理掉。每次都是針對整個半?yún)^(qū)進(jìn)行內(nèi)存回收，分配內(nèi)存時也就不用考慮有空間碎片的復(fù)雜情況，只要移動堆頂指針，按順序分配即可。

這樣實現(xiàn)簡單，運行高效，但這種復(fù)制回收算法的代價是將可用內(nèi)存縮小為了原來的一半。

現(xiàn)在的商用Java虛擬機大多都優(yōu)先采用了這種收集算法去回收新生代。因為新生代中的對象有98%熬不過第一輪收集，所以，當(dāng)然實際實現(xiàn)并不是1：1的比例來劃分新生代內(nèi)存空間。而是使用“Appel式回收”，具體做法是把新生代分為一塊較大的Eden空間和兩塊較小的 Survivor空間，每次分配內(nèi)存只使用Eden和其中一塊Survivor。發(fā)生垃圾搜集時，將Eden和Survivor中仍然存活的對象一次性復(fù)制到另外一塊Survivor空間上，然后直接清理掉Eden和已用過的那塊Survivor空間。HotSpot虛擬機默認(rèn)Eden和Survivor的大小比例是8∶1，也即每次新生代中可用內(nèi)存空間為整個新生代容量的90%(Eden的80%加上一個Survivor的10%)，只有一個Survivor空間，即10%的新生代是會被“浪費”的。當(dāng)Survivor空間不足以容納一次Minor GC之后存活的對象時，就需要依賴其他內(nèi)存區(qū)域(實際上大多就是老年代)進(jìn)行分配擔(dān)保(Handle Promotion)，這些對象便將通過分配擔(dān)保機制直接進(jìn)入老年代。

 

標(biāo)記-整理算法

在對象存活率較高時就要進(jìn)行較多的復(fù)制操作，效率將會降低。更關(guān)鍵的是，如果不想浪費50%的空間，就需要有額外的空間進(jìn)行分配擔(dān)保，以應(yīng)對被使用的內(nèi)存中所有對象都100%存活的極端情況，所以在老年代一般不能直接選用標(biāo)記-復(fù)制算法。

針對老年代對象的存亡特征有另外一種有針對性的“標(biāo)記-整 理”(Mark-Compact)算法，其中的標(biāo)記過程仍然與“標(biāo)記-清除”算法一樣，但后續(xù)步驟不是直接對可回收對象進(jìn)行清理，而是讓所有存活的對象都向內(nèi)存空間一端移動，然后直接清理掉邊界以外的內(nèi)存。

如果移動存活對象，尤其是在老年代這種每次回收都有大量對象存活區(qū)域，移動存活對象并更新所有引用這些對象的地方將會是一種極為負(fù)重的操作，而且這種對象移動操作必須全程暫停用戶應(yīng)用程序才能進(jìn)行，這就更加讓使用者不得不小心翼翼地權(quán)衡其弊端了，像這樣的停頓被最初的虛擬機設(shè)計者形象地描述為“Stop The World”。

是否移動對象都存在弊端，移動則內(nèi)存回收時會更復(fù)雜，不移動則內(nèi)存分配時會更復(fù)雜。從垃圾收集的停頓時間來看，不移動對象停頓時間會更短，甚至可以不需要停頓，但是從整個程序的吞吐量來看，移動對象會更劃算。HotSpot虛擬機里面關(guān)注吞吐量的Parallel Scavenge收集器是基于標(biāo)記-整理算法的，而關(guān)注延遲的CMS收集器則是基于標(biāo)記-清除算法的。

CMS收集器也會在內(nèi)存空間的碎片化程度已經(jīng)大到影響對象分配時，采用標(biāo)記-整理算法收集一次，以獲得規(guī)整的內(nèi)存空間。

 

根節(jié)點枚舉

固定可作為GC Roots的節(jié)點主要在全局性的引用(例如常量或類靜態(tài)屬性)與執(zhí)行上下文(例如棧幀中的本地變量表)中，盡管目標(biāo)明確，但現(xiàn)在Java應(yīng)用越做越龐大，光是方法區(qū)的大小就常有數(shù)百上千兆，里面的類、常量等更是恒河沙數(shù)，查找過程要做到高效并非一件容易的事情。迄今為止，所有收集器在根節(jié)點枚舉這一步驟時都是必須暫停用戶線程的。必須在一個能保障一致性的快照中才得以進(jìn)行——這里“一致性”的意思是整個枚舉期間執(zhí)行子系統(tǒng)看起來就像被凍結(jié)在某個時間點上，不會出現(xiàn)分析過程中，根節(jié)點集合的對象引用關(guān)系還在不斷變化的情況，若這點不能滿足的話，分析結(jié)果準(zhǔn)確性也就無法保證。

主流Java虛擬機都是準(zhǔn)確式垃圾收集，所以并不需要一個不漏地檢查完所有執(zhí)行上下文和全局的引用位置。在HotSpot 的解決方案里，是使用一組稱為OopMap的數(shù)據(jù)結(jié)構(gòu)來達(dá)到這個目的。OopMap 記錄了棧上本地變量和寄存器到堆上對象的引用關(guān)系。其作用是：收集器只要掃描這些OopMap就可以直接得知這些GC Roots，并不需要真正一個不漏地從執(zhí)行上下文等GC Roots開始查找。

 

安全點

在OopMap的協(xié)助下，HotSpot可以快速準(zhǔn)確地完成GC Roots枚舉，但是，可能導(dǎo)致引用關(guān)系變化，或者說導(dǎo)致OopMap內(nèi)容變化的指令非常多，如果為每一條指令都生成對應(yīng)的OopMap，那將會需要大量的額外存儲空間。HotSpot只是在“特定的位置”記錄 了這些信息，這些位置被稱為安全點(Safep oint)。有了安全點的設(shè)定，也就決定了用戶程序執(zhí)行時 并非在代碼指令流的任意位置都能夠停頓下來開始垃圾收集，而是強制要求必須執(zhí)行到達(dá)安全點后才能夠暫停。

因此，安全點的選定既不能太少以至于讓收集器等待時間過長，也不能太過頻繁以至于過分增大運行時的內(nèi)存負(fù)荷。安全點位置的選取基本上是以“是否具有讓程序長時間執(zhí)行的特征”為標(biāo)準(zhǔn)進(jìn)行選定的，又因為每條指令執(zhí)行的時間都非常短暫，程序不太可能因為指令流長度太長這樣的原因而長時間執(zhí)行，所以“長時間執(zhí)行”的最明顯特征就是指令序列的復(fù)用，例如方法調(diào)用、循環(huán)跳轉(zhuǎn)、異常跳轉(zhuǎn)等都屬于指令序列復(fù)用，所以只有具有這些功能的指令才會產(chǎn)生安全點。（實際上還要加上所有創(chuàng)建對象和其他需要在Java堆上分配內(nèi)存的地方，這是為了檢查是否即將要發(fā)生垃圾收集，避免沒有足夠內(nèi)存分配新對象）

那如何在垃圾收集發(fā)生時，讓所有線程都跑到最近的安全點，然后停頓下來呢。有兩種方案可供選擇:搶先式中斷 (Preemptive Suspension)和主動式中斷(Voluntary Suspension)。

搶先式中斷不需要線程的執(zhí)行代碼主動去配合，在垃圾收集發(fā)生時，系統(tǒng)首先把所有用戶線程全部中斷，如果發(fā)現(xiàn)有用戶線程中斷的地方不在安全點上，就恢復(fù)這條線程執(zhí)行，讓它一會再重新中斷，直到跑到安全點上?，F(xiàn)在幾乎沒有虛擬機實現(xiàn)采用搶先式中斷來暫停線程響應(yīng)GC事件。

主動式中斷的思想是當(dāng)垃圾收集需要中斷線程的時候，不直接對線程操作，僅僅簡單地設(shè)置一個標(biāo)志位，各個線程執(zhí)行過程時會不停地主動去輪詢這個標(biāo)志，一旦發(fā)現(xiàn)中斷標(biāo)志為真時就自己在最近的安全點上主動中斷掛起。輪詢標(biāo)志的地方和安全點是重合的。

 

安全區(qū)域

安全點機制保證了程序執(zhí)行時，在不太長的時間內(nèi)就會遇到可進(jìn)入垃圾收集過程的安全點。但是如果程序不執(zhí)行，比如沒有分配處理器時間的情況，典型的場景便是用戶線程處于Sleep 狀態(tài)或者Blocked狀態(tài)，這時候線程無法響應(yīng)虛擬機的中斷請求，不能再走到安全點去中斷掛起自己，虛擬機也顯然不可能等待線程重新被激活分配處理器時間。對于這種情況，就必須引入安全區(qū)域(Safe Region)來解決。

安全區(qū)域是指能夠確保在某一段代碼片段之中，引用關(guān)系不會發(fā)生變化，因此，在這個區(qū)域中任意地方開始垃圾收集都是安全的。我們也可以把安全區(qū)域看作被擴展拉伸了的安全點。

當(dāng)用戶線程執(zhí)行到安全區(qū)域里面的代碼時，首先會標(biāo)識自己已經(jīng)進(jìn)入了安全區(qū)域，那樣當(dāng)這段時間里虛擬機要發(fā)起垃圾收集時就不必去管這些已聲明自己在安全區(qū)域內(nèi)的線程了。當(dāng)線程要離開安全區(qū)域時，它要檢查虛擬機是否已經(jīng)完成了根節(jié)點枚舉(或者垃圾收集過程中其他需要暫停用戶線程的階段)，如果完成了，那線程就當(dāng)作沒事發(fā)生過，繼續(xù)執(zhí)行;否則它就必須一直等待，直到收到可以離開安全區(qū)域的信號為止。

 

記憶集與卡表（卡表是記憶集的一種實現(xiàn)方式）

記憶集是一種用于記錄從非收集區(qū)域指向收集區(qū)域的指針集合的抽象數(shù)據(jù)結(jié)構(gòu)。

解決對象跨代引用所帶來的問題，垃圾收集器在新生代中建立了名為記憶集(Remembered Set)的數(shù)據(jù)結(jié)構(gòu)，用以避免把整個老年代加進(jìn)GC Roots掃描范圍。而在垃圾 收集的場景中，收集器只需要通過記憶集判斷出某一塊非收集區(qū)域是否存在有指向了收集區(qū)域的指針 就可以了，并不需要了解這些跨代指針的全部細(xì)節(jié)。那設(shè)計者在實現(xiàn)記憶集的時候，便可以選擇更為粗獷的記錄粒度來節(jié)省記憶集的存儲和維護(hù)成本。

一種稱為“卡表”(Card Table)的方式去實現(xiàn)記憶集，這也是目前最常用的一種記憶集實現(xiàn)形式，HotSpot虛擬機的卡表只是一個字節(jié)數(shù)組，字節(jié)數(shù)組CARD_TABLE的每一個元素都對應(yīng)著其標(biāo)識的內(nèi)存區(qū)域中一塊特定大小的內(nèi)存塊，這個內(nèi)存塊被稱作“卡頁”(Card Page)。一般來說，卡頁大小都是以2的N次冪的字節(jié)數(shù)，HotSpot中使用的卡頁是2的9次冪，即512字節(jié)。一個卡頁的內(nèi)存中通常包含不止一個對象，只要卡頁內(nèi)有一個(或更多)對象的字段存在著跨代指針，那就將對應(yīng)卡表的數(shù)組元素的值標(biāo)識為1，稱為這個元素變臟(Dirty)，沒有則標(biāo)識為0。在垃圾收集發(fā)生時，只要篩選出卡表中變臟的元素，就能輕易得出哪些卡頁內(nèi)存塊中包含跨代指針，把它們加入GC Roots中一并掃描。

 

寫屏障

卡表如何維護(hù)呢？如果是解釋執(zhí)行，虛擬機用充分的介入空間，但如果是編譯執(zhí)行呢？經(jīng)過即時編譯后的代碼已經(jīng)是純粹機器指令流了，所以必須在機器碼層面把卡表的維護(hù)動作放到每一次賦值操作中。

HotSpot通過寫屏障技術(shù)維護(hù)卡表狀態(tài)。寫屏障可以看作在虛擬機層面對“引用類型字段賦值”這個動作的AOP切面，在引用對象賦值時會產(chǎn)生一個環(huán)形(Around)通知，供程序執(zhí)行額外的動作，也就是說賦值的前后都在寫屏障的覆蓋范疇內(nèi)。在賦值前的部分的寫屏障叫作寫前屏障(Pre-Write Barrier)，在賦值后的則叫作寫后屏障(Post-Write Barrier)。

當(dāng)然額外的環(huán)形增強來維護(hù)卡表會有性能開銷，但相比掃描整個非收集代的代價相比還是低很多。

此外卡表維護(hù)還會面臨多線程并發(fā)的偽共享，為了減少偽共享帶來的性能損失，虛擬機會判斷只有卡表元素未臟的情況下才去更新此卡表元素?？梢酝ㄟ^UseCondCardMark參數(shù)開啟這一判斷，默認(rèn)是關(guān)閉的。

 

并發(fā)的可達(dá)性分析

當(dāng)前主流編程語言的垃圾收集器基本上都是依靠可達(dá)性分析算法來判定對象是否存活的，可達(dá)性分析算法理論上要求全過程都基于一個能保障一致性的快照中才能夠進(jìn)行分析， 這意味著必須全程凍結(jié)用戶線程的運行。

由于GC Roots相比起整個Java堆中全部的對象畢竟還算是極少數(shù)，且在各種優(yōu)化技巧(如OopMap)的加持下，它帶來的停頓已經(jīng)是非常短暫且相對固定(不隨堆容量而增長)的了?？蓮腉C Roots再繼續(xù)往下遍歷對象圖，這一步驟的停頓時間就必定會與Java堆容量直接成正比例關(guān)系了:堆越大，存儲的對象越多，對象圖結(jié)構(gòu)越復(fù)雜，要標(biāo)記更多對象而產(chǎn)生的停頓時間自然就更長。要知道包含“標(biāo)記”階段是所有追蹤式垃圾收集算法的共同特征，如果這個階段會隨著堆變大而等比例增加停頓時間，其影響就會波及幾乎所有的垃圾收集器。

那么為什么必須在一個能保障一致性的快照上才能進(jìn)行對象圖的遍歷?

利用三色標(biāo)記(Tri-color Marking)作為工具來輔助推導(dǎo)，把遍歷對象圖過程中遇到的對象，按照“是否訪問過”這個條件標(biāo)記成以下三種顏色:

• 白色:表示對象尚未被垃圾收集器訪問過。顯然在可達(dá)性分析剛剛開始的階段，所有的對象都是白色的，若在分析結(jié)束的階段，仍然是白色的對象，即代表不可達(dá)。

• 黑色:表示對象已經(jīng)被垃圾收集器訪問過，且這個對象的所有引用都已經(jīng)掃描過。黑色的對象代表已經(jīng)掃描過，它是安全存活的，如果有其他對象引用指向了黑色對象，無須重新掃描一遍。黑色對象不可能直接(不經(jīng)過灰色對象)指向某個白色對象。

• 灰色:表示對象已經(jīng)被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過。

如果用戶線程與收集器是并發(fā)工作呢?收集器在對象圖上標(biāo)記顏色，同時用戶線程在修改引用關(guān)系——即修改對象圖的結(jié)構(gòu)，這樣可能出現(xiàn)兩種后果。一種是把原本消亡的對象錯誤標(biāo)記為存活。另一種是把原本存活的對象錯誤標(biāo)記為已消亡，這就是非常致命的后果了，程序肯定會因此 發(fā)生錯誤。

理論上，當(dāng)且僅當(dāng)以下兩個條件同時滿足時，會產(chǎn)生“對象消失”的問 題，即原本應(yīng)該是黑色的對象被誤標(biāo)為白色:

• 賦值器插入了一條或多條從黑色對象到白色對象的新引用; 因為黑色對象的指向不會再次掃描，白色的就不會變黑。

• 賦值器刪除了全部從灰色對象到該白色對象的直接或間接引用。白色對象有可能又被黑色對象指向了，又變成前一種情況了。

所以只需破壞這兩個條件的任意一個即可。

由此分別產(chǎn)生了兩種解決方案:增量更新(Incremental Update)和原始快照(Snapshot At The Beginning， SAT B ) 。

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

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

以上無論是對引用關(guān)系記錄的插入還是刪除，虛擬機的記錄操作都是通過寫屏障實現(xiàn)的。

在 HotSpot虛擬機中，增量更新和原始快照這兩種解決方案都有實際應(yīng)用，譬如，CMS是基于增量更新 來做并發(fā)標(biāo)記的，G1、Shenandoah則是用原始快照來實現(xiàn)。

 

小結(jié)

垃圾收集為什么只能暫停在安全點上呢？

垃圾收集中判斷是否為垃圾對象，依據(jù)的是GC Roots可達(dá)性分析，而可達(dá)性分析的第一步就是要進(jìn)行GC Roots的枚舉，HotSpot利用OopMaps來高效實現(xiàn)GC Roots的枚舉（不需要掃描所有的虛擬機棧，只需要掃描OopMap就能得到GC Roots）。又因為運行中觸發(fā)變動OopMap指令非常多，如果每一條指令生成對應(yīng)的OopMap，就需要大量的額外空間，所以HotSpot只在“特定位置”記錄OopMap信息，而這些位置就是安全點。這也是為什么垃圾收集只能暫停在安全點上的原因，主要是為了保證OopMap記錄完全，以便進(jìn)行GC Roots的枚舉，才能繼續(xù)進(jìn)行后續(xù)的垃圾收集操作。

中獎人員名單

喜歡，在看