常見的垃圾回收算法原理及其模擬實現

1.標記 - 清除（Mark - Sweep）算法：

這是一種基礎的垃圾回收算法。首先標記所有可達的對象，然后清除未被標記的對象。
缺點是會產生內存碎片。

原理：

如下圖分配一段內存，假設已經存儲上數據了

標記所有可達對象
清除未標記的對象，然后重置標記

模擬實現代碼:

實現GCObject類：

 internal class GCObject{private List<GCObject> referencesObjs;public bool Marked { get; set; }public List<GCObject> ReferencesObjs { get => this.referencesObjs; }public string Name { get; private set; }public GCObject(string name) {referencesObjs = new List<GCObject>();Name = name;}public void AddReference(GCObject obj){referencesObjs.Add(obj);}}

實現GC回收類：

   internal class MarkSweepGC{private List<GCObject> _heap;public MarkSweepGC(){_heap = new List<GCObject>();}// 分配新對象到堆public GCObject CreateObject(string name){var obj = new GCObject(name);_heap.Add(obj);return obj;}public void Collect(params GCObject[] roots){// 標記階段void Mark(GCObject obj){ if (!obj.Marked){obj.Marked = true;foreach (var child in obj.ReferencesObjs) Mark(child);}}foreach (var root in roots) Mark(root);// 清除階段_heap.RemoveAll(obj =>{if (!obj.Marked && !obj.Name.Equals("root")) Console.WriteLine($"回收 {obj.GetHashCode()},{obj.Name}");return !obj.Marked;});// 重置標記_heap.ForEach(obj => obj.Marked = false);}}

?實現測試類：創建一些內存節點，將gc2及其子節點標記

/// <summary>
/// 標記清除算法測試
/// </summary>
static void MarkSweepGCTest()
{var gcCollector = new MarkSweepGC();GCObject root = gcCollector.CreateObject("root");GCObject gc2 = gcCollector.CreateObject("gc2");GCObject gc3 = gcCollector.CreateObject("gc3");GCObject gc4 = gcCollector.CreateObject("gc4");root.AddReference(gc2);gc2.AddReference(gc3);gc2.AddReference(gc4);GCObject gc5 = gcCollector.CreateObject("gc5");GCObject gc6 = gcCollector.CreateObject("gc6");GCObject gc7 = gcCollector.CreateObject("gc7");root.AddReference(gc5);gc5.AddReference(gc6);gc5.AddReference(gc7);gcCollector.Collect(gc2);
}

結果：

2.復制（Copying）算法：

將內存分為兩塊，每次只使用其中一塊。當進行垃圾回收時，將存活對象復制到另一塊內存中，然后清空原來的內存塊。
優點是不會產生內存碎片，缺點是內存使用率只有 50%。

原理：

將內存分成兩塊，假設其中已經存儲上數據了

將存活的對象標記
將存活對象和根對象賦值到target內存區，并重置標記

模擬實現代碼:

GCObject類：同上

CopyingGC類：

 internal class CopyingGC{private List<GCObject> _fromSpace;private List<GCObject> _toSpace;private bool _isFromActive = true;public CopyingGC() { _fromSpace = new List<GCObject>();_toSpace = new List<GCObject>();}// 分配對象到當前活動區public GCObject CreateObject(string name){var obj = new GCObject(name);(_isFromActive ? _fromSpace : _toSpace).Add(obj);return obj;}public void Collect(params GCObject[] roots){var active = _isFromActive ? _fromSpace : _toSpace;var target = _isFromActive ? _toSpace : _fromSpace;target.Clear();var marked = new HashSet<GCObject>();void Mark(GCObject obj){if (obj == null || marked.Contains(obj)) return;marked.Add(obj);foreach (var child in obj.ReferencesObjs) Mark(child);}foreach (var root in roots) Mark(root);// 復制存活對象到目標區foreach (var obj in active){if (marked.Contains(obj) || obj.Name.Equals("root")) target.Add(obj);}// 交換區域_isFromActive = !_isFromActive;Console.WriteLine($"GC完成，存活對象數：{target.Count}");foreach (var child in target){Console.WriteLine($"存活對象： {child.GetHashCode()},{child.Name}");}}}

CopyingGCTest類：

/// <summary>
/// 復制算法測試
/// </summary>
static void CopyingGCTest()
{var gcCollector = new CopyingGC();GCObject root = gcCollector.CreateObject("root");GCObject gc2 = gcCollector.CreateObject("gc2");GCObject gc3 = gcCollector.CreateObject("gc3");GCObject gc4 = gcCollector.CreateObject("gc4");root.AddReference(gc2);gc2.AddReference(gc3);gc2.AddReference(gc4);GCObject gc5 = gcCollector.CreateObject("gc5");GCObject gc6 = gcCollector.CreateObject("gc6");GCObject gc7 = gcCollector.CreateObject("gc7");root.AddReference(gc5);gc5.AddReference(gc6);gc5.AddReference(gc7);gcCollector.Collect(gc2);
}

結果：

3.標記 - 壓縮（Mark - Compact）算法：

標記階段與標記 - 清除算法相同，在清除階段會將所有存活對象移動到一端，然后清理另一端的內存。
解決了內存碎片問題，同時避免了復制算法的內存浪費。

原理：

分配一段內存，假設已經存儲上數據了

標記可達對象

移動對象

清除未標記對象
重置標記

模擬實現代碼:

GCObject類：同上

MarkCompactGC類：

    internal class MarkCompactGC{private List<GCObject> _heap;public MarkCompactGC(){_heap = new List<GCObject>();}// 分配新對象到堆public GCObject CreateObject(string name){var obj = new GCObject(name);_heap.Add(obj);return obj;}public void Collect(params GCObject[] roots){// 標記階段void Mark(GCObject obj){if (!obj.Marked){obj.Marked = true;foreach (var child in obj.ReferencesObjs) Mark(child);}}foreach (var root in roots) Mark(root);// 壓縮階段int newAddress = 0;for (int i = 0; i < _heap.Count; i++){if (_heap[i].Marked || _heap[i].Name.Equals("root")){// 移動對象到新位置并更新引用_heap[newAddress] = _heap[i];newAddress++;}}_heap.RemoveRange(newAddress, _heap.Count - newAddress);foreach (var child in _heap){Console.WriteLine($"存活對象： {child.GetHashCode()},{child.Name}");}}}

測試代碼：?

   /// <summary>/// 標記壓縮算法測試/// </summary>static void MarkCompactGC(){var gcCollector = new MarkCompactGC();GCObject root = gcCollector.CreateObject("root");GCObject gc2 = gcCollector.CreateObject("gc2");GCObject gc3 = gcCollector.CreateObject("gc3");GCObject gc4 = gcCollector.CreateObject("gc4");root.AddReference(gc2);gc2.AddReference(gc3);gc2.AddReference(gc4);GCObject gc5 = gcCollector.CreateObject("gc5");GCObject gc6 = gcCollector.CreateObject("gc6");GCObject gc7 = gcCollector.CreateObject("gc7");root.AddReference(gc5);gc5.AddReference(gc6);gc5.AddReference(gc7);gcCollector.Collect(gc2);}

結果：

4.引用計數（Reference Counting）算法：

為每個對象維護一個引用計數器，當有新的引用指向對象時計數器加 1，引用失效時計數器減 1。當計數器為 0 時，對象被回收。
缺點是無法處理循環引用的情況。

原理：

分配一塊內存，假設已經存儲上數據了

分配的每塊內存都有一個計數

如果引用計數歸0，則就釋放這塊內存

模擬實現代碼:

RefCountObject類：

internal class RefCountedObject
{private int _refCount = 0;private List<RefCountedObject> _children;private List<WeakReference<RefCountedObject>> _weakRefs; // 弱引用容器private string _name;public RefCountedObject(string name){_children = new List<RefCountedObject>();_weakRefs = new List<WeakReference<RefCountedObject>>();_name = name;}/// <summary>/// 添加強引用/// </summary>public void AddRef(){if (_refCount == int.MaxValue) return;_refCount++;}/// <summary>/// 添加弱引用（用于解決循環引用）/// </summary>public void AddWeakRef(RefCountedObject target){var weakRef = new WeakReference<RefCountedObject>(target);_weakRefs.Add(weakRef);}/// <summary>/// 釋放引用/// </summary>public void Release(){if (_refCount <= 0) return;_refCount--;if (_refCount == 0){Dispose();}}/// <summary>/// 添加子對象（自動管理引用計數）/// </summary>public void AddChild(RefCountedObject child){if (child == null) return;child.AddRef();_children.Add(child);}public void Dispose(){// 釋放強引用子對象foreach (var child in _children){child.Release();}_children.Clear();// 釋放弱引用（不操作引用計數）_weakRefs.Clear();// 釋放非托管資源ReleaseResources();}protected virtual void ReleaseResources(){Console.WriteLine($"{this.ToString()} 釋放資源");}public override string ToString(){return $"[{this._name}@{GetHashCode():x4}]";}
}

測試：

/// <summary>
/// 引用計數算法測試
/// </summary>
static void RefCountedGCTest()
{//正常引用var refObj1 = new RefCountedObject("refObj1var refObj2 = new RefCountedObject("refObj2refObj1.AddRef(); //根引用refObj1.AddChild(refObj2); //weapon 引用+1//手動釋放原始引用refObj2.Release();refObj1.Release();//循環引用（使用弱引用解決）var nodeA = new RefCountedObject("節點A");var nodeB = new RefCountedObject("節點B");nodeA.AddRef(); // 根引用// 相互引用（A強引用B，B弱引用A）nodeA.AddChild(nodeB);nodeB.AddWeakRef(nodeA);  // 使用弱引用避免循//nodeB.AddChild(nodeA);// 釋放根引用nodeA.Release();  // 正確釋放整個引用鏈
}

?結果：

5.分代收集（Generational Collection）算法：

將對象按照生命周期分為不同的代（如新生代、老生代），不同代采用不同的回收策略。
通常新生代使用復制算法，老生代使用標記 - 清除或標記 - 壓縮算法。

原理：

將對象分不同代，以分成三代為例
在new新對象時，檢查第0代內存是否已達上限，如果是觸發第0代GC，

標記復制，存活對象晉升到第1代

清除掉沒有被標記的

如果第1代內存達到上限，觸發第1代GC，將存活對象晉升到第2代，和第0代GC處理類似。?

在第2代內存達到上限后，觸發第2代GC，將全堆執行GC。

模擬實現代碼:

GCObject類：

  internal class GCObject{private List<GCObject> referencesObjs;public int Generation {  get; set; }public List<GCObject> ReferencesObjs { get => this.referencesObjs; }public string Name { get; private set; }public GCObject(string name,int generation = 0){referencesObjs = new List<GCObject>();Name = name;Generation = generation;}public void AddReference(GCObject obj){referencesObjs.Add(obj);}}

GenerationalGC類：

internal class GenerationalGC
{private readonly List<GCObject>[] _generations;private readonly HashSet<GCObject> _marked;public GenerationalGC(){_generations = new List<GCObject>[3];_marked = new HashSet<GCObject>();for (int i = 0; i < 3; i++)_generations[i] = new List<GCObject>();}// 分配新對象（默認進入0代）public GCObject NewObject(string name , int generation = 0){var obj = new GCObject(name,generation);_generations[generation].Add(obj);return obj;}// 執行分代回收//這里將可標記對象傳進來，模擬可達對象public void Collect(int generation, params GCObject[] roots){Console.WriteLine($"\n=== 執行第{generation}代GC ===");// 標記階段（遞歸標記可達對象）void Mark(GCObject obj){if (obj == null || _marked.Contains(obj)) return;_marked.Add(obj);foreach (var child in obj.ReferencesObjs) Mark(child);}// 從根出發（實際應包含全局/棧引用）foreach (var root in roots) Mark(root);// 清除和晉升for (int gen = 0; gen <= generation; gen++){var toRemove = new List<GCObject>();foreach (var obj in _generations[gen]){if (!_marked.Contains(obj)){Console.WriteLine($"回收 {obj.GetHashCode():x4} (代{gen})");}else if (gen < 2) // 晉升存活對象{obj.Generation = gen + 1;_generations[gen + 1].Add(obj);}toRemove.Add(obj);}_generations[gen].RemoveAll(toRemove.Contains);}_marked.Clear();}public int GetGenerationCount(int idx){return _generations[idx].Count;}
}

測試代碼：

  /// <summary>/// 分代垃圾回收算法測試/// </summary>static void GenerationalGCTest(){var gc = new GenerationalGC();// 創建對象并建立引用var obj1 = gc.NewObject("obj1");var obj2 = gc.NewObject("obj2");obj1.AddReference(obj2);var obj3 = gc.NewObject("obj3");var obj4 = gc.NewObject("obj4");// 執行第0代GC（回收無引用的對象）gc.Collect(0,obj1);// 查看對象分布Console.WriteLine("\n=== 每代對象分布 ===");for (int gen = 0; gen < 3; gen++){Console.WriteLine($"代{gen}: {gc.GetGenerationCount(gen)} 對象");}// 創建新對象for (int i = 0; i < 5; i++){var temp = gc.NewObject("oldGCObj" + i);if (i % 2 == 0)obj2.AddReference(temp); // 建立引用}// 查看對象分布Console.WriteLine("\n=== 每代對象分布 ===");for (int gen = 0; gen < 3; gen++){Console.WriteLine($"代{gen}: {gc.GetGenerationCount(gen)} 對象");}// 模擬多次GC觸發晉升gc.Collect(0,obj1);// 查看對象分布Console.WriteLine("\n=== 每代對象分布 ===");for (int gen = 0; gen < 3; gen++){Console.WriteLine($"代{gen}: {gc.GetGenerationCount(gen)} 對象");}gc.Collect(0, obj1);// 查看對象分布Console.WriteLine("\n=== 每代對象分布 ===");for (int gen = 0; gen < 3; gen++){Console.WriteLine($"代{gen}: {gc.GetGenerationCount(gen)} 對象");}gc.Collect(1,obj1); // 顯式回收第1代// 查看對象分布Console.WriteLine("\n=== 最終代分布 ===");for (int gen = 0; gen < 3; gen++){Console.WriteLine($"代{gen}: {gc.GetGenerationCount(gen)} 對象");}}

結果：