Woowen You can do anything you set your mind to, man

垃圾回收的算法与实现 总结

本书主要讲解了常用的一些垃圾回收算法,以及根据这些基础算法而演化出来的算法

  • 标记-清除
  • 标记-复制
  • 标记-压缩
  • 引用计数
  • 合并型引用计数
  • 分代回收
  • 分区回收

标记-清除

由标记阶段和清除阶段组成,先将需要清除的垃圾对象标记住,然后在一起清除

优点

  • 实现简单
  • 与保守式GC算法兼容,因为在保守式GC中,对象是不能移动的

缺点

  • 碎片化,假设在第一次GC之后,因为标记清除之后是不会对存活的对象进行整理的,因此存活对象在堆中总是不连续的,那么就会给后续的分配带来问题,如图
  • 分配速度,因为标记清除之后存活对象在堆中是不连续的,因此后续给新对象分配堆空间时必须遍历整个空闲的空间,从而找到合适新对象大小的空闲堆空间

标记-复制

标记-复制算法简而言之就是将原本的堆一分为二,每次使用其中一份,当空间1需要垃圾回收的时候,将存活的对象复制到另外一份空间(空间2)中,然后清理空间1

优点

  • 优秀的吞吐量
  • 可实现高速分配,因为在垃圾回收之后会将存活对象复制到一块新的空间,因此在新空间中存活的对象是连续的.不需要为分配新对象而去遍历整个堆来找到合适的空闲空间来安置
  • 不会发生碎片,复制算法中每次运行gc都会进行压缩,因此不会产生碎片
  • 与缓存兼容,通过压缩算法,会把彼此之间有引用关系的对象放到较近的位置

缺点

  • 堆空间使用效率低下,因为一个堆被分成了2份,那么使用率只有原来的1/2
  • 不兼容保守式GC,因为会移动存活对象
  • 使用递归调用函数,复制某个对象时要递归复制它的子对象,每次进行复制都要调用该函数,因此会存在性能问题,以及栈溢出

演化算法

多空间复制算法,我们都知道标记-复制算法最大的缺点是堆空间利用率太低,被分成了2份,使用率只有50%,一份在使用的时候,另外一份在旁边等待,因此为了提高堆的利用率就演化出了多空间复制算法

整体逻辑是将空间分配成N份,然后每次gc保留其中2份作为from和to空间,用来使用标记-复制算法,其他N-2份使用标记-清除算法,从而提高堆的整体使用率,每次不能使用的堆只有1/N份,大大的提高堆利用率 但是引入了标记-清除算法,虽然提高了堆的使用率,但是引入了新的问题,例如上面提到的分配耗时,碎片等问题.然而技术从来都是个取舍的过程.永远没有完美的方案.需要根据业务需求制定合适的回收策略

标记-压缩

由标记阶段和压缩阶段组成

压缩阶段并不会改变对象的顺序,只是缩小他们之间的间隙,把他们聚集到堆的一端

优点

  • 可以有效的利用堆空间
  • 与缓存兼容,之前也提到过,压缩算法会将有引用关系的对象放置在堆中距离较近的位置,这样cpu就能根据缓存去读取从而编码读取多次,提高执行效率.

缺点

  • 压缩需要花费计算成本

引用计数

引用计数的本质是每个对象中有一个计数器,用来表示有多少个程序引用了该对象,当对象的计数>0时,表示这个对象有人在引用需要存活,当对象的计数=0时,表示可以回收,因为没人引用它,属于垃圾

优点

  • 可以立刻回收对象,当对象的计数变成0时可以立马被回收掉,增加堆空间的利用率,因为垃圾被回收之后就变成了空闲空间可以用来分配新对象
  • 最大暂停时间短
  • 可以不用从根沿着指针去查找标记过的对象,例如标记类的算法,都需要从根节点开始遍历所有标记过的对象然后开始清除

缺点

  • 计数器有性能问题,且会占用空间
  • 实现复杂
  • 存在对象之间相互引用的问题,比如对象A引用对象B,对象B引用对象A,其实这两个都是垃圾对象,但是无法回收

演化算法

引用计数算法有很多优点,比如当对象没有引用时可以立刻回收,加快堆的使用效率,但是因为计数器的引入也同时引入了新的问题,比如计数器本身也是要占用每个对象的存储空间的,计数器计数范围越大,占用的空间也就越大,因此优化的思路很大一部分是优化计数器

1位引用计数法

1位引用计数法的意思是,计数器只用1位表示,因为对象计数为0时变成垃圾可以回收,对象引用计数>1时就存在引用不能回收.考虑到这一点使用1位来计算就能解决问题,0表示有一个人在引用它,1表示引用它的人数量大于2

部分标记-清除算法

这种算法也是用来优化引用计数算法的,我们知道引用计数还有个循环引用的问题,因此优化方案就是对可能存在循环引用的对象,采取标记-清除算法执行,因为本身存在循环引用的对象的概率是很小的

