Understanding .net CLR garbage collection
引言
内存管理是计算机科学中一个相当复杂而有趣的领域。在计算机诞生的这几十年间，内存的管理的技术不断进步，使系统能够更加有效地利用内存这一计算机必不可少的资源。
一般而言，内存管理可以分为三类：硬件管理（如TLB），操作系统管理（如Buddy System，Paging，Segmentation），应用程序管理（如C++，Java，.net的内存管理机制）。鉴于篇幅和笔者水平的限制，本文只涉及了内存管理的很小一部分，即.net中的内存管理方法。.net是一个当代的应用程序框架，采用了内存自动管理技术，就是通常所说的内存垃圾自动回收技术――Garbage Collection（下文中简称GC），对.net的剖析比较具有代表性。
GC的历史与好处
虽然本文是以.net作为目标来讲述GC，但是GC的概念并非才诞生不久。早在1958年，由鼎鼎大名的图林奖得主John McCarthy所实现的Lisp语言就已经提供了GC的功能，这是GC的第一次出现。Lisp的程序员认为内存管理太重要了，所以不能由程序员自己来管理。但后来的日子里Lisp却没有成气候，采用内存手动管理的语言占据了上风，以C为代表。出于同样的理由，不同的人却又不同的看法，C程序员认为内存管理太重要了，所以不能由系统来管理，并且讥笑Lisp程序慢如乌龟的运行速度。的确，在那个对每一个Byte都要精心计算的年代GC的速度和对系统资源的大量占用使很多人的无法接受。而后，1984年由Dave Ungar开发的Small talk语言第一次采用了的技术（这个技术在下文中会谈到），但是Small talk也没有得到十分广泛的应用。
直到20世纪90年代中期GC才以主角的身份登上了历史的舞台，这不得不归功于Java的进步，今日的GC已非吴下阿蒙。Java采用VM（Virtual Machine）机制，由VM来管理程序的运行当然也包括对GC管理。90年代末期.net出现了，.net采用了和Java类似的方法由CLR(Common Language Runtime)来管理。这两大阵营的出现将人们引入了以虚拟平台为基础的开发时代，GC也在这个时候越来越得到大众的关注。
为什么要使用GC呢？也可以说是为什么要使用内存自动管理？有下面的几个原因：
l 提高了软件开发的抽象度；
l 程序员可以将精力集中在实际的问题上而不用分心来管理内存的问题；
l 可以使模块的接口更加的清晰，减小模块间的偶合；
l 大大减少了内存人为管理不当所带来的Bug；
l 使内存管理更加高效。
总的说来就是GC可以使程序员可以从复杂的内存问题中摆脱出来，从而提高了软件开发的速度、质量和安全性。
什么是GC
GC如其名，就是垃圾收集，当然这里仅就内存而言。Garbage Collector（垃圾收集器，在不至于混淆的情况下也成为GC）以应用程序的root为基础，遍历应用程序在Heap上动态分配的所有对象，通过识别它们是否被引用来确定哪些对象是已经死亡的哪些仍需要被使用。已经不再被应用程序的root或者别的对象所引用的对象就是已经死亡的对象，即所谓的垃圾，需要被回收。这就是GC工作的原理。为了实现这个原理，GC有多种算法。比较常见的算法有Reference Counting，Mark Sweep，Copy Collection等等。目前主流的虚拟系统.net CLR，Java VM和Rotor都是采用的Mark Sweep算法。本文以.net为基础，这里只对Mark Sweep算法进行讲述。
相关的GC算法
Mark Sweep
在程序运行的过程中，不断的把Heap的分配空间给对象，当Heap的空间被占用到不足以为下一个对象分配的时候Mark Sweep算法被激活，将垃圾内存进行回收并将其返回到free list中。
Mark Sweep就像它的名字一样在运行的过程中分为两个阶段，Mark阶段和Sweep阶段。Mark阶段的任务是从root出发，利用相互的引用关系遍历整个Heap，将被root和其它对象所引用的对象标记起来。没有被标记的对象就是垃圾。之后是Sweep阶段，这个阶段的任务就是回收所有的垃圾。如图1所示。
图1：m就是被标记的对象
Mark Sweep算法虽然速度比Reference Counting要快，并且可以避免循环引用造成的内存泄漏。但是也有不少缺点，它需要遍历Heap中所有的对象（存活的对象在Mark阶段遍历，死亡的对象在Sweep阶段遍历）所以速度也不是十分理想。而且对垃圾进行回收以后会造成大量的内存碎片。
为了解决这两个问题，Mark Sweep算法得到了改进。首先是在算法中加入了Compact阶段，即先标记存活的对象，再移动这些对象使之在内存中连续，最后更新和对象相关的地址和free list。这就是Mark Compact算法，它解决了内存碎片的问题。而为了提高速度，Generation的概念被引入了。
Generation
Generational garbage collector（又被称为ephemeral garbage collector）是基于以下几个假设的：
l 对象越年轻则它的生命周期越短；
l 对象越老则它的生命周期越长；
l 年轻的对象和其它对象的关系比较强，被访问的频率也比较高；
l 对Heap一部分的回收压缩比对整个Heap的回收压缩要快。
Generation的概念就是对Heap中的对象进行分代（分成几块，每一块中的对象生存期不同）管理。当对象刚被分配时位于Generation 0中，当Generation 0的空间将被耗尽时，Mark Compact算法被启动。经过几次GC后如果这个对象仍然存活则会将其移动到Generation 1中。同理，如果经过几次GC后这对象还是存活的，则会被移动到Generation 2中，直到被移动到最高级中最后被回收或者是同程序一同死亡。 采用Generation的最大好处就在于每次GC不用对整个Heap都进行处理，而是每次处理一小块。对于Generation 0中的对象，因为它们死亡的可能性最大，所以对它们GC的次数可以安排多一些，而其它相对死亡的可能性小一些的对象所在的Generation可以少安排几次GC。这样做就使得GC的速度得到了一定程度的提高。这样就产生了几个有待讨论的问题，首先是应该设置几个Generation，每个Generation应该设置成多大，然后是对每个对象升级时它应该是已被GC了多少次而仍然存活。关于.net CLR对这个问题的处理，在本文的最后将给出一个例子对其进行测试。
相关的数据结构
与.net GC相关的数据结构有三个Managed Heap，Finalization Queue和Freachable Queue。
Managed Heap
Managed Heap是一个设计简单而优化的堆，它与传统的C-runtime的堆不太一样。它的简单管理方法是为了提高对堆的管理速度，同时也是基于一个简单的（也是不可能的）假设。对Managed Heap的管理假设内存是无穷无尽的。在Managed Heap上有一个称为NextObjPtr的指针，这个指针用于指示堆上最后一个对象的地址。当有一个新的对象要分配到这个堆上时，所要做的仅仅是将NextObjPtr的值加上新对象的大小形成新的NextObjPtr。这只是一个简单的相加，当NextObjPtr的值超出了Managed Heap边界的时候说明堆已经满了，GC将被启动。
图2：相关数据结构示意图
Finalization Queue和Freachable Queue
这两个队列和.net对象所提供的Finalize方法有关。这两个队列并不用于存储真正的对象，而是存储一组指向对象的指针。当程序中使用了new操作符在Managed Heap上分配空间时，GC会对其进行分析，如果该对象含有Finalize方法则在Finalization Queue中添加一个指向该对象的指针。在GC被启动以后，经过Mark阶段分辨出哪些是垃圾。再在垃圾中搜索，如果发现垃圾中有被Finalization Queue中的指针所指向的对象，则将这个对象从垃圾中分离出来，并将指向它的指针移动到Freachable Queue中。这个过程被称为是对象的复生（Resurrection），本来死去的对象就这样被救活了。为什么要救活它呢？因为这个对象的Finalize方法还没有被执行，所以不能让它死去。Freachable Queue平时不做什么事，但是一旦里面被添加了指针之后，它就会去触发所指对象的Finalize方法执行，之后将这个指针从队列中剔除，这是对象就可以安静的死去了。.net framework的System.GC类提供了控制Finalize的两个方法，ReRegisterForFinalize和SuppressFinalize。前者是请求系统完成对象的Finalize方法，后者是请求系统不要完成对象的Finalize方法。ReRegisterForFinalize方法其实就是将指向对象的指针重新添加到Finalization Queue中。这就出现了一个很有趣的现象，因为在Finalization Queue中的对象可以复生，如果在对象的Finalize方法中调用ReRegisterForFinalize方法，这样就形成了一个在堆上永远不会死去的对象，像凤凰涅槃一样每次死的时候都可以复生。
对GC的直接控制
.net framework的System.GC类提供一些可以对GC直接进行操作的方法。而System.Runtime.InteropServices.GCHandle类提供从非托管内存访问托管对象的方法（这里对此不作讨论）。先来看下面的这个利用System.GC进行直接操作的例子。
using System;
namespace gcTest
{
class gcDemo
{
private static void GenerationDemo()
{
// Let's see how many generations the GCH supports (we know it's 2)
Console.WriteLine("Maximum GC generations: {0}", GC.MaxGeneration);
// Create a new BaseObj in the heap
GenObj obj = new GenObj("Generation");
// Since this object is newly created, it should be in generation 0
obj.DisplayGeneration(); // Displays 0
for(int i = 1; i <= GC.MaxGeneration; i++)
{
// Performing a garbage collection promotes the object's generation
GC.Collect();
obj.DisplayGeneration(); // Displays i
}
obj = null; // Destroy the strong reference to this object
for(int i = 0; i <= GC.MaxGeneration; i++)
{
GC.Collect(i);
GC.WaitForPendingFinalizers();
//suspend this thread until the freachable queue of
//the i generation has been emptied
//only when i = GC.MaxGeneration, this finalization method
//of obj will be performed
}
Console.WriteLine("Demo stop: Understanding Generations.");
//total gc times
//generation 0 : 5 times
//generation 1 : 4 times
//generation 2 : 3 times
}
public static void Main()
{
GenerationDemo();
}
}
class GenObj
{
private string objName;
public GenObj(string name)
{
this.objName = name;
}
public void DisplayGeneration()
{
Console.WriteLine("I am in Generation {0}", GC.GetGeneration(this));
}
};
}
这是个有趣的例子，首先利用GC.MaxGeneration()得知了在.net CLR中的GC采用了3代的结构，即Generation 0～2。接下来在Managed Heap上分配了一个GenObj的实例obj。在开始时obj位于Generation 0中，然后对整个Managed Heap进行两次GC。可以发现每进行一次GC存活的对象都会升一级直至到达Generation 2中。设置obj = null，这样做是为了取消root对obj的强引用，使obj成为垃圾。紧接着利用GC.Collect(i)对Managed Heap逐级进行GC，这个方法会对Generation 0～i进行GC。GC.WaitForPendingFinalizers()的作用是使整个进程挂起，等到Freachable Queue中所指向的对象的Finalize方法被调用。这样做的目的是为了保障对本次GC所确定的垃圾进行完全的回收，而不会因为对象的Finalize方法使对象复生。
这个例子得到的一些结果可以直观的看出.net CLR对GC的处理，要想得到更具体的数据读者可以使用Windows提供的性能监视器perfmon.exe对.net应用程序进行测试。
最后还要提到的是GC对大对象（large object）的处理，这个处理和以上所讨论的大同小异，只是GC不会进行Compact这个过程，因为要在内存中移动一个较大的对象对系统性能带来的不良影响是显而易见的。
结论
本文旨在让读者对.net CLR garbage collection有一个大致的理解，这里作出的只是粗浅的讨论，很多方面并没有涉及，比如多线程状态下GC的工作原理，各种不同版本的.net GC等等。有兴趣深入下去朋友可以阅读Rotor和mono的源码，Microsoft .net framework的源码是不可能得到的了。非常欢迎有兴趣的朋友来与我讨论。
原文链接：