增量式垃圾回收
爲了控制最大暫停時間,經過逐漸推動垃圾回收即垃圾回收與mutator交替執行。html
三色標記算法
以標記-清除算法爲例使用三色標記算法。算法
利用下降吞吐量來縮短最大停頓時間。markdown
基礎
- 將GC中對象分紅三種顏色:
- 白色:還未搜索過
- 灰色:正在搜索
- 黑色:搜索完成
- 增量式的GC標記-清除算法分紅如下三個階段:
- 根查找階段
- 標記階段
- 清除階段
執行過程
- 根查找階段,直接將GC root直接引用的對象從白色塗爲灰色,並將其加到標記棧。
- 標記階段,每次標記必定數量對象,從標記棧中取出對象將其子對象塗成灰色,當標記階段要結束時再次將GC root的直接引用的對象加入到標記棧,再次標記。
- 清除階段,當標記棧爲空時,每次清除必定數量的白色對象,對此執行次步驟直到遍歷完整個堆。
寫入屏障
- 因爲標記階段是屢次完成的,所以可能產生「標記遺漏」即從黑色對象指向白色對象的指針。此時該白色的活躍對象會被認爲是垃圾。
- 經過寫入屏障解決,在修改指針時若是新引用的對象是白色的就將其標爲灰色(加入到標記棧)
分配
- 分配時檢查可用空間是否小於某個值,小於則開始進行GC(Mark-Sweep是內存不足才進行GC)。
- 分配時若是GC處於清除階段,且分配位置還未遍歷則須要給該對象標爲黑色。
Steele的算法
- 標記階段加入到標記棧時不設置標誌,而是在遍歷子對象時設置其標記標誌。
- 寫入屏障增長條件,標記過程當中發生引用的對象是黑色對象且新的引用的目標對象爲灰色或白色,則將發出引用的對象塗成灰色。
湯淺的算法
-原則:基於在GC開始時保留活動對象。post
- 標記階段不須要進行從新遍歷GC root,由於其在寫入屏障中若是GC處於標記階段則將對該對象加入標記棧。
- 分配時若是處於標記階段則將對象設爲黑色。
RC Immix算法
合併型引用計數法
- 引用計數法因爲頻繁修改計數器致使吞吐量不高。設計一種把注意力放在某一時期最初和最後狀態上,這期間不對計數器作修改,即合併型引用計數法。
- 引入更改緩衝區,指針的改動記錄到該緩衝區。
- 當指針發送改變時將指針發送改變的對象和其全部子對象註冊到更改緩衝區,經過寫入屏障實現。
- 對象增長dirty標誌,用於記錄該對象是否寫入了緩衝區。
- 當緩衝區滿了時進行GC,先對對象當前的引用的子對象進行增量,然後對更改緩衝區記錄的子對象進行減量,從而實現了對計數器的恢復。
- 優勢在於增長了吞吐量
- 缺點則是增長了最大停頓時間
合併型引用計數法和Immix的融合
- 回收以線爲對象,若是線內沒有一個活動對象則回收該線。
- 線也增長計數器,表示線內存活對象數。
- 全部沒經歷過GC的新對象均會記錄在更改緩衝區,在GC時只對新對象進行復制算法,實現被動的碎片整理。
- 積極的碎片整理,採用標記-壓縮算法,選擇一個塊進行。