垃圾回收逻辑推演

Updated on with 0 views and 0 comments

1 从内存分配说起

1.1 指针碰撞

008fca3f20194b5bb0fba3f18fb3af50.png

282bb0444b864b56818222719e8505c4.png

1.2 空闲列表

426a4c2aca0848ee82bcea88de7cf39a.png

08f506b51da34efe81d853db39d82153.png

0af74f85c46743808a61dd7a2f43864d.png

fa77861484a64a62aca457d6b4acac7a.png

2 引用计数法

引用计数逻辑简单,可以做到对无用的资源进行立即回收,但无法应对高并发、高吞吐的场景,另外循环引用问题是其致命缺陷。

2.1 更新引用

4ef2547d375c44b9a883ce9b272de53f.png

2.2 减少计数

ceb2db71b33d45cb9ff7c52a5b7e1fe1.png

2.3 合并型引用计数法

14cb9397b38e4a5eb5a81879200e0811.png

1ce813758b344df89a9b42725b409552.png

3 标记-清除法

Mark-Sweep 算法回收的是垃圾对象,如果垃圾对象比较少,回收阶段所做的事情就比较少,所以它适合于存活对象多、垃圾对象少的情况。

3.1 标记阶段

c1ef338a46f94a7aa59dd0dc3f7281fd.png

3.2 清除阶段

37ab405e5a4d4eefb5e60f5fe5ec8279.png

3.3 标记位图

标记位图与写时复制技术兼容,清除操作更高效。

0cba2c332c6b4b6c87291cf9c189454c.png

3a0eb358eff6445d961917d4c6f71b8f.png

6fcf9a128e194caa98a4e57ec81accf2.png

3.4 多个空闲列表

ee15cc1c0ca7427680ab8aad1f0d340d.png

4 复制算法

复制算法搬移的是活跃对象,所以它更适合存活对象少、垃圾对象多的情况。

4.1 forwarding指针

238ebe80506c44fe8a66a3e30d58ce21.png

4.2 非递归广度优先复制算法

b8b8aff1a826495fa6d38c82303969a0.png

4.3 近似深度优先复制算法

9ca1b5596bae43568832177603f66ad1.png

关键变量:

44f72900e9e44cb096298b07bb4cd419.png

  • $page,将堆分割成一个个页面的数组,$page[i] 指向第 i 个页面的开头
  • $local_scan,将每个页面中搜索用的指针作为元素的数组,$local_scan[i] 指向第 i 个页面中下一个应该搜索的位置
  • $major_scan,指向搜索尚未完成的页面开头的指针
  • $free,指向分块开头的指针

核心思想:在每个页面上分别进行广度优先搜索

执行结果如下图所示:

0b907a98c43b4a81880b1bde6ba45e01.png

b65d98a048a64536950430f9b92e02ed.png

5 标记-压缩法

287710f8349d4c47b50215936931ef76.png

5.1 设定forwarding指针

e4c1dc839d6b4027b821b33f524e0115.png

在 GC 标记-压缩算法中对象的新空间和原空间可能会有重合,因此在移动对象前,需要事先将各对象的指针全部更新到预计要移动到的地址。

7c95f35712864412a38f19b0c54d38d6.png

5.2 更新指针

6cf6f5b2dcdc4ece978e5596830ea185.png

在这个步骤中需要搜索整个堆,更新各个对象的指针。请注意,这是第 2 次对整个堆执行搜索。

e24e8bc4626944c3a82c8542d40201b6.png

5.3 移动对象

d3e5b95525264ba8b667832a254c3f3e.png

在这个步骤中需要搜索整个堆,将活动对象移动到forwarding指针的引用目标处。请注意,这是第 3 次搜索整个堆。

06e2dfc24324405286791012111cd5a4.png

6 分代垃圾回收

6.1 分代GC核心思想

分代GC这个概念最早由 David Ungar 于1984年在论文中提出的,他将堆内存分为4个空间:Eden、两个Survivor、OldGen,其中Eden和两个Survivor合称为新生代空间。堆结构如下图所示:

4acb4f46639a418c9ad32415b5f3b477.png

核心思想:对于存活时间比较短的对象,用复制算法回收;对于存活时间比较长的对象,就可以使用 Mark-Sweep 算法

6.2 记录集

记录集(Remember Set)被用于高效地寻找跨代引用,具体来说,在 GC 时将记录集看成根(像根一样的东西),并进行搜索,以发现指向待回收区的指针。

