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

追蹤回收算法回收策略

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

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

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

原理

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

優(yōu)缺點

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

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

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

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

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

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

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

Appel式回收原理

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

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

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

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

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

原理

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

優(yōu)缺點

??優(yōu)點：
????1. 減少了內(nèi)存碎片化；
????1. 在對象大量存活的情況下五续，效率要高于復制算法洒敏；
??缺點：
????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)存時更加復雜，對于大量的碎片化空間就只能通過其他分配空間手段（比如：分區(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ù)到底應該解讀為引用類型還是其他數(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)

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

分代收集理論

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

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

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

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

• 跨代引用假說：跨代引用對比與同代引用來說僅占極少數(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)對應該數(shù)組里的一個bit或一個byte，例如

struct CardTable {  
  byte table[MAX_CARDTABLE_SIZE];  
};  

字節(jié)數(shù)組卡表的每一個元素都對應著其標識的內(nèi)存區(qū)域中一塊特定大小的內(nèi)存塊列林，這個內(nèi)存塊被稱作“卡頁”(Card Page)瑞你，一般來說卡頁大小都是以2的N次冪的字節(jié)數(shù)。一個卡頁的內(nèi)存中通常不止包含一個對象希痴，只要卡頁中有一個或者多個對象的字段存在著跨代指針者甲，那就將對應的卡表的數(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. 空間分配擔保

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