Взаимная блокировка

Взаимная блокировка (англ. deadlock, также известна как «тупик» или «дедлок») — это состояние в многозадачной вычислительной системе, при котором два или более процесса (или потока) бесконечно ожидают освобождения ресурсов, захваченных друг другом, что приводит к полной остановке их выполнения. Взаимная блокировка является одной из классических проблем синхронизации в операционных системах, базах данных и распределённых системах. Основными условиями возникновения взаимной блокировки являются: взаимное исключение (ресурс может быть занят только одним процессом), удержание и ожидание (процесс удерживает уже захваченный ресурс и запрашивает новый), отсутствие приоритетного отчуждения (ресурс нельзя принудительно изъять у процесса), а также циклическое ожидание (существует кольцевая цепь процессов, каждый из которых ждёт ресурс, удерживаемый следующим в цепи). Эти условия были впервые формализованы американским учёным Эдвардом Коффманом мл. в 1971 году и носят название «условия Коффмана».

История

Проблема взаимной блокировки возникла с появлением первых многозадачных операционных систем в 1960-х годах. В ранних мэйнфреймах, таких как IBM System/360, использовались механизмы блокировок для синхронизации доступа к общим ресурсам (память, файлы, устройства ввода-вывода). Первое систематическое описание deadlock было сделано в 1965 году Эдсгером Дейкстрой в контексте разработки операционной системы THE, где он ввёл понятие «семафоров» и показал, что неправильное использование примитивов синхронизации может приводить к бесконечному ожиданию. В 1971 году Эдвард Коффман мл., вместе с соавторами, опубликовал работу, в которой определил четыре необходимых условия для возникновения взаимной блокировки. С тех пор эта концепция стала фундаментальной для курсов операционных систем, баз данных и параллельного программирования.

Условия возникновения

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

• Взаимное исключение: Ресурс не может одновременно использоваться более чем одним процессом (например, принтер не может печатать два документа одновременно). Если ресурс допускает совместный доступ (например, файл, открытый только для чтения), deadlock невозможен.
• Удержание и ожидание: Процесс уже удерживает хотя бы один ресурс (например, захватил память) и при этом ожидает получения другого ресурса, который в данный момент занят другим процессом.
• Отсутствие принудительного отчуждения: Ресурс нельзя принудительно отобрать у процесса; освободить его может только сам процесс, завершив свою работу или явно отпустив.
• Циклическое ожидание: Существует замкнутая цепочка процессов, в которой каждый процесс ожидает ресурс, удерживаемый следующим процессом в этой цепочке.

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

Пример

Классический пример взаимной блокировки — ситуация с двумя процессами (P1 и P2) и двумя ресурсами (R1 и R2). Процесс P1 захватывает ресурс R1, в то же время процесс P2 захватывает ресурс R2. Затем P1 запрашивает R2, который удерживается P2, а P2 запрашивает R1, который удерживается P1. Оба процесса переходят в состояние ожидания, и ни один из них не может продолжить выполнение. Такая ситуация полностью парализует работу обоих процессов до внешнего вмешательства (например, завершения одного из них операционной системой).

Стратегии обработки взаимных блокировок

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

Предотвращение (Prevention)

Этот подход направлен на исключение возможности возникновения deadlock путём нарушения одного из четырёх условий Коффмана.

• Нарушение взаимного исключения: Использование ресурсов, допускающих совместный доступ (например, разделяемые файлы вместо монопольного захвата). Однако этот подход неприменим к неделимым ресурсам (принтер, плоттер).
• Нарушение удержания и ожидания: Процесс должен запросить все необходимые ресурсы сразу до начала выполнения. Если хотя бы один ресурс недоступен, процесс не запускается. Недостаток — низкая эффективность использования ресурсов и возможность голодания (когда процесс долго не может получить доступ).
• Нарушение отсутствия принудительного отчуждения: Разрешить системе принудительно отбирать ресурсы у процесса (например, если процесс блокируется, система освобождает его ресурсы). Этот механизм сложен в реализации и может приводить к потере данных (при работе с устройствами вывода).
• Нарушение циклического ожидания: Введение строгого порядка захвата ресурсов (нумерация). Например, все процессы обязаны захватывать ресурсы только в возрастающем порядке номеров. Если процессу нужны ресурсы R1 и R2, он сначала захватывает R1, затем — R2. Это исключает циклические цепочки.

Обход (Avoidance)

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

Обнаружение и восстановление (Detection and Recovery)

Этот подход не предотвращает deadlock, а позволяет системе обнаружить его факт и принять меры.

• Обнаружение: Операционная система периодически проверяет граф распределения ресурсов на наличие циклов. Если хотя бы один цикл обнаружен, фиксируется взаимная блокировка. Частота проверки — компромисс между накладными расходами и временем простоя.
• Восстановление:
• Завершение процесса: Убить один или несколько процессов, участвующих в deadlock. Стратегия выбора «жертвы» может учитывать время выполнения, количество использованных ресурсов или приоритет.
• Принудительное отчуждение: Отобрать ресурсы у одного из процессов и передать их другому. Это может потребовать создания контрольных точек (checkpoint) для последующего восстановления состояния «жертвы».

Игнорирование (Ostrich algorithm)

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

Примеры в различных системах

• Базы данных: При одновременных транзакциях, блокирующих строки таблиц. Транзакция 1 блокирует строку A и ждёт C, транзакция 2 блокирует C и ждёт A. СУБД (например, PostgreSQL) автоматически обнаруживает deadlock и завершает одну из транзакций (обычно ту, которая потребляет меньше ресурсов).
• Файловые системы: Процесс A ожидает захвата файла file.txt, удерживаемого процессом B, а процесс B ожидает file.txt, удерживаемого A. В современных ОС это решается через отложенную запись или принудительное завершение процесса.
• Распределённые системы: В кластерных системах или сетевых базах данных, где блокировки распространяются на несколько узлов, обнаружение deadlock усложняется и решается с помощью распределённых алгоритмов (например, двухфазного блокирования).

Критика

Концепция взаимной блокировки является идеализированной моделью. На практике условия Коффмана редко выполняются в полной мере, особенно в современных вычислительных системах с виртуализацией и несколькими ядрами. Правильное проектирование параллельных алгоритмов (использование атомарных операций, неблокирующих структур данных, асинхронного ввода-вывода) часто позволяет избежать deadlock без явного применения стратегий предотвращения. Также критикуется «страусиный алгоритм» за то, что в высоконадёжных системах (например, в системах управления полётами ракет или в медицинском оборудовании) зависание недопустимо, и необходимо гарантировать либо отсутствие deadlock, либо его быстрое обнаружение.

Связанные понятия

• Livelock (активный тупик): Состояние, при котором процессы не заблокированы, но постоянно изменяют своё состояние в ожидании друг друга, не выполняя полезной работы. Например, два процесса пытаются избежать deadlock и бесконечно отказываются от своих ресурсов, создавая циклическую последовательность освобождения/захвата.
• Starvation (голодание): Состояние, при котором низкоприоритетный процесс никогда не получает доступ к ресурсу из-за того, что другие высокоприоритетные процессы постоянно его перехватывают. В отличие от deadlock, процесс остаётся в очереди ожидания, но не блокируется навсегда.

Источники

• Э. Коффман мл., М. Ж. Элфик, А. Шошани. «Системные тупики» (1971).
• Э. Дейкстра. «Взаимодействие процессов» (1965).
• А. С. Таненбаум. «Современные операционные системы» (4-е издание, 2014).
• Дж. Л. Карвер. «Обнаружение и восстановление тупиков в базах данных» (1990).