前言

內(nèi)存碎片一直是非移動(dòng)垃圾回收器(指在垃圾回收時(shí)不進(jìn)行對(duì)象的移動(dòng))的一個(gè)問(wèn)題，比如說(shuō)在前面的標(biāo)記-清除垃圾回收器就有這樣的問(wèn)題。而標(biāo)記-壓縮垃圾回收算法能夠有效的緩解這一問(wèn)題。

算法原理

既然叫標(biāo)記-壓縮算法，那么它也分為兩個(gè)階段，一個(gè)是標(biāo)記(mark)，一個(gè)是壓縮(compact). 其中標(biāo)記階段跟標(biāo)記-清除算法中的標(biāo)記階段是一樣的，可以參考前面的文章。

而對(duì)于壓縮階段，它的工作就是移動(dòng)所有的可達(dá)對(duì)象到堆內(nèi)存的同一個(gè)區(qū)域中，使他們緊湊的排列在一起，從而將所有非可達(dá)對(duì)象釋放出來(lái)的空閑內(nèi)存都集中在一起，通過(guò)這樣的方式來(lái)達(dá)到減少內(nèi)存碎片的目的。

在壓縮階段，由于要移動(dòng)可達(dá)對(duì)象，那么需要考慮移動(dòng)對(duì)象時(shí)的順序，一般分為下面三種：

任意順序 - 即不考慮原先對(duì)象的排列順序，也不考慮對(duì)象間的引用關(guān)系，隨意的移動(dòng)可達(dá)對(duì)象，這樣可能會(huì)有內(nèi)存訪問(wèn)的局部性問(wèn)題。

線性順序 - 在重新排列對(duì)象時(shí)，會(huì)考慮對(duì)象間的引用關(guān)系，比如A對(duì)象引用了B對(duì)象，那么就會(huì)盡可能的將A，B對(duì)象排列在一起。

滑動(dòng)順序 - 顧名思義，就是在重新排列對(duì)象時(shí)，將對(duì)象按照原先堆內(nèi)存中的排列順序滑動(dòng)到堆的一端。

現(xiàn)在大多數(shù)的垃圾收集算法都是按照任意順序或滑動(dòng)順序去實(shí)現(xiàn)的。下面我們分別來(lái)看下它們各自的算法原理。

Two-Finger 算法

Two-Finger算法來(lái)自Edwards, 它在壓縮階段移動(dòng)對(duì)象時(shí)是任意順序移動(dòng)的，它最適用于處理包含固定大小對(duì)象的內(nèi)存區(qū)域。由于Mark階段都是跟標(biāo)記-清除算法一致的，這里我們只關(guān)注Compact階段。

Two-Finger算法是一個(gè)Two Passes算法，即需要遍歷堆內(nèi)存兩次，第一次遍歷是將堆末尾的可達(dá)對(duì)象移動(dòng)到堆開(kāi)始的空閑內(nèi)存單元去，第二次遍歷則需要修改可達(dá)對(duì)象的引用，因?yàn)橐恍┛蛇_(dá)對(duì)象已經(jīng)被移動(dòng)到別的地址，而原先引用它們的對(duì)象還指向著它們移動(dòng)前的地址。

在這兩次遍歷過(guò)程中，首尾兩個(gè)指針?lè)謩e從堆的頭尾兩個(gè)位置向中間移動(dòng)，直至兩個(gè)指針相遇，由于它們的運(yùn)動(dòng)軌跡酷似兩根手指向中間移動(dòng)的軌跡，因此稱為T(mén)wo Finger算法。

第一次遍歷

下面我們先看下第一遍遍歷的偽代碼 - 來(lái)自<>,

compact():

relocate(HeapStart,HeapEnd)

updateReferences(HeapStart,free)

relocate(start,end)

free

scan

while free < scan

//找到一個(gè)可以被釋放的空間

while isMarked(free)

unsetMarked(free)

free

//找到一個(gè)可以移動(dòng)的可達(dá)對(duì)象

while not isMarked(scan) && scan > free

scan

if scan > free

unsetMarked(scan)

move(scan, free) //將scan位置的可達(dá)對(duì)象移動(dòng)到free位置上

