Кратко постановка задачи

В многопользовательской ОС процессы берут блокировки на ресурсы (файлы, сокеты и т.п.). Пример простой ситуации: процесс A держит файл F и ждёт сокет S; процесс B держит S и ждёт F — классический deadlock (взаимная блокировка).

Матрицы и представление
1) Обозначения

Процессы: P = {A, B, ...}Ресурсы: R = {F, S, ...} (каждому ресурсу соответствует m_i экземпляров; часто m_i = 1 для mutex/исключительных блокировок)
2) Allocation (A) — матрица выделений, A[i,j] = число экземпляров ресурса j, удерживаемых процессом i.
3) Request/Need (R) — матрица запросов, R[i,j] = число экземпляров ресурса j, которые процесс i сейчас ждёт (ожидаемый запрос).
4) Available (V) — вектор доступных экземпляров каждого ресурса.

Пример (по вашему сценарию, m_F = m_S = 1):

Allocation:
A = [ [1, 0], // A держит F
[0, 1] ] // B держит S
столбцы: [F, S]Request (текущий блокирующий запрос):
R = [ [0, 1], // A ждёт S
[1, 0] ] // B ждёт FAvailable V = [0, 0] (оба ресурса заняты)

Это легко визуализируется как граф ожиданий (wait‑for graph): вершины A,B; ребро A→B (A ждёт ресурс у B), ребро B→A → цикл ⇒ deadlock.

Алгоритм обнаружения дедлоков (на основе графа ожиданий)

Построить wait‑for graph G: для каждого процесса P и каждого ресурса r, если P ждёт r и r удерживается процессом Q, добавить ребро P→Q.Найти цикл в G (DFS или алгоритм Тарьяна для SCC). Наличие цикла ⇒ deadlock среди процессов в цикле (при ресурсах с единичной инстанцией). Для ресурсов с несколькими экземплярами нужен более тонкий анализ (алгоритм поиска невозможности удовлетворения).Сложность: O(|P| + |E|) для DFS; поддержка инкрементного обновления графа позволяет запускать проверку при изменениях.

Алгоритм предотвращения — Banker's algorithm (избежание)

Требует заранее известных "Max" требований каждого процесса (макс. потребности по каждому ресурсу).Считаем Need = Max − Allocation. При поступлении нового запроса, симулируем выделение (Available' = Available − request; Allocation' = Allocation + request; Need' = Need − request) и запускаем Safety-check:
Имеется набор Finish[] = false; Work = Available'.Пока существует процесс i с Finish[i]=false и Need[i] ≤ Work: Work += Allocation[i]; Finish[i]=true.Если в конце все Finish[i]=true, состояние безопасно → разрешаем запрос, иначе отклоняем (не давать выделение).Banker's предотвращает вход в небезопасное состояние, но не обязательно обнаруживает будущие deadlock, а гарантирует, что система будет в состоянии, из которого все процессы могут завершиться.Сложность проверки: O(|P| * |R|) за одну проверку (можно считать приемлемым для небольших систем).

Сравнение Banker's algorithm и графа состояния (wait‑for graph / RAG)

Требования к входным данным:
Banker's: требуется заранее известный Max (пассирование максимальных потребностей). Это часто невозможно для динамических ресурсов (сокеты, файлы, неопределённая логика).RAG/Wait‑for: работает на фактическом текущем состоянии Allocation/Request — не требует Max.Превентивность vs детекция:
Banker's — избежание (prevention/avoidance): не допускает переход в небезопасное состояние.Граф — детекция: обнаруживает уже возникший цикл; затем требуется восстановление.Производительность:
Banker's: вычислительная нагрузка при каждом запросе (симуляция), масштаб может ухудшаться при большом числе процессов и ресурсов.Граф: поддержка инкрементного обновления, периодическая проверка или проверка при каждом событии — дешевле (DFS).Практичность:
Banker's редко применим в реальных ОС из‑за требуемого знания Max и динамичности ресурсов. Подходит для специализированных систем (базы данных с заранее известными потребностями).Wait‑for / RAG — широко применимы для обнаружения и диагностики (например, deadlock detector).Точность:
Banker's гарантирует отсутствие тупиковых состояний, но может отказать в обслуживании (требует отказать некоторым запросам) даже если реального deadlock не возник бы.Детектор на графах обнаружит фактический цикл, но восстановление может быть дорогим (aborts, rollbacks).

Восстановление после обнаружения дедлока (опции)

Прервать один или несколько процессов (равномерно или по приоритету) — простое, но потеря работы.Принудительная отнятие ресурсов (preemption) — иногда невозможно или дорого (файлы, сокеты, т.н. «непрерываемые» операции).Откат/транзакция — если приложение поддерживает checkpoint/rollback.Таймауты и авто‑перепроба (try‑lock + backoff) — часто практично, уменьшает вероятность застревания.

Практические компромиссы и рекомендации для реальной ОС
1) Не пытаться универсально применять Banker's:

Требует Max и хорошо работает при небольшом количестве ресурсов/процессов и предсказуемых потребностях.Для файло-сокетов (динамичные соединения, неизвестные max) неприменим.
2) Использовать локальные простые правила проектирования:Глобальный порядок блокировок (resource ordering): присвоить всем ресурсам строгий порядок и требовать захватывать в порядке возрастания — устраняет circular wait. Очень эффективно и дешево, но требует дисциплины и сложно в распределённых системах.Минимизировать hold‑and‑wait: брать все нужные блокировки одномоментно (try‑lock для всех), либо освобождать уже взятые при неудаче и повторять с backoff.
3) Предпочесть детекцию + восстановление и таймауты в динамичных системах:Периодический deadlock detector (wait‑for graph) + политика восстановления (abort lowest‑cost process / restart) — гибкая и практичная стратегия.Логирование для диагностики (Linux lockdep, инструменты) помогает отлавливать шаблоны взаимоблокировок.
4) Non‑blocking/асинхронные конструкции:Там, где возможно, избегать блокировок: nonblocking IO, epoll/select, lock‑free структуры, transactional file operations.
5) Специфика файлов и сокетов:Файловые блокировки: использовать advisory locks аккуратно; разрешать shared (чтение) и exclusive (запись), минимизировать границы критических секций.Сокеты: обычно не блокируют другие ресурсы — архитектурно стоит избегать ситуаций, где сокет‑операция одновременно требует внешних файловых lock‑ов.
6) Мониторинг и метрики:Метрики ожиданий и блокировок, pprof/trace для поиска «горячих» точек, которые чаще приводят к взаимоблокировкам.

Пример гибридной практики (что реально делают ОС/сервисы)

Для ядра/библиотек: запретить некоторые сочетания блокировок, ввести ранжирование (lock classes), использовать динамическую проверку (lockdep в kernel) для отлова потенциальных циклов в разработке.Для серверных приложений: попытка получить все ресурсы через try‑lock, при неудаче release и retry с экспоненциальной задержкой; также задать таймауты и мониторинг.Для транзакционных подсистем: использовать протоколы блокировок с откатом (табличные БД применяют Deadlock detection + abort одного транзакта).

Итого — практическое резюме

Banker's хороший теоретический инструмент для избежания deadlock, но в реальной ОС с динамичными требованиями и множеством типов ресурсов он малопригоден. Wait‑for / Resource Allocation Graph — простой и практичный метод обнаружения (cycle detection) и диагностики; требует политики восстановления. Лучшие практики в реальной системе: сочетание проектных ограничений (порядок блокировок), неблокирующих техник (async, try‑lock), таймаутов и периодического детектора с разумной стратегией восстановления. Это обеспечивает баланс между производительностью, простотой и надёжностью.