Предлагается основываться на алгоритме MNR (в этой статье хорошо описан), который изменяет топологический порядок не на всем графе, а только на необходимом участке. Возможно, стоит посмотреть в сторону других алгоритмов.
Зачем это нужно?
На текущий момент инструмент Dl-Check (https://github.com/Devexperts/dlcheck) использует его для поиска циклов в графе блокировок (см. pre-print статьи, прикрепил к письму). Для корректной синхронизации используется ReadWriteLock следующим образом: при чтении значения топологического порядка используется ReadLock, а при его изменении – WriteLock. Таким образом, при изменении топологического порядка происходит практически stop the world, а меняется он не быстро судя по собранной статистике. Предлагается оптимизировать эту часть.
Идея
1. Будем изменять значения топ. порядка на affected region с помощью CASN. Однако, есть подозрение, что такой способ будет не очень быстр.
2. Научимся захватывать WriteLock не на весь граф целиком, а только на тот «отрезочек» (affected region в статье), который собираемся изменять. Таким образом, появляется свой менеджер блокировок. Хотелось бы, чтобы этот менеджер блокировок работал lock-free при ограничении «один писатель на affected region».
3. Сделаем добавление ребра в граф lock-free в случае, когда оно не нарушает текущий топологический порядок. При этом параллельно работающее изменение топологического порядка не должно мешать данной операции.
Итого, в большинстве для Dl-Check случаев алгоритм будет lock-free, но даже в случае изменение топологического порядка его часто можно будет распараллелить.