CLR 垃圾回收算法

c#相较于c，c++而言，在内存管理上为程序员提供了极大的方便，解放了程序员与内存地址打交道，提高了程序员的工作效率。比如c中分配的malloc堆空间没有释放导致的内存泄露，数组越界导致的踩内存错误，使用了已释放的内存空间错误等等。这些在C#中统统的都不存在，主要是由于clr提供的安全检查机制以及垃圾回收机制。本篇文章主要来介绍常用的垃圾回收算法以及CLR中使用的垃圾回收算法。

在通常的情况下当分配对象时发现内存堆空间不足时，此时GC会执行垃圾回收算法。默认情况下，进程启动，会被分配相应的堆空间的大小，堆空间的大小受到进程虚拟空间的限制。32位系统上的堆空间最大为1.5G,64位为8T,

1.引用计数：

引用计数的回收算法的思想是：对于堆中创建的一个对象，内部维护一个引用计数，但该对象被引用的时候，该对象的引用计数加1，当该对象的引用超过了生存期时（如方法结束）或者指向新的对象时，该对象的引用计数减一，当对象的引用计数为0时则可以被垃圾收集。该算法的优点是实现简单，垃圾收集不会终止线程的执行，适用于实时的环境，但是缺点时不能够解决循环引用。例如，一个对象A指向B,而B又指向A，但是没有其他的引用指向两者，这时永远也不能回收两者。

2.引用追踪算法：

引用追踪算法的基本步骤是： 当GC启动时，1.首先暂停所有的线程。2.GC标记阶段：首先遍历堆中所有的对象，将其中的标识置0（标识包含在同步块索引字段中),表明初始时都是可以被删除的。其次CLR查找所有的根引用（这里的根引用指的是一些引用变量，包括类静态引用变量，实例引用变量，方法局部引用变量以及方法参数），如果根引用为空的话，CLR会忽略该引用，并且查找下一个根引用，当该根引用不为空时，将其指向的对象的标识置1，同时查找该对象里的根引用，以此进行标识下去，当遇到对已经标识过的对象时，他将不会再查找该对象的里的根引用，防止循环引用导致的无限循环。

下面举个例子，如图1所示，堆中的对象有ABCDEFGHIJ,当CLR执行GC时，在标记的第二阶段他会查找根引用，发现其指向ACD，将该对象的对应的标识位值1，同时发现D也引用了H，则将H的标识位置1，当标记阶段执行完成，GC开始执行对象的压缩，将存活下来的对象压缩到连续的空间中，释放掉不再使用的对象，GC执行压缩后的对象内存分配如图2所示。执行压缩的好处是：对象都在连续的内存空间中，减少了应用的工作空间，提高了访问对象的性能。其次，防止内存碎片的产生。最后，当存活的对象压缩到连续的空间中时，他们的内存地址发生了相应的改变，这是我们需要改变根引用指向的对象移动后的地址。图中的NextObjPtr指向的是接下来将分配对象的地址的位置。当压缩完成后，CLR恢复所有的线程，以使其继续执行。

图1，未执行GC前堆中对象的分布。

图2.执行GC后，堆中的对象分布

3.基于代的垃圾回收算法。

基于代的垃圾回收算法是根据三个方面的推断所提出来的：1.越新的对象，越短的生命周期。2.老对象将会有更长的生命周期。3.一次回收部分堆空间比回收整个堆的空间更快。

下面通过例子来说明基于代的垃圾回收的思想：

1.首先，初始时堆空间中没有对象，当对象开始被分配到堆中时，会被分配到0代堆空间中，初始只有0代。CLR初始化时会为0代空间分配相应的大小，几k字节。如下图所示ABCDE被分配到0代空间：

程序运行一段时间后，C,E不可达，当要分配对象F时，由于0代已经没有空间可供分配，这时需要执行垃圾回收，回收CE，与此同时执行压缩，将ABD存放到连续空间，与此同时，ABD被提升为1代空间。执行垃圾收集后的堆空间如下所示：

垃圾收集后，可以看到0代空间已经没有对象，因此新的对象总是会被分配到0代空间中，接下来当我们在分配F到K的对象时，堆的空间如下图所示：

程序运行一段时间后，我们在分配新的对象L给0代空间时，0代空间已满，现在需要执行GC, （在这里需要说明的时CLR初始化时也会分配相应空间的大小给1代空间，1代空间分配的大小要大于0代空间）。GC在执行垃圾收集时首先会检查1代空间已使用的大小是否已经达到分配的大小，没有的话不执行垃圾对象的检查。因此垃圾收集只检查0代空间的对象，发现H和J不可用，可以回收，经过压缩和提升后，堆空间中的分配如下图所示：

可以看到1代空间中的B随然不可达，但是没有被回收，垃圾收集器只回收了0代空间中的不可用的对象，接下来我们在分配L到0的对象到0代内存空间中，分配后堆空间如下图所示：

当我们再次分配对象P时，0代空间已满，执行GC,同上面一样，执行GC后堆空间如下所示：

可以看到1代的被分配的空间在不断增大，不可达对象在缓慢增多。让我们再次分配对象P到S,分配后堆空间图如下所示：

当我们分配对象T时，由于0代空间已满，需要执行GC,假设1代对象分配所占空间已达到最大的分配空间，这时GC会检查1代堆空间中的对象以及0代堆空间中的对象，回收不可用对象，并执行压缩，回收后的堆空间如下图所示：

由图可以看到，1代空间中幸存的对象被提到2代空间中，0代空间中的对象被提到2代空间中，0代空间为空。

通过以上的例子可以看到，垃圾收集器会多次回收0代堆空间中的对象后才执行1代内存空间中的对象回收，这样做的目的主要是为了提供程序的性能。通常情况下，具有更长时间的对象具有更长的生命周期。同时，CLR垃圾回收算法也是自适应的，他会根据每个代空间中对象的分配后的生命期以及每次回收对象时的回收的程度，来动态调整代空间的大小以及相应的执行1代或2代堆空间的回收。比如，0代空间中的对象都是垃圾时，可以不执行压缩，直接将nextObj指向第一个对象的位。当发现0代空间中的对象执行GC时回收的对象很少时，可以增大0代空间的大小，当0代空间的对象回收比较多时，可以调小0代空间的大小等等。

参考资料：CLR VIA C# BOOK