大內高手專欄：

.NET 的自動記憶體管理

作者：蔡學鏞

2004 年 4 月

自動記憶體管理也就是俗稱的垃圾收集 (garbage collection，GC)。綜觀近年出現的語言，往往都具備 GC，也因此有越來越多程式員都已經在享用 GC 所帶來的好處了，但是對於這個默默在背後運作的機制，大部分的程式員不太清楚它的原理。本文章以言簡意賅的方式，為各位剖析了 .NET CLR 和 Rotor 的 GC。

Why GC ?

硬碟容量越來越大、記憶體容量也越來越大，大部份的原因在於：軟體體積越來越大。幾百 KB 記憶體就能打發一個程式的時代，已經不復存在。現在軟體內部的組織方式看起來就像是許多物件彼此之間盤根錯節，互相牽扯不清，所以這類軟體的內部指標 (pointer) 管理相當複雜而為人所詬病，也因此容易導致記憶體管理不佳。

計算機科學家一直在尋找最佳的記憶體管理方式，每個人都有自己喜好的方式，長期以來爭論不休。有一個老掉牙的笑話是這麼說的：C 語言的程式員認為記憶體管理太重要了，所以不應該由系統來管理；Lisp 語言的程式員認為記憶體管理太重要了，所以不應該由程式員來管理。對同一件事，有同樣的目的，看法卻可以如此南轅北轍。

有人很反對 GC，他們認為只有程度不夠的人才會將就著使用 GC，他們譏笑 GC 的效率不彰，認為 GC 會導致程式常常「呆住」好一陣子。

有人很贊成 GC，他們認為 GC 可以減低軟體開發過程中的負擔，雖然因此少了一些控制權，但是就像是蜘蛛人 (spiderman) 電影中所說的：「責任伴隨著權力而來」。換言之，想要少負一些責任，就要放棄一些權利。

暫且不理會這些人的說法，而單純地從市場的角度來看，GC 似乎越來越普及了，新一代的語言，諸如：Eiffel、Python、Ruby、Java、C#，都是支援 GC 的，究竟這樣的趨勢是怎麼造成的？

GC 受歡迎其來有自。首先，GC 已非吳下阿蒙，經過這些年的演進，非但硬體效率提升可以讓 GC 的接受度提高，連 GC 演算法也更聰明、快速，更甚以往。況且，開發現代化軟體是很複雜的事，程式員總是希望能把時間精力花在刀口上，系統能代勞的事，能別插手就別插手。畢竟，自行管理記憶體可不是一件易如反掌的小事，一個不小心還可能捅出大摟子。研究顯示，C++ 專案有超過 50% 的開發時間在處理記憶體相關的議題。所以，在這個時代，多數應用軟體的開發都有必要透過系統自動的 GC 機制。

GC 不只是給程式員帶來方便，也讓系統變得的可靠，即使遇到 bug 或惡意搞破壞的程式所導致的錯誤仍可回復。大多數的時候，.NET CLR 以及 JVM 都可以讓程式員拋棄記憶體管理的重擔，也因此不再有直接處理記憶體位置的必要，間接地，對於安全 (Security) 的提升也有助益。

記憶體配置種類

記憶體配置方式可以概略地分成三種，分別是：

• 靜態配置 (static allocation)：是最早出現的記憶體配置方式，將記憶體區域綁到 (bind) 某個名稱，一直到程式結束為止。這類的記憶體，常被稱為全域變數 (global variables)。
• 堆疊配置 (stack allocation)：堆疊配置使用在堆疊框 (stack frame) 中，記憶體配置的生命週期受到其區塊範圍 (block scope) 的影響，當進入區塊時，會自動配置記憶體，當離開此區塊，記憶體配置也隨之消失。這類的記憶體，常被稱為區域變數 (local variables)。
• 動態配置 (dynamic allocation)：動態配置可以隨時配置，隨時釋放。配置當然是由程式員負責，但是釋放則有不同的作法。對於 C/C++ 這一類傳統的系統語言來說，釋放仍是由程式員負責；對於 Java 與 C# 這類 VM-based 現代語言來說，釋放是由 VM (虛擬機)負責。這種用來進行動態配置的記憶體，稱為 heap。請注意，這裡 heap 和資料結構的 heap 沒有任何關係。

