Одновременная сборка мусора для структуры данных графа С++

У меня есть структура диаграмм направленного графа, используемая для обработки звукового сигнала (см. http://audulus.com, если вам интересно).

Я хотел бы, чтобы графы были сильными ссылками, поэтому в отсутствие циклов std::shared_ptr выполнил бы трюк. Увы, на графике есть потенциальные циклы.

Итак, у меня была эта идея для простого параллельного сборщика меток:

поток мутатора отправляет события в поток коллектора. Коллекторный поток поддерживает собственное представление графика и не пересекает график потока мутаторов. В коллекторной резьбе с помощью регулярных интервалов используется разметка.

События будут следующими (в форме вызова функции):

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

Правильно ли эта схема? В потоке коллектора есть более старая версия того, что видит мутаторный поток. Моя интуиция заключается в том, что, поскольку node, недоступный в более раннее время, по-прежнему будет недоступен позднее, поток коллектора может удалить недоступный объект, как только он найдет его.

Кроме того, если он правильный для одного потока мутаторов, будет ли он работать для нескольких потоков мутаторов?

UPDATE

Я выпустил здесь код: https://github.com/audulus/collector. Код на самом деле довольно общий. Используйте RootPtr<T> для автоматического отслеживания корневых узлов. Связи между узлами управляются с помощью EdgePtr<T>.

Коллекционер, похоже, работает для нескольких потоков мутаторов (как в моем приложении, так и в модульных тестах), но я чувствую, что требуется подтверждение правильности.

ОБРАТИТЕ ВНИМАНИЕ (в ответе на комментарий @AaronGolden ниже, , судя по комментариям ниже, люди не читают этот): поток мутаторов отвечает за вызов коллектора в правильном порядке. Например, если поток мутатора вызывает RemoveEdge(a,b) перед назначением b на RootPtr, сборщик может вмешиваться и собирать b.

ОБНОВЛЕНИЕ 2:

Я обновил код до своей последней версии и обновил ссылку выше. Я уже более года использовал код в своем приложении и не приписывал ему никаких ошибок.

Ответ 1

Один аргумент, который, по моему мнению, несколько убедителен (хотя я бы с сомнением назвал его доказательством), что эта схема работает, так это то, что в отсутствие циклов схема эквивалентна подсчету ссылок с подсчетами атомных ссылок.

В отсутствие циклов, AddRoot и AddEdge отобразится для увеличения количества отсчетов ссылок и RemoveRoot и RemoveEdge для уменьшения. Нажатие события в очередь (я использую boost:: lockfree:: queue) - это атомная операция, как и подсчет ссылок обновления.

Итак, оставшийся вопрос: как циклы меняют картину с точки зрения правильности? Чтобы немного помахать руками, циклы являются свойством связности графика, но не влияют на атомарность операций или способность одного потока знать что-то раньше, чем это могло бы (в противном случае это могло бы вызвать потенциальный плохой порядок операций).

Это предполагает, что если есть контрпример для схемы, это будет включать в себя игру в игру с циклами.

Ответ 2

Правильно ли эта схема?

Я обеспокоен тем, что у вас нет понятия безопасных точек. В частности, может ли обновление выполнить более одного из ваших действий для атомизации? Возможно, это нормально, потому что вы всегда можете добавить все вершины и ребра в пакет, прежде чем удалять.

Кроме того, если он правильный для одного потока мутаторов, будет ли он работать для нескольких потоков мутаторов?

Если один поток отбрасывает корень на подграф сразу после того, как другой подбирает корень к одному и тому же подграфу, вы должны убедиться, что вы получаете сообщения в порядке, что означает, что вы не можете использовать очереди на мутаторе. И глобальная очередь, вероятно, уничтожит масштабируемость.

Одно из моих ограничений состоит в том, что GC должен быть заблокирован из-за моего потока DSP в реальном времени

Является ли блокиратор блокируемым?
Что делать, если GC не может идти в ногу с мутатором?

Кроме того, я бы рекомендовал рассмотреть:

Викинг и сбор в дочернем процессе.
Инкрементальная маркировка с помощью трехцветной маркировки Dijkstra.
Беговая дорожка Бейкера.
VCGC.
Отдельные куски для потоков с глубоким копированием сообщений.