几种经典的垃圾回收算法

原创
2014/07/16 10:11
阅读数 5.2K

来自:http://blog.csdn.net/wallwind/article/details/6889917

自动发现和回收不再使用的内存,不需要程序员的协助。C#,java,python都引入了垃圾回收机制。c++中的智能指针和弱引用也使用了类似机制。

自动垃圾回收机制消除了空指针、多次释放指针空间和内存泄露等问题。

1、引用计数

 引用计数(Reference Counting)算法是每个对象计算指向它的指针的数量,当有一个指针指向自己时计数值加1;当删除一个指向自己的指针时,计数值减1,如果计数值减为0,说明已经不存在指向该对象的指针了,所以它可以被安全的销毁了。

引用计数的优点是它在进行垃圾回收的时候无需挂起程序,常用在实时系统中;空间上的引用局部性比较好。某个对象的引用计数变为0后,系统无需访问位于堆中其他页面的单元。废弃即回收。

缺点:每次创建和销毁都要更新引用计数值,会引起额外的开销;引用计数占据了额外的空间;无法处理环形引用;

python中使用的是引用计数算法。当对象的引用计数值为0时,将会调用__del__函数,至于为什么Python要选用引用计数算法,据我看过的一篇文章里面说,由于Python作为脚本语言,经常要与C/C++这些语言交互,而使用引用计数算法可以避免改变对象在内存中的位置,而Python为了解决环形引用问题,也引入gc模块,所以本质上Python的GC的方案是混合引用计数和跟踪(后面要讲的三个算法)两种垃圾回收机制。

2、跟踪垃圾回收

2.1标记-清除算法

对所有存活对象进行一次全局遍历来确定哪些对象可以回收,遍历的过程从根出发,找到所有可达对象,除此之外,其它不可达的对象就是垃圾对象,可被回收。整个过程分为两个阶段:标记阶段找到所有存活对象;清除阶段清除所有垃圾对象。

相比较引用计数算法,标记-清除算法可以非常自然的处理环形引用问题,另外在创建对象和销毁对象时时少了操作引用计数值的开销。

它的缺点在于标记-清除算法是一种“停止-启动”算法,在垃圾回收器运行过程中,应用程序必须暂时停止。另外,标记-清除算法在标记阶段需要遍历所有的存活对象,会造成一定的开销,在清除阶段,清除垃圾对象后会造成大量的内存碎片。

2.2 标记-缩进算法

 标记-缩并算法是为了解决内存碎片问题而产生的一种算法。它的整个过程可以描述为:标记所有的存活对象;通过重新调整存活对象位置来缩并对象图;更新指向被移动了位置的对象的指针。

2.3 复制算法

复制算法是把整个堆分成两个半区(From,To), GC的过程其实就是把存活对象从一个半区From拷贝到另外一个半区To的过程,而在下一次回收时,两个半区再互换角色。在移动结束后,再更新对象的指针引用

 节点拷贝算法由于在拷贝过程中,就可以进行内存整理,所以不会再有内存碎片的问题,同时也不需要再专门做一次内存压缩。,而它最大的缺点在于需要双倍的空间

3、 三色标记法

(1)黑色:本身强引用,并已处理对象中的子引用

(2)灰色:本身强引用,还没处理对象中的子引用

(3)白色:不可达对象


java中的分代垃圾回收

http://www.blogjava.net/fancydeepin

Java 中的堆是 JVM 所管理的最大的一块内存空间,主要用于存放各种类的实例对象。在 Java 中,堆被划分成两个不同的区域:新生代 ( Young )、老年代 ( Old )。新生代 ( Young ) 又被划分为三个区域:Eden、From Survivor、To Survivor。这样划分的目的是为了使 JVM 能够更好的管理堆内存中的对象,包括内存的分配以及回收。

JVM 每次只会使用 Eden 和其中的一块 Survivor 区域来为对象服务,所以无论什么时候,总是有一块 Survivor 区域是空闲着的。因此,新生代实际可用的内存空间为 9/10 ( 即90% )的新生代空间。新生代垃圾回收采用复制算法,清理的频率比较高。如果新生代在若干次清理(可以进行设置)中依然存活,则移入老年代,有的内存占用比较大的直接进入老年代。老年代使用标记清理算法,清理的频率比较低。


展开阅读全文
打赏
2
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
2
分享
返回顶部
顶部