上述三種方式，哪一種最好？簡單地說，耗費的記憶體成本比越低越好，也就是說「越慢配置，越早釋放」最好。堆疊配置的速度又快，配置的時間點又很晚，釋放的時間點又很早，一切全自動所以程式員的負擔又很輕，諸多優點使得堆疊配置成為最佳選擇。禍福相倚，堆疊配置的記憶體也因此受到範圍的影響，嚴重地限制了程式上的彈性。所以我們有時候必須使用動態配置。只有在堆疊配置與動態配置都不適合的情況下，才使用靜態配置。

物件的記憶體究竟要如何配置，其實這方面深深受到物件生命期的影響。以.NET來說，緒 (thread) 以及應用域 (application domain) 等程式的控制結構 (control structure) 都有各自的方式來管理物件的生命期和記憶體：緒利用堆疊方式來儲存資料，應用域利用靜態方式來儲存資料。儲存的方式由這些機制所決定，然而元件生命期和資源配置必須與控制結構的生命期一致，但是有些情況下勢必無法做到這一點。還好，除了堆疊和靜態配置，我們還可以在heap進行動態配置，控制物件的生命期。

在動態配置的作法中，如果是由程式員控制記憶體的釋放，會造成一些問題：

• 應該釋放的時候忘了釋放，造成「記憶體漏失」(memory leak)：程式執行時會一點一滴地把記憶體吃光。
• 不應該釋放的時候卻釋放了，造成「懸空指標」(dangling pointer)。一般咸認為，這是最糟糕的事。

在動態配置的作法中，如果是由 GC 負責控制記憶體的釋放，就不會有這些問題了。下一節簡單地介紹一個最常用的 GC 演算法，並以一個範例以為說明。

標記、清掃、縮併

.NET CLR、Rotor 以及許多 Java VM 的 GC 都使用「標記、清掃、縮併」的演算法。

GC 會追蹤 (tracing) 所有活著的物件。那些不是活著的物件就是該被 GC 清除的垃圾。追蹤活著物件的方式，就是到所有的靜態配置、動態配置、以及堆疊配置的物件內找尋看看有那些指向heap的指標，每找到一個指標 (pointer)，都要順著再繼續找下去，以找出更多的指標，一直到全部找過一遍為止，這就叫做沿著根指標追蹤 (tracing the roots)。根指標的取得方式比較複雜，牽涉到 JIT Compiler 等 .NET CLR 的子系統 (sub-system)，所以本文章不對此部分進行說明。

在追蹤期間，活著的物件被標記起來，然後未用的記憶體就可以被掃除，這個方法就稱為標記且清掃 (mark and sweep collection)。

標記且清掃的作法固然簡單又有效，但是一段時間之後記憶體就會支離破碎，出現許多縫隙，容易導致記憶體不夠用。為瞭解決此問題，我們可以採用縮併收集 (compacting collection) 的方式。最簡單的縮併手法是：移除垃圾物件騰出空位之後，將下一個活著的物件往前搬移到此位置，緊鄰著上一個活著的物件。物件只要有被搬移，就必須把所有參考到此物件的指標也更新成新的位址。如此的縮併收集等於是把所有可用的記憶體通通集中在一起，放在 heap 的後面，連帶造成的正面效益是：後續建立的數個物件都可以集中在一起。如此的記憶體區域性 (locality)，可以減少虛擬記憶體的 paging，對於執行效率很有幫助。

