.Net 垃圾回收机制原理和算法（一）

有了Microsoft.Net clr中的垃圾回收机制程序员不需要再关注什么时候释放内存，释放内存这件事儿完全由GC做了，对程序员来说是透明的。尽管如此，作为一个.Net程序员很有必要理解垃圾回收是如何工作的。这篇文章我们就来看下.Net是如何分配和管理托管内存的，之后再一步一步描述垃圾回收器工作的算法机制。

为程序设计一个适当的内存管理策略是困难的也是乏味的，这个工作还会影响你专注于解决程序本身要解决的问题。有没有一种内置的方法可以帮助开发人员解决内存管理的问题呢？当然有了，在.Net中就是GC，垃圾回收。

让我们想一下，每一个程序都要使用内存资源：例如屏幕显示，网络连接，数据库资源等等。实际上，在一个面向对象环境中，每一种类型都需要占用一点内存资源来存放他的数据，对象需要按照如下的步骤使用内存：
1. 为类型分配内存空间
2. 初始化内存，将内存设置为可用状态
3. 存取对象的成员
4. 销毁对象，使内存变成清空状态
5. 释放内存

这种貌似简单的内存使用模式导致过很多的程序问题，有时候程序员可能会忘记释放不再使用的对象，有时候又会试图访问已经释放的对象。这两种bug通常都有一定的隐藏性，不容易发现，他们不像逻辑错误，发现了就可以修改掉。他们可能会在程序运行一段时间之后内存泄漏导致意外的崩溃。事实上，有很多工具可以帮助开发人员检测内存问题，比如：任务管理器，System Monitor AcitvieX Control, 以及Rational的Purify。

而GC可以完全不需要开发人员去关注什么时候释放内存。然而，垃圾回收器并不是可以管理内存中的所有资源。有些资源垃圾回收器不知道该如何回收他们，这部分资源就需要开发人员自己写代码实现回收。在.Net framework中，开发人员通常会把清理这类资源的代码写到Close、Dispose或者Finalize方法中，稍后我们会看下Finalize方法，这个方法垃圾回收器会自动调用。

不过，有很多对象是不需要自己实现释放资源的代码的，比如：Rectangle，清空它只需要清空它的left，right，width，height字段就可以了，这垃圾回收器完全可以做。下面让我们来看下内存是如何分配给对象使用的。

对象分配：

.Net clr把所有的引用对象都分配到托管堆上。这一点很像c-runtime堆，不过你不需要关注什么时候释放对象，对象会在不用时自动释放。这样，就出现一个问题，垃圾回收器是怎么知道一个对象不再使用该回收了呢？我们稍后解释这个问题。

现在有几种垃圾回收算法，每一种算法都为一种特定的环境做了性能优化，这篇文章我们关注的是clr的垃圾回收算法。让我们从一个基础概念谈起。

当一个进程初始化之后，运行时会保留一段连续的空白内存空间，这块内存空间就是托管堆。托管堆会记录一个指针，我们叫它NextObjPtr，这个指针指向下一个对象的分配地址，最初的时候，这个指针指向托管堆的起始位置。

应用程序使用new操作符创建一个新对象，这个操作符首先要确认托管堆剩余空间能放得下这个对象，如果能放得下，就把NextObjPtr指针指向这个对象，然后调用对象的构造函数，new操作符返回对象的地址。

图1托管堆

这时候，NextObjPtr指向托管堆上下一个对象分配的位置，图1显示一个托管堆中有三个对象A、B和C。下一个对象会放在NextObjPtr指向的位置（紧挨着C对象）

现在让我们再看一下c-runtime堆如何分配内存。在c-runtime堆，分配内存需要遍历一个链表的数据结构，直到找到一个足够大的内存块，这个内存块有可能会被拆分，拆分后链表中的指针要指向剩余内存空间，要确保链表的完好。对于托管堆，分配一个对象只是修改NextObjPtr指针的指向，这个速度是非常快的。事实上，在托管堆上分配一个对象和在线程栈上分配内存的速度很接近。

到目前为止，托管堆上分配内存的速度似乎比在c-runtime堆上的更快，实现上也更简单一些。当然，托管堆获得这个优势是因为做了一个假设：地址空间是无限的。很显然这个假设是错误的。必须有一种机制保证这个假设成立。这个机制就是垃圾回收器。让我们看下它如何工作。

当应用程序调用new操作符创建对象时，有可能已经没有内存来存放这个对象了。托管堆可以检测到NextObjPtr指向的空间是否超过了堆的大小，如果超过了就说明托管堆满了，就需要做一次垃圾回收了。

在现实中，在0代堆满了之后就会触发一次垃圾回收。“代”是垃圾回收器提升性能的一种实现机制。“代”的意思是：新创建的对象是年轻一代，而在回收操作发生之前没有被回收掉的对象是较老的对象。将对象分成几代可以允许垃圾回收器只回收某一代的对象，而不是回收所有对象。

垃圾回收算法：

垃圾回收器检查看是否存在应用程序不再使用的对象。如果这样的对象存在，那么这些对象占用的空间就可以被回收（如果堆上没有足够的内存可用，那么new操作符就会抛出OutofMemoryException）。你可能会问垃圾回收器是怎样判断一个对象是否还在用呢？这个问题不太容易得到答案。
每个应用程序都有一组根对象，根是一些存储位置，他们可能指向托管堆上的某个地址，也可能是null。例如，所有的全局和静态对象指针是应用程序的根对象，另外在线程栈上的局部变量/参数也是应用程序的根对象，还有CPU寄存器中的指向托管堆的对象也是根对象。存活的根对象列表由JIT（just-in-time）编译器和clr维护，垃圾回收器可以访问这些根对象的。

当垃圾回收器开始运行，它会假设托管堆上的所有对象都是垃圾。也就是说，假定没有根对象，也没有根对象引用的对象。然后垃圾回收器开始遍历根对象并构建一个由所有和根对象之间有引用关系对象构成的图。

图2显示，托管堆上应用程序的根对象是A，C，D和F，这几个对象就是图的一部分，然后对象D引用了对象H，那么对象H也被添加到图中；垃圾回收器会循环遍历所有可达对象。

图2 托管堆上的对象

垃圾回收器会挨个遍历根对象和引用对象。如果垃圾回收器发现一个对象已经在图中就会换一个路径继续遍历。这样做有两个目的：一是提高性能，二是避免无限循环。

所有的根对象都检查完之后，垃圾回收器的图中就有了应用程序中所有的可达对象。托管堆上所有不在这个图上的对象就是要做回收的垃圾对象了。构建好可达对象图之后垃圾回收器开始线性的遍历托管堆，找到连续垃圾对象块（可以认为是空闲内存）。然后垃圾回收器将非垃圾对象移动到一起（使用c语言中的memcpy函数），覆盖所有的内存碎片。当然，移动对象时要禁用所有对象的指针（因为他们都可能是错误的了）。因此垃圾回收器必须修改应用程序的根对象使他们指向对象的新内存地址。此外，如果某个对象包含另一个对象的指针，垃圾回收器也要负责修改引用。图3显示了一次回收之后的托管堆。