...
На текущий момент инструмент 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». 2. Давайте научимся читать значение топологического порядка (нужно для проверки, что добавление ребра
3. Сделаем добавление ребра в граф lock-free в случае, когда оно не нарушает текущий топологический порядок. При этом параллельно работающее изменение топологического порядка не должно мешать данной операции.
Итого, в большинстве для Dl-Check случаев алгоритм будет lock-free, но даже в случае изменение топологического порядка его часто можно будет распараллелить. не нарушает текущий топ. порядок) lock-free. На текущий момент, если происходит изменение значения топ. порядка, то чтение ждет его окончания. Это долго.
Итого, все должны уметь читать значение топологического порядка lock-free, а его изменения должны производиться параллельно с ограничением «только один поток может изменять этот affected region».