通常程式中會充斥著許多短命物件，當物件的「存活率」不高時，縮併收集尤其能發揮效益，因為搬移的次數少，且縮併出來的空間大。試想，當物件一口氣全死光了，連一次的搬移都不必了。

為了幫助理解，下面以一個簡單的範例作為說明：

1. 一開始 heap 是空的

2. 配置一個物件 A

3. 配置一個物件 B

4. 依序配置物件 C、D、E、F、G、H、I

5. 配置一個物件 J

6. 當準備配置一個物件 K 時，發現所耗費的記憶體已經超過段落限定的大小 (下一節會介紹何為段落)，所以無法配置成功。必須開始進行 GC，然後才能配置 K。GC 的第一步驟是：假設一切都是垃圾。

7. 開始沿著根節點追蹤

8. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

9. 追蹤到根節點 D

10. 透過根節點 D，追蹤到 H

11. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

12. 追蹤到根節點 C

13. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

14. 追蹤到根節點 F

15. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

16. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

17. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

18. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

19. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

20. 更新 NextObjPtr 指標。

21. 終於完成了 GC。配置新物件 K。

22. 配置一個物件 A

23. 配置一個物件 B

24. 依序配置物件 C、D、E、F、G、H、I

25. 配置一個物件 J

26. 當準備配置一個物件 K 時，發現所耗費的記憶體已經超過段落限定的大小 (下一節會介紹何為段落)，所以無法配置成功。必須開始進行 GC，然後才能配置 K。GC 的第一步驟是：假設一切都是垃圾。

27. 開始沿著根節點追蹤

28. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

29. 追蹤到根節點 D

30. 透過根節點 D，追蹤到 H

31. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

32. 追蹤到根節點 C

33. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

34. 追蹤到根節點 F

35. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

36. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

37. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

38. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

39. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

40. 更新 NextObjPtr 指標。

41. 終於完成了 GC。配置新物件 K。

42. 配置一個物件 B

43. 依序配置物件 C、D、E、F、G、H、I

44. 配置一個物件 J

45. 當準備配置一個物件 K 時，發現所耗費的記憶體已經超過段落限定的大小 (下一節會介紹何為段落)，所以無法配置成功。必須開始進行 GC，然後才能配置 K。GC 的第一步驟是：假設一切都是垃圾。

46. 開始沿著根節點追蹤

47. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

48. 追蹤到根節點 D

49. 透過根節點 D，追蹤到 H

50. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

51. 追蹤到根節點 C

52. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

53. 追蹤到根節點 F

54. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

55. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

56. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

57. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

58. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

59. 更新 NextObjPtr 指標。

60. 終於完成了 GC。配置新物件 K。

61. 
    圖 1

62. 依序配置物件 C、D、E、F、G、H、I

63. 配置一個物件 J

64. 當準備配置一個物件 K 時，發現所耗費的記憶體已經超過段落限定的大小 (下一節會介紹何為段落)，所以無法配置成功。必須開始進行 GC，然後才能配置 K。GC 的第一步驟是：假設一切都是垃圾。

65. 開始沿著根節點追蹤

66. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

67. 追蹤到根節點 D

68. 透過根節點 D，追蹤到 H

69. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

70. 追蹤到根節點 C

71. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

72. 追蹤到根節點 F

73. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

74. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

75. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

76. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

77. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

78. 更新 NextObjPtr 指標。

79. 終於完成了 GC。配置新物件 K。

80. 配置一個物件 J

81. 當準備配置一個物件 K 時，發現所耗費的記憶體已經超過段落限定的大小 (下一節會介紹何為段落)，所以無法配置成功。必須開始進行 GC，然後才能配置 K。GC 的第一步驟是：假設一切都是垃圾。

82. 開始沿著根節點追蹤

83. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

84. 追蹤到根節點 D

85. 透過根節點 D，追蹤到 H

86. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

87. 追蹤到根節點 C

88. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

89. 追蹤到根節點 F

90. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

91. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

92. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

93. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

94. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

95. 更新 NextObjPtr 指標。

96. 終於完成了 GC。配置新物件 K。

97. 當準備配置一個物件 K 時，發現所耗費的記憶體已經超過段落限定的大小 (下一節會介紹何為段落)，所以無法配置成功。必須開始進行 GC，然後才能配置 K。GC 的第一步驟是：假設一切都是垃圾。

98. 開始沿著根節點追蹤

99. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

100. 追蹤到根節點 D

101. 透過根節點 D，追蹤到 H

102. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

103. 追蹤到根節點 C

104. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

105. 追蹤到根節點 F

106. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

107. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

108. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

109. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

110. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

111. 更新 NextObjPtr 指標。

112. 終於完成了 GC。配置新物件 K。

113. 
     圖 2

114. 開始沿著根節點追蹤

115. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

116. 追蹤到根節點 D

117. 透過根節點 D，追蹤到 H

118. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

119. 追蹤到根節點 C

120. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

121. 追蹤到根節點 F

122. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

123. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

124. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

125. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

126. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

127. 更新 NextObjPtr 指標。

128. 終於完成了 GC。配置新物件 K。

129. 追蹤到根節點 A，A 是末稍節點，回到下一個根節點

130. 追蹤到根節點 D

131. 透過根節點 D，追蹤到 H

132. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

133. 追蹤到根節點 C

134. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

135. 追蹤到根節點 F

136. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

137. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

138. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

139. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

140. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

141. 更新 NextObjPtr 指標。

142. 終於完成了 GC。配置新物件 K。

143. 
     圖 3

144. 追蹤到根節點 D

145. 透過根節點 D，追蹤到 H

146. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

147. 追蹤到根節點 C

148. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

149. 追蹤到根節點 F

150. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

151. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

152. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

153. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

154. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

155. 更新 NextObjPtr 指標。

156. 終於完成了 GC。配置新物件 K。

157. 透過根節點 D，追蹤到 H

158. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

159. 追蹤到根節點 C

160. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

161. 追蹤到根節點 F

162. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

163. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

164. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

165. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

166. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

167. 更新 NextObjPtr 指標。

168. 終於完成了 GC。配置新物件 K。

169. 
     圖 4

170. 透過 H，追蹤到 J。J 是末稍節點，回到下一個根節點

171. 追蹤到根節點 C

172. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

173. 追蹤到根節點 F

174. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

175. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

176. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

177. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

178. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

179. 更新 NextObjPtr 指標。

180. 終於完成了 GC。配置新物件 K。

181. 追蹤到根節點 C

182. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

183. 追蹤到根節點 F

184. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

185. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

186. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

187. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

188. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

189. 更新 NextObjPtr 指標。

190. 終於完成了 GC。配置新物件 K。

191. 
     圖 5

192. 透過根節點 C，追蹤到 D。D 雖然非末稍節點，但是 D 已經被標記過了，所以 D 往下的節點都已經被標記過了。不用繼續從 D 追蹤下去，回到下一個根節點。

193. 追蹤到根節點 F

194. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

195. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

196. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

197. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

198. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

199. 更新 NextObjPtr 指標。

200. 終於完成了 GC。配置新物件 K。

201. 追蹤到根節點 F

202. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

203. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

204. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

205. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

206. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

207. 更新 NextObjPtr 指標。

208. 終於完成了 GC。配置新物件 K。

209. 
     圖 6

210. 全都追蹤完了，沒被標記的物件就是垃圾，開始清掃。

211. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

212. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

213. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

214. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

215. 更新 NextObjPtr 指標。

216. 終於完成了 GC。配置新物件 K。

217. 掃除 B，搬移 CD。由於 CD 被搬移，所以必須更新指向 CD 的根節點指標、並更新指向 D 的 C 指標。

218. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

219. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

220. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

221. 更新 NextObjPtr 指標。

222. 終於完成了 GC。配置新物件 K。

