《深入理解計算機(jī)系統(tǒng)》P606
9.10.1 垃圾收集器的基本知識
? ? ? 垃圾收集器將內(nèi)存視為一張有向可達(dá)圖( reachability graph ),其形式如圖9-49所示。該圖的節(jié)點被分成一組根節(jié)點( root node )和一組堆節(jié)點( heap node )。每個堆節(jié)點對應(yīng)于堆中的一個已分配塊。有向邊p → q意味著塊p中的某個位置指向塊 q 中的某個位置。根節(jié)點對應(yīng)于這樣一種不在堆中的位置,它們中包含指向堆中的指針。這些位置可以是寄存器、棧里的變量,或者是虛擬內(nèi)存中讀寫數(shù)據(jù)區(qū)域內(nèi)的全局變量。
? ? ? 當(dāng)存在一條從任意根節(jié)點出發(fā)并到達(dá)p的有向路徑時,我們說節(jié)點p是可達(dá)的( reachable )。在任何時刻,不可達(dá)節(jié)點對應(yīng)于垃圾,是不能被應(yīng)用再次使用的。垃圾收集器的角色是維護(hù)可達(dá)圖的某種表示,并通過釋放不可達(dá)節(jié)點且將它們返回給空閑鏈表,來定期地回收它們。
? ? ? 像 ML 和 Java 這樣的語言的垃圾收集器,對應(yīng)用如何創(chuàng)建和使用指針有很嚴(yán)格的控制,能夠維護(hù)可達(dá)圖的一種精確的表示,因此也就能夠回收所有垃圾。然而,諸如C和C ++這樣的語言的收集器通常不能維持可達(dá)圖的精確表示。這樣的收集器也叫做保守的垃圾收集器( conservative garbage collector )。從某種意義上來說它們是保守的,即每個可達(dá)塊都被正確地標(biāo)記為可達(dá)了,而一些不可達(dá)節(jié)點卻可能被錯誤地標(biāo)記為可達(dá)。
收集器可以按需提供它們的服務(wù),或者它們可以作為一個和應(yīng)用并行的獨立線程,不斷地更新可達(dá)圖和回收垃圾。例如,考慮如何將一個 C 程序的保守的收集器加入到已存在的 malloc 包中,如圖9-50所示。
? ? ? 無論何時需要堆空間時,應(yīng)用都會用通常的方式調(diào)用malloc。如果 malloc 找不到一個合適的空閑塊,那么它就調(diào)用垃圾收集器,希望能夠回收一些垃圾到空閑鏈表。收集器識別出垃圾塊,并通過調(diào)用 free 函數(shù)將它們返回給堆。關(guān)鍵的思想是收集器代替應(yīng)用去調(diào)用 free。當(dāng)對收集器的調(diào)用返回時, malloc 重試,試圖發(fā)現(xiàn)一個合適的空閑塊。如果還是失敗了,那么它就會向操作系統(tǒng)要求額外的內(nèi)存。最后, malloc 返回一個指向請求塊的指針(如果成功)或者返回一個空指針(如果不成功)。
9.10.2 Mark & Sweep 垃圾收集器
? ? ? Mark & Sweep 垃圾收集器由標(biāo)記( mark )階段和清除( sweep )階段組成,標(biāo)記階段標(biāo)記出根節(jié)點的所有可達(dá)的和已分配的后繼,而后面的清除階段釋放每個未被標(biāo)記的已分配塊。塊頭部中空閑的低位中的一位通常用來表示這個塊是否被標(biāo)記了。
? ? ? 我們對 Mark & Sweep 的描述將假設(shè)使用下列函數(shù),其中 ptr 定義為 typedef void *ptr:
? ? ? -- ptr isPtr(ptr p)。如果 p 指向一個已分配塊中的某個字,那么就返回一個指向這個塊的起始位置的指針 b。否則返回 NULL。
? ? ? --?int blockMarked(ptr b)。如果塊 b 是已標(biāo)記的,那么就返回 true。
? ? ? --?int blockAllocated(ptr b)。如果塊 b 是已分配的,那么就返回 true。
? ? ? --?void markBlock(ptr b)。標(biāo)記塊 b。
? ? ? --?int length ( b )。返回塊 b 的以字為單位的長度(不包括頭部)。
? ? ? --?void unmarkBlock(ptr b)。將塊 b 的狀態(tài)由已標(biāo)記的改為未標(biāo)記的。
? ? ? --?ptr nextBlock(ptr b)。返回堆中塊 b 的后繼。
? ? ? 標(biāo)記階段為每個根節(jié)點調(diào)用一次圖9-51a所示的 mark 函數(shù)。如果 p 不指向一個已分配并且未標(biāo)記的堆塊, mark 函數(shù)就立即返回。否則,它就標(biāo)記這個塊,并對塊中的每個字遞歸地調(diào)用它自己。每次對 mark 函數(shù)的調(diào)用都標(biāo)記某個根節(jié)點的所有未標(biāo)記并且可達(dá)的后繼節(jié)點。在標(biāo)記階段的末尾,任何未標(biāo)記的已分配塊都被認(rèn)定為是不可達(dá)的,是垃圾,可以在清除階段回收。
? ? ? 清除階段是對圖9-51b所示的 sweep 函數(shù)的一次調(diào)用。 Sweep 函數(shù)在堆中每個塊上反復(fù)循環(huán),釋放它所遇到的所有未標(biāo)記的已分配塊(也就是垃圾)。
圖9-52 展示了一個小堆的 Mark & Sweep 的圖形化解釋。塊邊界用粗線條表示。每個方塊對應(yīng)于內(nèi)存中的一個字。每個塊有一個字的頭部,要么是已標(biāo)記的,要么是未標(biāo)記的。
? ? ? 初始情況下,圖9-52中的堆由六個已分配塊組成,其中每個塊都是未分配的。第3塊包含一個指向第1塊的指針。第4塊包含指向第3塊和第6塊的指針。根指向第4塊。在標(biāo)記階段之后,第1塊、第3塊、第4塊和第6塊被做了標(biāo)記,因為它們是從根節(jié)點可達(dá)的。第2塊和第5塊是未標(biāo)記的,因為它們是不可達(dá)的。在清除階段之后,這兩個不可達(dá)塊被回收到空閑鏈表。
9.10.3 C程序的保守 Mark & Sweep
? ? ? Mark & Sweep 對 C 程序的垃圾收集是一種合適的方法,因為它可以就地工作,而不需要移動任何塊。然而, C 語言為 isPtr 函數(shù)的實現(xiàn)造成了一些有趣的挑戰(zhàn)。
? ? ? 第一, C 不會用任何類型信息來標(biāo)記內(nèi)存位置。因此,對 isPtr 沒有一種明顯的方式來判斷它的輸人參數(shù) p 是不是一個指針。第二,即使我們知道 p 是一個指針,對 isPtr 也沒有明顯的方式來判斷 p 是否指向一個已分配塊的有效載荷中的某個位置。
? ? ? 對后一問題的解決方法是將已分配塊集合維護(hù)成一棵平衡二叉樹,這棵樹保持著這樣一個屬性:左子樹中的所有塊都放在較小的地址處,而右子樹中的所有塊都放在較大的地址處。如圖9-53所示,這就要求每個已分配塊的頭部里有兩個附加字段(1eft和 right )。每個字段指向某個已分配塊的頭部。 isPtr(ptr p)函數(shù)用樹來執(zhí)行對已分配塊的二分查找。在每一步中,它依賴于塊頭部中的大小字段來判斷 p 是否落在這個塊的范圍之內(nèi)。
? ? ? 平衡樹方法保證會標(biāo)記所有從根節(jié)點可達(dá)的節(jié)點,從這個意義上來說它是正確的。這是一個必要的保證,因為應(yīng)用程序的用戶當(dāng)然不會喜歡把他們的已分配塊過早地返回給空閑鏈表。然而,這種方法從某種意義上而言又是保守的,因為它可能不正確地標(biāo)記實際上不可達(dá)的塊,因此它可能不會釋放某些垃圾。雖然這并不影響應(yīng)用程序的正確性,但是這可能導(dǎo)致不必要的外部碎片。
? ? ? C 程序的 Mark & Sweep 收集器必須是保守的,其根本原因是 C 語言不會用類型信息來標(biāo)記內(nèi)存位置。因此,像 int 或者 float 這樣的標(biāo)量可以偽裝成指針。例如,假設(shè)某個可達(dá)的已分配塊在它的有效載荷中包含一個 int ,其值碰巧對應(yīng)于某個其他已分配塊 b 的有效載荷中的一個地址。對收集器而言,是沒有辦法推斷出這個數(shù)據(jù)實際上是 int 而不是指針。因此,分配器必須保守地將塊 b 標(biāo)記為可達(dá),盡管事實上它可能是不可達(dá)的。
