探索Lua5.2內部實現:Garbage Collection(1) 原理

Lua5.2採用垃圾回收機制對所有的lua對象(GCObject)進行管理。Lua虛擬機會定期運行GC，釋放掉已經不再被被引用到的lua對象。

基本算法

基本的垃圾回收算法被稱為"mark-and-sweep"算法。算法本身其實很簡單。

首先，系統管理著所有已經創建了的對象。每個對像都有對其他對象的引用。root集合代表著已知的系統級別的對象引用。我們從root集合出發，就可以訪問到系統引用到的所有對象。而沒有被訪問到的對象就是垃圾對象，需要被銷毀。

我們可以將所有對象分成三個狀態：

1. White狀態，也就是待訪問狀態。表示對像還沒有被垃圾回收的標記過程訪問到。
2. Gray狀態，也就是待掃描狀態。表示對像已經被垃圾回收訪問到了，但是對象本身對於其他對象的引用還沒有進行遍歷訪問。
3. Black狀態，也就是已掃描狀態。表示對像已經被訪問到了，並且也已經遍歷了對象本身對其他對象的引用。

基本的算法可以描述如下：

[plain] view plain copy print ?

1. 當前所有對像都是White狀態;  
2. 將root集合引用到的對像從White設置成Gray，並放到Gray集合中;  
3. while(Gray集合不為空)  
4. {  
5.     從Gray集合中移除一個對象O，並將O設置成Black狀態;  
6.     for(O中每一個引用到的對象O1) {  
7.         if(O1在White狀態) {  
8.             將O1從White設置成Gray，並放到到Gray集合中；  
9.         }  
10.     }  
11. }  
12. for(任意一個對象O){  
13.     if(O在White狀態)  
14.         銷毀對象O;  
15.     else  
16.         將O設置成White狀態;  
17. }  

Incremental Garbage Collection

上面的算法如果一次性執行，在對像很多的情況下，會執行很長時間，嚴重影響程序本身的響應速度。其中一個解決辦法就是，可以將上面的算法分步執行，這樣每個步驟所耗費的時間就比較小了。我們可以將上述算法改為以下下幾個步驟。

首先標識所有的root對象：

[plain] view plain copy print ?

1. 當前所有對像都是White狀態;  
2. 將root集合引用到的對像從White設置成Gray，並放到Gray集合中;  

遍歷訪問所有的gray對象。如果超出了本次計算量上限，退出等待下一次遍歷:

[plain] view plain copy print ?

1. <p>while(Gray集合不為空,並且沒有超過本次計算量的上限)</p>{  
2.     從Gray集合中移除一個對象O，並將O設置成Black狀態;  
3.     for(O中每一個引用到的對象O1) {  
4.         if(O1在White狀態) {  
5.             將O1從White設置成Gray，並放到到Gray集合中；  
6.         }  
7.     }  
8. }  

銷毀垃圾對象：

[plain] view plain copy print ?

1. for(任意一個對象O){  
2.     if(O在White狀態)  
3.         銷毀對象O;  
4.     else  
5.         將O設置成White狀態;  
6. }  

在每個步驟之間，由於程序可以正常執行，所以會破壞當前對象之間的引用關係。black對象表示已經被掃描的對象，所以他應該不可能引用到一個white對象。當程序的改變使得一個black對象引用到一個white對象時，就會造成錯誤。解決這個問題的辦法就是設置barrier。barrier在程序正常運行過程中，監控所有的引用改變。如果一個black對象需要引用一個white對象，存在兩種處理辦法：

1. 將white對象設置成gray，並添加到gray列表中等待掃描。這樣等於幫助整個GC的標識過程向前推進了一步。
2. 將black對象該回成gray，並添加到gray列表中等待掃描。這樣等於使整個GC的標識過程後退了一步。

這種垃圾回收方式被稱為"Incremental Garbage Collection"(簡稱為"IGC"，Lua所採用的就是這種方法。使用"IGC"並不是沒有代價的。IGC所檢測出來的垃圾對象集合比實際的集合要小，也就是說，有些在GC過程中變成垃圾的對象，有可能在本輪GC中檢測不到。不過，這些殘餘的垃圾對像一定會在下一輪GC被檢測出來，不會造成洩露。