223. 
     圖 7

224. 掃除 E，搬移 F。由於 F 被搬移，所以必須更新指向F的根節點指標。

225. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

226. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

227. 更新 NextObjPtr 指標。

228. 終於完成了 GC。配置新物件 K。

229. 掃除 G，搬移 H。由於 H 被搬移，所以必須更新指向H的根節點指標、並更新指向 H 的 D 指標。

230. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

231. 更新 NextObjPtr 指標。

232. 終於完成了 GC。配置新物件 K。

233. 
     圖 8

234. 掃除 I，搬移 J。由於 J 被搬移，所以必須更新指向 J 的 H 指標。

235. 更新 NextObjPtr 指標。

236. 終於完成了 GC。配置新物件 K。

237. 更新 NextObjPtr 指標。

238. 終於完成了 GC。配置新物件 K。

239. 
     圖 9

240. 終於完成了 GC。配置新物件 K。

241. 
     圖 10

縮併收集的另一種變形是複製收集 (copying collection) 作法是將活著的物件搬到一個全新的 heap，然後將舊的 heap 內的東西全都丟掉，變成下次的新 heap。

和只用一個 heap 的作法比起來，複製收集的方式有數個優點：因為所有的物件都會被複製到新的 heap，在配置新物件時變得很簡單，不需要尋找最適合容納的記憶體空位，直接就可以配置。而且，因為縮併到新的 heap，可以具備不錯的記憶體區域性。複製收集主要的缺點是：複製物件以及修改指標的代價太高，而且因為使用兩個 heap，所以需要的記憶體空間比原來多出一倍。

世代收集

透過引進世代收集 (generational collection) 的技術，收集的成本是可以被有效地降低的 (或者說是分次攤還)。世代收集的方式將物件隨著時間先後的次序分成多個世代，世代收集比起前述的各種方法都來得更複雜，但是已經被大多數的 GC 所採用了，因為它通常所耗費的時間比其其他方式更短 (畢竟不是整個 heap 都要被處理，不是全部的物件都需要被複製)。因為使用方式的差異，所以物件的生命長短不一，有些很長，有些則很短，而世代收集則利用了這一點特性。除了生命長短不同，物件的體積也不盡相同。將 heap 切割成不同的區域，不同區域放置不同特性的物件，不同的區域使用不同的頻率來進行 GC，如此一來對於 CPU 和記憶體的運用會更有效益。

heap 分成數個段落 (segment)，從年老段落到年輕段落。活越久的物件，就會出現在越年老的段落中。段落的年齡次序不見得和位址次序相同，因為段落是視需要而取得的虛擬記憶體，而且 GC 演算法也不需要世代之間保有位元址次序。在 heap 加入新的區段之後，物件會被建立到此一新的區段。Rotor 和 .NET CLR 的作法總是將最新建立的段落當作最新的世代，一個世代只用一個段落。每個 heap 段落內的物件，可被視為相同年紀。Rotor 只使用兩個世代，.NET CLR 則使用三個世代。

請注意：最老的物件「通常」可以在最低的位址處發現，但是不保證一定是如此，因為被釘住物件 (pinned objects) 會導致次序改變。所謂的被釘住物件，指的是有特殊理由而不能被搬移的物件。.NET 允許物件被釘住，但是 Java 則否。

如果純粹採用世代收集的方法，物件一開始會被配置在最年輕的世代。經過一段時間之後依然存活的物件，會被升級到新的世代 (搬移到新的世代)，這種技巧加諸於縮併收集可以帶來很大的好處。年輕世代的存活率很低，年老世代的存活率很高，因為不同的世代被置於不同的位置，所以不同的世代可以採用不同的作法來進行 GC。年老世代不太適合使用壓縮收集，因為存活率太高了，搬移的效益不高 (縫隙不大)，但成本很高 (要搬移太多次)。但是，在最年輕的世代，縮併搬移的作法就相當適合。

