标记-清除算法 #
STW(stop the world) 让程序暂停，程序出现卡顿
- 标记(Mark phase)
- 清除(Sweep phase)
缺点:
- STW，stop the world；让程序暂停，程序出现卡顿 (重要问题)；
- 标记需要扫描整个heap；
- 清除数据会产生heap碎片。
三色并发标记法 #
说明 #
三种颜色:白色( White)、灰色(Grey)、黑色(Black)
- 白色:对象尚未被访问过
- 灰色:对象正在被访问
- 黑色:对象访问已完成
工作流程
- 开始时所有对象都为白色
- 根集对象(比如静态变量等)被标记为灰色
- 递归地遍历从根集对象开始的可达对象,将其标记为灰色
- 从灰色队列中取出一个对象,访问其字段和引用,将被访问的对象标记为灰色
- 对灰色队列中的对象进行同样操作,直到队列为空
- 将遍历完的灰色对象标记为黑色
- 从第二步开始重复遍历过程,直到没有灰色对象为止
- 遍历结束后,扫描内存,回收尚为白色的未使用对象
白->灰->黑
- 第一步 , 每次新创建的对象，默认的颜色都是标记为"白色"
- 第二步, 每次GC回收开始, 会从根节点开始遍历所有对象，把遍历到的对象从白色集合放入“灰色”
- 第三步, 遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合
为了在GC过程中保证数据的安全，我们在开始三色标记之前就会加上STW，在扫描确定黑白对象之后再放开STW
没有STW加持下存在的问题 #
- 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下)
- 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)
如果当以上两个条件同时满足时，就会出现对象丢失现象!
屏障机制 #
三色不变式
- 强三色不变式 不存在黑色对象引用到白色对象的指针
- 弱三色不变式 所有被黑色对象引用的白色对象都处于灰色保护状态。
插入屏障 #
在A对象引用B对象的时候，B对象被标记为灰色
删除屏障 #
被删除的对象，如果自身为灰色或者白色，那么被标记为灰色
缺点
- 插入写屏障：结束时需要STW来重新扫描栈，标记栈上引用的白色对象的存活；
- 删除写屏障：回收精度低，GC开始时STW扫描堆栈来记录初始快照，这个过程会保护开始时刻的所有存活对象。
混合写屏障 #
- GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行第二次重复扫描，无需STW)，
- GC期间，任何在栈上创建的新对象，均为黑色。
- 被删除的对象标记为灰色。
- 被添加的对象标记为灰色。