`
123003473
  • 浏览: 1064625 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

垃圾回收算法【转载】

 
阅读更多
引用计数( Reference Counting )算法

1960 年以前,人们为胚胎中的 Lisp 语言设计垃圾收集机制时,第一个想到的算法是引用计数算法。拿餐巾纸的例子来说,这种算法的原理大致可以描述为:

午餐时,为了把脑子里突然跳出来的设计灵感记下来,我从餐巾纸袋中抽出一张餐巾纸,打算在上面画出系统架构的蓝图。按照“餐巾纸使用规约之引用计数版”的要求,画图之前,我必须先在餐巾纸的一角写上计数值 1 ,以表示我在使用这张餐巾纸。这时,如果你也想看看我画的蓝图,那你就要把餐巾纸上的计数值加 1 ,将它改为 2 ,这表明目前有 2 个人在同时使用这张餐巾纸(当然,我是不会允许你用这张餐巾纸来擦鼻涕的)。你看完后,必须把计数值减 1 ,表明你对该餐巾纸的使用已经结束。同样,当我将餐巾纸上的内容全部誊写到笔记本上之后,我也会自觉地把餐巾纸上的计数值减 1 。此时,不出意外的话,这张餐巾纸上的计数值应当是 0 ,它会被垃圾收集器——假设那是一个专门负责打扫卫生的机器人——捡起来扔到垃圾箱里,因为垃圾收集器的惟一使命就是找到所有计数值为 0 的餐巾纸并清理它们。

引用计数算法的优点和缺陷同样明显。这一算法在执行垃圾收集任务时速度较快,但算法对程序中每一次内存分配和指针操作提出了额外的要求(增加或减少内存块的引用计数)。更重要的是,引用计数算法无法正确释放循环引用的内存块,对此, D. Hillis 有一段风趣而精辟的论述:

一天,一个学生走到 Moon 面前说:“我知道如何设计一个更好的垃圾收集器了。我们必须记录指向每个结点的指针数目。” Moon 耐心地给这位学生讲了下面这个故事:“一天,一个学生走到 Moon 面前说:‘我知道如何设计一个更好的垃圾收集器了……’”

D. Hillis 的故事和我们小时候常说的“从前有座山,山上有个庙,庙里有个老和尚”的故事有异曲同工之妙。这说明,单是使用引用计数算法还不足以解决垃圾收集中的所有问题。正因为如此,引用计数算法也常常被研究者们排除在狭义的垃圾收集算法之外。当然,作为一种最简单、最直观的解决方案,引用计数算法本身具有其不可替代的优越性。 1980 年代前后, D. P. Friedman , D. S. Wise , H. G. Baker 等人对引用计数算法进行了数次改进,这些改进使得引用计数算法及其变种(如延迟计数算法等)在简单的环境下,或是在一些综合了多种算法的现代垃圾收集系统中仍然可以一展身手。

标记-清除( Mark-Sweep )算法

第一种实用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地应用于 Lisp 语言的标记-清除算法。仍以餐巾纸为例,标记-清除算法的执行过程是这样的:

午餐过程中,餐厅里的所有人都根据自己的需要取用餐巾纸。当垃圾收集机器人想收集废旧餐巾纸的时候,它会让所有用餐的人先停下来,然后,依次询问餐厅里的每一个人:“你正在用餐巾纸吗?你用的是哪一张餐巾纸?”机器人根据每个人的回答将人们正在使用的餐巾纸画上记号。询问过程结束后,机器人在餐厅里寻找所有散落在餐桌上且没有记号的餐巾纸(这些显然都是用过的废旧餐巾纸),把它们统统扔到垃圾箱里。

正如其名称所暗示的那样,标记-清除算法的执行过程分为“标记”和“清除”两大阶段。这种分步执行的思路奠定了现代垃圾收集算法的思想基础。与引用计数算法不同的是,标记-清除算法不需要运行环境监测每一次内存分配和指针操作,而只要在“标记”阶段中跟踪每一个指针变量的指向——用类似思路实现的垃圾收集器也常被后人统称为跟踪收集器( Tracing Collector )

伴随着 Lisp 语言的成功,标记-清除算法也在大多数早期的 Lisp 运行环境中大放异彩。尽管最初版本的标记-清除算法在今天看来还存在效率不高(标记和清除是两个相当耗时的过程)等诸多缺陷,但在后面的讨论中,我们可以看到,几乎所有现代垃圾收集算法都是标记-清除思想的延续,仅此一点, J. McCarthy 等人在垃圾收集技术方面的贡献就丝毫不亚于他们在 Lisp 语言上的成就了。

复制( Copying )算法

为了解决标记-清除算法在垃圾收集效率方面的缺陷, M. L. Minsky 于 1963 年发表了著名的论文“一种使用双存储区的 Lisp 语言垃圾收集器( A LISP Garbage Collector Algorithm Using Serial Secondary Storage )”。 M. L. Minsky 在该论文中描述的算法被人们称为复制算法,它也被 M. L. Minsky 本人成功地引入到了 Lisp 语言的一个实现版本中。

复制算法别出心裁地将堆空间一分为二,并使用简单的复制操作来完成垃圾收集工作,这个思路相当有趣。借用餐巾纸的比喻,我们可以这样理解 M. L. Minsky 的复制算法:

餐厅被垃圾收集机器人分成南区和北区两个大小完全相同的部分。午餐时,所有人都先在南区用餐(因为空间有限,用餐人数自然也将减少一半),用餐时可以随意使用餐巾纸。当垃圾收集机器人认为有必要回收废旧餐巾纸时,它会要求所有用餐者以最快的速度从南区转移到北区,同时随身携带自己正在使用的餐巾纸。等所有人都转移到北区之后,垃圾收集机器人只要简单地把南区中所有散落的餐巾纸扔进垃圾箱就算完成任务了。下一次垃圾收集的工作过程也大致类似,惟一的不同只是人们的转移方向变成了从北区到南区。如此循环往复,每次垃圾收集都只需简单地转移(也就是复制)一次,垃圾收集速度无与伦比——当然,对于用餐者往返奔波于南北两区之间的辛劳,垃圾收集机器人是决不会流露出丝毫怜悯的。

M. L. Minsky 的发明绝对算得上一种奇思妙想。分区、复制的思路不仅大幅提高了垃圾收集的效率,而且也将原本繁纷复杂的内存分配算法变得前所未有地简明和扼要(既然每次内存回收都是对整个半区的回收,内存分配时也就不用考虑内存碎片等复杂情况,只要移动堆顶指针,按顺序分配内存就可以了),这简直是个奇迹!不过,任何奇迹的出现都有一定的代价,在垃圾收集技术中,复制算法提高效率的代价是人为地将可用内存缩小了一半。实话实说,这个代价未免也太高了一些。

标记-整理( Mark-Compact )算法

标记-整理算法是标记-清除算法和复制算法的有机结合。把标记-清除算法在内存占用上的优点和复制算法在执行效率上的特长综合起来,这是所有人都希望看到的结果。不过,两种垃圾收集算法的整合并不像 1 加 1 等于 2 那样简单,我们必须引入一些全新的思路。 1970 年前后, G. L. Steele , C. J. Cheney 和 D. S. Wise 等研究者陆续找到了正确的方向,标记-整理算法的轮廓也逐渐清晰了起来:

在我们熟悉的餐厅里,这一次,垃圾收集机器人不再把餐厅分成两个南北区域了。需要执行垃圾收集任务时,机器人先执行标记-清除算法的第一个步骤,为所有使用中的餐巾纸画好标记,然后,机器人命令所有就餐者带上有标记的餐巾纸向餐厅的南面集中,同时把没有标记的废旧餐巾纸扔向餐厅北面。这样一来,机器人只消站在餐厅北面,怀抱垃圾箱,迎接扑面而来的废旧餐巾纸就行了。

实验表明,标记-整理算法的总体执行效率高于标记-清除算法,又不像复制算法那样需要牺牲一半的存储空间,这显然是一种非常理想的结果。在许多现代的垃圾收集器中,人们都使用了标记-整理算法或其改进版本。

增量收集( Incremental Collecting )算法

对实时垃圾收集算法的研究直接导致了增量收集算法的诞生。

最初,人们关于实时垃圾收集的想法是这样的:为了进行实时的垃圾收集,可以设计一个多进程的运行环境,比如用一个进程执行垃圾收集工作,另一个进程执行程序代码。这样一来,垃圾收集工作看上去就仿佛是在后台悄悄完成的,不会打断程序代码的运行。

在收集餐巾纸的例子中,这一思路可以被理解为:垃圾收集机器人在人们用餐的同时寻找废弃的餐巾纸并将它们扔到垃圾箱里。这个看似简单的思路会在设计和实现时碰上进程间冲突的难题。比如说,如果垃圾收集进程包括标记和清除两个工作阶段,那么,垃圾收集器在第一阶段中辛辛苦苦标记出的结果很可能被另一个进程中的内存操作代码修改得面目全非,以至于第二阶段的工作没有办法开展。

M. L. Minsky 和 D. E. Knuth 对实时垃圾收集过程中的技术难点进行了早期的研究, G. L. Steele 于 1975 年发表了题为“多进程整理的垃圾收集( Multiprocessing compactifying garbage collection )”的论文,描述了一种被后人称为“ Minsky-Knuth-Steele 算法”的实时垃圾收集算法。 E. W. Dijkstra , L. Lamport , R. R. Fenichel 和 J. C. Yochelson 等人也相继在此领域做出了各自的贡献。 1978 年, H. G. Baker 发表了“串行计算机上的实时表处理技术( List Processing in Real Time on a Serial Computer )”一文,系统阐述了多进程环境下用于垃圾收集的增量收集算法。

增量收集算法的基础仍是传统的标记-清除和复制算法。增量收集算法通过对进程间冲突的妥善处理,允许垃圾收集进程以分阶段的方式完成标记、清理或复制工作。详细分析各种增量收集算法的内部机理是一件相当繁琐的事情,在这里,读者们需要了解的仅仅是: H. G. Baker 等人的努力已经将实时垃圾收集的梦想变成了现实,我们再也不用为垃圾收集打断程序的运行而烦恼了

分代收集( Generational Collecting )算法

和大多数软件开发技术一样,统计学原理总能在技术发展的过程中起到强力催化剂的作用。 1980 年前后,善于在研究中使用统计分析知识的技术人员发现,大多数内存块的生存周期都比较短,垃圾收集器应当把更多的精力放在检查和清理新分配的内存块上。这个发现对于垃圾收集技术的价值可以用餐巾纸的例子概括如下:

如果垃圾收集机器人足够聪明,事先摸清了餐厅里每个人在用餐时使用餐巾纸的习惯——比如有些人喜欢在用餐前后各用掉一张餐巾纸,有的人喜欢自始至终攥着一张餐巾纸不放,有的人则每打一个喷嚏就用去一张餐巾纸——机器人就可以制定出更完善的餐巾纸回收计划,并总是在人们刚扔掉餐巾纸没多久就把垃圾捡走。这种基于统计学原理的做法当然可以让餐厅的整洁度成倍提高。

D. E. Knuth , T. Knight , G. Sussman 和 R. Stallman 等人对内存垃圾的分类处理做了最早的研究。 1983 年, H. Lieberman 和 C. Hewitt 发表了题为“基于对象寿命的一种实时垃圾收集器( A real-time garbage collector based on the lifetimes of objects )”的论文。这篇著名的论文标志着分代收集算法的正式诞生。此后,在 H. G. Baker , R. L. Hudson , J. E. B. Moss 等人的共同努力下,分代收集算法逐渐成为了垃圾收集领域里的主流技术。

分代收集算法通常将堆中的内存块按寿命分为两类,年老的和年轻的。垃圾收集器使用不同的收集算法或收集策略,分别处理这两类内存块,并特别地把主要工作时间花在处理年轻的内存块上。分代收集算法使垃圾收集器在有限的资源条件下,可以更为有效地工作——这种效率上的提高在今天的 Java 虚拟机中得到了最好的证明。

转载地址:http://www.game798.com/html/2007-04/3425.htm


http://www.javatang.com/archives/2007/12/03/1653250.html

http://www.wangdanwei.com/?p=80


http://hi.baidu.com/xuwanbest/blog/item/0587d82f2c44a73d1e30892e.html


http://www.diybl.com/course/3_program/java/javajs/2008630/129292_2.html


http://lists.canoo.com/pipermail/webtest/2004q3/002460.html
分享到:
评论

相关推荐

    高清完整版 The Garbage Collection Cookbook 垃圾回收算法手册

    The Garbage Collection Cookbook 垃圾回收算法手册

    The Garbage Collection Cookbook(垃圾回收算法手册)(中文版)

    垃圾回收算法的经典著作之一,常见的垃圾回收算法 【中文版】 垃圾回收算法的经典著作之一,常见的垃圾回收算法 【中文版】

    JVM之基本的垃圾回收算法汇总

    这篇博客将探讨JVM中的基本垃圾回收算法,帮助我们更好地理解JVM内存管理的原理。 1. 标记-清除(Mark-Sweep)算法 这是最早的垃圾回收算法之一。它分为两个阶段:标记和清除。首先,从根节点开始遍历所有可达对象...

    java虚拟机垃圾回收算法

    这是一篇关于java虚拟机垃圾回收算法的论文。

    JVM调优总结(三)基本垃圾回收算法.pdf

    JVM垃圾回收算法总结 垃圾回收算法是Java虚拟机(JVM)中的一种机制,用于回收无用的对象以释放内存空间。垃圾回收算法可以从不同的角度划分,下面是常见的垃圾回收算法: 1. 引用计数(Reference Counting) ...

    垃圾回收算法与实现——高清非扫描.pdf

    算法篇介绍了标记-清除算法、引用计数法、复制算法、标记-压缩算法、保守式GC、分代垃圾回收、增量式垃圾回收、RC Immix算法等几种重要的算法;实现篇介绍了垃圾回收在Python、DalvikVM、Rubinius、V8等几种语言处理...

    11 垃圾回收算法.md,学习代码

    《垃圾回收算法详解》 在Java编程语言中,内存管理是一项关键任务,它涉及到程序运行时的内存分配和释放。由于程序员无需手动管理内存(即回收不再使用的对象),这一过程由Java虚拟机(JVM)的垃圾回收机制自动...

    各种垃圾回收算法的实现,C语言版本.zip

    然而,这个压缩包"各种垃圾回收算法的实现,C语言版本.zip"提供了一些C语言实现的垃圾回收算法,让我们来详细探讨一下这些算法。 1. **引用计数法(Reference Counting)**: 引用计数是最简单的垃圾收集策略,每...

    GC.mmap-垃圾回收算法脑图

    GC总结

    关于javal垃圾回收机制的一些文档

    Java垃圾回收机制是Java编程语言中的一个重要特性,它自动管理程序的内存,释放不再使用的对象,以防止内存泄漏。在Java中,程序员不需要手动管理内存,这是Java与C++等其他语言的一个显著区别。垃圾回收机制是Java...

    一种基于差分进化的Flash文件系统垃圾回收算法.zip

    标题中的“一种基于差分进化的Flash文件系统垃圾回收算法”指的是在Flash存储设备上的文件系统中,采用差分进化算法来实现更高效的垃圾回收机制。这种算法是针对Flash存储的特点,解决其在长时间使用后可能出现的...

    Java垃圾回收新算法刍探.pdf

    本文将深入探讨Java垃圾回收的新算法,并分析它与传统算法的区别以及所带来的潜在优势。 首先,我们回顾一下Java垃圾回收机制的几项主要优点。自动内存管理是Java垃圾回收机制的核心,它能够自动识别和回收不再被...

    深入理解JVM垃圾收集算法与垃圾收集器

    深入理解JVM垃圾收集算法与垃圾收集器

    垃圾回收的算法与实现.docx

    "垃圾回收的算法与实现" 垃圾回收是指将废弃物中有再利用价值的部分分离出来,进行加工处理、再生利用,以减少垃圾对环境的污染和资源的浪费。垃圾回收的重要性在于,它既是环境保护的重要措施,也是资源循环利用的...

    新一代垃圾回收器ZGC设计与实现.ch01.print1

    本章主要介绍了垃圾回收算法和JVM中实现的不同类型的垃圾回收器。 首先,垃圾回收的目的是识别并回收不再使用的对象,释放它们占用的内存资源。在Java中,主要采用可达性分析法来确定哪些对象是可回收的,即从根...

    C++模拟存储器的分配与回收算法实现

    本文将深入探讨C++中模拟存储器的分配与回收算法,包括最先适应法、最佳适应法和最坏适应法,并通过运行结果截图进行辅助理解。 **最先适应法(First Fit)** 最先适应法是一种简单的内存分配策略。当一个进程请求...

    java垃圾回收机制

    Tracing算法是目前广泛使用的垃圾回收算法之一,它通过追踪从根集(root set)出发可达的对象来确定哪些对象仍然有效。根集通常包括当前栈中的局部变量、静态变量以及常量池中的引用等。 该算法的过程如下: - 从...

Global site tag (gtag.js) - Google Analytics