Информатика · объяснение и практика
Взаимная блокировка: цикл ожидания и необходимые условия
Взаимная блокировка: цикл ожидания двух ресурсов, необходимые условия и единый порядок захвата.

В теме Операционные системы и память: углубление · Учебная карта
В маршруте Цифровая схема и работа вычислителя · 10 тем
Главная мысль
Взаимная блокировка возникает, когда участники ждут ресурсы друг друга и никто не может продолжить освобождение. Для классической модели нужны исключительное владение, удержание при ожидании, отсутствие принудительного изъятия и цикл ожидания. Обычная временная занятость ресурса ещё не доказывает deadlock.
Сначала строим реальное ожидание
У процесса А есть единственный сканер, у Б — единственный принтер. А запрашивает принтер, сохраняя сканер; Б запрашивает сканер, сохраняя принтер. Допустим, оба освобождают имеющееся только после получения второго и внешнего изъятия нет. Теперь ни один не дойдёт до освобождения.
Если же Б закончит самостоятельную работу и освободит принтер без получения сканера, замкнутого ожидания в описанном виде нет. Поэтому из факта «А ждёт Б» нельзя заключать взаимную блокировку. Нужно проверить цепочку в обе стороны и правила завершения, а не только увидеть два медленно работающих окна.
Проверяем необходимые условия
В примере ресурс нельзя разделить между двумя участниками одновременно. Каждый удерживает один ресурс при запросе другого. Забрать его принудительно по условиям нельзя. Наконец, ожидание образует круг А→Б→А. Эти условия описывают причину невозможности прогресса в нашей конкретной системе.
Цикл в упрощённом графе ожидания достаточен для этой модели с одним экземпляром каждого ресурса. Для ресурсов с несколькими экземплярами общая задача сложнее: нельзя механически переносить тот же рисунок без сведений о количестве и свободных экземплярах. Границы модели должны оставаться частью ответа.
Пример
А держит сканер и ждёт принтер; Б держит принтер и ждёт сканер. Оба ресурса единичны.
Освобождение зависит от завершения, завершение — от второго ресурса. Получается замкнутая зависимость, а не просто очередь.
Разрываем возможность кругового ожидания
Можно договориться, что любой участник сначала получает сканер и только затем принтер. Если сканер занят, следующий участник ждёт, ещё не удерживая принтер. Тогда один из них сможет получить оба, выполнить работу и освободить их. Общий порядок должен соблюдаться всеми путями программы.
Отдельное решение — ограниченное ожидание с корректным освобождением и повтором; однако случайный повтор сам по себе не гарантирует прогресс. Нельзя просто снять чужую блокировку и считать данные целыми. Способ восстановления зависит от того, можно ли отменить уже выполненные действия и вернуть ресурсы в согласованное состояние.
От чтения к действию
А теперь — вы
Частые вопросы
Любое ожидание — взаимная блокировка?
Нет. Если владелец ресурса способен закончить и освободить его независимо от ожидающего, это может быть обычная очередь.
Единый порядок полезен только для двух замков?
Нет. Можно упорядочить больше ресурсов, но все участники должны соблюдать выбранное правило.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Процесс и поток: какие данные общие, а какие отдельные
Процесс и поток: общее адресное пространство, собственный ход исполнения и ошибка несогласованного обновления.
Открыть темуСильные компоненты: какие вершины взаимно достижимы
Компоненты сильной связности ориентированного графа: взаимная достижимость, максимальность группы и ациклический граф сжатия.
Открыть тему