Предотвращение взаимоблокировок

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

Основные условия возникновения взаимоблокировок

Для возникновения взаимоблокировки необходимо одновременное выполнение четырёх условий (условия Коффмана):

1. Взаимное исключение (Mutual Exclusion) — ресурс не может быть одновременно использован более чем одним процессом.
2. Удержание и ожидание (Hold and Wait) — процесс, удерживающий один или несколько ресурсов, может запрашивать дополнительные ресурсы, удерживаемые другими процессами.
3. Отсутствие принудительного отъёма (No Preemption) — ресурс не может быть принудительно изъят у процесса; освободить его может только сам процесс.
4. Циклическое ожидание (Circular Wait) — существует замкнутая цепочка процессов, в которой каждый процесс ожидает ресурс, удерживаемый следующим процессом в цепочке.

Предотвращение взаимоблокировок заключается в нарушении хотя бы одного из этих условий.

Методы предотвращения

Нарушение условия взаимного исключения

Этот метод применим только для ресурсов, которые могут быть разделяемыми (например, файлы, открытые только для чтения). Для ресурсов, требующих монопольного доступа (например, принтер, запись в критическую секцию), условие взаимного исключения является необходимым и не может быть нарушено. Поэтому на практике данный подход используется редко и только для специфических типов ресурсов.

Нарушение условия удержания и ожидания

Существует два основных подхода:

1. Запрос всех ресурсов до начала выполнения — процесс должен запросить и получить все необходимые ему ресурсы до начала работы. Если хотя бы один ресурс недоступен, процесс не запускается. Недостаток: низкая эффективность использования ресурсов, так как они могут простаивать длительное время, а также риск «голодания» процессов, требующих большого количества ресурсов.
2. Освобождение всех удерживаемых ресурсов при запросе нового — если процесс, удерживающий ресурсы, запрашивает новый ресурс, который недоступен, он должен освободить все ранее захваченные ресурсы и затем запросить их снова вместе с новым. Это снижает эффективность из-за частого переключения контекста и повторного захвата ресурсов.

Нарушение условия отсутствия принудительного отъёма

Этот метод предполагает, что операционная система может принудительно изъять ресурс у процесса, если он удерживает его и запрашивает другой недоступный ресурс. При этом состояние процесса сохраняется, и он может быть возобновлён после получения ресурса. Применяется в основном для ресурсов, состояние которых легко сохраняется и восстанавливается (например, регистры процессора, память). Для ресурсов с несохраняемым состоянием (например, принтер, ленточный накопитель) этот метод неприменим.

Нарушение условия циклического ожидания

Наиболее распространённый и практически реализуемый метод. Он основан на введении глобального порядка (иерархии) для всех ресурсов. Каждому типу ресурса присваивается уникальный номер. Процесс может запрашивать ресурсы только в порядке возрастания их номеров. Если процесс уже удерживает ресурс с номером N, он может запросить только ресурс с номером, большим N. Это гарантирует отсутствие циклического ожидания, так как в любой цепочке запросов номера ресурсов строго возрастают, и замкнутый цикл невозможен.

Пример: в операционной системе Windows для синхронизации используется иерархия объектов (например, сначала захватывается критическая секция, затем мьютекс, затем семафор). Нарушение порядка приводит к взаимоблокировке, которая может быть обнаружена отладчиком.

Алгоритм банкира (Banker’s Algorithm)

Алгоритм банкира, предложенный Эдсгером Дейкстрой, является классическим методом предотвращения взаимоблокировок, основанным на моделировании состояния системы. Он требует, чтобы каждый процесс заранее объявлял максимальное количество ресурсов каждого типа, которое ему может потребоваться. Операционная система проверяет, приведёт ли выделение запрошенного ресурса к небезопасному состоянию (состоянию, из которого возможна взаимоблокировка). Если нет — ресурс выделяется, иначе процесс приостанавливается.

Основные структуры данных

• Available — вектор доступных ресурсов каждого типа.
• Max — матрица максимальных потребностей каждого процесса.
• Allocation — матрица текущего выделения ресурсов каждому процессу.
• Need — матрица оставшихся потребностей (Need = Max — Allocation).

Алгоритм проверки безопасности

1. Инициализация: Work = Available; Finish[i] = false для всех процессов.
2. Поиск процесса i, для которого Finish[i] = false и Need[i] <= Work.
3. Если такой процесс найден: Work = Work + Allocation[i]; Finish[i] = true; перейти к шагу 2.
4. Если все Finish[i] = true — состояние безопасно, иначе — небезопасно.

Пример

Система с 5 процессами (P0–P4) и 3 типами ресурсов (A, B, C). Available = (3, 3, 2). Max и Allocation заданы. Алгоритм позволяет определить, можно ли безопасно выделить запрошенный ресурс (например, P1 запрашивает (1, 0, 2)). Если после выделения состояние остаётся безопасным, запрос удовлетворяется.

Практические реализации

• Операционные системы — в ядре Linux используется порядок захвата блокировок (lock ordering) для предотвращения взаимоблокировок при работе с внутренними структурами данных. В Windows — иерархия объектов синхронизации.
• Базы данных — в системах управления базами данных (СУБД) применяются блокировки с тайм-аутами и двухфазная блокировка (2PL), которая предотвращает взаимоблокировки за счёт строгого порядка блокировок. Однако в распределённых СУБД часто используется обнаружение и разрешение взаимоблокировок, а не предотвращение, из-за сложности поддержания глобального порядка.
• Распределённые системы — в протоколах синхронизации (например, на основе маркеров) предотвращение может быть реализовано через упорядочивание запросов по времени (алгоритм Лампорта).

Ограничения и недостатки

• Снижение производительности — методы предотвращения, особенно алгоритм банкира, требуют значительных вычислительных ресурсов для проверки безопасности и могут приводить к неоптимальному использованию ресурсов.
• Необходимость априорной информации — алгоритм банкира требует от процессов объявления максимальных потребностей, что не всегда возможно или практично.
• Неприменимость для некоторых типов ресурсов — нарушение взаимного исключения или принудительного отъёма невозможно для многих физических устройств.
• Риск «голодания» — процессы, требующие большого количества ресурсов, могут постоянно откладываться, если система отдаёт предпочтение более «лёгким» запросам.

Альтернативы

В современных системах часто применяется обнаружение взаимоблокировок с последующим восстановлением (например, принудительное завершение процесса или откат транзакции), а не предотвращение. Это связано с тем, что взаимоблокировки относительно редки, а затраты на постоянное предотвращение могут быть неоправданно высоки. Кроме того, используются тайм-ауты — если процесс не получает ресурс в течение заданного времени, он освобождает все свои ресурсы и повторяет попытку.

Источники

1. Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
2. Сильбершатц А., Корн Г., Судхаршан С. «Операционные системы: внутреннее устройство и проектирование». 9-е издание. — М.: Вильямс, 2018.
3. Дейкстра Э. «Взаимодействие последовательных процессов» (E. W. Dijkstra, «Co-operating sequential processes», 1965).
4. Коффман Э. Г., Элфик М. Дж., Шошани А. «Системные тупики» (E. G. Coffman, M. J. Elphick, A. Shoshani, «System Deadlocks», 1971).