*scan

free

scan

第一次遍歷的原理是，頭指針(free)沿著堆頭向堆尾前進(jìn)，直到找到一個(gè)空閑的內(nèi)存單元(即沒(méi)有被標(biāo)記為可達(dá)對(duì)象的內(nèi)存單元)，如遇到可達(dá)對(duì)象，則清除其標(biāo)記。接著尾指針(scan)從堆尾向堆頭方向前進(jìn)，直到找到一個(gè)被標(biāo)記為可達(dá)的內(nèi)存單元。最后，collector將可達(dá)對(duì)象從尾指針(scan)指向的位置移動(dòng)到頭指針(free)指向的位置，最后將可達(dá)對(duì)象移動(dòng)后的位置(當(dāng)前free指針指向的位置)寫(xiě)到原先可達(dá)對(duì)象處于的位置(當(dāng)前尾指針scan指向的位置), 為下一次的遍歷 - 更新對(duì)象相互間的引用做好準(zhǔn)備。注：當(dāng)移動(dòng)可達(dá)對(duì)象時(shí)，其引用的對(duì)象在可達(dá)對(duì)象移動(dòng)后保持不變，如下圖中的G對(duì)象移動(dòng)后依然指向位置5和位置10。

第一次遍歷

第二次遍歷

而第二次的遍歷則是為了更新引用關(guān)系，一個(gè)可達(dá)對(duì)象可以被其他對(duì)象引用，比如上圖中的K對(duì)象，如果其被移動(dòng)后，引用它的對(duì)象比如說(shuō)G并不知道它被移動(dòng)了，那么這第二次的遍歷就是為了告訴G它所引用的對(duì)象K已經(jīng)被移動(dòng)到新的位置上去了，它需要更新它對(duì)K的引用。

updateReferences(start,end)

for each fld in Roots //先更新mutator根對(duì)象所引用的對(duì)象關(guān)系

ref

if ref >= end

*fld

scan

while scan < ned

for each fld in Pointers(scan)

ref

if ref >= end

*fld

scan

第二次遍歷，collector先會(huì)對(duì)根對(duì)象進(jìn)行遍歷，比如根對(duì)象2引用著位置6的內(nèi)存單元，根據(jù)算法，該位置大于等于end指針?biāo)赶虻奈恢?- 即第一次遍歷free指針和scan指針相遇的位置，那么我們就認(rèn)為這個(gè)位置的對(duì)象已經(jīng)被移動(dòng)，需要更新根對(duì)象2的引用關(guān)系，即從引用位置6改為引用位置2(位置6的內(nèi)存單元中記錄著該對(duì)象被移動(dòng)后的新位置)。同理，在移動(dòng)G對(duì)象的時(shí)候，也是要判斷看G所引用的內(nèi)存單元位置是否大于end指針指向的位置，如果小于，則不處理。否則則修改G的引用關(guān)系。

第二次遍歷

LISP2 算法

Lisp2算法是一種應(yīng)用更為廣泛的壓縮算法，它屬于滑動(dòng)順序算法中的一種。它跟Two-Finger算法的不同還在于它可以處理不同大小的對(duì)象，而不再是固定大小的對(duì)象。同時(shí)，計(jì)算出來(lái)的可達(dá)對(duì)象的遷移地址需要額外的空間進(jìn)行存儲(chǔ)而不再是復(fù)寫(xiě)原先對(duì)象所在的位置。最后，Lips2算法需要進(jìn)行3次堆內(nèi)存的遍歷。

第一次遍歷

第一次遍歷，collecor僅僅是計(jì)算和記錄可達(dá)對(duì)象應(yīng)該遷移去的地址。

compact():

computeLocations(HeapStart,HeapEnd,HeapStart)

updateReferences(HeapStart,HeapEnd)

relocate(HeapStart,HeapEnd)

computeLocations(start,end,toRegion):

scan

free

while scan < end

if isMarked(scan)

forwardingAddress(scan)

free

scan

第一次遍歷

指針free, scan同時(shí)指向堆起始位置，同時(shí)scan指針向堆尾移動(dòng)，目的是要找到被標(biāo)記的可達(dá)對(duì)象。

