Что такое взаимоблокировка (deadlock)
(продолжение предыдущего поста)

Рассмотрим взаимоблокировки: условия возникновения, способы предотвращения и стратегии восстановления.

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

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

Условия Коффмана (названы в честь Эдварда Г. Коффмана‑младшего, который впервые сформулировал их в 1971 году) описывают четыре необходимых условия, которые должны присутствовать одновременно для возникновения взаимоблокировки:
* взаимное исключение (Mutual Exclusion);
* удерживание и ожидание (Hold and Wait);
* отсутствие принудительного изъятия (No Preemption);
* циклическое ожидание (Circular Wait).

Предотвращение взаимоблокировок

* Упорядочивание ресурсов: установить полный порядок для всех типов ресурсов и требовать, чтобы каждый процесс запрашивал ресурсы в строго возрастающем порядке.
* Таймауты: процесс, который удерживает ресурсы слишком долго, может быть откатан назад (выполнен откат).
* Алгоритм банкира (Banker’s Algorithm): алгоритм предотвращения взаимоблокировок, который имитирует распределение ресурсов между процессами и помогает определить, безопасно ли удовлетворять запрос на ресурс, исходя из будущего наличия ресурсов. Это позволяет избегать небезопасных состояний.

Восстановление после взаимоблокировки

* Выбор «жертвы»: большинство современных систем управления базами данных (СУБД) и операционных систем реализуют сложные алгоритмы для обнаружения взаимоблокировок и выбора «жертв». Часто допускается настройка критериев выбора «жертвы» через параметры конфигурации. Выбор может основываться на использовании ресурсов, приоритете транзакции, стоимости отката и т. д.
* Откат (Rollback): база данных может выполнить откат всей транзакции или только её части — достаточной для снятия взаимоблокировки. Откаченные транзакции могут быть автоматически перезапущены системой управления базами данных.