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