Дедлок¶

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

¶История

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

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

¶Условия возникновения (условия Коффмана)

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

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

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

¶Методы борьбы с дедлоками

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

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

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

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

¶Избегание (Avoidance)

Избегание требует от операционной системы знания о будущих запросах ресурсов каждого процесса. Система анализирует текущее состояние распределения ресурсов и, получив запрос от процесса, принимает решение: предоставить ресурс или отложить запрос, чтобы избежать перехода в «небезопасное состояние» — состояние, из которого при определённом стечении обстоятельств может возникнуть дедлок. Наиболее известным алгоритмом избегания является алгоритм банкира (Banker's algorithm), предложенный Эдсгером Дейкстрой. Алгоритм моделирует работу банка, который выдаёт кредиты (ресурсы) клиентам (процессам) и должен гарантировать, что сможет удовлетворить все запросы, не обанкротившись (не попав в дедлок). Недостаток — необходимость априорного знания максимальных потребностей процессов, что на практике часто невозможно.

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

Этот метод допускает возникновение дедлоков, но система должна уметь их обнаруживать и восстанавливать работоспособность.

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

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

Некоторые системы, особенно однопользовательские или встроенные, просто игнорируют проблему дедлоков, полагая, что они возникают крайне редко и не оказывают существенного влияния на работу. Этот подход известен как «стратегия страуса» (Ostrich algorithm). В случае возникновения дедлока пользователь вынужден перезагрузить систему вручную. Такой подход применяется в некоторых ранних версиях операционных систем или в простых микроконтроллерах.

¶Примеры дедлоков

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

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

¶Дедлок в базах данных

Транзакция 1 блокирует строку A и запрашивает блокировку строки B. Транзакция 2 блокирует строку B и запрашивает блокировку строки A. Обе транзакции ждут друг друга, и система управления базами данных (СУБД) должна обнаружить и разрешить этот дедлок (обычно путём отката одной из транзакций).

¶Дедлок в сетевых протоколах

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

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

• Livelock (живая блокировка): Ситуация, при которой процессы не находятся в состоянии ожидания, но постоянно меняют свои состояния, пытаясь избежать дедлока, и в результате ни один из них не может выполнить полезную работу. Процессы «активно» ждут, но без прогресса.
• Starvation (голодание): Ситуация, при которой один или несколько процессов бесконечно долго не получают доступ к необходимому ресурсу, в то время как другие процессы используют его. В отличие от дедлока, голодание не обязательно приводит к полной остановке системы, но может существенно снизить её производительность.
• Race condition (состояние гонки): Ситуация, при которой результат работы системы зависит от порядка выполнения или синхронизации процессов. Состояние гонки может привести к непредсказуемому поведению и, в некоторых случаях, к дедлоку.

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

• Термин «deadlock» впервые был использован в контексте вычислительной техники в 1968 году в статье «System Deadlocks» авторства Дж. У. Хэвиленда (J. W. Havender).
• Проблема дедлоков не ограничивается только программным обеспечением. Она может возникать в любых системах, где есть конкуренция за ресурсы, например, в дорожном движении (когда автомобили блокируют друг друга на перекрёстке) или в управлении проектами (когда две команды ждут друг от друга результатов работы).
• Алгоритм банкира, несмотря на свою теоретическую элегантность, редко применяется на практике из-за сложности получения точных данных о будущих потребностях процессов.