Определение взаимной блокировки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него ис…»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 1: Строка 1:
Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего  сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден.  
+
[[Категория: Параллельное программирование]]
 +
Задача: есть процессы, они могут друг друга ждать (в этот момент они ничего не могут делать и не меняют своё внутреннее состояние).
 +
Мы хотим запустить алгоритм, который будет нам сообщать о появлении взаимных блокировок, когда процессы ждут друг друга по циклу.
 +
Практическое применение — поиск ошибок в программах (динамические анализаторы распределённого кода, базы данных и SQL-запросы).
  
Рассмотрим два среза:  
+
Алгоритм централизированный: есть выделенный координатор.
 +
 
 +
Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если было изменение (даже если сейчас граф снова совпадает с тем, что был послан, во избежание ABA), а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, взаимная блокировка найдена.
 +
 
 +
Здесь мы пользуемся тем, что "процессы находятся во взаимной блокировке" — [[локально стабильный предикат]] и процесс в ожидании ничего не делает.
 +
 
 +
Рассмотрим два среза:
 
* когда взаимно блокирующие процессы прислали координатору свои графы;
 
* когда взаимно блокирующие процессы прислали координатору свои графы;
 
* когда они прислали ему notChanged.
 
* когда они прислали ему notChanged.
Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.
+
Эти срезы не обязательно согласованны, но они [[Барьерная синхронизация (3 алгоритма)|барьерно-синхронизированы]] (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.

Текущая версия на 19:06, 4 сентября 2022

Задача: есть процессы, они могут друг друга ждать (в этот момент они ничего не могут делать и не меняют своё внутреннее состояние). Мы хотим запустить алгоритм, который будет нам сообщать о появлении взаимных блокировок, когда процессы ждут друг друга по циклу. Практическое применение — поиск ошибок в программах (динамические анализаторы распределённого кода, базы данных и SQL-запросы).

Алгоритм централизированный: есть выделенный координатор.

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

Здесь мы пользуемся тем, что "процессы находятся во взаимной блокировке" — локально стабильный предикат и процесс в ожидании ничего не делает.

Рассмотрим два среза:

  • когда взаимно блокирующие процессы прислали координатору свои графы;
  • когда они прислали ему notChanged.

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