1.?????? 自動(dòng)垃圾收集 (GC) 中的常用算法

關(guān)鍵術(shù)語(yǔ)：

a)?????? 垃圾 (garbage/live object) ，指在程序中堆上已經(jīng)被分配但是不會(huì)被再次使用的對(duì)象。許多數(shù)據(jù)說(shuō)明，在實(shí)際的程序中，大多數(shù)的對(duì)象只存在一個(gè)很短的周期，需要長(zhǎng)期保存 Reference 的對(duì)象很少。

b)?????? 垃圾收集：所有的允許分配堆內(nèi)存的程序都提供了垃圾收集方法。在 C/C++ 中，實(shí)現(xiàn)需要用戶自己調(diào)用 alloc/free , new/delete 分配內(nèi)存。在 C#/Java 中，虛擬機(jī)都提供了自動(dòng)垃圾收集，根據(jù)對(duì)象的生存周期與引用計(jì)數(shù)對(duì)垃圾對(duì)象進(jìn)行回收。

c)?????? 堆空間的增長(zhǎng)與重整： [To-do ： how did C/C++ do this]

C# 的堆空間大小限制取決于虛擬內(nèi)存的大小，通常來(lái)說(shuō) .net 虛擬機(jī)并不會(huì)限制可用的內(nèi)存大小，而 java 默認(rèn)的堆大小在 256M 左右，如果需要使用更大的堆，則需要使用 JVM 的 -Xmx 參數(shù)指定堆棧的上限。 java 和 C++ 都采用了分段的堆，在 gc 過(guò)程中會(huì)移動(dòng)對(duì)象，從而得到更加連續(xù)的堆可用內(nèi)存，更高的空間使用效率。

d)?????? 并行的與串行的垃圾收集

并行的垃圾收集指的是在單獨(dú)的線程中執(zhí)行 GC ，不影響其他的線程執(zhí)行

串行的垃圾收集： GC 線程將會(huì)掛起當(dāng)前所有的執(zhí)行線程直到 GC 線程返回。

e)?????? Root Set 與可達(dá)集

優(yōu)化的編譯器可以通過(guò)變量的生存周期決定對(duì)象在最合適的時(shí)候 ( 不會(huì)被將要執(zhí)行的程序引用 ) 回收，但是在常用的算法中，一種簡(jiǎn)化的方式更加經(jīng)常被采用，就是對(duì)象根集合與可達(dá)集合。因?yàn)閷?duì)象只有通過(guò)被引用或者作為全局對(duì)象的時(shí)候才可以被訪問(wèn)，所以從全局對(duì)象可以導(dǎo)航到所有的活動(dòng)對(duì)象，而其他的對(duì)象則被視為無(wú)用內(nèi)存，被 GC 回收。全局對(duì)象的集合稱為 Root Set ，而通過(guò)導(dǎo)航測(cè)試確定垃圾的過(guò)程被稱為可達(dá)性測(cè)試，可以被導(dǎo)航的對(duì)象集合被稱為可達(dá)集。

?

通常 GC 都包含了垃圾檢測(cè)和垃圾回收兩個(gè)階段。

?

基本的 GC 算法包括以下幾種：

a)?????? Reference Counting( 引用計(jì)數(shù) )

引用計(jì)數(shù)為每一個(gè)對(duì)象提供了當(dāng)前被引用的次數(shù)。前者顯式的便利了系統(tǒng)中所有的指針得到可用的對(duì)象集合，后者便利每一個(gè)對(duì)象，判斷對(duì)象是否仍被引用，即對(duì)象是否還將被使用。 RC 的一個(gè)重要的好處是它的實(shí)時(shí)性，因?yàn)槊恳粋€(gè)操作都可以及時(shí)地修改對(duì)象的 Reference count 。從而在語(yǔ)言的層面上實(shí)現(xiàn) GC 。而且其他的執(zhí)行進(jìn)程不需要被掛起。問(wèn)題是 GC 本身需要占用多余的存儲(chǔ)空間。

Comment: Not always effective, hard to make efficient!

當(dāng)程序創(chuàng)建一個(gè)循環(huán)引用關(guān)系的時(shí)候，環(huán)中的對(duì)象的引用計(jì)數(shù)永遠(yuǎn)不會(huì)降為 0 ，也就永遠(yuǎn)無(wú)法被回收，這種情況下，引用計(jì)數(shù)算法將會(huì)失效。

效率的問(wèn)題源于 RC 的本質(zhì)，它的耗費(fèi)與處理時(shí)間成正比 (per operation update) 。這個(gè)問(wèn)題對(duì)于棧上的生存期較短的對(duì)象尤其顯著。延遲的引用計(jì)數(shù)技術(shù)可以有效地提高效率，然而其占用的處理時(shí)間仍然是成比例的，只是比例相比下降了很多。