因此过程就是

  • 1.采用引用计数清除一批计数为0的垃圾
  • 2.针对可能存在的循环引用的问题的对象标记出来作为嫌疑对象
  • 3.针对嫌疑对象再次使用标记-清除算法

部分标记清除算法也不是完美的,因为嫌疑对象比较是候选垃圾,因此数量也是很多的,所以虽然出现循环引用的对象概率小,清除时期性能影响不大,但是从候选垃圾中找出循环引用就比较耗费时间了

如何解决引用计数中循环引用的问题

  • 使用弱引用
  • 类似部分标记-清除算法解决,例如PHP,Python,redis都是使用标记-清除算法解决循环引用问题

合并型引用计数

在吞吐量方面,引用计数算法比不上搜索型的"标记-"算法,因为计数器的频繁增加减少导致的瓶颈,随着计算器的值变化,对应的是写入屏障的不断执行,计数器变化越是频繁,写入屏障执行也就越频繁

有时候我们一个计数器先+1,然后-1,这期间值其实是没有变化的,因为两次值更改对冲掉了.因此合并型引用计数的思想就是不在意计数器的变化过程,只在意值的最终结果从而提高性能

在合并型引用计数法中引入了一个缓冲区,当计数器变化时先写入缓冲区,这时候对象的计数不一定是正确的,因为缓冲区中的更改并没作用到对象,等到缓冲区满了.GC正式开始,通过查找缓冲区中对应的值来给每个对象的计数器做出最终判断

合并型引用计数器的优点是避免对计数器的频繁修改而增加吞吐量,它不是记录每次计数器的值变化,它在意的只有最终结果,数据的最终一致,从而提高吞吐量,但是它的缺点就是增加了最大暂停时间,因为当GC开始的时候需要去缓冲区中查找对应的最终结果,可以通过调整缓冲区的空间大小来缩短暂停时间

分代回收

分代回收算法是各种语言中常用到的垃圾回收算法,比如java7,引入了年龄的概念,使得堆空间被分为了"年轻代","老年代","元空间"(永久代),根据不同空间中对象的特性执行垃圾回收策略,提高回收效率

年龄的意思就是比如一个对象在一次垃圾回收中存活了下来,那么它的年龄就是1,存活几次每次的年龄都会自增,当年龄超过一点限制的时候就会晋升为老年代

根据28定律,大部分对象只能存活1次或者几次就会被回收,而只有少部分对象能存活到老年代,因此年轻代中的新生对象很大一部分都会在第一次执行gc的时候就被回收掉,因此新生代中的gc执行次数一定是最频繁的.而存活了几次都没有被回收(java中是15次)那么就一定是个生命力顽强的对象了.可以晋升到老年代,一般晋升到老年代的对象都是活跃了,存在垃圾的可能性较小,因此可以减少gc的执行频率,针对不同的对象进行分区,然后执行不同的gc策略进而争取最大的执行效率就是分代回收的根本目的

另外需要注意的是,分代回收并不是一种算法,跟上面的标记-清除,标记-压缩,甚至引用计数不同,它只是将上面多种算法组合使用的一种策略,对不同区使用不同算法,提高效率

从图可以看出,分成了新生代和老年代,新生代执行标记-复制算法,老年代执行标记-清除算法

新生代的执行过程

演化算法

多代垃圾回收

多代垃圾回收是将堆分成多个年龄段,每代都会有一个记录集,用于记录比当前代更年老的代中对象的引用,但是分的代太多,每代空间也就小,每代之间的相互引用就增多,各个代中的垃圾回收时间也会增加,因此少设置一些分代能增加吞吐量,一般2-3代就够了

列车垃圾回收

这个算法是针对分代回收中的老年代,因为原本的老年代是通过标记-清除算法进行的,每次都是对整个老年代进行标记,然后回收,暂停时间会比较长,而列车垃圾回收的思想就是将老年代划分为多个大小相同的区间,1次老年代回收就回收其中一个区间,而且在老年代中存在相互引用的对象被放置在同一个区间,这样回收效率也会增加,且减少了每次暂停的时间,当然代价肯定是回收的次数也会增加,但是作为整个应用来说,减少暂停时间增加暂停次数是可以接受的.

至于为什么叫做列车垃圾回收,是因为老年代的划分区间可以看做一个车厢,相互引用的对象被放置到同一个车厢中,每次回收一整个车厢的垃圾

最后,没有一种垃圾回收算法是完美的,增加了吞吐量,比如会增加最大暂停时间,要想缩短每次gc的暂停时间,那么吞吐量就会下降,这也是个权衡的过程,根据业务需求选择合适的算法和算法组合来达成目的

书中还有一些其他的算法,感兴趣的可以自己去看看

参考

垃圾回收的算法与实现

Woowen 浙ICP备15013647号