深入理解計算機系統-垃圾回收簡介

09-23

深入理解計算機系統-垃圾回收簡介

垃圾收集器

簡單的記錄下Mark & Sweep (標記&清除)演算法。2018.09.21

垃圾收集器的基本知識

垃圾收集器將內存視為一張可達圖(reachability graph)。該圖的節點被分成一組根節點(root node)和一組堆節點(heap node)。每個堆節點對應於堆中的一個已分配塊。有向邊(p->q)表示塊p中的某個指針指向塊q中的某個位置。根節點對應於這樣一種不在堆中的位置，它們包含指向堆中的指針。

垃圾收集器的角色就是維護可達圖的某種表示，並通過釋放不可達節點且將他們返回給空閑鏈表，來定期回收它們。

Java這類語言可以維護精確地可達圖的表示，因此垃圾回收可以回收所有垃圾；而C++和C這樣的語言的收集器通常不能維護精確的可達圖表示，叫做保守的垃圾收集器。

Mark & Sweep 垃圾收集器

Mark & Sweep 垃圾收集器由標記(mark)階段和清除(sweep)階段組成，標記階段標記處根節點的所有可達的和已分配的後繼。後繼是指根節點可達的節點指向的下一個已分配內存塊。而後面的清除階段釋放每個未被標記的已分配塊。塊頭部中空閑的低位中的一位通常用來表示這個塊是否被標記了。

每次對mark函數的調用都標記某個根節點的所有未標記並且可達的後繼節點。在標記階段的末尾，任何未標記的已分配塊都被認定為是不可達的，是垃圾，可以在清除階段回收。

清除階段基於sweep函數的調用實現，sweep函數在堆中每個塊上反覆循環，釋放它所遇到的所有未標記的已分配塊，也就是垃圾。

void mark(ptr p){ if ((b = isPtr(p)) == NULL) { return ; } if (blockMarked(b)) { return ; } markBlock(b); len = length(b); for(i = 0; i < len; i++) mark(b[i]); // 標記後繼節點 return ;}void sweep(ptr b, ptr end){ while(b < end) { if (blockMarked(b)) unmarkBlock(b); else if (blockAllocated(b)) free(b); b = nextBlock(b); } return ;}

C程序的保守Mark & Sweep

這裡主要說明一下為什麼C中的mark和sweep是保守的，也就是不能精確的維護一個可達圖的表示。

C語言的isPtr函數的實現是一個挑戰，原因如下：

C不會用任何類型信息來標記內存位置。因此，對isPtr沒有一種明顯的方式來判斷它的輸入p是不是一個指針。
即使我們知道p是一個指針，對isPtr也沒有明顯的方式來判斷ps是否指向一個已分配塊的有效載荷中的某個位置。

對最後一個問題的解決辦法是，將已分配塊集合維護成一顆平衡二叉樹，這棵樹保持著這樣一個屬性：左子樹都是較小地址的塊，右子樹都是較大地址的塊。isPtr函數用樹來執行對已分配塊的二分查找。在每一步中，它依賴於塊頭部中的大小欄位來判斷p是否落在這個塊的範圍之內。

C語言中的Mark & sweep收集器必須是保守的，其根本原因是C語言不會用類型信息來標記內存位置。因此，像int或float這樣的標量可以偽裝成指針。對收集器而言，由於缺少類型信息，因此不能推斷出這個數據實際上是int而不是指針。因此，分配器必須保守地將塊b標記為可達，儘管事實上它可能是不可達的。