Коротко — почему возможна взаимная блокировка:
- Вопрошаемые условия (Кофман): взаимное исключение, удержание+ожидание, отсутствие принудительного изъятия, циклическое ожидание. Если все четыре выполняются, возможен deadlock (например, цикл в графе распределения ресурсов).
Решения (минимум три принципиально разных), их преимущества/недостатки, влияние на производительность и корректность:
1) Жёсткий порядок захвата ресурсов (resource ordering)
- Идея: присвоить всем ресурсам глобальный порядок и всегда захватывать в возрастающем порядке.
- Плюсы: просто, формально устраняет условие циклического ожидания → deadlock исключён.
- Минусы: требует рефакторинга, неудобно при динамических/неизвестных заранее ресурсов; снижает гибкость.
- Производительность: небольшие накладные расходы на проверку порядка; может снизить параллелизм (фиксация последовательности захватов).
- Корректность: сохраняется (без deadlock), но возможны задержки/конвейинги; атомарность операций нужно обеспечивать отдельно.
2) Таймауты / try-lock + откат и экспоненциальный бэкофф
- Идея: вместо блокирующего lock использовать try-lock с таймаутом; при неудаче освободить удерживаемые ресурсы, подождать/увеличить задержку и повторить; или откатывать операцию и повторять.
- Плюсы: простая реализация, работает для динамических наборов ресурсов, не нужен глобальный порядок.
- Минусы: возможны живые блокировки/голодание, усложнение логики отката/повторов, вероятность частых повторов при высокой нагрузке.
- Производительность: при невысокой конкуренции почти не влияет; при высокой конкуренции — много повторных попыток → падение пропускной способности и рост задержек.
- Корректность: deadlock не гарантированно исключён, но вероятность статической блокировки снижается; нужно корректно реализовать откат, чтобы не нарушать инварианты.
3) Детекция и восстановление (deadlock detection + abort/retry)
- Идея: позволить блокировки, но периодически строить граф распределения ресурсов и искать циклы; при обнаружении — выбрать жертву (abort/rollback) и освободить ресурсы.
- Плюсы: высокая параллельность в нормальном режиме, работает с динамическими ресурсами.
- Минусы: сложность реализации (согласованное состояние для анализа), стоимость откатов, выбор жертвы может быть тяжёлым, возможны повторные аварии.
- Производительность: накладные расходы на детекцию; затраты на восстановление (rollback) могут быть значительны; в целом хорошая пропускная способность при редких конфликтах.
- Корректность: после корректного отката система выходит из deadlock; нужно обеспечить атомарность и компенсацию операций, чтобы не разрушать целостность данных.
4) Отказ от блокировок (lock-free / wait-free / STM / акторная модель)
- Идея: заменить мьютексы атомарными неблокирующими примитивами (CAS), алгоритмами без блокировок, или транзакционной/событийной архитектурой (STM, actor loop).
- Плюсы: исключает deadlock по определению; при правильном дизайне улучшенная масштабируемость и предсказуемость задержек.
- Минусы: высокая сложность разработки и верификации; ABA-проблемы, необходимость сложных алгоритмов; STM имеет накладные расходы (логирование, откаты) и не всегда эффективен.
- Производительность: при высокой конкуренции часто лучше, при низкой конкуренции накладные расходы могут быть выше; wait-free даёт теоретические гарантии прогресса.
- Корректность: при корректной реализации сохраняется линерализуемость/согласованность; deadlock невозможен.
Короткие рекомендации по выбору
- Требуется гарантия отсутствия deadlock и простота реализации → глобальный порядок (если применим).
- Ресурсы динамические, можно допустить откаты → таймауты/try-lock с откатом или детекция+восстановление.
- Высокая конкуренция и требование масштабируемости/низкой задержки → переход на неблокирующие структуры или акторную/транзакционную модель.
Если нужно, могу дать пример кода для конкретного подхода (try-lock с бэкоффом, проверка порядка или простая детекция цикла).