21

我有一个用于音频信号处理的有向图数据结构（如果您好奇，请参阅http://audulus.com ）。

我希望图形边缘成为强引用，因此在没有循环的情况下，std::shared_ptr可以解决问题。唉，图中可能存在循环。

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

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

事件将如下（以函数调用形式）：

  • AddRoot(Node*)
  • RemoveRoot(Node*)
  • AddEdge(Node*, Node*)
  • RemoveEdge(Node*, Node*)

这个方案正确吗？收集器线程具有更改器线程所看到的旧版本。我的直觉是，由于早期无法访问的节点在以后仍然无法访问，因此收集器线程可能会在找到一个无法访问的对象时立即删除它。

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

更新

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

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

请注意（针对@AaronGolden 下面的评论，从下面的评论来看，人们没有阅读此内容）：mutator 线程负责以正确的顺序调用收集器函数。例如，如果 mutator 线程RemoveEdge(a,b)在分配b给 a之前调用RootPtr，则收集器可能会干预并收集b。

更新 2：

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

4

2 回答 2

1

One argument I think is somewhat persuasive (though I would hesitate to call it proof) that this scheme works is that in the absence of cycles, the scheme is equivalent to reference counting with atomic reference counts.

In the absence of cycles, AddRoot and AddEdge map to incrementing a reference count and RemoveRoot and RemoveEdge map to decrementing. Pushing an event onto the queue (I use boost::lockfree::queue) is an atomic operation just like the updating reference counts.

So then the remaining question is: how do cycles change the picture in terms of correctness? To wave hands a bit, cycles are a property of the connectivity of the graph, but don't have an effect on the atomicity of the operations or the ability of one thread to know something earlier than it would otherwise (causing a potential bad ordering of operations).

This would suggest that if there's a counterexample for the scheme, it will involve playing some game with cycles.

于 2013-06-21T18:43:37.353 回答
0

这个方案正确吗？

我担心你没有任何安全点的概念。特别是，更新是否需要原子执行多个操作？也许没关系，因为您总是可以在删除之前批量添加所有顶点和边。

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

如果一个线程在另一个线程拾取同一个子图的根之后将一个根放到子图，那么您必须确保按顺序获取消息，这意味着您不能使用 per-mutator 队列。全局队列可能会扼杀可扩展性。

我的限制之一是 GC 必须是无锁的，因为我的实时 DSP 线程

  1. 分配器是无锁的吗？
  2. 如果 GC 跟不上 mutator(s) 怎么办？

另外，我建议考虑：

  1. 在子进程中分叉和收集。
  2. 使用 Dijkstra 的三色标记方案进行增量标记扫描。
  3. 贝克的跑步机。
  4. VCGC。
  5. 通过消息的深度复制来分离每个线程的堆。
于 2013-07-05T21:15:25.667 回答