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

關鍵術語：

a)?????? 垃圾 (garbage/live object) ，指在程序中堆上已經被分配但是不會被再次使用的對象。許多數據說明，在實際的程序中，大多數的對象只存在一個很短的周期，需要長期保存 Reference 的對象很少。

b)?????? 垃圾收集：所有的允許分配堆內存的程序都提供了垃圾收集方法。在 C/C++ 中，實現需要用戶自己調用 alloc/free , new/delete 分配內存。在 C#/Java 中，虛擬機都提供了自動垃圾收集，根據對象的生存周期與引用計數對垃圾對象進行回收。

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

C# 的堆空間大小限制取決于虛擬內存的大小，通常來說 .net 虛擬機并不會限制可用的內存大小，而 java 默認的堆大小在 256M 左右，如果需要使用更大的堆，則需要使用 JVM 的 -Xmx 參數指定堆棧的上限。 java 和 C++ 都采用了分段的堆，在 gc 過程中會移動對象，從而得到更加連續的堆可用內存，更高的空間使用效率。

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

并行的垃圾收集指的是在單獨的線程中執行 GC ，不影響其他的線程執行

串行的垃圾收集： GC 線程將會掛起當前所有的執行線程直到 GC 線程返回。

e)?????? Root Set 與可達集

優化的編譯器可以通過變量的生存周期決定對象在最合適的時候 ( 不會被將要執行的程序引用 ) 回收，但是在常用的算法中，一種簡化的方式更加經常被采用，就是對象根集合與可達集合。因為對象只有通過被引用或者作為全局對象的時候才可以被訪問，所以從全局對象可以導航到所有的活動對象，而其他的對象則被視為無用內存，被 GC 回收。全局對象的集合稱為 Root Set ，而通過導航測試確定垃圾的過程被稱為可達性測試，可以被導航的對象集合被稱為可達集。

?

通常 GC 都包含了垃圾檢測和垃圾回收兩個階段。

?

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

a)?????? Reference Counting( 引用計數 )

引用計數為每一個對象提供了當前被引用的次數。前者顯式的便利了系統中所有的指針得到可用的對象集合，后者便利每一個對象，判斷對象是否仍被引用，即對象是否還將被使用。 RC 的一個重要的好處是它的實時性，因為每一個操作都可以及時地修改對象的 Reference count 。從而在語言的層面上實現 GC 。而且其他的執行進程不需要被掛起。問題是 GC 本身需要占用多余的存儲空間。

Comment: Not always effective, hard to make efficient!

當程序創建一個循環引用關系的時候，環中的對象的引用計數永遠不會降為 0 ，也就永遠無法被回收，這種情況下，引用計數算法將會失效。

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

對象的回收：

RC 為零的對象將會被添加到一個回收鏈表中，等待回收進程回收。

b)?????? Mark-Sweep

標記清掃 (MS) 算法首先通過 Root Set 得到當前的可達集并對相應的對象作出標記 (Mark) ，然后將非可達集添加到回收鏈表中 (Sweep) 。

MS 的第一個問題是它容易造成零碎地內存，小對象往往散步在堆中，造成難以創建大對象。 ( 事實上這個問題對于所有的 GC 算法都存在 )

MS 第二個問題也是它的效率問題，其耗費與堆大小（活動對象與垃圾對象的總合）成正比。

MS 的第三個問題是對象局部性 (locality) ，因為對象不會被移動，造成堆上存在大量空隙。

c)?????? Mark-Compact

標記 - 壓縮算法 (MC) 與 MS 算法的第一步驟相同，在第二步驟中， MC 移動所有的活動對象是他們在堆上相鄰的位置存在，從而形成聯系的空閑內存。這個過程類似于 Windows 的內存碎片整理。

MC 的問題顯而易見，對于大量臨時對象的情況下，其性能遠低于 MS 算法。

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

d)?????? Coping

拷貝回收合并了 MC 算法中的掃描與壓縮兩個過程，它的目標也是將所有的活動對象移動到相鄰的空間中，從而形成連續的可用內存。