找到可達(dá)對(duì)象后，在scan指針對(duì)應(yīng)的位置分配一個(gè)額外的空間來(lái)存儲(chǔ)該可達(dá)對(duì)象應(yīng)該遷移到的地址 - 就是free指針指向的位置0，同時(shí)free指針向堆尾移動(dòng)B對(duì)象大小的距離- free'指針指向的位置。最后scan指針繼續(xù)往前走，直到尋找到下一個(gè)可達(dá)對(duì)象D - scan'指針指向的位置。

同理，在可達(dá)對(duì)象D處分配一塊空間來(lái)保存對(duì)象D應(yīng)該遷移到的位置，由于B對(duì)象已經(jīng)占用了2個(gè)內(nèi)存單元，所以對(duì)象E的遷移地址是從位置2開(kāi)始，也就是當(dāng)前free指針指向的位置。

指針free，scan繼續(xù)向前移動(dòng)。

第一次遍歷完后，所有的可達(dá)對(duì)象都有了對(duì)應(yīng)的遷移地址，free指針指向位置9，因?yàn)樗械目蛇_(dá)對(duì)象總共占了9個(gè)單元大小的空間。

第二次遍歷

第二次遍歷主要是修改對(duì)象間的引用關(guān)系，基本跟Two Finger算法的第二次遍歷一樣。

updateReferences(start,end):

for each fld in Roots

ref

if ref != null

*fld

scan

while scan < end

if isMarked(scan)

for each fld in Pointers(scan)

if *fld != null

*fld

scan

第二次遍歷

修改根對(duì)象的引用關(guān)系，根對(duì)象1引用對(duì)象B，對(duì)象B的遷移地址為0，于是collector將根對(duì)象對(duì)B對(duì)象的引用指向它的遷移地址 - 位置0， 現(xiàn)在A對(duì)象所處的位置。

同理，對(duì)于根對(duì)象2，3都執(zhí)行同樣的操作，將它們對(duì)其所引用的對(duì)象的引用修改為對(duì)應(yīng)的它們所引用的對(duì)象的遷移地址。

通過(guò)scan指針遍歷堆內(nèi)存，更新所有的可達(dá)對(duì)象對(duì)其引用對(duì)象的引用為其引用對(duì)象的遷移地址。比如說(shuō)，對(duì)于可達(dá)對(duì)象B， 它引用了對(duì)象D，D的遷移地址是2，那么B直接將其對(duì)D對(duì)象的引用重新指向2這個(gè)位置。

第二次遍歷結(jié)束后的對(duì)象之間的引用關(guān)系。

第三次遍歷

第三次遍歷則是根據(jù)可達(dá)對(duì)象的遷移地址去移動(dòng)可達(dá)對(duì)象，比如說(shuō)可達(dá)對(duì)象B，它的遷移地址是0，那么就將其移動(dòng)到位置0，同時(shí)去除可達(dá)對(duì)象的標(biāo)記，以便下次垃圾收集。

relocate(start,end):

scan

while scan < end

if isMarked(scan)

dest

move(scan,dest) //將可達(dá)對(duì)象從scan位置移動(dòng)到dest位置

unsetMarked(dest)

scan

所有可達(dá)對(duì)象移動(dòng)結(jié)束后，內(nèi)存單元展示為：

第三次遍歷

后記

通過(guò)上面的兩種算法的展示，我想大家應(yīng)該都大概了解了標(biāo)記-壓縮算法工作的基本原理，除了上面兩種實(shí)現(xiàn)，還有其它的一些壓縮算法的實(shí)現(xiàn)，這里就不一一陳列。有興趣者可以自己到網(wǎng)絡(luò)上搜索。

標(biāo)記-壓縮算法雖然緩解的內(nèi)存碎片問(wèn)題，但是它也引用了額外的開(kāi)銷(xiāo)，比如說(shuō)額外的空間來(lái)保存遷移地址，需要遍歷多次堆內(nèi)存等。

總結(jié)

以上是生活随笔為你收集整理的lisp 标记形心_标记-压缩算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。