让我简单介绍一下三色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更新都必须使对象变为灰色.
如果确实如此,使用增量更新可能比我最初想象的更棘手,并且有一些性能缺陷,因为堆栈更改是最常见的.
python gc.collect()是一个停止世界（STW）垃圾收集器吗？
如果是 STW 垃圾收集器，何时何地停止世界？
我知道 python 使用确定性引用计数，这不需要停止世界。然而，在处理循环时，python 是否需要停止世界？