Page tree

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 2 Next »

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

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

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

Идея

1. Давайте научимся захватывать WriteLock не на весь граф целиком, а только на тот «отрезочек» (affected region в статье), который собираемся изменять. Таким образом, появляется свой менеджер блокировок. Хотелось бы, чтобы этот менеджер блокировок работал lock-free при ограничении «один писатель на affected region». 

2. Давайте научимся читать значение топологического порядка (нужно для проверки, что добавление ребра не нарушает текущий топ. порядок) lock-free. На текущий момент, если происходит изменение значения топ. порядка, то чтение ждет его окончания. Это долго.

Итого, все должны уметь читать значение топологического порядка lock-free, а его изменения должны производиться параллельно с ограничением «только один поток может изменять этот affected region». 

  • No labels