垃圾收集的原理浅析.doc

垃圾收集的原理浅析1. 自动垃圾收集(GC)中的常用算法关键术语： a) 垃圾(garbage/live object)，指在程序中堆上已经被分配但是不会被再次使用的对象。许多数据说明，在实际的程序中，大多数的对象只存在一个很短的周期，需要长期保存Reference的对象很少。b) 垃圾收集：所有的允许分配堆内存的程序都提供了垃圾收集方法。在C/C+中，实现需要用户自己调用alloc/free , new/delete分配内存。在C#/Java中，虚拟机都提供了自动垃圾收集，根据对象的生存周期与引用计数对垃圾对象进行回收。c) 堆空间的增长与重整：To-do：how did C/C+ do thisC#的堆空间大小限制取决于虚拟内存的大小，通常来说.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 CollectionGGC为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. 实用中的一些建议自动垃圾收集取代了人工回