鑒于復(fù)制算法中，沒(méi)有內(nèi)存碎片的方式能大大提高分配效率，因此，在mark_sweep的基礎(chǔ)上，也可以改良出mark_compact算法，使得空閑空間連續(xù)。同時(shí)又沒(méi)有復(fù)制算法的無(wú)幫吃一半堆的問(wèn)題。
首先是最簡(jiǎn)單的算法，叫Lisp2算法。
在標(biāo)記階段，不變，仍然是對(duì)每個(gè)活動(dòng)對(duì)象打上標(biāo)簽。
隨后，開(kāi)始移動(dòng)活動(dòng)對(duì)象到堆的開(kāi)頭。因?yàn)闆](méi)有兩個(gè)堆，又要挪動(dòng)對(duì)象放到一起，那么forwarding指針便需要在對(duì)象頭中占用空間（復(fù)制算法中不用占用是因?yàn)樗欠腔顒?dòng)對(duì)象），且在移動(dòng)前要做一輪forwarding指針的重指。還要做一輪子對(duì)象指針的重指?？傮w流程如下：
compaction_phase() {
set_forwarding_ptr()
adjust_ptr()
move_obj()
}
// 設(shè)forward指針最簡(jiǎn)單set_forwarding_ptr() {
scan = new_addr = $heap_start while (scan < $heap_end) if (scan.mark == TRUE)
scan.forwarding = new_addr
new_addr += scan.size
scan += scan.size
}
// 調(diào)整對(duì)象的成員指針，指向成員在堆中的新地址。對(duì)于全局變量，因?yàn)樗鼈兪歉淖訉?duì)象，也需要重指。adjust_ptr() { for (r : $roots)
r = r.forwarding
scan = $heap_start while (scan < $heap_end) // 這里為什么要掃堆，而不能從根直接遞歸遍歷？因?yàn)橹苯舆f歸可能會(huì)遞歸到不正確的已經(jīng)重指過(guò)的值。直接遍歷的話(huà)不會(huì)有順序問(wèn)題。
if (scan.mark == TRUE) for (child : children(scan))
child = child.forwarding
scan += scan.size
}
// 最后，移動(dòng)對(duì)象//不列了，比較簡(jiǎn)單，只需要掃堆，把活動(dòng)對(duì)象向前移，清除forwarding和mark標(biāo)記即可
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線(xiàn)安全]玩轉(zhuǎn)無(wú)線(xiàn)電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式