Mec*_*cki 28 language-agnostic garbage-collection
让我简单介绍一下三色GC(如果有人读到它,从未听说过它); 如果你不在乎,跳过它并跳转到问题.
在三色GC中,物体具有三种可能的颜色中的一种; 白色,灰色和黑色.三色GC可描述如下:
所有物体最初都是白色的.
由于全局变量或堆栈变量引用它("根对象"),所有可到达的对象都是灰色的.
我们采用任何灰色物体,找到它对白色物体的所有参考,并将这些白色物体着色为灰色.然后我们将对象本身涂成黑色.
只要我们有灰色物体,我们就在第3步继续.
如果我们不再有灰色物体,则所有剩余的物体都是白色或黑色.
所有黑色物体都被证明是可以到达的,必须保持活力.所有白色对象都无法访问,可以删除.
到目前为止,这并不是太复杂......至少如果GC是StW(停止世界),这意味着它会在收集垃圾时暂停所有线程.如果它是并发的,则三色GC具有必须始终保持为真的不变量:
黑色物体不得指白色物体!
这对于StW GC自动成立,因为之前已经检查过每个黑色的物体,并且它指向的所有白色物体都是灰色的,因此黑色物体可能仅指其他黑色物体或灰色物体.
如果线程没有暂停,线程可以执行会破坏此不变量的代码.有几种方法可以防止这种情况:
捕获对指针的所有读取访问权限,并查看是否对白色对象进行了读取访问.如果是,立即将对象的颜色变为灰色.如果现在将对此对象的引用分配给黑色对象,则无关紧要,该对象不再是灰色而不是白色(此实现使用读取屏障)
捕获对指针的所有写访问权,并查看指定的对象是否为白色,并且指定的对象是否为黑色.如果是这样,请将白色物体着色为灰色.这是更明显的做事方式,但也需要更多的处理时间(此实现使用写屏障)
由于读取访问比写入访问更常见,即使第二种可能性涉及更多的处理时间,当屏障被击中时,它被称为不那么频繁而且是受欢迎的.像这样工作的GC称为"增量更新GC".
这两种技术都有其他选择,称为SatB(起点时的快照).考虑到在任何时候都没有必要坚持不变量这一事实,这种变化略有不同,因为只要GC知道这个白色物体曾经是黑色物体是否引用白色物体并不重要并且在当前GC循环期间仍然可以访问(或者因为仍然有灰色对象引用此白色对象,或者因为此白色对象的引用被放置到GC运行时也考虑的显式堆栈上用灰色物体).SatB收藏家在实践中更常使用,因为它们有一些优点,但恕我直言,它们更难实施.
我在这里指的是增量更新GC,它使用变量2:每当代码试图使黑色物体指向白色物体时,它立即将物体灰色着色.这样,在收集周期中不会错过这个对象.
关于三色GC的问题非常多.但有一点我不了解三色GC.假设我们有一个对象A,它由栈引用,它本身引用一个对象B.
stack -> A.ref -> B
现在GC启动一个循环,停止线程,扫描堆栈并将A视为可直接访问,着色为灰色.一旦完成扫描整个堆栈,它再次取消线程并在步骤(3)开始处理.在它开始执行任何操作之前,它被抢占(可能发生)并且线程再次运行并执行以下代码:
localRef = A.ref; // localRef points to B
A.ref = NULL; // Now only the stack points to B
sleep(10000); // Sleep for the whole GC cycle
由于没有违反不变量,B是白色的,但是没有被分配给黑色物体,B的颜色没有变化,它仍然是白色的.A不再引用B,因此在处理"灰色"A时,B不会改变其颜色,A将变为黑色.在周期结束时,B仍然是白色的,看起来像垃圾.但是,localRef指的是B,因此它不是垃圾.
我是对的,三色GC必须扫描每个线程的堆栈两次吗？一旦开始,识别根对象(变为灰色)并在删除白色对象之前再次识别,因为堆栈可能会引用这些对象,即使没有其他对象再引用它们.到目前为止,我没有看到过关于扫描堆栈两次的任何关于算法的描述.他们都只是说,当使用并发时,重要的是始终强制执行不变量,否则会丢失可达对象.但据我所知,这还不够.必须将堆栈视为单个大对象,并且一旦扫描,"堆栈为黑色",堆栈的每次ref更新都必须使对象变为灰色.
如果确实如此,使用增量更新可能比我最初想象的更棘手,并且有一些性能缺陷,因为堆栈更改是最常见的.
Tho*_*nin 22
一点术语:
让我给出一些名字,以便解释更清楚.
甲变量是用于数据的任何时隙,其可以包含一个指针,并且可以随时间改变.这包括全局变量,局部变量,CPU寄存器和分配对象中的字段.
在三色增量或并发GC中,有三种类型的变量:
以下将"真正的根"和"快速变量"统称为根.
应用程序线程称为mutators,因为它们会更改变量的内容.
使用增量或并发GC时,GC暂停会定期发生.世界停止了(变异器暂停),根被扫描.此扫描显示了对彩色对象的大量引用.相应地调整对象颜色(这样的白色对象变为灰色).
当GC是增量式时,会发生一些对象扫描活动:扫描一些灰色物体(并涂成黑色),灰化参考的白色物体.此活动("标记")保持一段时间,但不一定只要有灰色对象.在某些时候,标记停止,世界被唤醒.GC被称为"增量",因为GC循环以小增量执行,与增变器活动交错.
在并发 GC中,灰色对象的扫描与增变器活动同时发生.一旦根被扫描,世界就会被唤醒.使用并发GC,访问障碍有点复杂,因为它们必须处理来自GC线程的并发访问; 但从概念上讲,这与增量GC没有太大差别.并发GC可以被视为对增量GC的优化,它利用了多个CPU核心的存在(当只有一个核心时,并发GC比增量GC几乎没有优势).
根不需要受到访问障碍的保护,因为它们在世界停止的情况下进行扫描.当满足以下条件时,GC标记阶段结束:
所以这种情况只能在暂停期间发生.此时,扫描阶段开始,在此期间释放白色物体.扫描可以递增或同时进行; 扫描过程中创建的对象立即涂成黑色.扫描完成后,可以进行新的GC标记阶段:对象(在该点全部为黑色)全部重新绘制为白色(这通过简单地改变颜色位的解释方式以原子方式完成).
变量分类:
话虽如此,我现在可以回答你的问题了.通过上面的描述,问题变成了:根源是什么？这实际上取决于实施; 有几种可能性和权衡取舍.
必须始终扫描真根; 真正的根是CPU寄存器内容和全局变量.请注意,堆栈不是真正的根; 只有当前的堆栈帧指针.
由于快速变量是在没有障碍的情况下访问的,因此习惯上使堆栈帧变为快速变量(即根也是如此).这是因为虽然写访问在系统范围内很少见,但它们在局部变量中很常见.已经测量(在一些Lisp程序上)大约99%的(指针值)写入具有局部变量作为目标.
在代际GC的情况下,快速变量通常会进一步扩展:"年轻代"包含新对象的特殊分配区域,长度有限,扫描为快速变量.快速变量的好处是快速访问(因此得名); 缺点是所有这些快速变量只能在暂停期间扫描(世界停止).对快速变量的大小进行权衡,这通常会转化为年轻一代的大小.较大的年轻一代以较长的停顿为代价,提升平均表现(通过减少访问障碍的数量).
在另一个极端,你可能根本没有快速变量,没有根,但真正的根.然后将堆栈帧作为对象处理,每个对象都有自己的颜色.暂停是最小的(仅仅是十几个寄存器的快照),但是即使访问局部变量也必须使用障碍.这很贵,但有一些优点:
call/cc原语一样,这是必需的.在这种情况下,帧不再被视为纯粹的"堆栈".在GC感知语言中正确处理连续性主要要求动态分配功能帧.可以使堆栈帧非root,同时将年轻代保持为root.暂停时间的保证仍然可以进行(取决于年轻代的大小,这是固定的),并且可以应用一些技巧来确保堆栈帧在其功能处于活动状态时处于年轻代.这可以确保无障碍访问局部变量.这些都不是真正免费的,但它可以在大多数情况下足够有效.
另一个概念观点:
查看根处理的另一种方法如下:root是三色规则(没有黑到白指针)始终不保持的变量; 允许这些变量在没有约束的情况下进行变异.但是必须通过停止世界并扫描它们来定期恢复它们.
在实践中,变异者正在与GC竞争.Mutators创建新对象,并指向它们; 每次暂停都会创建新的灰色对象 在并发或增量GC中,如果让mutator在root中播放的时间过长,那么每次暂停都可能会产生大量新的灰色对象.在最坏的情况下,GC无法快速扫描对象以跟上灰色对象创建的速度.这是一个问题,因为白色物体只能在扫描阶段释放,只有在某些时候GC可以完成其标记时才能达到.增量GC的通常实施策略是在每次暂停期间扫描灰色物体,以获得与根的总尺寸成比例的总尺寸.因此,暂停时间仍然受到根总大小的限制,并且如果比例因子很好地平衡,则可以保证GC最终终止是标记阶段并进入扫描阶段.
在并发GC中,事情有点复杂,因为变异器在野外自由漫游.一个可能的实现将在世界仍然停止时进行一些增量标记.
参考书目:
垃圾收集:自动动态内存管理的算法:垃圾收集必读书.
小智 6
托马斯显然有最好的答案。但是，我只是要在这里添加一点旁注。
根节点在概念上可以被认为是黑色节点，因为根节点所指的任何对象都必须是灰色或黑色的。
因此，为了保持不变性，对根变量的赋值应该自动使对象变灰。