GC演算法-標記清除演算法
- 2020 年 4 月 8 日
- 筆記
概述
標記清除演算法, 描述起來很簡單, 從名字上就能看出, 分為兩個階段:
- 標記階段: 遍歷所有對象, 將活動對象都打上標記
- 清除階段: 遍歷堆, 將沒有標記的對象釋放掉.
介紹完畢, 本文結束. 開玩笑, 確實看上去很簡單啦. 那就具體思考一下實現吧.
實現
介紹寫的很清楚了, 實現也是兩個階段唄, 先打tag, 後清除.
標記
尋找所有的活動對象, 要從一個起點開始, 根集合(包括棧、常量池等等), 然後一層一層找下去. 簡單來說就像這樣:
add_mark(obj){ // 防止重複標記 if(obj.mark == true) return; obj.mark = true // 遍歷所有子對象 for(o in objs){ add_mark(o) } }
將根集合的所有對象都調用一遍, 標記完成.
清除
標記時遍歷的是活動對象, 清除階段呢? 遍歷堆. 將堆上所有非活動對象清除. 就比如:
// 這裡一直堆的開始位置 HEAP_START 和結束位置 HEAP_END p = HEAP_START while(p < HEAP_END){ size = p.size // 對象的大小, 用於找到下一個對象 // 判斷當前對象是否是活動對象 if(p.mark == true){ p.mark = false // 為下一次標記做準備 }else{ // 回收 free(p) } p += size }
當然, 其中的free函數也不是簡單的將地址回收, 而是將其記錄到一個鏈表中, 以方便下次申請記憶體. 實現大概如下:
free(p){ // 這裡有一個全局變數, 保存鏈表頭: FREE_HEAD // 若當前對象和上一次回收的對象是連續記憶體, 直接合併 if(FREE_HEAD + FREE_HEAD.size == p){ FREE_HEAD.size += p.size }else{ p.next = FREE_HEAD FREE_HEAD = p } }
這樣, 申請記憶體時遍歷FREE_HEAD, 找到大小合適的分塊. 若沒有找到, 就動態擴容咯. 這裡其實還有一個優化的小方向, 開始的時候忘記了. 為了提高查找記憶體時速度, 可以將空閑鏈表按照大小進行區分, 這樣, 需要多大的記憶體, 直接到對應的鏈表中找就行了.
雖然實現寫的很粗糙, 但大致意思有了.
問題
1.記憶體的碎片化
從上面可以看到, 只對記憶體進行了清除, 但是沒有整理. 而記憶體的申請又是動態的, 就會導致出現很多離散的小片空閑記憶體. 極端情況甚至可能記憶體中還有200mb的空閑記憶體, 但是申請個10kb的空間卻找不到.
2.暫停時間長
其暫停時間與堆的大小成正比, 堆越大, 遍歷清除耗費的時間就越久.
為了解決標記清除演算法的問題, 衍生出了點陣圖標記法, BiBOP法 ,延遲清除演算法等等個人感覺很雞肋(好吧, 或許是我未得其精髓).
為了解決標記清除的問題, 有衍生出了 標記複製 , 標記整理 演算法, 之後再議.
