一钓简、GC的原理及其算法設(shè)計
不同的語言，對GC算法的設(shè)計不同麻汰，常見的GC算法是引用計數(shù)和Mark-Sweep算法疏日， c#采用的是Mark-sweep && compact算法， Lua采用的是Mark-sweep算法涯肩，分開說一下：
引用計數(shù)算法：在一個對象被引用的情況下轿钠，將其引用計數(shù)加1，反之則減1病苗，如果計數(shù)值為0疗垛，則在GC的時候回收，這個算法有個問題就是循環(huán)引用铅乡。
Mark-sweep算法：每次GC的時候继谚，對所有對象進(jìn)行一次掃描烈菌，如果該對象不存在引用阵幸，則被回收花履，反之則保存。
在Lua5.0及其更早的版本中挚赊，Lua的GC是一次性不可被打斷的過程诡壁，使用的Mark算法是雙色標(biāo)記算法(Two color mark)，這樣系統(tǒng)中對象的非黑即白荠割，要么被引用妹卿，要么不被引用，這會帶來一個問題：在GC的過程中如果新加入對象蔑鹦，這時候新加入的對象無論怎么設(shè)置都會帶來問題夺克，如果設(shè)置為白色，則如果處于回收階段嚎朽，則該對象會在沒有遍歷其關(guān)聯(lián)對象的情況下被回收铺纽；如果標(biāo)記為黑色，那么沒有被掃描就被標(biāo)記為不可回收哟忍，是不正確的狡门。
為了降低一次性回收帶來的性能問題以及雙色算法的問題，在Lua5.1后锅很，Lua都采用分布回收以及三色增量標(biāo)記清除算法（Tri-color incremental mark and sweep）
每個新創(chuàng)建的對象顏色設(shè)置為白色
//初始化階段
遍歷root節(jié)點中引用的對象，從白色置為灰色爆安，并且放入到灰色節(jié)點列表中
//標(biāo)記階段
while(灰色鏈表中還有未掃描的元素)：
從中取出一個對象叛复，將其置為黑色
遍歷這個對象關(guān)聯(lián)的其他所有對象：
if 為白色
標(biāo)記為灰色，加入到灰色鏈表中(insert to the head)
//回收階段
遍歷所有對象：
if 為白色扔仓，
沒有被引用的對象致扯，執(zhí)行回收
else
重新塞入到對象鏈表中，等待下一輪GC
二当辐、GC的數(shù)據(jù)結(jié)構(gòu)
分析Lua中對于需要GC的類型數(shù)據(jù)
define iscollectable(o) (ttype(o) >= LUA_TSTRING)
都會有一個基本的定義CommonHeader抖僵，其定義為：
next: GCObject鏈表指針，該指針用來將所有的GC對象都鏈接在一個表中缘揪；
tt: 數(shù)據(jù)類型：nil, boolean, number, string...
marked: 標(biāo)記字段耍群，byte表示的字段顏色定義為
這兒特定解釋一下為什么會有兩種白色，前面提到找筝，5.1后的Lua采用的是三色標(biāo)記算法蹈垢，其實質(zhì)是四色標(biāo)記算法，分為0型白色和1型白色袖裕，在GC回收的時候曹抬，會設(shè)置當(dāng)前的白色為其中一種，詳見globalstate中的currentwhite急鳄，這樣在代碼回收的時候谤民，如果當(dāng)前對象的白色不為currentwhite,則認(rèn)為其不可回收堰酿，這樣的對象需要等到下一次的GC才能決定是否回收，具體參看后面的张足，會有對應(yīng)的應(yīng)用触创。對于global_state的設(shè)計為：
參考《Lua設(shè)計與實現(xiàn)》
