在上篇我們主要對 C# 的記憶體分區及垃圾回收機制進行簡單的介紹，在這篇中我們將介紹 Mark-Sweep 演算法如何達成清理記憶體的目標。
無論任何垃圾回收演算法，皆需包含兩大部分：
- 必須能搜尋無相關參考的物件。
- 必須要能對占用空間的垃圾物件進行回收的動作。
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 進行標記。
MarkPhase(root) If targetNode(root) = false then targetNode(root) = true For each node referenced by root MarkPhase(node)
圖一
二、Sweep Phase
此階段的目的是掃描並清除在上階段中 Heap 區域無法觸及的物件，根據在上一階段曾進行過物件的標記結果，將未被搜尋到、狀態為 False 的物件從記憶中釋放，並將上階段判定為 True 的物件重置狀態。
Sweep() For each object in heap If targetNode(object) = true targetNode(object) = false else heap.release(object)
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