在上篇我們主要對 C# 的記憶體分區及垃圾回收機制進行簡單的介紹，在這篇中我們將介紹 Mark-Sweep 演算法如何達成清理記憶體的目標。   無論任何垃圾回收演算法，皆需包含兩大部分：

1. 必須能搜尋無相關參考的物件。
2. 必須要能對占用空間的垃圾物件進行回收的動作。

Mark and Sweep 演算法也不例外，在此演算法中，第一部分稱為 Mark Phase，遍歷所有參考物件並標記哪些仍在使用、哪些沒有；第二部分則稱為 Sweep Phase，清除在上一步驟備標記為未使用的物件，釋放記憶體空間。

一、Mark Phase 假設一個前提：在 Heap 儲存區的所有物件都是可以回收的，當一個物件創建出來時先給予標記為 false，在進入垃圾回收階段時會由 Root 為起點，以深度優先搜尋演算法（Depth First Search）對所有物件進行逡巡的動作，並將過程中可搜尋到的物件標記為 true。Root 是一個物件的參考，可由局域變數直接存取，在一般狀況下，同一組完整的圖我們通常假設只會有一個 Root 存在。.NET 中的垃圾回收機制的 Root List 交由 JIT Compiler 和 Run Time 維護管理，進行垃圾回收時將遍歷此清單中的所有 Root 進行標記。  

圖一

二、Sweep Phase 此階段的目的是掃描並清除在上階段中 Heap 區域無法觸及的物件，根據在上一階段曾進行過物件的標記結果，將未被搜尋到、狀態為 False 的物件從記憶中釋放，並將上階段判定為 True 的物件重置狀態。  

  Mark and Sweep 演算法有幾項優缺點，優點是這項演算方式從根本迴避了進入無窮迴圈的可能性，同時不需要消耗額外的資源（例如指標的分配等等）；缺點是在進行 Heap 記憶體區塊的遍歷時會暫停其它執行中的程序，並且會造成記憶體的破碎。原因是在經過幾次上述的二階段循環之後，被清乾淨的物件和未被清掉的物件使的記憶體分配變得不連續，進而造成空間的浪費。如圖二所示，空白的部分代表未使用的記憶體空間，藍色代表已使用的記憶體，橘黃色則代表背標記的內容：

圖二

因此在垃圾回收的程序中，做完 Mark and Sweep 之後還會進行壓縮整理，此階段稱為稱之為 Compact，將仍存在於 Heap 記憶體中較細碎的物件移動到頂端成為連續的使用空間，藉此達到減少記憶體碎片的效果。所謂細碎的定義為所儲存的物件佔據空間小於 85 KB，此類物件稱為SOH（Small Object Heap），相對之下大於 85 KB 的物件稱為 LOH（Large Object Heap）。整理 LOH 會花費較多的資源與時間，因此一般的預設狀況下是只針對 SOH 作壓縮。順帶一題，自 .NET Framework 4.5.1 之後的版本可藉由 GCSettings.LargeObjectHeapCompactionMode property 控制是否將 LOH 加入壓縮步驟的目標。

而物件在記憶體中的位置移動之後，所有參考的指標也須進行指標修復，重新設定指向的記憶體位置，以免造成錯誤的結果。   在某些特定狀況下，垃圾回收機制會在單獨的 Thread 上執行：  

• 作業系統警告可用記憶體過低。
• 目標物件使用的 Heap 記憶體超過特定門檻值。
• 在程式碼中呼叫了 GC.Collect() 函式。

通常，在一般狀況下 GC.Collect() 不會被直接呼叫，只有在需要處理錯誤的情境下才會直接被使用。但在某些例外狀況，例如一些記憶體分析軟體中，會在使用者觀看結果之前強制呼叫，便於使用者檢查在進行垃圾回收之後是否仍有 Memry Leaks 或相關問題存在，這種使用方式也屬於合理的使用範圍。

另外，當垃圾回收機制開始運行，在預設的狀況下除了觸發回收的 Thread 以外，其他的 Threads 將會停止運作，可以藉由將垃圾回收設定為工作站或伺服器模式，使其同步、或是在背景中執行。   在這篇文章中我們介紹了在 C# 及 .NET 中，基本的垃圾回收機制運行原理：標記－清理－壓縮三步驟，在下一篇我們將討論關於分代垃圾回收機制（Generational Garbage Collection）的概念。  

參考資料：

https://chodounsky.net/2017/05/03/garbage-collection-in-c-sharp/ https://plumbr.io/handbook/garbage-collection-algorithms https://docs.microsoft.com/en-us/dotnet/standard/garbage-collection/fundamentals https://docs.microsoft.com/zh-tw/dotnet/api/system.gc.collect?view=netframework-4.8