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