垃圾回收-- 引用計數法

引用計數法

引用計數法，最重要的就是計數器，記錄有多少引用該對象

引用計數法與mutator 的執行密切相關，在mutator 的處理過程中通過增減計數器的值來進行記憶體管理， 在配置設定和更新對象時會發生計數的變化

更新操作過程：

1. 對指針ptr 新引用的對象（obj）的計數器進行增量操作
2. 對指針ptr 之前引用的對象（*ptr）的計數器進行減量操作

update_ptr(ptr, obj){
   inc_ref_cnt(obj)
   dec_ref_cnt(*ptr)
   *ptr = obj
}
           

注： 為了處理*ptr 和obj 是同一對象時的情況，向增加，後遞減， 防止對象在發生位置改變時，還沒有改變就已經被回收了

更新指針，可能會産生沒有被任何程式引用的垃圾對象。引用計數法中會監督在更新指針的時候是否有産生垃圾，進而在産生垃圾時将其立刻回收

特點：

1. 可即刻回收垃圾
2. 最大暫停時間短 因為不用掃描全部堆，是以時間節省量
3. 計數器值的增減處理繁重 嚴重依賴計數器
4. 計數器需要占用很多位 假如我們用的是32 位機器，那麼就有可能要讓2 的32 次方個對象同時引用一個對象， 計數器有32 位大小
5. 實作煩瑣複雜 對于每次對象的變更都需要進行精确的維護， 否則會造成記憶體無法會回收， 即記憶體溢出
6. 循環引用無法回收

改進：

1. 延遲引用計數法

在延遲引用計數法中使用ZCT（Zero Count Table）。ZCT 是一個表，它會事先

記錄下計數器值在dec_ref_cnt() 函數的作用下變為0 的對象， 因為計數器值為0 的對象不一定都是垃圾，是以暫時先将這些對象保留

在延遲引用計數法中，程式延遲了根引用的計數，将垃圾一并回收。通過延遲，減輕了

因根引用頻繁發生變化而導緻的計數器增減所帶來的額外負擔。當然也失去量垃圾即可回收的特點

1. Sticky 引用計數法

是用來減少計數器位寬

. 什麼都不做 很多情況下，計數器的值會在0 到1 的範圍内變化，鮮少出現5 位計數器溢出這樣的情況 , 不增減計數器的值，就把它那麼放着也不會有什麼大問題

. 使用GC 标記- 清除算法進行管理

1. 1 位引用計數法

計數器隻有1 位大小，特點總結是： 幾乎沒有對象是被共有的，所有對象都能被馬上回收。指針通常預設為4 位元組對齊，是以沒法利用低2 位。隻要好好利用這個性質，就能確定拿出1 位來用作記憶體管理

1 位引用計數法的優點，是不容易出現高速緩存缺

可能會出現很多對象計數器溢出的情況

1. 部分标記- 清除算法

采用一般情況下執行引用計數法，在某個時刻啟動GC 标記- 清除算法的方法。

“有循環引用的垃圾”，一般來說這種垃圾應該很少，單純的GC 标記- 清除算法又是以全部堆為對象的，是以會産生許多無用的搜尋。隻對“可能有循環引用的對象群”使用GC 标記- 清除

算法，對其他對象進行記憶體管理時使用引用計數法。像這樣隻對一部分對象群使用GC 标記-

清除算法的方法，叫作“部分标記- 清除算法”（Partial Mark & Sweep）

部分标記- 清除算法中，對象會被塗成4 種不同的顔色來進行管理

1. 黑（BLACK）：絕對不是垃圾的對象（對象産生時的初始顔色）
2. 白（WHITE）：絕對是垃圾的對象
3. 灰（GRAY）：搜尋完畢的對象
4. 陰影（HATCH）：可能是循環垃圾的對象

頭中配置設定2 位空間，然後用00～11 的值對應這4 個顔色

部分标記- 清除算法的優點，就是把要搜尋的對象限定在陰影對象及其子對象，也就是

“可能是循環垃圾的對象群”中

循環垃圾産生過程： 初始狀态下根引用對象A，對象A 引用對象B，對象B 引用對象C。接下來我們建立一個從對象C 到對象A 的引用。在這裡就形成了A → B → C → A 的循環引用。最後我們删除從根到對象A 的引用。這樣一來，對象A 到C 的循環引用對象群就成了垃圾

條件：

1. 産生循環引用
2. 删除從外部到循環引用的引用

部分标記- 清除算法中用dec_ref_cnt() 函數來檢查這個值。如果對象的計數器值減量

後不為0，說明這個對象可能是循環引用的一份子。這時會先讓這個對象連接配接到隊列，以方

便之後搜尋它

标記- 清除算法并不是完美的，因為從隊列搜尋對象所付出的成本太大了。

被隊列記錄的對象畢竟是候選垃圾，是以要搜尋的對象絕對不在少數。這個算法總計需要

查找3 次對象，也就是說需要對從隊列取出的陰影對象分别執行1 次mark_gray() 函數、

scan_gray() 函數以及collect_white() 函數。這大大增加了記憶體管理所花費的時間， 是以引用計數的優勢- 最大暫停時間就沒有