對(duì)象的回收：

RC 為零的對(duì)象將會(huì)被添加到一個(gè)回收鏈表中，等待回收進(jìn)程回收。

b)?????? Mark-Sweep

標(biāo)記清掃 (MS) 算法首先通過(guò) Root Set 得到當(dāng)前的可達(dá)集并對(duì)相應(yīng)的對(duì)象作出標(biāo)記 (Mark) ，然后將非可達(dá)集添加到回收鏈表中 (Sweep) 。

MS 的第一個(gè)問(wèn)題是它容易造成零碎地內(nèi)存，小對(duì)象往往散步在堆中，造成難以創(chuàng)建大對(duì)象。 ( 事實(shí)上這個(gè)問(wèn)題對(duì)于所有的 GC 算法都存在 )

MS 第二個(gè)問(wèn)題也是它的效率問(wèn)題，其耗費(fèi)與堆大小（活動(dòng)對(duì)象與垃圾對(duì)象的總合）成正比。

MS 的第三個(gè)問(wèn)題是對(duì)象局部性 (locality) ，因?yàn)閷?duì)象不會(huì)被移動(dòng)，造成堆上存在大量空隙。

c)?????? Mark-Compact

標(biāo)記 - 壓縮算法 (MC) 與 MS 算法的第一步驟相同，在第二步驟中， MC 移動(dòng)所有的活動(dòng)對(duì)象是他們?cè)诙焉舷噜彽奈恢么嬖冢瑥亩纬陕?lián)系的空閑內(nèi)存。這個(gè)過(guò)程類似于 Windows 的內(nèi)存碎片整理。

MC 的問(wèn)題顯而易見(jiàn)，對(duì)于大量臨時(shí)對(duì)象的情況下，其性能遠(yuǎn)低于 MS 算法。

MC 與 MS 在第一個(gè)階段非常類似，但是不同是 MC 并不回收垃圾，而 MS 往往進(jìn)行回收。

d)?????? Coping

拷貝回收合并了 MC 算法中的掃描與壓縮兩個(gè)過(guò)程，它的目標(biāo)也是將所有的活動(dòng)對(duì)象移動(dòng)到相鄰的空間中，從而形成連續(xù)的可用內(nèi)存。

最常見(jiàn)的 Coping 算法將堆分為兩個(gè)區(qū)域，在運(yùn)行過(guò)程中同時(shí)僅有一個(gè)區(qū)域可以被引用。在每一次整理過(guò)程中，使用區(qū)域的對(duì)象將會(huì)被拷貝到空閑區(qū)域中連續(xù)的存儲(chǔ)空間中。 (Cheney) 使用廣度優(yōu)先的遍歷算法 ( 內(nèi)存中的引用關(guān)系是樹狀的結(jié)構(gòu) ) 。

Coping 的最大問(wèn)題是它要求實(shí)際需要的近兩倍的內(nèi)存。增加可用的內(nèi)存可以顯著的提高 Coping 算法的效率，當(dāng)可用內(nèi)存不足的時(shí)候， Coping 的次數(shù)將會(huì)增加，提高 GC 對(duì)系統(tǒng)性能的影響。

e)?????? Non-Coping implicit collection

非拷貝隱式的內(nèi)存收集算法為每一個(gè)對(duì)象增加了兩個(gè)指針和一個(gè)顏色域，從而將內(nèi)存中的所有對(duì)象組成了一個(gè)雙向鏈表的結(jié)構(gòu) ( 顏色域標(biāo)志當(dāng)前對(duì)象處于哪一個(gè)內(nèi)存節(jié)點(diǎn) -bulk 中 ) 。與 Coping 相比，活動(dòng)對(duì)象并不會(huì)在整理過(guò)程中被移動(dòng)，所被改動(dòng)的僅僅是對(duì)象的三個(gè)附加域。因此對(duì)象的回收可以在常數(shù)時(shí)間內(nèi)被完成， NCIC 的消耗與系統(tǒng)中的對(duì)象的數(shù)目成正比。

NCIC 提高了對(duì)象遍歷的效率，尤其是大對(duì)象的便利效率，但是它無(wú)法避免稀疏內(nèi)存的問(wèn)題。

f)??????? 基本的 GC 算法可能造成的問(wèn)題

所有的 GC 算法都存在 Time-Space 的平衡問(wèn)題，即使主存的價(jià)格日益降低， CPU 的速度越來(lái)越快，他們?nèi)詫幢壤恼加孟到y(tǒng)資源，帶來(lái)很多額外的消耗。虛擬內(nèi)存的存在使得 GC 算法的實(shí)現(xiàn)更加困難，因?yàn)閷?duì)象存在于不同的頁(yè)面當(dāng)中，一次簡(jiǎn)單的 Coping 可能造成意想不到的大量頁(yè)面交換。從而帶來(lái)比理論值大的多得消耗。

