Параллельные вычисления
Deadlock, Livelock, Starvation
2003 год. Mars Rover Spirit застыл и начал перезагружаться каждые несколько часов. Диагностика с Земли заняла несколько дней. Причина: Priority Inversion - deadlock-подобная ситуация, где высокоприоритетный поток шины данных ждёт мьютекс, захваченный низкоприоритетным потоком файловой системы, а средний поток с другой задачей не пускал низкий. Система зависала. Исправление: включить Priority Inheritance в VxWorks RTOS. Один параметр планировщика - через 75 миллионов километров космоса.
- **Базы данных**: PostgreSQL обнаруживает deadlock между транзакциями и откатывает одну из них
- **Транзакции**: lock ordering - стандартное решение deadlock в банковских системах
- **Go goroutines**: channel deadlock обнаруживается рантаймом Go и паникует с трейсом
- **Java**: ThreadMXBean.findDeadlockedThreads() для runtime обнаружения deadlock
Проблема обедающих философов: как это начиналось
В 1965 году Эдсгер Дейкстра сформулировал задачу об обедающих философах: пять философов сидят за круглым столом, между ними пять вилок. Чтобы есть, философ берёт вилку слева и вилку справа. Если все возьмут вилку слева одновременно - deadlock. Задача стала стандартным benchmark для алгоритмов синхронизации. В 1971 году Дейкстра предложил решение через упорядоченный захват ресурсов. Все современные алгоритмы предотвращения deadlock восходят к этой задаче 1965 года.
Deadlock: 4 условия Коффмана
**Deadlock** (взаимная блокировка) - ситуация когда два или более потока ждут ресурсы, удерживаемые друг другом, и никто не может продолжить выполнение.
**Wait-for Graph:** Deadlock = цикл в графе ожидания. Узлы - потоки, рёбра - 'ждёт ресурс потока'. Алгоритм обнаружения deadlock - поиск цикла в этом графе. PostgreSQL строит такой граф для транзакций и раз в секунду проверяет наличие циклов.
Поток T1 держит ресурс R1 и ждёт R2. Поток T2 держит R2 и ждёт R1. Все 4 условия Коффмана выполнены. Какое условие проще всего нарушить в этом случае?
Предотвращение и обнаружение deadlock
Три стратегии работы с deadlock: Prevention (нарушить условия Коффмана), Avoidance (Banker's Algorithm), Detection + Recovery.
**Banker's Algorithm (Avoidance):** Перед выделением ресурса проверяет, останется ли система в 'safe state' (может ли каждый поток завершиться). Теоретически оптимален, но требует знания максимальных потребностей заранее - непрактично для большинства реальных систем.
PostgreSQL обнаружил deadlock между транзакциями T1 и T2. Как он разрешает ситуацию?
Livelock: движение без прогресса
**Livelock** - потоки активно работают и реагируют друг на друга, но системное состояние не меняется. В отличие от deadlock, потоки не заблокированы - они заняты, но бесполезно.
**Ethernet CSMA/CD** - исторический пример livelock prevention: при collision обе станции ждут случайное время (Binary Exponential Backoff) перед повторной передачей. Без рандомизации они бы коллидировали снова и снова.
Два HTTP клиента одновременно пытаются создать ресурс. При конфликте каждый делает retry немедленно. Что произойдёт?
Starvation: вечное ожидание
**Starvation** - поток никогда не получает необходимый ресурс из-за постоянно приоритетных конкурентов. В отличие от deadlock, система работает корректно - просто некоторые потоки никогда не продвигаются.
**Read-Write Lock и Writer Starvation:** Если читателей много и постоянно приходят новые, писатель может ждать бесконечно. Решение: как только писатель ожидает, новые читатели блокируются. Это нарушает read preference в пользу fairness.
Deadlock и starvation - одно и то же: поток не получает ресурс
Deadlock - взаимная блокировка (circular wait, все участники заблокированы). Starvation - несправедливое планирование (система работает, но один поток системно обходится).
При deadlock система в целом заблокирована в цикле ожидания. При starvation система работает корректно, но планировщик никогда не выбирает конкретный поток. Разные причины требуют разных решений: deadlock - lock ordering или detection; starvation - fair scheduling с aging.
В системе с Priority Scheduling низкоприоритетный поток (priority=10) ждёт CPU уже 10 минут. Какой механизм предотвратит starvation?
Ключевые идеи
- **Deadlock**: 4 условия Коффмана - Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait. Все четыре необходимы.
- **Prevention**: нарушить одно из 4 условий - обычно Circular Wait через lock ordering
- **Detection**: граф ожидания (Wait-for graph) - цикл означает deadlock
- **Livelock**: потоки активно работают, но не продвигаются. Решение - рандомизация
- **Starvation**: поток никогда не получает ресурс. Решение - fair scheduling с aging
Вопросы для размышления
- Почему обнаружение deadlock (detection + recovery) часто предпочтительнее предотвращения (prevention) в базах данных?
- Livelock трудно диагностировать - CPU usage высокий, но работа не делается. Как отличить livelock от нормальной работы под нагрузкой?
- Priority Inheritance решает Priority Inversion - но вводит свои проблемы с propagation. Когда лучше использовать Priority Ceiling вместо Priority Inheritance?