详解gc(垃圾回收)机制三:GC复制算法

在前2篇中,我们大致了解了语言的gc,以及gc的基本概念

详解gc(垃圾回收)机制(一)

详解gc(垃圾回收)机制二:认识GC基本概念

gc算法大致分为以下几种:

1:标记-清除

2:引用计数法
3:GC复制
4:GC标记-压缩
5:保守GC

6:分代垃圾回收

7:增量式垃圾回收

8:RC Immix

在第一篇文章,有讲到  标记-清除,引用计数,以及go的特色 三色标记法.

GC复制算法

GC复制简单来说,就是获取到空间里的活动对象,将所有活动对象复制到其他框架,再把原来空间的所有对象回收掉.

我们把复制活动对象的原空间称为from空间,将粘贴活动对象的新空间称为 to空间

再复制完之后,下一次回收, to空间又变成了from空间,反之from变为了to空间

GC复制算法步骤:

1:设置指针地址为to空间地址开头

2:找到对象的根(root)

3:根据根进行遍历,同时将活动对象复制到to空间,标记该对象复制成功,记录新活动对象的指针

4:将活动对象的引用子对象遍历,复制到to空间,标记该对象复制成功,记录新活动对象的指针

5:重复3,4动作,直到没有任何可遍历对象

6:将from和to空间互换,整个复制过程完成

优点

1:吞吐量优秀

gc复制算法只搜索并复制活动对象,比一般的标记-清除算法来说,它能够在较短时间完成gc,吞吐量优秀.

2:可实现高数分配

gc复制算法不使用空闲的链表,因为to空间是连续的内存空间,只要to空间不小于from空间大小即可分配

3:不存在内存碎片

因为是直接在连续空间复制变量,不存在内存碎片,而一般的标记-清除算法,在清理非活动对象时,会产生一堆的内存碎片,导致需要通过空闲链表去管理

4:与cpu缓存兼容

在gc复制过程中,由于是 "深度优先遍历" 导致只要和活动对象相关的对象内存地址都在一起,因此mutator执行速度会非常快,cpu高速缓存也是读取位置较近的对象

缺点

1:堆使用效率低下

由于gc复制需要额外使用一个不小于from空间大小的to空间,那就只能让堆空间进行划分一半一半,使其能够支持gc复制,也就意味着进程只能使用一半的内存

2:不兼容保守式GC

保守式GC是啥我也不知道,等后面可以看看,主要是,GC复制需要移动对象重写指针,因为是直接复制到了to空间.

3:需要递归调用函数

在复制对象时,需要递归的复制子对象,每次复制都是需要递归的调用函数,消耗栈,还会出现栈溢出的风险

Cheney的gc复制算法

为了解决递归调用函数的栈问题,C.J.Cheney 研究出了自己的gc复制算法,他的算法不是递归的复制,而是迭代的进行复制

1:设置2个指针地址为to空间地址开头,为free,scan指针

2:找到对象的根(root)

3:根据根进行遍历,同时将根引用的活动对象复制到to空间,同时free指针增加 为 一个对象长度

4:遍历完根之后,移动一个scan指针到to空间的第一个复制对象,并且将对象引用的活动对象复制到to空间,同时free指针增加为一个对象长度

5:to空间第一个复制对象完成之后,scan指针移动到第二个对象,并且将对象引用的活动对象复制到to空间,同时free指针增加为一个对象长度

6:重复4,5步骤,直到scan指针和free指针重合

7:将from和to空间互换,整个复制过程完成

图解:

1:根引用对象为BG,

2:复制B,G对象,free指针右移,此时根对象遍历完成

3:开始复制B引用的对象A,复制成功之后B对象完成遍历,scan指针右移到G

优点

该算法比常规gc复制算法优化了递归操作,抑制了调用函数的额外负担和栈的消耗,从深度优先遍历改为了广度优先遍历

缺点

缺点就是抛弃了相邻内存的这个优点,无法充分利用cpu缓存

近似深度优先搜索方法

这个头晕了,以后有空补补

简单说一下就是增加了一个页的概念,

多空间复制算法

GC复制算法最大的缺点就是只能利用半个堆

但是如果我们把from空间分隔成n个部分,例如100M一个部分,总共10个 1000M,那么我们只要每次只复制一个空间,to空间只需要100M即可
那内存利用率就到达了90%!

当然,这个需要使用到标记-清除  算法进行给对象打上标记,

复制from1到to成功之后,将to改为from1,同时将from1改为to空间,去复制from2.....