相關(guān)術(shù)語(yǔ)翻譯說(shuō)明:

Mark,標(biāo)記;

Sweep,清除;

Compact,整理; 也有人翻譯為壓縮,譯者認(rèn)為GC時(shí)不存在壓縮這回事。

Copy,復(fù)制; copy 用作名詞時(shí)一般翻譯為拷貝/副本,用作動(dòng)詞時(shí)翻譯為復(fù)制。

本篇文章主要介紹GC回收算法概念

總體而言垃圾收集器都專(zhuān)注于兩件事

• 查找所有存活對(duì)象
• 拋棄其他的部分，即死對(duì)象，不在使用對(duì)象。
  第一步，記錄所有存活的對(duì)象，在垃圾收集中有一個(gè)做，標(biāo)記的過(guò)程專(zhuān)門(mén)干這件事。

I.標(biāo)記可達(dá)對(duì)象(Marking Reachable Objects)

下示意圖對(duì)此作出最好的解釋

首先,有一些特定的對(duì)象被指定為 Garbage Collection Roots(GC根元素)。包括:

• 當(dāng)前正在執(zhí)行的方法里的局部變量和輸入?yún)?shù)
• 活動(dòng)線(xiàn)程(Active threads)
• 內(nèi)存中所有類(lèi)的靜態(tài)字段(static field)
• JNI引用

其次, GC遍歷(traverses)內(nèi)存中整體的對(duì)象關(guān)系圖(object graph),從GC根元素開(kāi)始掃描, 到直接引用，以及其他對(duì)象(通過(guò)對(duì)象的屬性域)。所有GC訪(fǎng)問(wèn)到的對(duì)象都被標(biāo)記(marked)為存活對(duì)象。

存活對(duì)象在上圖中用藍(lán)色表示。標(biāo)記階段完成后, 所有存活對(duì)象都被標(biāo)記了。而其他對(duì)象(上圖中灰色的數(shù)據(jù)結(jié)構(gòu))就是從GC根元素不可達(dá)的, 也就是說(shuō)程序不能再使用這些不可達(dá)的對(duì)象(unreachable object)。這樣的對(duì)象被認(rèn)為是垃圾, GC會(huì)在接下來(lái)的階段中清除他們。

在標(biāo)記階段有幾個(gè)需要注意的點(diǎn):
在標(biāo)記的時(shí)候，會(huì)暫停所有的應(yīng)用線(xiàn)程，以遍歷所有對(duì)象的引用關(guān)系，因?yàn)槿绻粫和＞蜔o(wú)法跟蹤一直變化的引用關(guān)系。
此階段<font color=blue>暫停的時(shí)間, 與堆內(nèi)存大小,對(duì)象的總數(shù)沒(méi)有直接關(guān)系, 而是由存活對(duì)象(alive objects)的數(shù)量來(lái)決定。所以增加堆內(nèi)存的大小并不會(huì)直接影響標(biāo)記階段占用的時(shí)間。</font>

II.刪除不可達(dá)對(duì)象(Removing Unused Objects)

各種GC算法在刪除不可達(dá)對(duì)象時(shí)略有不同, 但總體可分為三類(lèi): 清除(sweeping)、整理(compacting)和復(fù)制(copying)。

• Sweep(清除)
  Mark and Sweep(標(biāo)記-清除) 算法的概念非常簡(jiǎn)單: 直接忽略所有的垃圾。也就是說(shuō)在標(biāo)記階段完成后, 所有不可達(dá)對(duì)象占用的內(nèi)存空間, 都被認(rèn)為是空閑的, 因此可以用來(lái)分配新對(duì)象。

這種算法需要使用 空閑表(free-list),來(lái)記錄所有的空閑區(qū)域, 以及每個(gè)區(qū)域的大小。維護(hù)空閑表增加了對(duì)象分配時(shí)的開(kāi)銷(xiāo)。此外還存在另一個(gè)弱點(diǎn) :<font color=red>明明還有很多空閑內(nèi)存, 卻可能沒(méi)有一個(gè)區(qū)域的大小能夠存放需要分配的對(duì)象, 從而導(dǎo)致分配失敗(在Java 中就是 OutOfMemoryError)。</font>
問(wèn)題的原因呢？就是碎片太多，如圖示

• Compact(整理)

標(biāo)記-清除-整理算法(Mark-Sweep-Compact), 將所有被標(biāo)記的對(duì)象(存活對(duì)象), 遷移到內(nèi)存空間的起始處, 消除了標(biāo)記-清除算法的缺點(diǎn)。 相應(yīng)的缺點(diǎn)就是GC暫停時(shí)間會(huì)增加, 因?yàn)樾枰獙⑺袑?duì)象復(fù)制到另一個(gè)地方, 然后修改指向這些對(duì)象的引用。此算法的優(yōu)勢(shì)也很明顯, 碎片整理之后, 分配新對(duì)象就很簡(jiǎn)單, 只需要通過(guò)指針碰撞(pointer bumping)即可。使用這種算法, 內(nèi)存空間剩余的容量一直是清楚的, 不會(huì)再導(dǎo)致內(nèi)存碎片問(wèn)題。

• Copy(復(fù)制)
  標(biāo)記-復(fù)制算法(Mark and Copy) 和 標(biāo)記-整理算法(Mark and Compact) 十分相似: 兩者都會(huì)移動(dòng)所有存活的對(duì)象。區(qū)別在于, 標(biāo)記-復(fù)制算法是將內(nèi)存移動(dòng)到另外一個(gè)空間: 存活區(qū)。標(biāo)記-復(fù)制方法的優(yōu)點(diǎn)在于: 標(biāo)記和復(fù)制可以同時(shí)進(jìn)行。缺點(diǎn)則是需要一個(gè)額外的內(nèi)存區(qū)間, 來(lái)存放所有的存活對(duì)象。