1.       自动垃圾收集 (GC) 中的常用算法

关键术语：

a)       垃圾 (garbage/live object) ，指在程序中堆上已经被分配但是不会被再次使用的对象。许多数据说明，在实际的程序中，大多数的对象只存在一个很短的周期，需要长期保存 Reference 的对象很少。

b)       垃圾收集：所有的允许分配堆内存的程序都提供了垃圾收集方法。在 C/C++ 中，实现需要用户自己调用 alloc/free , new/delete 分配内存。在 C#/Java 中，虚拟机都提供了自动垃圾收集，根据对象的生存周期与引用计数对垃圾对象进行回收。

c)       堆空间的增长与重整： [To-do ： how did C/C++ do this]

C# 的堆空间大小限制取决于虚拟内存的大小，通常来说 .net 虚拟机并不会限制可用的内存大小，而 java 默认的堆大小在 256M 左右，如果需要使用更大的堆，则需要使用 JVM 的 -Xmx 参数指定堆栈的上限。 java 和 C++ 都采用了分段的堆，在 gc 过程中会移动对象，从而得到更加连续的堆可用内存，更高的空间使用效率。

d)       并行的与串行的垃圾收集

并行的垃圾收集指的是在单独的线程中执行 GC ，不影响其他的线程执行

串行的垃圾收集： GC 线程将会挂起当前所有的执行线程直到 GC 线程返回。

e)       Root Set 与可达集

优化的编译器可以通过变量的生存周期决定对象在最合适的时候 ( 不会被将要执行的程序引用 ) 回收，但是在常用的算法中，一种简化的方式更加经常被采用，就是对象根集合与可达集合。因为对象只有通过被引用或者作为全局对象的时候才可以被访问，所以从全局对象可以导航到所有的活动对象，而其他的对象则被视为无用内存，被 GC 回收。全局对象的集合称为 Root Set ，而通过导航测试确定垃圾的过程被称为可达性测试，可以被导航的对象集合被称为可达集。

 

通常 GC 都包含了垃圾检测和垃圾回收两个阶段。

 

基本的 GC 算法包括以下几种：

a)       Reference Counting( 引用计数 )

引用计数为每一个对象提供了当前被引用的次数。前者显式的便利了系统中所有的指针得到可用的对象集合，后者便利每一个对象，判断对象是否仍被引用，即对象是否还将被使用。 RC 的一个重要的好处是它的实时性，因为每一个操作都可以及时地修改对象的 Reference count 。从而在语言的层面上实现 GC 。而且其他的执行进程不需要被挂起。问题是 GC 本身需要占用多余的存储空间。

Comment: Not always effective, hard to make efficient!

当程序创建一个循环引用关系的时候，环中的对象的引用计数永远不会降为 0 ，也就永远无法被回收，这种情况下，引用计数算法将会失效。

效率的问题源于 RC 的本质，它的耗费与处理时间成正比 (per operation update) 。这个问题对于栈上的生存期较短的对象尤其显著。延迟的引用计数技术可以有效地提高效率，然而其占用的处理时间仍然是成比例的，只是比例相比下降了很多。

对象的回收：

RC 为零的对象将会被添加到一个回收链表中，等待回收进程回收。

b)       Mark-Sweep

标记清扫 (MS) 算法首先通过 Root Set 得到当前的可达集并对相应的对象作出标记 (Mark) ，然后将非可达集添加到回收链表中 (Sweep) 。

MS 的第一个问题是它容易造成零碎地内存，小对象往往散步在堆中，造成难以创建大对象。 ( 事实上这个问题对于所有的 GC 算法都存在 )

MS 第二个问题也是它的效率问题，其耗费与堆大小（活动对象与垃圾对象的总合）成正比。

MS 的第三个问题是对象局部性 (locality) ，因为对象不会被移动，造成堆上存在大量空隙。

c)       Mark-Compact

标记 - 压缩算法 (MC) 与 MS 算法的第一步骤相同，在第二步骤中， MC 移动所有的活动对象是他们在堆上相邻的位置存在，从而形成联系的空闲内存。这个过程类似于 Windows 的内存碎片整理。

MC 的问题显而易见，对于大量临时对象的情况下，其性能远低于 MS 算法。

MC 与 MS 在第一个阶段非常类似，但是不同是 MC 并不回收垃圾，而 MS 往往进行回收。

d)       Coping

拷贝回收合并了 MC 算法中的扫描与压缩两个过程，它的目标也是将所有的活动对象移动到相邻的空间中，从而形成连续的可用内存。

最常见的 Coping 算法将堆分为两个区域，在运行过程中同时仅有一个区域可以被引用。在每一次整理过程中，使用区域的对象将会被拷贝到空闲区域中连续的存储空间中。 (Cheney) 使用广度优先的遍历算法 ( 内存中的引用关系是树状的结构 ) 。

