Первый инсайт: дедлоки не возникают просто так, для них необходимо 3 условия: exclusive access, no-preemption, hold-and-wait + одно достаточное: circular wait.
Второй инсайт: чтобы побороть дедлок, достаточно избавить от одного из условий!
Пункт 2 особенно интересен, и позволяет другими глазами взглянуть на работу с ресурсами и привычные «программистские трюки». Например: почему часто разделяют локи на read-only и write-only локи? Для перформанса, конечно. Но ещё и потому что в read-only локе не может возникнуть дедлок, так как он не эксклюзивный (первое условие)!
Или вот я недавно сделал нечаянно не concurrent индекс в postgres на табличку с парой сотен миллионов записей и всё встало колом. Решение проблемы — preemption! Руками грохаем транзакцию и дедлок перестаёт существовать. И это магистры компьютерных наук знали ещё в 70-ых. Подобные же механизмы можно и автоматизировать. Правда не так просто. С одной стороны, обнаружение дедлока — в сущности задача на графах, где просто нужно правильно пройтись по ребрам от процессов до ресурсов. С другой, граф постоянно меняется буквально пока по нему проходишься. Кажется решений проблемы в общем случае нет, но в частных, например только в БД, они есть и работают.
С hold-and-wait тоже интересно. А что если бы процесс сразу же запрашивал все ресурсы, которые ему требуются? Или по крайней мере захватывал бы их постепенно, но при не успехе отпускал бы все уже захваченные. Такой подход, оказывается, тоже убирает проблему дедлоков. К сожалению, не каждый процесс знает наперёд ни все нужные ему ресурсы, ни порядок, в котором они будут захватываться. Опять в общем случае решить тяжело, в частном вполне. Например обычно заранее известно, сколько памяти и CPU нужной новой виртуалке/контейнеру, а это тоже ресурсы, за которые тоже может быть конкуренция. Там правда ситуация не обязательно завершиться дедлоком, а скорее перемещением одного из процессов, но это детали. Раскидывать задачи по компьютерам — очень сложная задача, поэтому в как-нибудь в следующий раз.
Наконец, circular-wait. А пусть все ресурсы должны захватывать только в определенном порядке. К примеру, перечислим все ресурсы в системе от
1 до n. И добавим условие: если процесс захватил ресурс 1 <= k <= n, он может захватить только любой другой ресурс с номером m, где m < k. Другими словами, процессу сначала нужно захватить самый «высокоуровневый» ресурс, а дальше все ресурсы пониже. Наличие нумерованных ресурсов и одного условия на их захватывание также позволяет избавиться от дедлоков. Полный пруф есть в [5].Все эти подходы можно широкими мазками разделить на 3 категории:
- Detection. Подходы, которые по графу ресурсов и их зависимостей позволяют обнаружить дедлок. Для борьбы используется preemption.
- Prevention. Цель: задизайнить систему таким образом, чтобы дедлок был невозможен. Например: пронумеровать ресурсы и ввести условие их захвата. Или запретить захватить ресурс, а затем ждать второй.
- Avoidance. Подходы, при которых система переходит только из одного «безопасного» состояния в другое. Решение о выдаче ресурса принимается динамически, к примеру во время запроса. Самый популярный алгоритм: алгоритм банкира. К сожалению для него необходимо, чтобы процессы сразу знали, какие ресурсы им нужны.
- Алгоритм страуса. Или ничего не делать. Стратегия при которой программист сажается на on-call и ему выдаётся кнопка «отмена».
Ресурсы:
1. E.G. Coffman, M. Elphick, A. Shoshani. System Deadlocks.
2. Richard C. Holt. Some deadlock properties of computer systems.
3. S.S. Isloor, T.A. Marsland. The Deadlock Problem: An Overview.
4. Gertrude Neuman Levine. Defining deadlocks.
5. Charles M. Shub. A Unified Treatment of Deadlock.