简明现代魔法 -> 编程思想 -> 自动垃圾回收的算法实现思路

自动垃圾回收的算法实现思路

2011-05-27

显式的内存管理的复杂性,而且还容易出错。因此我们需要一种自动内存管理的策略,这就是自动垃圾回收机制。既然是自动垃圾回收,那么平台肯定得采取一种方式发现垃圾,然后清除。这就是垃圾收集算法所关注的问题。垃圾收集算法的任务就是将活动的对象和已经死掉的对象分别出来,然后将死掉的对象的内存回收,而且为了更好的利用内存,有的算法还会对内存碎片进行压缩。下面会对常用的垃圾收集算法进行介绍:

引用计数(Reference Counting)

引用计数,顾名思义,就是每个对象上有个计数器,当添加了一个对它的引用时它的计数器就会加1,当不再使用这个引用时它的计数器就会递减1。当计数器为0的时候则认为该对象是垃圾,可以被回收了,如果该对象被回收则该对象所引用的所有对象的计数器会跟着递减。这样有可能会有很多对象的引用都减为0。

使用引用计数做垃圾收集的算法的一个优点是实现很简单,与其他垃圾收集算法相比还有个特点是它的垃圾收集过程不会造成程序暂停(这个后面会提到)。因为计数的递增和递减是在程序运行过程中进行的,当一发现某个对象的计数为0马上可以回收掉。

但是引用计数也有自己的困难:环形引用。比如现在A对象引用B对象,B对象的计数器加1,然后B引用C,C的计数加1,后来C又引用B,B的计数加1得到2。假如现在A不再引用B了,B的计数器成为1。而由于B、C互相引用,形成一个孤岛,但是计数器又没有变成0,又无法回收。这个问题在面向对象这类语言里更加严重。

实际上引用计数是如此简单,又很有效的资源管理方法,在很多场景中都会得到应用。比如你可以为了高效的利用资源,不每添加一次引用就拷贝一份资源,你可以只增加引用计数,而不拷贝。

之前曾做过一个实时监视的系统,安装在客户端上的进程不断的把监视客户端的信息(比如屏幕截图)发送到服务器端。服务器端是一个Web程序,多个管理员可以监视同一个客户端。当一个管理员监视开始监视某个客户端时我就给对应的数据上的一个计数器加1,当停止监视会管理员退出登录时,就减1,当递减为0时服务器端就不再接受客户端的监视数据,并发送停止监视的指令给客户端。这样不仅避免了为每个正在监视的管理员复制一份数据,还很好的控制了数据的生命周期。

跟踪(trace)

使用跟踪对象的关系图,然后进行收集。使用跟踪方式的垃圾收集算法主要有以下几种:

标记清扫(Mark-Sweep)

当内存分配时,可能超过某个阀值(具体操作根据各平台有所不同),然后触发垃圾回收。首先垃圾收集器会确定一些根:比如线程当前正在执行的方法的局部变量,方法参数,以及所在类的实例变量及所有静态变量。然后垃圾收集器会从这些根对象出发查找他们所有的引用,然后在被引用的对象上作标记(mark),当垃圾收集器遇上一个已经被标记的对象后就不再往前走了(避免循环标记,造成死循环)。这个阶段就是所谓的标记阶段(Mark Phase)。当标记阶段结束后,所有被标记的对象就称为可达对象(Reachable Object)或活对象(Live Object),而所有没有被标记的对象则被认为是垃圾,可以被回收。这个阶段进行完后就进入了清扫阶段(Sweep Phase)。这个阶段会遍历所有对象,然后将没有做标记的对象所占的内存全部回收。

这个算法存在一个问题就是内存碎片。在开始的时候内存可能是按顺序分配的,然后经过几次垃圾回收后,这块连续的内存空间中有的对象变成了垃圾,被回收了,而有的还是存活的对象。这样这块内存中就会出现很多洞。内存碎片是非常有害的,有可能空闲内存还很多,但都是不够大的碎片,会造成下一次分配时因没有任何一个"洞"可以装得下这个对象,抛出out of memory的异常(OOM)。这样另一种算法就出现了。

标记压缩(Mark-Compact)

