保守
到精準
。contributed by JulianATA
從基礎的 Garbage Collector 中的 mark-and-sweep
演算法開始,再來探討保守 Conservative
垃圾回收的缺點。
延伸 mark-and-sweep
介紹效能相較優秀的 Tri-colored
演算法。了解 GO
語言中,GC的基礎運作機制。
介紹精準 Precise
垃圾回收的好處與限制,透過 文獻回顧
與簡介專案 magpie
了解精準垃圾回收在 C語言
實現上的難點。
最後,以 Java8 為基礎,了解 JVM 中進階的垃圾回收機制。
包含兩個階段 Mark
標記和 Sweep
掃除。
Mark
Phase從 root 開始,找尋 可到達
的物件。 ( Reachable Objects
)
標記 可到達
的物件。
Sweep
Phase從 heap 中,找尋未被標記的物件( Unreachable Objects
),即需要被清除的物件。
將未被標記的物件加入到 free list
中,準備清除。
將已被標記的物件重置為未被標記,以利下次的清掃。
Mark
todo
將所有 root 中的物件加入。todo
中有物件時,執行以下3~4。todo
中選任一物件 v
,將其除外於 todo
。v
未被標記,標記 v
,將所有 v
包含的物件放到 todo
中。Sweep
p
從 heap
的最底層物件開始。p
還不是 top
的時候,執行以下3~5。p
已被標記,則將其改為未標記。p
的記憶體區塊加到 free list
中,準備清除。p
改為在 heap 中上一層的物件。 ( using p <- p + sizeof(p)
)1
解決方法
pointer reversal
,用 depth first search
取代訪問清單。2
解決方法
parent
位置,就可以不用 pointer reversal
也能執行 depth firsth search
。Reference: Golang realtime garbage collector
上述的基礎 mark and sweep
演算法有一個缺點。每次在執行 mark
的時候,都需要將 process 暫停。
舉例: 以下 process 有物件 obj0, obj1, obj2, obj3
時間t0:執行 mark
將 reachable
物件標記。
時間t1:因為沒有暫停 process,出現 obj4 指向 obj3
時間t2: 執行 sweep
,刪除物件 obj3, obj4 產生錯誤。
因此,為了讓 mark and sweep
過程可以不暫停 process, 延伸出了Tri-colored
演算法
Paper Review: Precise Garbage Collection for C
Precise
GC vs.Conservative
GC在 C 或 C++ 的實作中,pointer
的使用沒有硬性規定,因為可能會有 unreachable
的物件被標為 reachable
,原因可能為 type imprecision 或是 liveness imprecision 等等。
非指標
之資料型別作為指標尋找物件。以下為實作 type imprecision 情況的程式 Based on ogc .
#include <assert.h>
#include "gc.h"
void ImPrecise(long *l)
{
int* Unreachable;
Unreachable = gc_alloc(sizeof(int));
assert(Unreachable);
*l = (long)Unreachable;
}
int main(int argc, char *argv[])
{
gc_init(&argc, 1);
long *l;
l = gc_alloc(sizeof(long));
assert(l);
ImPrecise(l);
gc_run();
gc_dump_internals();
gc_destroy();
return 0;
}
預計輸出
## GC internals ##
- GC.ptr_map[20]:
{ ptr: 0x7ffc624006a0, size: 8, marked: 0 }
實際輸出
## GC internals ##
- GC.ptr_map[20]:
{ ptr: 0x7fceecc006a0, size: 8, marked: 0 }
- GC.ptr_map[58]:
{ ptr: 0x7fceecc02bd0, size: 4, marked: 0 }
可以看到 reachable
的物件,應該只有 type 為 long
的 l
。
但是 l
中儲存的值 剛好
等於為一個 unreachable
物件的地址。
因此,GC 便保守地將其標為 reachable
。
In our experience, however, conservative GC works
poorly for long-running programs, such as a web server, a programming environment, or an operating system kernel.
Conservative GC
在小型的程式中有不錯的效果。但在長期執行的 long-running
程式中,因為沒有持續的記憶體維護對於記憶體管理會造成很大的負擔。
論文中提到對於 PLT Scheme ( 現名為Racket ) 的實驗。
另外,在 Kernel 中,在使用 linked list 來管理執行緒 thread
的情況下,可能會造成 unbounded memory 的問題。
其中,很多問題的原因並不只是因為 type imprecision
,而是因為 liveness imprecision
。
固然,使用 Precise GC 可以回收更多記憶體,在使用上卻有許多限制。
例1:宣告的型別需要跟 run-time 的行為一樣,至少在「指標與非指標」變數之間,不能混用。
我們常使用 void* 作為 generic pointer type,也會造成他所指向的資料有模糊的狀況。
例2:處理 Union 的使用,也容易造成型態的混用。
因此,讓C語言程式適應 Precise GC 的行為,是一大挑戰。
For GC to work, all live objects must be reachable via pointer
chains starting from roots, which include static and local variables with pointer types.
為了讓 GC 可以如期執行,所有活著
的物件都必須是從 root
藉由指標可達的。
為了讓 precise
GC 能精準的控制資源,所有非指標類的都確保不會被當作 GC-allocated
物件的指標。
Cprogramming