最常見的 Coping 算法將堆分為兩個區域，在運行過程中同時僅有一個區域可以被引用。在每一次整理過程中，使用區域的對象將會被拷貝到空閑區域中連續的存儲空間中。 (Cheney) 使用廣度優先的遍歷算法 ( 內存中的引用關系是樹狀的結構 ) 。

Coping 的最大問題是它要求實際需要的近兩倍的內存。增加可用的內存可以顯著的提高 Coping 算法的效率，當可用內存不足的時候， Coping 的次數將會增加，提高 GC 對系統性能的影響。

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

非拷貝隱式的內存收集算法為每一個對象增加了兩個指針和一個顏色域，從而將內存中的所有對象組成了一個雙向鏈表的結構 ( 顏色域標志當前對象處于哪一個內存節點 -bulk 中 ) 。與 Coping 相比，活動對象并不會在整理過程中被移動，所被改動的僅僅是對象的三個附加域。因此對象的回收可以在常數時間內被完成， NCIC 的消耗與系統中的對象的數目成正比。

NCIC 提高了對象遍歷的效率，尤其是大對象的便利效率，但是它無法避免稀疏內存的問題。

f)??????? 基本的 GC 算法可能造成的問題

所有的 GC 算法都存在 Time-Space 的平衡問題，即使主存的價格日益降低， CPU 的速度越來越快，他們仍將按比例的占用系統資源，帶來很多額外的消耗。虛擬內存的存在使得 GC 算法的實現更加困難，因為對象存在于不同的頁面當中，一次簡單的 Coping 可能造成意想不到的大量頁面交換。從而帶來比理論值大的多得消耗。

因此在常用的 GC 實現中，都采用了合并集中算法的擴展的 GC ，我們將在下一部分對擴展的 GC 算法進行論述。

2.?????? 擴展的垃圾收集算法

a)?????? Incremental Tracing Collectors

漸進的遍歷回收 (ITC) 算法要求伴隨程序執行的同時漸進的進行垃圾收集。但是應用程序本身可能在不斷的修改已經被遍歷過的對象，所以 ITC 必須有一個監視這些改變的方法。

?

b)?????? Generational Garbage Collection

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

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

在一個程序中，如果對象在創建后一分鐘仍然沒有被回收，則，該對象很可能還要生存更長的周期， GGC 通過對堆進行劃分，將比較老的對象 Copy 到更高的代中從而實現更加有效的垃圾回收。高代往往采用更高效的 Tracing 算法，而且不會被非常頻繁的收集，這樣可以有效地提高非實時性系統對于 GC 效率的要求，從而使 GC 造成的系統中斷降低到用戶不易覺察的程度。

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

GGC 的主要問題包括：

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

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

?????? Collection Scheduling ：即何時啟動每個代的收集過程

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

?????? 所有這些問題都與具體的應用程序相關，因此通用的解決方案可能難以滿足特定應用的要求。

?

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

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

4.?????? C# 中的垃圾機制機制

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

5.?????? 垃圾收集機制的效率測量

Garbage Collection 的效率比起手動的內存管理，性能上是會有些差距的，具體可能造成多大的影響？

注意：并不是只有自動內存回收的程序語言才會有垃圾回收的消耗，對于 C/C++ 這些手動管理內存的語言，內存分配與釋放也是會造成系統一定的開銷的。

?

6.?????? 實用中的一些建議

自動垃圾收集取代了人工回收棄置內存的回收工作，極大地減少了內存維護方面的工作量，但是在實際的使用中我們必須注意如下一些問題，避免造成系統瓶頸。

避免頻繁地創建臨時指針

減少對象分配的次數，使用對象池的方法

連續存放需要持久使用的對象，避免頻繁地頁面切換。

?

對于 .Net 程序員，學會使用 System Monitor 中的 CLR 性能計數器分析系統的瓶頸所在。CLR Profiler 也是一個很好的實用工具。