垃圾收集算法综述田红，余文(北京邮电大学计算机学院，北京100X76)摘要：全面总结垃圾收集算法的发展现状，阐述主要垃圾收集算法的思想，旨在帮助读者了解垃圾收集算法。本文首先阐述垃圾收集算法的引入和需求，然后介绍现冇的垃圾收集算法,最后总结并对比儿种主要垃圾收集思想的区别。关键词：算法理论；垃圾收集；引用计数；标记■清扫；节点复制中图分类号：TP39AnoverviewofgarbagecollectionalgorithmTianHong,YuWen(Beijinguniversityofpostsandcommunications,ComputerScience,Beijing100876)Abstract:Thepaperisanoverviewaboutgarbagecollectioninvirtualmachine.1(mainlydescribedtheideaofthemaingarbagecollectionalgorithmsroughlyaimingtofacilitatereaderstounderstandthisfield.Firsttheresearchbackgroundisintroduced.Afterformallyandinformallydescribingthegarbagecolletionalgorithm,acomparisonstudyisconductedbasedonthethreefundmentalalgorithms.Keywords:theoryofalgorithms;garbagecollection;referencecounting;mark-sweep;nodereplication0引言自动内存冋收机制⑴，是指不需要程序员手动进行内存的冋收，系统自动将不在需要的对象进行冋收。Java语言、Python语言的虚拟机⑵等具有这一特性，使得程序员不再需要像C语言程序员因为内存泄錨问题追踪对指针的处理，而这在大型系统构建时往往是难以发现和避免的。1现有垃圾收集算法在理解各种垃圾冋收算法叭⑸⑹前，必须先理解三经典方法：引用计数(referencecounting)＞标记■清扫(ma「k・sweep)ii和节点复制(copying)o然后其它种类的垃圾收集算法大多是这三种方法的结合或者衍生。1.1引用计数引用计数，通过计算指向每个单元的引用的数量，来判断该单元是否是可触及状态(只有不可触及的单元才能被垃圾收集器冋收)。引川计数的优点在于能够非常简单地判断单元是否正在使川。它夭生还是一个渐进式的技术，能够将内存管理的开销分布到整个程序Z中。从木质上说，苹于引用技术算法的垃圾收集器的工作策略，与那些苹于追踪的垃圾收集器完全不同。每个单元都冇一个额外的域，存放引用计数值(referencecount)。内存管理器必须为每个单元维护引用计数值，使之等于指向该单元的指针的数量。首先，这一算法把所有的单元放在一个自山单元池中，这个池的实现常常是一个链表。自山单元的引用计数为0,当一个新单元从池中被分配，它的引用计数被设为1.每次增加一个指针指向这一单元时，该单元的计数值加1；而每次删除某个指向它的指针时，它的计数值减1。如果单元的计数作者简介：III红，(I990-),女，在读硕士，数据挖掘。通信联系人：余文,(1964-),男,副教授,高性能计算。E-mail:yuwen@bupt.edu.cn值降为0,表示不再存在指向该单元的指针，即该单元变为不可触及状态。引用计数方法的长处在于内存管理的开销分布在整个计算过程Z中，对存活单元和废弃单元的管理与用户程序的执行交织在一起。这一特点与那些非渐进式的、基于追踪的收集器构成了一个对比，非渐进式垃圾收集器在运行时会挂起完成实际工作的用户程序。因此，若更“平滑”的响应时间比较巫要，那么引用计数可能是个合适的选择。基于引用计数的内存管理机制总是与客户程序或它的编译器紧密地耦合在一起。每一次更新或是复制指针，都必须调整引用计数值。就拿最简单的一种情况作为例子：这意味着当一个指针被传递给一个子过程时，必须增大引用计数，而返冋时必须减小。只要有一处遗漏,就会带来灾难性的后果。简单的引用技术的最主要的缺陷是它们无法冋收环形的数据结构，对于许多系统，冋收这类结构时个巫要的需求。环形数据结构的使用频率比表面上看上去高。1.2标记-清扫算法在标记■清扫算法中，内存单元不会在变成垃圾的同时立刻冋收，而是保持不可到达和未被发现的状态，直到所冇可用的内存都耗尽。如果此时再次出现对新单元的请求，系统会暂时挂起"右用''的程序，并调用垃圾收集例程，将堆中所有当前并未使用的单元清扫冋自山单元池中。其中，挂起”有用"程序会导致用户程序响应的延迟。标记■清扫算法依靠对所有存活单元进行一次全局遍历来确定哪些单元可...