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

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

• **Банковские системы:** два потока одновременно переводят деньги между одними и теми же счетами в разных направлениях - оба захватывают по одному мутексу и ждут второго. Система зависает.
• **Базы данных:** транзакция A блокирует строку X и ждёт строку Y, транзакция B блокирует Y и ждёт X. СУБД должна обнаружить deadlock и откатить одну из транзакций.
• **Операционные системы:** процессы конкурируют за ресурсы (память, файлы, принтеры). ОС должна либо предотвращать deadlock через умное планирование, либо обнаруживать и разрешать их.

Цели урока

• Назвать 4 условия Coffman: mutual exclusion, hold-and-wait, no preemption, circular wait
• Прорисовать resource allocation graph и найти цикл
• Применять prevention (lock ordering), avoidance (Banker's), detection (wait-for graph в БД)
• Различать deadlock, livelock и starvation
• Распознать классику: dining philosophers, reader-writer, sleeping barber

Deadlock Conditions

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

В 1971 году Эдвард Коффман сформулировал **четыре необходимых условия** для возникновения взаимоблокировки. Все четыре условия должны выполняться одновременно.

**Условия Коффмана (Coffman conditions):** 1. **Mutual Exclusion** - ресурс может использоваться только одним процессом 2. **Hold and Wait** - процесс удерживает ресурс и ждёт другие 3. **No Preemption** - ресурс нельзя отобрать принудительно 4. **Circular Wait** - существует циклическая цепочка ожидания ресурсов

Разбор каждого условия:

**1. Mutual Exclusion (взаимное исключение)** Ресурс находится в неразделяемом режиме - только один процесс может использовать его в данный момент. Примеры: принтер, файл в режиме записи, участок критической секции.

**2. Hold and Wait (удержание и ожидание)** Процесс, удерживающий хотя бы один ресурс, ждёт получения дополнительных ресурсов, удерживаемых другими процессами.

**3. No Preemption (отсутствие вытеснения)** Ресурс может быть освобождён только добровольно процессом, который его удерживает. Операционная система не может принудительно отобрать ресурс.

**4. Circular Wait (циклическое ожидание)** Существует циклическая цепочка процессов {P₀, P₁, ..., Pₙ}, где P₀ ждёт ресурс от P₁, P₁ ждёт ресурс от P₂, ..., Pₙ ждёт ресурс от P₀.

Resource Graph

**Resource Allocation Graph (граф выделения ресурсов)** - это ориентированный граф для визуализации состояния системы и обнаружения взаимоблокировок.

**Элементы графа:** - **Процессы (P)** - круглые узлы - **Ресурсы (R)** - квадратные узлы - **Рёбра:** - **Request edge** (P → R): процесс запрашивает ресурс - **Assignment edge** (R → P): ресурс выделен процессу - Точки внутри ресурса - количество экземпляров

**Теорема о deadlock:** Если граф **не содержит циклов** - deadlock невозможен. Если граф **содержит цикл**: - Для ресурсов с **одним экземпляром** - deadlock есть - Для ресурсов с **несколькими экземплярами** - deadlock возможен (но не гарантирован)

**Алгоритм обнаружения цикла** в графе выделения ресурсов:

Граф выделения ресурсов сводит обнаружение deadlock к поиску цикла в направленном графе: DFS за O(V+E) по состоянию системы. Ядро ОС может запускать такую проверку периодически, чтобы ловить deadlock в runtime.

Deadlock Prevention

**Deadlock Prevention** - это стратегия предотвращения взаимоблокировок путём нарушения хотя бы одного из четырёх условий Коффмана.

**Методы предотвращения deadlock:** 1. **Нарушить Mutual Exclusion** - сделать ресурсы разделяемыми 2. **Нарушить Hold and Wait** - захватывать все ресурсы сразу 3. **Нарушить No Preemption** - разрешить отбирать ресурсы 4. **Нарушить Circular Wait** - упорядочить ресурсы

**1. Нарушение Mutual Exclusion** Делаем ресурсы разделяемыми, где это возможно. Подходит для read-only ресурсов.

**2. Нарушение Hold and Wait** Процесс должен запросить все нужные ресурсы одновременно перед началом выполнения.

**3. Нарушение No Preemption** Если процесс не может получить ресурс, он освобождает все удерживаемые ресурсы и пробует позже.

**4. Нарушение Circular Wait через упорядочивание ресурсов** Самый практичный метод: назначаем всем ресурсам глобальный порядок и всегда захватываем их в этом порядке.

**Banker's Algorithm (алгоритм банкира)** Более сложный метод предотвращения - система предварительно проверяет, не приведёт ли выделение ресурса к небезопасному состоянию.

**Выбор метода предотвращения:** - **Упорядочивание ресурсов** - самый практичный для большинства случаев - **RW-locks** - для read-heavy нагрузки - **Алгоритм банкира** - когда нужна максимальная безопасность (критические системы) - **tryLock + backoff** - для распределённых систем

Deadlock Detection

**Deadlock Detection** - это стратегия, при которой система позволяет взаимоблокировкам происходить, но периодически обнаруживает их и восстанавливает работу.

**Подход Detection + Recovery:** 1. **Detection** - периодически проверяем наличие deadlock 2. **Recovery** - если обнаружен, разрешаем его **Методы восстановления:** - Завершить один или несколько процессов - Отобрать ресурсы у процессов (preemption)

**Wait-For Graph (граф ожидания)** Для систем с одним экземпляром каждого ресурса можно упростить Resource Allocation Graph до Wait-For Graph:

**Обнаружение deadlock для ресурсов с несколькими экземплярами:** Используется алгоритм, похожий на алгоритм банкира, но работающий с текущим состоянием:

**Восстановление после обнаружения deadlock:**

**Когда запускать Detection?** Компромисс между overhead и временем реакции:

**Частота запуска Detection:** 1. **По таймеру** - каждые N секунд - Простая реализация - Может пропустить короткие deadlock 2. **По событию** - когда процесс блокируется - Быстрое обнаружение - Высокий overhead 3. **Adaptive** - чаще при высокой нагрузке - Баланс производительности - Сложнее реализовать

**Detection vs Prevention:** **Prevention:** - ➕ Deadlock никогда не происходит - ➖ Низкая утилизация ресурсов - ➖ Ограничения на порядок запросов **Detection + Recovery:** - ➕ Высокая утилизация ресурсов - ➕ Нет ограничений на запросы - ➖ Overhead на detection - ➖ Нужен механизм recovery

Ключевые идеи

• **Четыре условия Коффмана:** для deadlock нужны все четыре - mutual exclusion, hold and wait, no preemption, circular wait. Нарушение хотя бы одного предотвращает deadlock.
• **Resource Allocation Graph:** визуализация состояния системы. Цикл в графе указывает на потенциальный (single instance) или возможный (multiple instances) deadlock.
• **Prevention vs Detection:** prevention ограничивает систему для гарантии отсутствия deadlock, detection позволяет большую свободу но требует механизмов обнаружения и восстановления.
• **Практичные методы:** упорядочивание ресурсов (нарушает circular wait) - самый простой и эффективный метод для большинства случаев. Алгоритм банкира - для критических систем. Detection через wait-for graph - для высоконагруженных систем.

Связанные темы

Взаимоблокировки тесно связаны с другими концепциями параллелизма и синхронизации:

• Process Synchronization — Deadlock возникает из-за неправильной синхронизации доступа к разделяемым ресурсам
• Semaphores & Mutexes — Основные примитивы синхронизации, неправильное использование которых приводит к deadlock
• CPU Scheduling — Планировщик должен учитывать взаимоблокировки и приоритеты при распределении CPU

Вопросы для размышления

• Почему в большинстве современных операционных систем (Linux, Windows) НЕ используется алгоритм банкира, хотя он гарантирует отсутствие deadlock?
• Как спроектировать систему управления ресурсами для многопоточного веб-сервера? Какая стратегия подходит больше - prevention или detection - и почему?
• В распределённой системе (несколько серверов) процессы находятся на разных машинах без общей памяти. Как обнаружить deadlock в таком сценарии?

Связанные уроки

• os-05-sync — Дедлок - патологический исход неправильной синхронизации
• os-03-threads — Дедлок возможен только при конкурентном доступе к ресурсам
• os-17-locks-advanced — Lock ordering и lock-free структуры - практическое решение дедлоков
• db-15-locks