Rotor 使用調適性世代 (adaptive generation) 的方式來進行 GC，它使用了兩個世代，正因為兩個世代，所以有時候也稱為半空間 (semi-space)。除此之外，Rotor 也會特別隔離大型物件。當配置空間或記憶體滿了，就會驅動 GC；當 heap 的空間所剩無幾，就會沿著跟指標追蹤，可以收集一個世代或同時收集兩個世代的垃圾，可以視情況決定縮併與否。

為了幫助理解，下面以一個簡單的範例來說明世代收集：

1. 程式執行的過程，產生了物件 ABCDE，它們歸屬於 0 世代。

2. 經過一段時間之後，CE 變成垃圾。對於 0 世代進行 GC 之後，只剩下 ABD，將 ABD 升級一個世代，成為 1世代。

3. 程式繼續執行，產生了物件 FGHIJK，它們歸屬於 0世代。

4. 經過一段時間之後，HJ 變成垃圾。對於 0 世代進行 GC 之後，只剩下 FGIK，將 FGIK 升級一個世代，併入 1 世代。

5. 程式繼續執行，B 變成垃圾，但未被清除，因為 B 是屬於 1 世代。

6. 程式繼續執行，產生了物件 LMNO，它們歸屬於 0 世代。經過一段時間之後，GLM 變成垃圾。現在的垃圾有 1 世代的 BG，以及 1 世代的 LM。

7. 對於 0 世代進行 GC，但是不對 1 世代進行 GC，因為 1 世代佔用體積尚未達到世代限制。GC 之後，0 世代只剩下 NO，將 NO 升級一個世代，併入 1 世代。

8. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

9. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

10. 經過一段時間之後，CE 變成垃圾。對於 0 世代進行 GC 之後，只剩下 ABD，將 ABD 升級一個世代，成為 1世代。

11. 程式繼續執行，產生了物件 FGHIJK，它們歸屬於 0世代。

12. 經過一段時間之後，HJ 變成垃圾。對於 0 世代進行 GC 之後，只剩下 FGIK，將 FGIK 升級一個世代，併入 1 世代。

13. 程式繼續執行，B 變成垃圾，但未被清除，因為 B 是屬於 1 世代。

14. 程式繼續執行，產生了物件 LMNO，它們歸屬於 0 世代。經過一段時間之後，GLM 變成垃圾。現在的垃圾有 1 世代的 BG，以及 1 世代的 LM。

15. 對於 0 世代進行 GC，但是不對 1 世代進行 GC，因為 1 世代佔用體積尚未達到世代限制。GC 之後，0 世代只剩下 NO，將 NO 升級一個世代，併入 1 世代。

16. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

17. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

18. 程式繼續執行，產生了物件 FGHIJK，它們歸屬於 0世代。

19. 經過一段時間之後，HJ 變成垃圾。對於 0 世代進行 GC 之後，只剩下 FGIK，將 FGIK 升級一個世代，併入 1 世代。

20. 程式繼續執行，B 變成垃圾，但未被清除，因為 B 是屬於 1 世代。

21. 程式繼續執行，產生了物件 LMNO，它們歸屬於 0 世代。經過一段時間之後，GLM 變成垃圾。現在的垃圾有 1 世代的 BG，以及 1 世代的 LM。

22. 對於 0 世代進行 GC，但是不對 1 世代進行 GC，因為 1 世代佔用體積尚未達到世代限制。GC 之後，0 世代只剩下 NO，將 NO 升級一個世代，併入 1 世代。

23. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

24. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

25. 
    圖 11

26. 經過一段時間之後，HJ 變成垃圾。對於 0 世代進行 GC 之後，只剩下 FGIK，將 FGIK 升級一個世代，併入 1 世代。

27. 程式繼續執行，B 變成垃圾，但未被清除，因為 B 是屬於 1 世代。