15a7548e52d744c481915703308ad947.png

最直观的思路是,记录集里记录被引用到的对象:

6cbd059387004314941a3ea17987753a.png

上图左边的记录集中记下了被跨代引用的 B 和 D 两个对象,那么当发生年轻代 GC 时,就能正确地找到 B 和 D 对象是根对象。但是这样做的问题是,当 B 和 D 再经过一轮年轻代 GC,它们的位置发生变化以后,A 对象对它们的引用无法正确维护。

为了解决这个问题,在记录集里不会记录引用的目标对象,而是记录发出引用的对象

038e0c50dd3040d6854ca2c536c0cb38.png

6.3 写屏障

写屏障(write barrier)是维护记录集的手段:

9410830fadb24baf899c19b4af2a2277.png

对象晋升也可能产生跨代引用:

96b8189da51448be9ae5e9ee1377a169.png

6.4 卡表

卡表(Card table)可以提升写屏障效率,借鉴了位图的思路。

9562455ee970413d94d7a873700538d7.png

只更新脏卡片:

384f6d2216914a07898cc1ebfcfed4a3.png

7 增量式垃圾回收

7.1 三色标记法

e62975b4024848d499ca9846a9f30c8a.png

  • GC 开始运行前所有的对象都是白色
  • 灰色表示该对象已经被访问过,但是该对象引用的其他对象还没有被全部访问
  • 在代码实现中,灰色代表将对象压入待处理的栈或者队列
  • 当 GC 结束时已经不存在灰色对象了,活动对象全部为黑色,垃圾则为白色

三色标记的问题:

  • 浮动垃圾
  • 对象漏标
    d3339ae3f1fd4dee90f92987b19bd592.png
    • CMS对增加引用环节进行处理(Increment Update)
    • G1则对删除引用环节进行处理(SATB)

7.2 写屏障对比

156d7f15aa634e22a6adbad6cf3d3baf.png

2ddc00e66f6340f58ea3d29b2b291eb0.png

da92666cbb2845baa369f41ca3ff52a6.png

7.3 分配与标记

7904f0484b734c28b1d1da3401f94b0a.png

a7aae458c228406a97f05f9478c10b55.png

8 无暂停垃圾回收

8.1 染色指针

d69f08e49fcb44b7bad2ab8a941fa441.png

第 46 和 47 位是预留的,也就是说标记位可以继续向左移两位,那么可以支持的堆空间就可以扩展到 16T。

8.2 读屏障

151e63dd653f4188bab9a1e72313fd29.png

上图中,当 foo 对象发生转移之后,对象 a 再访问 foo 时就会触发 read barrier。read barrier 会查找 forwarding table 来确定对象是否发生了转移,确定 foo 被转移到新地址 foo(new)之后,直接将这一次对 foo 的访问更改为 foo(new)。由于整个过程是依托于 read barrier 自动完成的,这个过程也叫“自愈”。

读屏障示例:

b6d26fde08ab489ab43b870cf0a2af36.png

8.3 ZGC的回收原理

47aa15cd9fbf4f179852c946958ddc49.png

  • 在 GC 开始之前,地址视图是 Remapped
  • 在 Mark 阶段需要做的事情是将遍历到的对象地址视图变成 Marked0
  • 应用线程在并发标记的过程中也会产生新的对象都认为是活的
  • 所有标记为 Marked0 的对象都认为是活跃对象,活跃对象会被记录在一张活跃表中
  • 视图仍旧是 Remapped 的对象,就认为是垃圾
  • Relocate 阶段的主要任务是搬移对象,但不会同时修复对象之间的引用
    • 选择一块区域(Page),将其中的活跃对象搬移到另一个区域
    • 将搬移的对象放到 forwarding table
  • 在 Relocate 阶段,应用线程新创建的对象地址视图标记为 Remapped
  • Remap 阶段主要是对地址视图和对象之间的引用关系做修正
    2cebc5b7fb964f989af2ac62a42f1f4c.png
    • 把当前 GC 周期的 Remap 阶段和下一个 GC 周期的 Mark 阶段复用
    • 在 Remap 阶段,新分配对象的地址视图是 Marked1
    • 如果遇到对象地址视图是 Marked0 或者 Remapped,就把地址视图置为 Marked1

标题:垃圾回收逻辑推演
作者:yanghao
地址:http://solo.fancydigital.com.cn/articles/2022/04/14/1649917311401.html