Go v1.3之前 清除标记算法
第一步, 暂停程序业务逻辑, 找出不可达的对象, 然后做上标记 第二步 , 回收对象
缺点
由于需要程序暂停, 会出现卡顿 标记的时候需要扫描整个heap 清除数据的时候也会产生heap碎片
三色标记
本文的主要内容, 也就是三色标记法
步骤
- 新创建的对象, 默认都是白色
- 每次GC回收开始, 从根节点遍历所有对象, 把遍历到的对象从白色集合放入灰色集合
- 遍历灰色集合, 把灰色对象引用到的对象从白色放入灰色集合, 之后将灰色对象放入黑色集合
- 重复第三步, 直到灰色无任何对象
- 回收白色标记表里的对象
如果没有STW, 也没有屏障处理的话 标记阶段让线程并发修改对象引用, 会打破三色不变式
- 黑->白 边破坏: 标记过程中, 一个已经标记成黑色的A, 如果被应用线程写入了指向某个白色对象B的指针,由于A不会被扫描了, B永远无法从白->灰->黑的升级, 就会在清扫阶段被错误回收, 悬垂引用
- 灰->白 边破坏: 应用线程如果在B刚被放入灰色队列之后,就又把指向B的指针删除,让B既不在根集合, 又不被其他对象引用, 缺还在灰色队列里, 导致B不会到黑色 -> 既不会被正确扫描, 又不会被立即回收,造成内存泄露
屏蔽机制
强-弱 三色不变式
强三色不变式
强制性的不允许黑色对象引用白色对象
弱三色不变式
所有被黑色对象引用的白色对象,都处于灰色保护状态, 也就是说这个白色对象除了这个黑色对象, 上游一定有一个灰色对象
插入屏障
在A对象引用B对象的时候, B被标记成灰色
满足强三色不变式, 白色会被强制变成灰色
假设A已经是黑色, 此时程序执行A.field = B
- 写屏障拦截: 看到B还是白色, 立刻变成灰色
- 再把指针写入
A.field, 此时状态是黑-> 灰 - 后续扫描, GC主线程从灰色里取B, 标成黑色, 扫描它所有引用
无论应用线程什么时候给一个已标记黑色的对象加上一条新指针, 都能保证不会出现 黑 -> 白, 因为在保证B写入前, 就确定已经变成了灰色
如果没有写屏障, A.field = B的时候, GC并发执行, 把B清理掉了, A还指向着一个不存在的B
写屏障只插入在对堆上对象的指针写操作, 而不会影响栈上局部变量的赋值 栈上的对象只在STW阶段GC根扫描时处理, 并且占访问比堆更高, 如果每次都对栈进行写屏障检查, 会造成很大的性能损耗
为了保证栈的白色对象不丢失引用, 会对栈启用STW暂停保护
删除屏障
被删除的对象, 如果自身为灰色或者白色, 那么被标记成灰色
考虑如下操作
A.field = nil
此时如果没有任何操作, B就会从活着状态变成 没有人看见, 也没有人引用的状态 GC会在清扫阶段把它当垃圾回收掉
此时给B标记成灰色,使一个对象即使被删除了最后一个指向它的指针也依旧可以活过这一轮
Go v1.8混合写屏障
插入写屏障和删除写屏障的短板
- 插入: 结束前要用STW扫描栈, 标记栈上引用的白色对象的存活
- 删除: 回收精度低, GC开始时STW扫描堆栈来记录初始快照, 这个过程会保护开始时刻的所有存活对象
混合写屏障规则
- GC开始将栈上对象全部扫描并标记为黑色
- GC期间任何在栈上创建的新对象, 均为黑色
- 被删除的对象标记为灰色
- 被添加的对象标记成灰色
相比于插入/删除屏障, 混合写屏障只在GC开始的时候对栈做预扫描,把所有栈上对象全部染成黑色, 后续全程不碰栈
一次GC的完整流程 (混合写屏障)
初始STW
暂停所有goruntine
也就是STW
开启混合写屏障机制
goruntine恢复执行的时候, 内存状态一致性会被打破, 所以STW的目的是为了顺利开启混合写屏障机制, 保证后续内存状态一致性
分批扫描goruntine栈帧, 标记栈内变量
分批扫描所有被暂停的goruntine栈帧, 每个栈扫描完毕后, 该goruntine会被立刻恢复运行, 扫描栈帧和程序是并行的, 可以有效降低STW的时间
接着标记栈上所有可达对象为黑色, 标记引用的堆对象为灰色
至于为什么不把根上所有对象全部染黑, 而是这样分阶段处理, 大概是为了确保GC的准确性, 同时也保证了效率, 不至于让初始STW停留时间过久
并发标记
GC和应用程序在这个阶段并发运行
并发运行
应用程序可以正常执行操作, GC在后台进行标记操作, 互不阻塞
处理灰色对象
GC从队列中取出灰色对象, 把所有引用了的对象染灰, 并标记成黑色 之后递归处理灰色对象, 重复上述操作, 直到所有灰色对象都被处理完毕
混合写屏障
在这个阶段, 混合写屏障发生作用, 堆上被删除的对象被标记成灰色, 堆上新添加的对象被标记成灰色,将新引用的对象标记成灰色
标记完成后的STW
暂停所有goruntine, 确保标记操作全部完成. 在这个期间, GC处理完可能存在的延迟屏障记录,确保并发标记阶段所有引用修改都被正确记录和处理了
关闭写屏障, 意味着GC不需要记录引用修改了, 只存在白色和黑色两种颜色
恢复goruntine
并发清除
在这个阶段, 应用程序继续正常运行, GC后台进行清除操作
遍历堆内存, 清除所有白色对象, 释放内存, 更新内存管理的数据结构,代表这块空间已经被释放, 可以被应用程序重新分配使用
清扫完成(遍历完堆内存, 清除所有白色对象)后, 准备下一次GC