Условия Коффмана

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

Формулировка условий

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

Взаимное исключение (Mutual Exclusion)

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

Удержание и ожидание (Hold and Wait)

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

Отсутствие принудительного вытеснения (No Preemption)

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

Циклическое ожидание (Circular Wait)

Существует замкнутая цепочка процессов, в которой каждый процесс ожидает ресурс, удерживаемый следующим процессом в цепочке. Например, процесс A ждёт ресурс, занятый процессом B, процесс B ждёт ресурс, занятый процессом C, а процесс C ждёт ресурс, занятый процессом A.

История возникновения

Эдвард Г. Коффман-младший (род. 1934) — американский учёный в области информатики, известный своими работами по теории массового обслуживания, планированию задач и операционным системам. В 1971 году в соавторстве с М. Дж. Эльфиком и А. Шошани он опубликовал статью «System Deadlocks» (ACM Computing Surveys, Vol. 3, No. 2), в которой впервые систематизировал и формализовал условия возникновения тупиковых ситуаций. До этой работы дедлоки изучались эмпирически, но не были сведены в единую теоретическую модель.

Примеры выполнения условий

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

Рассмотрим два процесса (P1 и P2) и два ресурса (R1 и R2), каждый из которых неделим и доступен в единственном экземпляре.

1. P1 захватывает R1.
2. P2 захватывает R2.
3. P1 запрашивает R2, но он занят P2 — P1 переходит в ожидание (удерживая R1).
4. P2 запрашивает R1, но он занят P1 — P2 переходит в ожидание (удерживая R2).

В результате образуется цикл: P1 → R2 → P2 → R1 → P1. Все четыре условия Коффмана выполнены, и система оказывается в состоянии взаимоблокировки.

Пример из реальной работы ОС

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

Связь с другими концепциями

Необходимость и достаточность

Условия Коффмана являются одновременно необходимыми и достаточными для возникновения дедлока. Это означает, что:

• Если дедлок произошёл, то все четыре условия обязательно выполняются.
• Если все четыре условия выполняются, то дедлок обязательно произойдёт (при условии, что процессы не будут прерваны извне).

Отличие от голодания

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

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

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

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

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

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

Обход (Avoidance)

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

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

Система не препятствует дедлоку, но периодически проверяет наличие циклов в графе распределения ресурсов. При обнаружении дедлока применяются меры:

• принудительное завершение одного или нескольких процессов-участников;
• откат состояния процессов до точки, предшествующей захвату ресурсов (checkpointing);
• принудительное изъятие ресурса у одного из процессов (с возможным последующим перезапуском).

Критика и ограничения

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

Источники

1. Coffman, E. G., Elphick, M. J., & Shoshani, A. (1971). System Deadlocks. ACM Computing Surveys, 3(2), 67–78.
2. Таненбаум, Э., Бос, Х. (2015). Современные операционные системы. 4-е изд. — СПб.: Питер.
3. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. 10th ed. — Wiley.