Try   HackMD

Garbage Collection 垃圾回收機制,從保守精準

contributed by JulianATA

從基礎的 Garbage Collector 中的 mark-and-sweep 演算法開始,再來探討保守 Conservative 垃圾回收的缺點。

延伸 mark-and-sweep 介紹效能相較優秀的 Tri-colored演算法。了解 GO 語言中,GC的基礎運作機制。

介紹精準 Precise 垃圾回收的好處與限制,透過 文獻回顧 與簡介專案 magpie 了解精準垃圾回收在 C語言 實現上的難點。

最後,以 Java8 為基礎,了解 JVM 中進階的垃圾回收機制。

mark-and-sweep 演算法

Naive 運作機制:

包含兩個階段 Mark 標記和 Sweep 掃除。

Mark Phase

從 root 開始,找尋 可到達 的物件。 ( Reachable Objects )
標記 可到達 的物件。

Sweep Phase

從 heap 中,找尋未被標記的物件( Unreachable Objects ),即需要被清除的物件。
將未被標記的物件加入到 free list 中,準備清除。
將已被標記的物件重置為未被標記,以利下次的清掃。

如何實作

簡單實作 Mark

  1. 建立訪問清單 todo 將所有 root 中的物件加入。
  2. todo 中有物件時,執行以下3~4。
  3. todo 中選任一物件 v ,將其除外於 todo
  4. 如果 v 未被標記,標記 v ,將所有 v 包含的物件放到 todo 中。

簡單實作 Sweep

  1. 物件 pheap 的最底層物件開始。
  2. p 還不是 top 的時候,執行以下3~5。
  3. 如果 p 已被標記,則將其改為未標記。
  4. 反之,將 p 的記憶體區塊加到 free list 中,準備清除。
  5. p 改為在 heap 中上一層的物件。 ( using p <- p + sizeof(p) )

問題點 1

  • 需要清除時,通常表示沒有記憶體空間。
  • 但是, Mark 階段需要記憶體空間去創造訪問清單 。
  • 訪問清單無法預測大小,因此無法預先保留。

解決方法

  • 應用 pointer reversal ,用 depth first search 取代訪問清單。

問題點 2

  • 有些物件沒有指標的空間。

解決方法

  • 使用一個暫存器記憶其 parent 位置,就可以不用 pointer reversal 也能執行 depth firsth search

Tri-Color 演算法與 Golang

上述的基礎 mark and sweep 演算法有一個缺點。每次在執行 mark 的時候,都需要將 process 暫停。

  • 在標記的時候,需要讓所有 object 維持不變,才能保持不出錯。

  • 舉例: 以下 process 有物件 obj0, obj1, obj2, obj3

  • 時間t0:執行 markreachable 物件標記。

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

  • 時間t1:因為沒有暫停 process,出現 obj4 指向 obj3

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

  • 時間t2: 執行 sweep,刪除物件 obj3, obj4 產生錯誤。

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

因此,為了讓 mark and sweep 過程可以不暫停 process, 延伸出了Tri-colored演算法

Tri-colored 演算法

  • 使用 Breadth-first 的策略。
  • 將物件用三種顏色來標記:
    • 白色:未標記,在 sweep 的階段被清掃
    • 灰色:已標記,目前 Breadth-first 的進行前緣。
    • 黑色:已標記。
  • 將新增物件,標記為灰色。

Precise Garbage Collector

Precise GC vs.Conservative GC

「保守」 Conservative

在 C 或 C++ 的實作中,pointer 的使用沒有硬性規定,因為可能會有 unreachable 的物件被標為 reachable ,原因可能為 type imprecision 或是 liveness imprecision 等等。

  • type 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 為 longl
但是 l 中儲存的值 剛好 等於為一個 unreachable 物件的地址。
因此,GC 便保守地將其標為 reachable

保守 GC 的缺點

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 程式中,因為沒有持續的記憶體維護對於記憶體管理會造成很大的負擔。

PTL Scheme 看 GC

論文中提到對於 PLT Scheme ( 現名為Racket ) 的實驗。

  • PLT Scheme在當時使用的正是 Conservative GC,每天都會讓記憶體消耗殆盡,導致重新啟動。就算是學生寫的簡單程式,也需要在運行幾小時候重新啟動。
  • 替換為 precise GC 後解決了這個問題。每次 Conservative GC 大概回收40MB,反之 Precise GC 可以回收100MB。

另外,在 Kernel 中,在使用 linked list 來管理執行緒 thread 的情況下,可能會造成 unbounded memory 的問題。

其中,很多問題的原因並不只是因為 type imprecision ,而是因為 liveness imprecision

C 語言使用 Precise GC 的限制:

固然,使用 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 物件的指標。

magpie

garbage collection in Java

tags: Cprogramming