# 探索Lua5.2內部實現:Garbage Collection(1) 原理 Lua5.2采用垃圾回收機制對所有的lua對象(GCObject)進行管理。Lua虛擬機會定期運行GC，釋放掉已經不再被被引用到的lua對象。 ## 基本算法 基本的垃圾回收算法被稱為"mark-and-sweep"算法。算法本身其實很簡單。 首先，系統管理著所有已經創建了的對象。每個對象都有對其他對象的引用。root集合代表著已知的系統級別的對象引用。我們從root集合出發，就可以訪問到系統引用到的所有對象。而沒有被訪問到的對象就是垃圾對象，需要被銷毀。 我們可以將所有對象分成三個狀態： 1. White狀態，也就是待訪問狀態。表示對象還沒有被垃圾回收的標記過程訪問到。 2. Gray狀態，也就是待掃描狀態。表示對象已經被垃圾回收訪問到了，但是對象本身對于其他對象的引用還沒有進行遍歷訪問。 3. Black狀態，也就是已掃描狀態。表示對象已經被訪問到了，并且也已經遍歷了對象本身對其他對象的引用。 基本的算法可以描述如下： ~~~ 當前所有對象都是White狀態;?? 將root集合引用到的對象從White設置成Gray，并放到Gray集合中;?? while(Gray集合不為空)?? {?? ????從Gray集合中移除一個對象O，并將O設置成Black狀態;?? ????for(O中每一個引用到的對象O1)?{?? ????????if(O1在White狀態)?{?? ????????????將O1從White設置成Gray，并放到到Gray集合中；?? ????????}?? ????}?? }?? for(任意一個對象O){?? ????if(O在White狀態)?? ????????銷毀對象O;?? ????else?? ????????將O設置成White狀態;?? }?? ~~~ ## Incremental Garbage Collection 上面的算法如果一次性執行，在對象很多的情況下，會執行很長時間，嚴重影響程序本身的響應速度。其中一個解決辦法就是，可以將上面的算法分步執行，這樣每個步驟所耗費的時間就比較小了。我們可以將上述算法改為以下下幾個步驟。 首先標識所有的root對象： ~~~ 1. 當前所有對象都是White狀態;?? 2. 將root集合引用到的對象從White設置成Gray，并放到Gray集合中;?? ~~~ 遍歷訪問所有的gray對象。如果超出了本次計算量上限，退出等待下一次遍歷: ~~~ while(Gray集合不為空,并且沒有超過本次計算量的上限){?? ????從Gray集合中移除一個對象O，并將O設置成Black狀態;?? ????for(O中每一個引用到的對象O1)?{?? ????????if(O1在White狀態)?{?? ????????????將O1從White設置成Gray，并放到到Gray集合中；?? ????????}?? ????}?? }?? ~~~ 銷毀垃圾對象： ~~~ for(任意一個對象O){?? ????if(O在White狀態)?? ????????銷毀對象O;?? ????else?? ????????將O設置成White狀態;?? }?? ~~~ 在每個步驟之間，由于程序可以正常執行，所以會破壞當前對象之間的引用關系。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被檢測出來，不會造成泄露。