Информатика · объяснение и практика

Взаимная блокировка: цикл ожидания и необходимые условия

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Операционные системы и память: углубление · Учебная карта

В маршруте Цифровая схема и работа вычислителя · 10 тем

Главная мысль

Взаимная блокировка возникает, когда участники ждут ресурсы друг друга и никто не может продолжить освобождение. Для классической модели нужны исключительное владение, удержание при ожидании, отсутствие принудительного изъятия и цикл ожидания. Обычная временная занятость ресурса ещё не доказывает deadlock.

Сначала строим реальное ожидание

У процесса А есть единственный сканер, у Б — единственный принтер. А запрашивает принтер, сохраняя сканер; Б запрашивает сканер, сохраняя принтер. Допустим, оба освобождают имеющееся только после получения второго и внешнего изъятия нет. Теперь ни один не дойдёт до освобождения.

Если же Б закончит самостоятельную работу и освободит принтер без получения сканера, замкнутого ожидания в описанном виде нет. Поэтому из факта «А ждёт Б» нельзя заключать взаимную блокировку. Нужно проверить цепочку в обе стороны и правила завершения, а не только увидеть два медленно работающих окна.

Проверяем необходимые условия

В примере ресурс нельзя разделить между двумя участниками одновременно. Каждый удерживает один ресурс при запросе другого. Забрать его принудительно по условиям нельзя. Наконец, ожидание образует круг А→Б→А. Эти условия описывают причину невозможности прогресса в нашей конкретной системе.

Цикл в упрощённом графе ожидания достаточен для этой модели с одним экземпляром каждого ресурса. Для ресурсов с несколькими экземплярами общая задача сложнее: нельзя механически переносить тот же рисунок без сведений о количестве и свободных экземплярах. Границы модели должны оставаться частью ответа.

Пример

А держит сканер и ждёт принтер; Б держит принтер и ждёт сканер. Оба ресурса единичны.

Освобождение зависит от завершения, завершение — от второго ресурса. Получается замкнутая зависимость, а не просто очередь.

Разрываем возможность кругового ожидания

Можно договориться, что любой участник сначала получает сканер и только затем принтер. Если сканер занят, следующий участник ждёт, ещё не удерживая принтер. Тогда один из них сможет получить оба, выполнить работу и освободить их. Общий порядок должен соблюдаться всеми путями программы.

Отдельное решение — ограниченное ожидание с корректным освобождением и повтором; однако случайный повтор сам по себе не гарантирует прогресс. Нельзя просто снять чужую блокировку и считать данные целыми. Способ восстановления зависит от того, можно ли отменить уже выполненные действия и вернуть ресурсы в согласованное состояние.

От чтения к действию

А теперь — вы

Оба участника обязаны сначала получить ресурс R, затем S. А уже держит R. Может ли Б держать S, ожидая R, если правило соблюдается?

Частые вопросы

Любое ожидание — взаимная блокировка?

Нет. Если владелец ресурса способен закончить и освободить его независимо от ожидающего, это может быть обычная очередь.

Единый порядок полезен только для двух замков?

Нет. Можно упорядочить больше ресурсов, но все участники должны соблюдать выбранное правило.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться