Короткий ответ: да, взаимоблокировка возможна.
1) Пример и граф выделения.
- У нас $4$ процесса $(P_1,\dots ,P_4)$ и $3$ ресурса $(R_1,R_2,R_3)$. Каждый процесс требует одновременно двух ресурсов.
- Возможная ситуация, приводящая к deadlock: $P_1$ захватил $R_1$ и ждёт $R_2$; $P_2$ захватил $R_2$ и ждёт $R_3$; $P_3$ захватил $R_3$ и ждёт $R_1$; $P_4$ ничего не захватил. Тогда циклическое ожидание между $P_1,P_2,P_3$.
- Граф выделения (написано множеством ориентированных рёбер):
$$\{R_1\to P_1,P_1\to R_2,R_2\to P_2,P_2\to R_3,R_3\to P_3,P_3\to R_1\}.$$ Этот цикл свидетельствует о deadlock.
2) Алгоритмы предотвращения (кратко, с плюсами/минусами)
- Принудительный порядок ресурсов (lock ordering). Назначить всем ресурсам глобальный порядок и требовать захвата в возрастающем порядке (например, по индексам). + Простая и дешёвая реализация, исключает циклы. − Требует планирования порядка, снижает гибкость, сложен при динамических ресурсах.
- Запрос всех ресурсов одновременно (atomic allocation). Процесс запрашивает сразу две единицы; если не получится — не захватывает ничего и пробует позже. + Исключает hold-and-wait. − Может сильно снизить параллелизм и вызвать голодание.
- Алгоритм Банковского (Banker’s). Система проверяет, что после выдачи остаётся безопасное состояние. + Гарантирует отсутствие deadlock, позволяет гибкость. − Требует заранее известных максимальных потребностей и дорого по проверкам; редко применим в реальном сервере.
- Предотвращение hold-and-wait и/или допуска предэмуляции (preemption). Принудительно вытаскивать ресурсы у процессов. + Может избавить от deadlock. − Невозможно/дорого для нелёгковесных или небезопасных ресурсов (I/O, внешние соединения).
3) Обнаружение и восстановление
- Обнаружение: периодически строить граф и искать цикл (алгоритм обнаружения циклов; сложность примерно $O(n+m)$, где $n$ — число процессов, $m$ — число рёбер). В многопользовательской системе можно делать scan по таймаутам/переполнениям.
- Восстановление:
- Принудительное убийство/перезапуск процессов по приоритету/возрасту до разрыва цикла. + Простая реализация. − Потеря работы, неудобно для пользователей.
- Отмены транзакций/rollback с сохранёнными контрольными точками. + Более корректно при транзакционной логике. − Требует поддержки checkpoint/undo.
- Принудительная принудительная отъёмка ресурса и перенос состояния. + Подходит для реплицируемых/идемпотентных операций. − Неприменимо к неотъемлемым ресурсам (аппаратному I/O).
- Практический подход часто: детекция + мягкое восстановление (таймауты, выбор «жертвы» по политике) вместо тяжёлых универсальных схем.
4) Практическая применимость для многопользовательской серверной системы
- Ресурс-порядок (lock ordering) — наиболее практичен для серверов: прост, эффективен, минимален overhead; требует проектирования API и соглашений о порядке захвата (рекомендуется).
- Try-lock + таймаут + backoff — тоже очень практичен: не требует глобальной информации, уменьшает шанс тупика, хорош для сетевых/конкурентных операций.
- Запрос всех ресурсов заранее — полезен, если операции короткие и редкие; иначе приводит к плохой пропускной способности.
- Банковский алгоритм — редко применяется в реальных многопользовательских серверах (требует знать максимальные потребности и высока вычислительная стоимость).
- Обнаружение + восстановление — используется как запасной механизм: логировать, детектировать циклы периодически, восстанавливать через rollback/убийство с учётом приоритетов. В реальных системах обычно комбинируют: профилактические меры (порядок, try-lock) + детекция/восстановление как крайнее средство.
Рекомендуемая практическая комбинация: ввести строгие соглашения о порядке блокировок (где возможно) + использовать неблокирующие попытки захвата с таймаутом и экспоненциальным backoff; держать механизм детекции/восстановления и политику выбора жертвы (kill/rollback) как резерв.