因此在常用的 GC 實(shí)現(xiàn)中，都采用了合并集中算法的擴(kuò)展的 GC ，我們將在下一部分對(duì)擴(kuò)展的 GC 算法進(jìn)行論述。

2.?????? 擴(kuò)展的垃圾收集算法

a)?????? Incremental Tracing Collectors

漸進(jìn)的遍歷回收 (ITC) 算法要求伴隨程序執(zhí)行的同時(shí)漸進(jìn)的進(jìn)行垃圾收集。但是應(yīng)用程序本身可能在不斷的修改已經(jīng)被遍歷過(guò)的對(duì)象，所以 ITC 必須有一個(gè)監(jiān)視這些改變的方法。

?

b)?????? Generational Garbage Collection

GGC 為 Java 和 .Net 機(jī)制共同支持，需額外注意！

分代的垃圾收集的理論基礎(chǔ)是大多數(shù) (80% - 98%) 的對(duì)象之在堆上存在極短的時(shí)間，通常幾百萬(wàn)條指令。對(duì)于簡(jiǎn)單的 Coping 算法，每一次都需要重復(fù)的移動(dòng)這些對(duì)象，從而造成了極大的性能損耗。 GGC 通過(guò)把生存周期較長(zhǎng)的對(duì)象移動(dòng)到單獨(dú)的堆代上，減少了這樣的負(fù)擔(dān)。

在一個(gè)程序中，如果對(duì)象在創(chuàng)建后一分鐘仍然沒(méi)有被回收，則，該對(duì)象很可能還要生存更長(zhǎng)的周期， GGC 通過(guò)對(duì)堆進(jìn)行劃分，將比較老的對(duì)象 Copy 到更高的代中從而實(shí)現(xiàn)更加有效的垃圾回收。高代往往采用更高效的 Tracing 算法，而且不會(huì)被非常頻繁的收集，這樣可以有效地提高非實(shí)時(shí)性系統(tǒng)對(duì)于 GC 效率的要求，從而使 GC 造成的系統(tǒng)中斷降低到用戶不易覺(jué)察的程度。

GGC 的每一個(gè)代可以采用不同的 GC 算法。

GGC 的主要問(wèn)題包括：

?????? Advancement Policies ，晉升策略，即確定將對(duì)象移到較老的代上所需要的生存周期。

?????? Heap Management ：即如何為不同的代分配堆空間

?????? Collection Scheduling ：即何時(shí)啟動(dòng)每個(gè)代的收集過(guò)程

?????? Inter-Generational Referencing ： 即跨代間的對(duì)象的相互引用。

?????? 所有這些問(wèn)題都與具體的應(yīng)用程序相關(guān)，因此通用的解決方案可能難以滿足特定應(yīng)用的要求。

?

3.?????? Java(TM) 中的垃圾收集機(jī)制

Java1.4 中包含了 2 段 Generation(Younger and older) ，每一段有三種可選的垃圾回收算法。 java 支持 Incremental Collection 。 Java 提供了并行的垃圾收集支持。

4.?????? C# 中的垃圾機(jī)制機(jī)制

C# 采取了 3 段 Generation 的模式進(jìn)行垃圾回收。每一代都采用了 Mark-Sweep 算法，在垃圾收集過(guò)程中會(huì)掛起所有的

5.?????? 垃圾收集機(jī)制的效率測(cè)量

Garbage Collection 的效率比起手動(dòng)的內(nèi)存管理，性能上是會(huì)有些差距的，具體可能造成多大的影響？

注意：并不是只有自動(dòng)內(nèi)存回收的程序語(yǔ)言才會(huì)有垃圾回收的消耗，對(duì)于 C/C++ 這些手動(dòng)管理內(nèi)存的語(yǔ)言，內(nèi)存分配與釋放也是會(huì)造成系統(tǒng)一定的開銷的。

?

6.?????? 實(shí)用中的一些建議

自動(dòng)垃圾收集取代了人工回收棄置內(nèi)存的回收工作，極大地減少了內(nèi)存維護(hù)方面的工作量，但是在實(shí)際的使用中我們必須注意如下一些問(wèn)題，避免造成系統(tǒng)瓶頸。

避免頻繁地創(chuàng)建臨時(shí)指針

減少對(duì)象分配的次數(shù)，使用對(duì)象池的方法

連續(xù)存放需要持久使用的對(duì)象，避免頻繁地頁(yè)面切換。

?

對(duì)于 .Net 程序員，學(xué)會(huì)使用 System Monitor 中的 CLR 性能計(jì)數(shù)器分析系統(tǒng)的瓶頸所在。CLR Profiler 也是一個(gè)很好的實(shí)用工具。