Изменения

Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания Задача: есть процессы, они могут друг друга ждать (ребра, которые из него исходятв этот момент они ничего не могут делать и не меняют своё внутреннее состояние), а также флажок changed.Мы хотим запустить алгоритм, который равен trueбудет нам сообщать о появлении взаимных блокировок, если его часть графа поменялась с последнего сообщения координатору. Координатор периодически опрашивает когда процессы, получая их графыждут друг друга по циклу. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если Практическое применение — поиск ошибок в нем есть циклпрограммах (динамические анализаторы распределённого кода, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найденбазы данных и SQL-запросы).

Алгоритм централизированный: есть выделенный координатор. Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, взаимная блокировка найдена. Здесь мы пользуемся тем, что "процессы находятся во взаимной блокировке" — [[локально стабильный предикат]] и процесс в ожидании ничего не делает. Рассмотрим два среза:

Эти срезы не обязательно согласованны, но они [[Барьерная синхронизация (3 алгоритма)|барьерно-синхронизированы ]] (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.