1. 概述
在传统的C/C++程序中，程序员需要显示地申请内存，然后在不需要的时候释放它。这样做虽然有很高的效率，但风险也是很大的。由于程序员需要自己来进行内存管理，这也难免会降低程序的开发效率。而目前的大多数应用都对效率本身的要求不会太高，那么我们是否可以找到一个兼顾效率和开发效率的方法来减轻程序员的负担，减少人工内存管理带来的风险呢?这就是自动垃圾回收。所谓的垃圾，也就是无用的内存。在面向对象的世界里，所谓的垃圾指的是那些不可触及的对象，它们能够被安全地回收重新用于应用程序。在现代的编程语言里，这些对象大多都分配在堆中。所以现代所提到的垃圾回收指的也就是回收堆中分配的无用内存，本文将从这个角度来阐述垃圾回收的问题。那么如何来检测无用内存，如果合理而有效地释放这些垃圾，这也就是自动垃圾回收所要处理的两大问题。由于JDK和.NET虚拟平台中都集成了自动垃圾回收，随着这两个平台日益被广大程序员所亲睐，对于自动垃圾回收的研究更是如火如荼。本文在前半部分阐述了自动垃圾回收用到的基本算法，在后半部分我们将针对这两个平台的自动垃圾回收机制进行简单的阐述，并提供实践方面的参考。
2. 基本概念
在进行垃圾回收的时候，我们往往需要处理两个问题，一个是如何检测垃圾，另外一个就是如何释放这些垃圾。下面我们通过下图来分别阐述现代垃圾算法中提到的一些基本概念：
图一 垃圾和存活对象
n 检测垃圾
在释放垃圾之前，我们需要通过一种有效的机制来区分垃圾和存活对象。当然，我们可以有两个策略来处理这个问题：找出垃圾和找出存活对象。现代的垃圾回收算法往往采用的是第二种策略。堆中所有的存活对象都被一个所谓的“根集”所直接或间接引用，反之则是垃圾。这里所提到的“根集”指的是那些由程序中的参数、局部变量以及全局变量组成的集合。
n 释放垃圾
通过垃圾检测，我们区分出了垃圾和存活对象。下一步我们要做的就是释放这些垃圾，同时我们还需要兼顾回收的效率、实时性以及内存碎片问题。仍旧可以有两种策略：抢救存活对象和清除垃圾。现代的垃圾算法大都采用的是第一种策略，因为这些策略灵活性很大而且可以兼顾上面提到的几点考虑。
n 根集
指的是那些由程序中的参数、局部变量以及全局变量组成的集合。上图中的根集为{R1,R2}。
n 存活对象
指的是以根基中的某个变量为起点通过图的深度优先算法可触及的那些应用对象。上图中的存活对象为{A,B,F}。
n 垃圾
指的是以根基中的某个变量为起点通过图的深度优先算法不可触及的那些引用对象。上图中的垃圾为{C,D,E}。
3. 简单示例
在这节中，根据图一，我们将演示一个简单的垃圾处理流程。如下：
1. 找出存活对象和垃圾
下图中“红色背景”所标记出来的对象多为存活对象
图二 找出存活对象和垃圾
2. 采用拷贝策略抢救存活对象
将上图中的{A,B,F}拷贝到堆中的另外一个位置，如下图
图三 垃圾区域
3. 释放垃圾
内存状态如下图：
图五 垃圾区域
图六 存活对象区域
4. 垃圾回收算法
垃圾回收多发生在当前应用程序不忙或者系统内存吃紧的时候。上面我们提到了垃圾回收解决了两个问题：检测垃圾和释放垃圾。检测垃圾的算法大致可分为两类：传统的引用计数和现代的引用跟踪。释放垃圾的算法大致可分为：即时清除,压缩堆栈，拷贝存活对象。
通过组合上述的检测垃圾和释放垃圾的算法，衍生出了许多实用算法，如分代收集算法、自适应算法等。目前.NET和JDK使用的都是分代收集算法的增强版本。
下面我们将对这些基本算法做简单介绍。
4.1. 垃圾检测算法
4.1.1. 引用计数
引用计数法是唯一没有使用根集的垃圾回收算法，该算法使用引用计数器来区分存活对象和不再使用的对象。一般来说，堆中的每个对象对应一个引用计数器。当每一次创建一个对象并赋给一个变量时，引用计数器置为1。当对象被赋给任意变量时，引用计数器每次加1。当对象出了作用域后(该对象丢弃不再使用)，引用计数器减1，一旦引用计数器为0，对象就满足了垃圾收集的条件。
虽然基于引用计数器的垃圾收集器运行较快，不会长时间中断程序执行，非常适宜实时运行的程序。但这种算法有很多致命的缺陷：
n 增加了程序执行的开销
因为每次对象赋给新的变量 ，计数器加1，而每次现有对象出了作用域生，计数器减1。
n 这种算法无法检测到引用环
这个缺陷导致的最终结果是，当程序中存在引用环的时候，环中引用的对象将永远不会得到释放，从而会导致内存泄露。
4.1.2. 引用跟踪
引用跟踪算法是为了解决引用计数法的问题而提出，它使用了根集的概念。基于引用跟踪算法的垃圾收集器从根集开始扫描，识别出哪些对象可达，哪些对象不可达，并用某种方式标记可达对象，例如对每个可达对象设置一个或多个位。
4.2. 垃圾释放算法
垃圾释放算法在垃圾回收中处于最重要的位置。因为它决定垃圾回收算法的效率、安
全性和实时性。
如果在堆栈中分配了很多占用内存很小的对象，使用上面描述的方式进行自动垃圾回收回造成内存碎片，不但会影响到程序本身的运行效率，而且会造成内存浪费。因此我们需要有一种方式对这些内存碎片进行压缩和整理，最大程度地提高内存的使用率。
因为一个垃圾回收器往往都管理这一个或者多个应用程序的内存。因此，在进行内存碎片的压缩和整理的时候，我们就需要将垃圾回收涉及到的每个应用都挂起，以防止内存访问违例。当然，也有很多复杂的GC为了提高应用程序的效率，采取了与应用程序并发或者并行运行的测路。
4.2.1. 即时清除
扫描堆以寻找未标记对象并释放它们的内存，但并不对这些垃圾进行整理。这种策略很容易导致内存碎片。
4.2.2. 拷贝存活对象
把存活对象复制到堆栈的新域中以便压缩堆。这种策略需要中止当前正在运行的程序。
4.3. 常见垃圾收集器
4.3.1. 标记－清除收集器
这种收集器首先遍历对象图并标记可到达的对象，然后扫描堆栈以寻找未标记对象并释放它们的内存。这种收集器一般使用单线程工作并停止其他操作。
4.3.2. 标记－压缩收集器
有时也叫标记－清除－压缩收集器，与标记－清除收集器有相同的标记阶段。在第二阶段，则把标记对象复制到堆栈的新域中以便压缩堆栈。这种收集器也停止其他操作。
4.3.3. 复制收集器
这种收集器将堆栈分为两个域，常称为半空间。每次仅使用一半的空间，生成的新对象则放在另一半空间中。GC运行时，它把可到达对象复制到另一半空间，从而压缩了堆栈。这种方法适用于短生存期的对象，持续复制长生存期的对象则导致效率降低。
4.3.4. 增量收集器
增量收集器把堆栈分为多个域，每次仅从一个域收集垃圾。这会造成较小的应用程序中断。
4.3.5. 分代收集器
.NET使用分代收集器。这种收集器把堆栈分为两个或多个域，用以存放不同寿命的对象。生成的新对象一般放在其中的某个域中。过一段时间，继续存在的对象将获得使用期并转入更长寿命的域中。分代收集器对不同的域使用不同的算法以优化性能。
4.3.6. 并发收集器
并发收集器与应用程序同时运行。这些收集器在某点上一般都不得不停止其他操作以完成特定的任务，但是因为其他应用程序可进行其他的后台操作，所以中断其他处理的实际时间大大降低。
4.3.7. 并行收集器
并行收集器使用某种传统的算法并使用多线程并行的执行它们的工作。在多CPU机器上使用多线程技术可以显著的提高应用程序的可扩展性。
5. 分代垃圾收集
相对标记-清除、标记-压缩等这些传统的垃圾收集器，分代垃圾收集具有更好的效率和灵活性，目前被广泛用于.NET和JVM的垃圾回收。所以在这节里，我们对这种垃圾收集策略进行详细的描述。
5.1. 为什么？
在任何一个应用程序堆中，一些对象在创建后很快就成为垃圾，另一些则在程序的整个运行期间一直保持生存。经验分析表明，对于大多数面向对象的语言，包括 Java 语言，绝大多数对象――可以多达 98%（这取决于您对年轻对象的衡量标准）是在年轻的时候死亡的。可以用时钟秒数、对象分配以后内存管理子系统分配的总字节或者对象分配后经历的垃圾收集的次数来计算对象的寿命。但是不管您如何计量，分析表明了同一件事――大多数对象是在年轻的时候死亡的。大多数对象在年轻时死亡这一事实对于收集器的选择很有意义。特别是，当大多数对象在年轻时死亡时，复制收集器可以执行得相当好，因为复制收集器完全不访问死亡的对象，它们只是将活的对象复制到另一个堆区域中，然后一次性收回所有的剩余空间。那些经历过第一次垃圾收集后仍能生存的对象，很大部分会成为长寿的或者永久的对象。根据短寿对象和长寿对象的混合比例，不同垃圾收集策略的性能会有非常大的差别。当大多数对象在年轻时死亡时，复制收集器可以工作得很好，因为年轻时死亡的对象永远不需要复制。不过，复制收集器处理长寿对象却很糟糕，它要从一个半空间向另一个半空间反复来回复制这些对象。相反，标记-整理收集器对于长寿对象可以工作得很好，因为长寿对象趋向于沉在堆的底部，从而不用再复制。不过，标记-清除和标记-理整收集器要做很多额外的分析死亡对象的工作，因为在清除阶段它们必须分析堆中的每一个对象。
分代收集器将老对象和年轻对象按照存活时间的不同，分别放在不同的域中。在进行垃圾回收的时候，优先处理那些年轻的对象，而对于那些老对象基本不做回收，这样不但可以提高垃圾回收的效率，而且还可以提高垃圾回收的实时性。
5.2. 怎样处理？
分域
将堆分为几个固定或可变的区域用于分别存放年轻对象和老对象。如.NET将托管堆（在后面有提到）分为三个区域，每个域中方不同代（共3代）的对象。