Coping 的最大问题是它要求实际需要的近两倍的内存。增加可用的内存可以显著的提高 Coping 算法的效率，当可用内存不足的时候， Coping 的次数将会增加，提高 GC 对系统性能的影响。

e)       Non-Coping implicit collection

非拷贝隐式的内存收集算法为每一个对象增加了两个指针和一个颜色域，从而将内存中的所有对象组成了一个双向链表的结构 ( 颜色域标志当前对象处于哪一个内存节点 -bulk 中 ) 。与 Coping 相比，活动对象并不会在整理过程中被移动，所被改动的仅仅是对象的三个附加域。因此对象的回收可以在常数时间内被完成， NCIC 的消耗与系统中的对象的数目成正比。

NCIC 提高了对象遍历的效率，尤其是大对象的便利效率，但是它无法避免稀疏内存的问题。

f)        基本的 GC 算法可能造成的问题

所有的 GC 算法都存在 Time-Space 的平衡问题，即使主存的价格日益降低， CPU 的速度越来越快，他们仍将按比例的占用系统资源，带来很多额外的消耗。虚拟内存的存在使得 GC 算法的实现更加困难，因为对象存在于不同的页面当中，一次简单的 Coping 可能造成意想不到的大量页面交换。从而带来比理论值大的多得消耗。

因此在常用的 GC 实现中，都采用了合并集中算法的扩展的 GC ，我们将在下一部分对扩展的 GC 算法进行论述。

2.       扩展的垃圾收集算法

a)       Incremental Tracing Collectors

渐进的遍历回收 (ITC) 算法要求伴随程序执行的同时渐进的进行垃圾收集。但是应用程序本身可能在不断的修改已经被遍历过的对象，所以 ITC 必须有一个监视这些改变的方法。

 

b)       Generational Garbage Collection

GGC 为 Java 和 .Net 机制共同支持，需额外注意！

分代的垃圾收集的理论基础是大多数 (80% - 98%) 的对象之在堆上存在极短的时间，通常几百万条指令。对于简单的 Coping 算法，每一次都需要重复的移动这些对象，从而造成了极大的性能损耗。 GGC 通过把生存周期较长的对象移动到单独的堆代上，减少了这样的负担。

在一个程序中，如果对象在创建后一分钟仍然没有被回收，则，该对象很可能还要生存更长的周期， GGC 通过对堆进行划分，将比较老的对象 Copy 到更高的代中从而实现更加有效的垃圾回收。高代往往采用更高效的 Tracing 算法，而且不会被非常频繁的收集，这样可以有效地提高非实时性系统对于 GC 效率的要求，从而使 GC 造成的系统中断降低到用户不易觉察的程度。

GGC 的每一个代可以采用不同的 GC 算法。

GGC 的主要问题包括：

       Advancement Policies ，晋升策略，即确定将对象移到较老的代上所需要的生存周期。

       Heap Management ：即如何为不同的代分配堆空间

       Collection Scheduling ：即何时启动每个代的收集过程

       Inter-Generational Referencing ： 即跨代间的对象的相互引用。

       所有这些问题都与具体的应用程序相关，因此通用的解决方案可能难以满足特定应用的要求。

 

3.       Java(TM) 中的垃圾收集机制

Java1.4 中包含了 2 段 Generation(Younger and older) ，每一段有三种可选的垃圾回收算法。 java 支持 Incremental Collection 。 Java 提供了并行的垃圾收集支持。

4.       C# 中的垃圾机制机制

C# 采取了 3 段 Generation 的模式进行垃圾回收。每一代都采用了 Mark-Sweep 算法，在垃圾收集过程中会挂起所有的

5.       垃圾收集机制的效率测量

Garbage Collection 的效率比起手动的内存管理，性能上是会有些差距的，具体可能造成多大的影响？

注意：并不是只有自动内存回收的程序语言才会有垃圾回收的消耗，对于 C/C++ 这些手动管理内存的语言，内存分配与释放也是会造成系统一定的开销的。

 

6.       实用中的一些建议

自动垃圾收集取代了人工回收弃置内存的回收工作，极大地减少了内存维护方面的工作量，但是在实际的使用中我们必须注意如下一些问题，避免造成系统瓶颈。

避免频繁地创建临时指针

减少对象分配的次数，使用对象池的方法

连续存放需要持久使用的对象，避免频繁地页面切换。

 

对于 .Net 程序员，学会使用 System Monitor 中的 CLR 性能计数器分析系统的瓶颈所在。CLR Profiler 也是一个很好的实用工具。