常见的垃圾回收算法原理及其模拟实现

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)} 对象");}}

结果：