垃圾收集的基本原理与算法

    到这里大家可能会问垃圾收集器是如何知道哪些对象是存活的（需要的），而哪些对
象是死亡的（不需要的）呢？许多Java的垃圾收集器都使用了引用的根集，作为分析对象
存活与否的依据。引用的根集是正在执行的Java程序随时都可以访问的引用的变量的集合
――也就是存在堆栈（Stack）或是静态存储空间(Static storage)上的引用变量。从这些
根集变量出发可直接或是间接到达的对象，垃圾收集器会认为这些对象是生命尚存的对象
；相对的从这些根集变量出发通过任意途径都无法到达的对象，就是死亡的，它们就会成
为下一次垃圾收集的对象。具体过程就像这样：从堆栈（Stack）和静态存储区域(Static
 storage)开始，走访所有引用之后，就能找出所有活动的对象。对于自己找到的每个引用
，都必须再跟踪到它指向的那个对象，然后跟随那个对象中的所有引用，“跟踪追击”到
它们指向的对象，如此反复，直到遍历了根源于堆栈或静态存储区域中的引用所形成的整
个网络为止。中途经历的每个对象都必须仍处于活动状态。 


    对于垃圾收集器找到的那些活动对象，具体应采取哪些操作呢？这正是我们接下去要
讨论的，大部分垃圾收集器都是基于几种算法的工作方式，并且它们是自适应的，也就是
说他们会根据情况自动的选择恰当的工作方式。 


    1、基于Copying算法的“停止而后复制（stop－and－copy）”方式：就像字面意思一
样，当一个内存堆满了，程序首先会停止运行。随后，基于Copying算法的垃圾收集器从根
集变量中跟踪所有存活的对象，并将已找到的每个活动对象从一个内存堆复制到另一个，
留下所有的垃圾。除此以外，随着对象复制到新堆，它们会一个接一个地首尾聚焦在一起
。这样可使新堆显得更加紧凑（并使新的存储区域可以简单地从最末端腾出空间，就像前
面讲述的那样）。当然，将一个对象从一处挪到另一处时，指向那个对象的所有引用（引
用变量）都必须改变。对于那些通过跟踪内存堆的对象而获得的引用，以及那些静态存储
区域，都可以立即改变。但在“遍历”过程中，还有可能遇到指向这个对象的其他引用。
一旦发现这个问题，就得通过后续过程才能找到。 


    但是在有的情况下将使得“复制式垃圾收集器”显得效率极为低下，比如随着程序进
入了稳定状态之后，它几乎不产生或产生很少的垃圾。尽管如此，这时的一个“复制式垃
圾收集器”仍会将所有内存从一处复制到另一处，这显得非常浪费。更糟的是：程序中的
对象不仅不死亡，而且一个个都很庞大，对两个大的内存堆管理也将成为不必要的消耗。
 






    2、基于Tracing算法、Compacting算法的“标记和清除（make－and－sweep）”方式
：对于常规性的应用，标记和清除显得非常慢，但一旦知道自己不产生垃圾，或者只产生
很少的垃圾，它的速度就会非常快。标记和清除（make－and－sweep）采用的逻辑：基于
Tracing算法从堆栈和静态存储区域开始，并跟踪所有引用，寻找活动对象。然而，每次发
现一个活动对象的时候，就会设置一个标记（一个位或多个位），为那个对象作上“记号
”。但此时尚不收集那个对象。只有在标记过程结束，清除过程才正式开始。在清除过程
中，不复存活的对象会被释放然而，不会进行任何形式的复制（这时的堆中被使用的空间
呈现不连续的状态）。所以假若收集器决定使这个断续的内存堆密集（compact），它将使
用Compacting算法重新整理他所找到的对象：垃圾收集器将所有的对象移置堆的一端。堆
的另一端就变成了一个相邻的空闲内存区。收集器会对它移动的所有对象的所有引用进行
更新，这样这些引用能够在新的位置识别同样的对象。为了简化对象引用的更新，compac
ting算法增加了间接的一层（level of indirection）。间接层通过句柄（handle）和句
柄表实现。在这种情况下，对象引用总是指向句柄表中同样的句柄入口。反过来，句柄入
口包含了句柄的实际引用。当compacting标记和清除垃圾收集器移动对象时，收集器在句
柄表中只修改实际的对象引用对句柄入口的所有引用没有受到影响。虽然使用句柄表简化
了堆碎片，访问每个对象增加了额外的开销这一缺点，这使得程序变慢。 


    3、Generational算法：前面提到的“停止而后复制（stop－and－copy）”方式的一
个缺点是收集器必须复制所有的存活对象，这就在程序执行之前增加了程序等待时间。在
实际中，我们可以发现：a、大多数程序对象存在的时间比较短，b、大多数程序创建了少
量的长时间存在的对象。Generational算法用以下的方法克服重复的复制长时间存在的对
象而带来的低效率：它们将内存堆分成两个或多个子堆，每个子堆都作为对象的一代（ge
neration）。垃圾收集更频繁地发生在代表年轻一代的子堆上。因为大多数程序对象存在
的时间都比较短，程序将逐渐不引用这些对象，垃圾收集器将从最年轻的子堆中收集他们
。在分代式的（generational）垃圾收集器运行一段时间后，上次运行中存活下来的对象
移动到下一个最高代的子堆中。每个日益增多的老一代子堆不会经常进行垃圾收集，因此
能够节约时间。   SUN的JVM中Garbage collector使用的是一种修改过的分代方式管理较
老的对象空间：引入了一种称为Incremental（train）增量式的算法。因为GC在JVM中通常
是由一个或一组进程来实现的，它本身也和用户程序一样占用heap空间，运行时也占用CP
U。当GC进程运行时，应用程序停止运行。因此，当GC运行时间较长时，用户能够感到Jav
a程序的停顿，另外一方面，如果GC运行时间太短，则可能对象回收率太低，这意味着还有
很多应该回收的对象没有被回收，仍然占用大量内存。因此，在设计GC的时候，就必须在
停顿时间和回收率之间进行权衡。增量式GC就是通过一定的回收算法，把一个长时间的中
断，划分为很多个小的中断，通过这种方式减少GC对用户程序的影响。虽然，增量式GC在
整体性能上可能不如普通GC的效率高（通常会使系统速度降低10%左右），但是它能够减少
程序的最长停顿时间。下图就表示了，增量式GC和普通GC的比较。其中灰色部分表示线程
占用CPU的时间。 




    4、Adaptive算法：对于特定的情况，一些垃圾收集算法要优于其他算法。Adaptive算
法监视当前的堆的情况，并基于具体的情况选择适当的垃圾收集方式，或者Adaptive算法
可能要将对象分成子堆，并在每个子堆赋予一个不同的垃圾收集方式。