28. 程式繼續執行，產生了物件 LMNO，它們歸屬於 0 世代。經過一段時間之後，GLM 變成垃圾。現在的垃圾有 1 世代的 BG，以及 1 世代的 LM。

29. 對於 0 世代進行 GC，但是不對 1 世代進行 GC，因為 1 世代佔用體積尚未達到世代限制。GC 之後，0 世代只剩下 NO，將 NO 升級一個世代，併入 1 世代。

30. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

31. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

32. 程式繼續執行，B 變成垃圾，但未被清除，因為 B 是屬於 1 世代。

33. 程式繼續執行，產生了物件 LMNO，它們歸屬於 0 世代。經過一段時間之後，GLM 變成垃圾。現在的垃圾有 1 世代的 BG，以及 1 世代的 LM。

34. 對於 0 世代進行 GC，但是不對 1 世代進行 GC，因為 1 世代佔用體積尚未達到世代限制。GC 之後，0 世代只剩下 NO，將 NO 升級一個世代，併入 1 世代。

35. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

36. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

37. 程式繼續執行，產生了物件 LMNO，它們歸屬於 0 世代。經過一段時間之後，GLM 變成垃圾。現在的垃圾有 1 世代的 BG，以及 1 世代的 LM。

38. 對於 0 世代進行 GC，但是不對 1 世代進行 GC，因為 1 世代佔用體積尚未達到世代限制。GC 之後，0 世代只剩下 NO，將 NO 升級一個世代，併入 1 世代。

39. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

40. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

41. 
    圖 12

42. 對於 0 世代進行 GC，但是不對 1 世代進行 GC，因為 1 世代佔用體積尚未達到世代限制。GC 之後，0 世代只剩下 NO，將 NO 升級一個世代，併入 1 世代。

43. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

44. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

45. 程式繼續執行，產生了物件 PQRS，隨後 0 世代的 ABGK 以及 1 世代的 PR 變成垃圾。

46. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

47. 由於 0 世代和 1 世代的體積都已經達到各自的世代限制，所以同時對兩個世代進行 GC。1 世代剩下 DFINO，升級為 2 世代。0 世代剩下 QS，升級為 1 世代。

48. 
    圖 13

外部資源管理

事實上，Java 和 C# 程式員就算不懂 GC 的內部作法，影響並不大。程式員只要注意下面兩件事，即可在大多數的情況下讓 GC 發揮效率：

• 不用的指標要及早設定為 null，以在下一次的 GC 中被清除。
• 許多程式員製造了大量的短命物件，仍然渾然未覺。例如：Java 和 C# 的「字串加法」，C# 語法允許自動地 box (也就是自動地把 value type 轉成 reference type)。

倒也不是說程式員就可以因此高枕無憂。GC 可以讓程式員免於注意記憶體管理細節，但是 GC 的觸角並未伸及外部資源管理，畢竟外部資源的生命期超出 VM 的掌控，而是由 OS 來掌控。甚至，GC 的存在，會使得資源釋放的問題益形複雜。所以，對於外部資源管理，程式員必須戒慎恐懼。

這裡所謂的外部資源包括了檔案、視窗代號 (window handle)、網路 socket…等。從程式員的觀點來看，那些代表外部資源，或者使用外部資源的類別，必須要能取得或釋放資源。以檔案為例，用來代表外部檔案資源的類別，必須能取得其檔案代號 (file handle)，必須能呼叫 close() 來關閉檔案。資源的取得很簡單，只要寫在 constructor 內就行了；資源的釋放卻很麻煩，因為在 GC 插手的情況下，程式員不能主動去釋放物件。

但是無論如何，系統還是得提供一個方法讓我們釋放外部資源，而對於 .NET 和 Java 來說，清除資源的過程稱為終結 (finalization)。簡單地說，終結就是：VM 呼叫物件的某 method 來釋放外部資源。在 VM 發現物件變成垃圾之後，且物件記憶體被釋放之前，這個空檔正是物件被終結的好時機。