标记压缩算法的标记阶段和标记清扫算法的标记阶段是一致的,就不再重复。使用标记压缩算法时,标记完可达对象之后,我们不再遍历所有对象清扫垃圾了,我们只需要将所有存活对象向"左"靠齐,让不连续的空间变成连续的,这样就没有内存碎片了。不仅如此,因为不再连续的空间变成连续的,内存分配也更快速了。

对于标记清扫算法来说,因为内存中有破洞,空闲内存不再连续,为了分配内存,系统内可能要维护着一个空闲内存空间的链表。当需要分配内存时,会遍历这个链表,找到一个够大的内存块,然后将其分成两份,一份用作当前的分配,另一份放回链表(这样有造成更多的内存碎片,也有一些策略并不是按顺序查找,找到够大的就好,有可能是找到一个更好的空闲内存块为止)。

而对于标记压缩算法,内存空间是连续的,我们只需要一个指针标记出下一次分配工作要从哪里开始就可以了,分配后将指针递增所分配对象的大小,这个工作是非常快速的,而且不用维护那个空间内存链表了。

这样一看好像标记压缩算法绝对的优于标记清扫算法,那标记清扫还有啥存在的必要了呢?不过要记住的一点是标记压缩算法为了达到压缩的目的,是需要移动对象的,这样所有对象的引用都必须更新。看来有利必有弊啊。

标记拷贝(Mark-Copy)

标记阶段还是和前面的一样,拷贝阶段会将所有存活对象拷贝到另一块空闲内存,而原先的内存将全部成为空闲内存。这个算法实现起来也很简单,高效(Sun JVM的新生代的垃圾回收就使用了这种算法)。

跟踪方式的其他问题

使用跟踪的方式来垃圾收集还有一些其他问题:

  1. 需要暂停当前程序的运行。 因为在垃圾收集过程中,如果当前程序还在运行,则会继续分配和使用内存,会带来更复杂的问题,为了避免这些问题大部分垃圾收集器的实现都会或多或少的暂停所有线程(只会暂停执行托管代码的线程)。这对于实时性很高的应用有可能是不可接受的。
  2. 有些垃圾收集器在某些阶段,垃圾收集的线程可以与应用程序的线程并发执行,但是垃圾收集线程也会占用系统资源,会降低应用程序的执行性能。
  3. 所有的线程都在同一个堆上分配,就有可能造成数据不一致的情况,这就需要锁定来做到线程的同步,这样会降低内存分配的效率,可以将内存划分为很多区域,给每个线程一个区域,做到不需要同步的情况。

分代

上面介绍了跟踪方式的垃圾收集算法,在这些算法中都有一个共同点:标记出可达对象。可想而知,如果需要标记的空间非常大,需要标记的对象非常多,这个过程将非常缓慢的,为了让这个过程更加快速,现代大多垃圾收集器都将内存空间分代。比如CLR的0、1和2代。JVM的新生代、旧生代和持久代。这样垃圾回收时就会在一个相对来说更小的空间里遍历标记。

不过这种分代的策略也依赖一些经验假设:

  1. 新分配的对象的生命周期相对更短
  2. 老对象的生命周期会更长
  3. 很少有老对象引用新对象
  4. 小对象的生命周期更短

总结

本篇主要关注垃圾收集的算法上,这些算法应用到实际的平台还会有各种各样的问题和应用策略。

可能有人会讲,我们为什么需要了解自动垃圾回收机制是如何工作的呢?这个对应用程序员来说不是一个黑盒么?在某种程度上来说是一个黑盒,你确实不能控制垃圾收集器的行为。但是知道这些细节之后我们可能会对垃圾收集器进行一些调校,让他更适合我们的应用:客户端应用?服务器端应用?实时应用?等等(在这方面JVM提供了很多可配置的选项,可以根据实际场景进行调整,而CLR只提供了很少的配置功能)。

而且,了解这些特性我们还能写出对垃圾收集器更友好的代码:比如对标记压缩算法了解后,我们可能会发现,对垃圾收集器来说,占时间的不是有多少垃圾,而是现在系统中存活的对象的多少。如果有很多小的存活对象,那么就需要更长时间来标记。

随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们