Page tree
Skip to end of metadata
Go to start of metadata

Предлагается основываться на алгоритме MNR (в этой статье хорошо описан), который изменяет топологический порядок не на всем графе, а только на необходимом участке. Возможно, стоит посмотреть в сторону других алгоритмов.

Зачем это нужно?

На текущий момент инструмент Dl-Check (https://github.com/Devexperts/dlcheck) использует его для поиска циклов в графе блокировок (см. pre-print прикрепленной статьи). Для корректной синхронизации используется ReadWriteLock следующим образом: при чтении значения топологического порядка используется ReadLock, а при его изменении – WriteLock. Таким образом, при изменении топологического порядка происходит практически stop the world, а меняется он не быстро судя по собранной статистике. Предлагается оптимизировать эту часть.

Идеи

  • No labels