c ++图形数据结构的并发垃圾收集

Question

我有一个用于音频信号处理的有向图数据结构(如果你很好奇,请参见http://audulus.com).

我想图形边缘是强引用,所以在没有周期的情况下,std::shared_ptr就可以了.唉,图中有潜在的周期.

所以,我有一个简单的并发标记扫描收集器的想法:

mutator线程将事件发送到收集器线程.收集器线程维护其自己的图形表示,并且不遍历mutator线程的图形.收集器线程只是定期使用标记扫描.

事件将是以下(在函数调用形式中):

这个方案是否正确？收集器线程具有mutator线程看到的旧版本.我的直觉是,由于较早时间无法访问的节点以后仍然无法访问,因此收集器线程可能会在找到无法访问的对象时立即删除它.

另外,如果它对于一个mutator线程是正确的,它是否适用于多个mutator线程？

UPDATE

我在这里发布了代码:https://github.com/audulus/collector.代码实际上是相当通用的.使用RootPtr<T>自动跟踪根节点.节点之间的链接使用EdgePtr<T>.

收集器似乎适用于多个mutator线程(在我的应用程序和单元测试中),但我觉得需要证明正确性.

请注意(在下面的@AaronGolden的评论中,从下面的评论来看,人们不会读这个):mutator线程负责以正确的顺序调用收集器函数.例如,如果mutator线程RemoveEdge(a,b)在分配b给a 之前调用RootPtr,则收集器可以进行干预和收集b.

更新2:

我已将代码更新到我的最新版本并更新了上面的链接.我现在已经在我的应用程序中使用了一年多的代码,并没有将任何错误归咎于它.

Answer 1

我认为该方案有效的一个论点有点有说服力（尽管我不愿意称其为证据），即在没有循环的情况下，该方案相当于使用原子引用计数进行引用计数。

在没有循环的情况下，AddRoot和AddEdge映射到递增引用计数，并且RemoveRoot和RemoveEdge映射到递减。将事件推送到队列（我使用 boost::lockfree::queue）是一个原子操作，就像更新引用计数一样。

那么剩下的问题是：周期如何改变正确性？稍微挥一下手，循环是图连接性的一种属性，但不会影响操作的原子性或一个线程比其他情况更早知道某事的能力（导致潜在的错误排序）的操作）。

这表明，如果该方案有一个反例，它将涉及玩一些循环游戏。