.NET 有個名為 Finalize() 的 ethod (Java 也有類似的 method)，不需要傳入參數和傳出值，它做的正是終結的事。當 .NET CLR GC 運作時，如果發現某物件有提供 Finalize()，GC 就會呼叫它。被標示為垃圾，且必須被 CLR 終結的物件，會被紀錄在終結佇列 (finalization queue) 中。

請注意：不是所有的物件都必須被終結，只有那些有提供 Finalize() 來釋放外部資源者，才需要被終結。如果沒有外部資源，就不要提供 Finalize()，就不會被終結。當可終結的物件一被建立，立刻會被紀錄在一個弱參考清單 (weak reference list) 中。GC 會監視著此清單，當所有指向某「可終結物件」的強參考 (strong reference) 被釋放，GC 就會立刻將此物件的參考從弱參考清單中轉送到終結佇列 (finalization queue)，物件持續活著。終結緒 (finalization thread) 每隔一陣子會一一造訪佇列中的物件，然後呼叫每個物件的終結方法 (finalization method)。如果在終結的過程中，該物件沒有再度被強參考所參考到，此參考於是終於被釋放，而物件也會依正常方式回收。

請注意：終結不是一個萬無一失的作法，在許多情況下，程式員必須小心配合，以達到最佳的資源管理。GC 發生的時間是由演算法和系統的負荷所決定，也因此，有時候我們有需要改用傳統的處置方式 (disposal pattern)，而不要完全依賴剛剛所提的終結機制。也就是說，程式員需要明白地呼叫 Dispose() 或 Close() 來「關閉」資源。

提醒各位，不管是 Java 或 .NET，在終結時，都有可能造成物件「死而復生」。這個議題很複雜，感興趣的讀者可以閱讀 Weak Reference 相關的資料。

結論

除了上述的 GC 之外，Java 和 .NET 其實還有另一個全然不同的 GC，用來管理分散式運算 (distributed computing) 的物件生命週期，但是這不在本文討論範圍。

另外，執行時 JIT 編譯所產生原生碼 (native code)，也會佔用記憶體，畢竟新產生的原生碼總得放在某個地方吧！儘管 metadata 必須一直處於隨時可用的狀態，method 卻不然，method 可以隨著需要而編譯產生。每次需要執行某 method，就編譯一次，卻不管先前編譯過與否，這會降低整體執行效率，但可以節省記憶體 (因為不需要儲存先前的編譯結果)，且可能會有較佳的地域性 (locality)。

Rotor 所使用的 JIT 編譯器在這兩種作法之間取得折衷點，這就叫做程式碼丟棄 (code pitching)，也算是 GC 的一種形式，只不過回收的不是資料，而是程式。當編譯出來的程式碼超過 code heap 的最大容量，緩衝區內的全部內容就會被丟棄 (pitch)，而堆疊內的全部返回位元址都被改成 JIT 編譯器的位址，這使得後續的所有 method 都會被重新編譯。作法同 GC 一樣，什麼 method 的程式碼該被丟棄，考量因素有許多，例如：原生碼的體積、IL 轉成原生碼所膨脹的比率，或者需要耗費 JIT 的時間…等，這些都可以作為考量。

不管是本地物件的 GC，遠端物件的 GC，還是原生碼的 GC，都是很複雜的主題。GC 固然複雜，但是這一切都是值得的，對於程式的可靠度和生產力提升都有幫助。如果你對此主題感興趣，你可以去研究 Rotor 和 JVM 的 Source Code，以及 Richard Jones 所著的 Garbage Collection: Algorithms for Automatic Dynamic Memory Management 一書。

意見與支援

 您有任何問題、意見或建議嗎？您可以透過下列電子郵件與作者連絡：
 xy.cai@msa.hinet.net

更多資訊

想知道大內高手專欄的其他文章嗎？請至此專欄所有列表