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

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

Причины возникновения

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

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

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

Классификация видов взаимоблокировок

Взаимоблокировки классифицируют по нескольким признакам:

По типу ресурсов

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

По масштабу

• Локальные. Ограничены одним вычислительным узлом (одним процессором или ядром).
• Распределённые. Охватывают несколько узлов сети, где процессы на разных машинах ожидают ресурсов друг друга.

По характеру проявления

• Явные (полные). Система полностью останавливается, все процессы в тупике.
• Частичные. В тупик попадает лишь часть процессов, остальные продолжают работу, но общая производительность падает.

Примеры

Классический пример с двумя процессами

Процесс A захватывает ресурс 1 и запрашивает ресурс 2. Процесс B захватывает ресурс 2 и запрашивает ресурс 1. Оба процесса ждут освобождения ресурсов, которые удерживают друг друга. Выполнение останавливается.

Пример из базы данных

Транзакция T1 блокирует строку таблицы A и запрашивает блокировку строки таблицы B. Транзакция T2 блокирует строку таблицы B и запрашивает блокировку строки таблицы A. Обе транзакции не могут завершиться, пока не получат недостающие блокировки.

Пример из реальной жизни

Два автомобиля встречаются на узком мосту, где движение возможно только в одну сторону. Каждый автомобиль не может проехать, пока другой не освободит мост, но ни один не уступает. Это наглядная иллюстрация циклического ожидания.

Методы борьбы

Существует четыре основных подхода к решению проблемы взаимоблокировок, каждый из которых имеет свои достоинства и недостатки.

Предотвращение

Система проектируется так, чтобы нарушить одно из четырёх условий Коффмана. Например, условие удержания и ожидания можно нарушить, заставив процесс запрашивать все необходимые ресурсы сразу до начала работы. Условие циклического ожидания — введя строгий порядок запроса ресурсов (например, все процессы должны запрашивать ресурсы в порядке возрастания их номеров). Недостаток: низкая эффективность использования ресурсов.

Избегание

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

Обнаружение и восстановление

Система не препятствует возникновению тупиков, но периодически проверяет их наличие (например, с помощью графа ожидания). При обнаружении взаимоблокировки применяется один из методов восстановления:

• Принудительное завершение одного или нескольких процессов (самый грубый метод, приводит к потере данных).
• Отъём ресурсов у одного из процессов и передача их другому (требует сохранения состояния процесса для последующего восстановления).
• Откат процесса к контрольной точке (checkpoint), после которой он повторяет выполнение.

Игнорирование

Наиболее распространённый на практике подход, особенно в пользовательских операционных системах (Windows, Linux, macOS). Предполагается, что взаимоблокировки случаются крайне редко, и их устранение ложится на пользователя или администратора (например, принудительное завершение зависшей программы). Этот подход известен как «страусовый алгоритм» — «если проблема случается раз в тысячу лет, то проще её игнорировать, чем тратить ресурсы на её предотвращение».

Взаимоблокировка в базах данных

В системах управления базами данных (СУБД) взаимоблокировки являются распространённой проблемой при параллельном доступе к данным. Для их решения используются:

• Тайм-ауты блокировок. Если транзакция не получает блокировку в течение заданного времени, она автоматически откатывается.
• Графы ожидания. СУБД строит граф, в котором вершины — транзакции, а рёбра — ожидания. Если в графе обнаруживается цикл, одна из транзакций выбирается в качестве «жертвы» и откатывается.
• Уровни изоляции транзакций. Более низкие уровни изоляции (например, READ COMMITTED) снижают вероятность возникновения взаимоблокировок, но могут приводить к другим аномалиям (фантомное чтение, неповторяющееся чтение).

Взаимоблокировка в распределённых системах

В распределённых системах обнаружение взаимоблокировок усложняется из-за отсутствия глобальной памяти и задержек в сети. Используются распределённые алгоритмы, такие как алгоритм Чанди—Мисры—Хааса, который позволяет обнаруживать тупики путём рассылки специальных сообщений-зондов по графу ожидания. Если зонд возвращается к инициатору, это означает наличие цикла.

Взаимоблокировка в операционных системах

В операционных системах общего назначения взаимоблокировки чаще всего возникают при работе с файловой системой, разделяемой памятью или сетевыми сокетами. Ядро ОС может использовать спин-блокировки (spinlocks) или мьютексы (mutexes), которые при неправильном использовании также приводят к тупикам. В современных ОС (Windows, Linux) применяются динамические механизмы обнаружения, такие как Lockdep (в ядре Linux) — инструмент, который анализирует зависимости между блокировками и предупреждает о потенциальных взаимоблокировках во время разработки драйверов.

Интересные факты

• Термин «deadlock» впервые был использован в контексте вычислительной техники в 1960-х годах в документации по операционной системе IBM OS/360.
• Алгоритм банкира был назван так потому, что он моделирует работу банка, который не может выдать кредит, если это приведёт к невозможности вернуть деньги всем вкладчикам.
• В некоторых языках программирования (например, в Go) существует встроенная конструкция «select» с тайм-аутом, которая позволяет избежать бесконечного ожидания при работе с каналами.
• Взаимоблокировки могут возникать не только в программном обеспечении, но и в аппаратуре — например, при конкуренции за шину данных в многопроцессорных системах.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание).
• Сильбершац А., Корф Г., Сударшан С. «Системы баз данных: полный курс».
• Stallings W. «Operating Systems: Internals and Design Principles».
• Документация ядра Linux: «Locking and Deadlock Detection».
• Coffman E. G., Elphick M. J., Shoshani A. «System Deadlocks» (ACM Computing Surveys, 1971).