Обнаружение и избегание deadlock

Как программно понять, что система застряла, и как не выдать ресурс, который заведёт в тупик.

Взаимоблокировку можно обнаружить, найдя цикл в графе ожидания, и избежать, выдавая ресурсы только если система остаётся в безопасном состоянии.

Граф ожидания

Построим граф, где узлы — процессы, а стрелка A → B означает «A ждёт ресурс, который держит B». Ключевая теорема: взаимоблокировка есть тогда и только тогда, когда в этом графе есть цикл (для ресурсов с одним экземпляром). Найти цикл — значит обнаружить deadlock.

Обнаружение через поиск цикла

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

def find_cycle(wait_for):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {n: WHITE for n in wait_for}
    cycle = []
    def dfs(u, path):
        color[u] = GRAY
        path.append(u)
        for v in wait_for.get(u, []):
            if color.get(v, WHITE) == GRAY:        # нашли ребро назад -> цикл
                cycle.extend(path[path.index(v):])
                return True
            if color.get(v, WHITE) == WHITE and dfs(v, path):
                return True
        path.pop()
        color[u] = BLACK
        return False
    for n in wait_for:
        if color[n] == WHITE and dfs(n, []):
            return cycle
    return None

# P1 ждёт ресурс у P2, P2 у P3, P3 у P1 — замкнутый круг
graph1 = {"P1": ["P2"], "P2": ["P3"], "P3": ["P1"]}
c = find_cycle(graph1)
print("Граф 1:", graph1)
print("ВЗАИМОБЛОКИРОВКА! Цикл:", " -> ".join(c + [c[0]]) if c else "нет")

# А здесь цикла нет — все смогут завершиться
graph2 = {"P1": ["P2"], "P2": ["P3"], "P3": []}
print("Граф 2:", graph2)
print("Результат:", "deadlock" if find_cycle(graph2) else "взаимоблокировки нет")

Вывод:

Граф 1: {'P1': ['P2'], 'P2': ['P3'], 'P3': ['P1']}
ВЗАИМОБЛОКИРОВКА! Цикл: P1 -> P2 -> P3 -> P1
Граф 2: {'P1': ['P2'], 'P2': ['P3'], 'P3': []}
Результат: взаимоблокировки нет

Избегание: алгоритм банкира

Алгоритм банкира (Banker's algorithm) — классический способ избегания. Аналогия: банкир выдаёт кредиты, только если уверен, что сможет удовлетворить все обещанные запросы и никто не «лопнет». Перед выдачей ресурса система проверяет: останется ли она в безопасном состоянии — то есть существует ли порядок, в котором все процессы смогут получить нужное и завершиться.

Каждый процесс заявляет максимум, который ему может понадобиться. Система знает, сколько уже выделено и сколько свободно. Need = Max − Allocation. Состояние безопасно, если можно «прокрутить» все процессы до завершения.

def is_safe(available, maximum, allocation):
    n = len(maximum)
    m = len(available)
    need = [[maximum[i][j] - allocation[i][j] for j in range(m)] for i in range(n)]
    work = available[:]
    finish = [False] * n
    order = []
    progress = True
    while progress:
        progress = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
                # процесс i может получить всё нужное -> завершится и вернёт ресурсы
                for j in range(m):
                    work[j] += allocation[i][j]
                finish[i] = True
                order.append(i)
                progress = True
    return all(finish), order

available  = [3, 3, 2]
maximum    = [[7,5,3], [3,2,2], [9,0,2], [2,2,2], [4,3,3]]
allocation = [[0,1,0], [2,0,0], [3,0,2], [2,1,1], [0,0,2]]

safe, order = is_safe(available, maximum, allocation)
if safe:
    print("Состояние БЕЗОПАСНО.")
    print("Безопасная последовательность:", " -> ".join(f"P{i}" for i in order))
else:
    print("Состояние НЕБЕЗОПАСНО — возможна взаимоблокировка")

Вывод:

Состояние БЕЗОПАСНО.
Безопасная последовательность: P1 -> P3 -> P4 -> P0 -> P2

Что делать, когда deadlock обнаружен

Обнаружили взаимоблокировку — нужно её разорвать. Варианты:

• Завершить процесс. Убить один или несколько процессов из цикла, освободив их ресурсы.
• Отнять ресурс (rollback). Отобрать ресурс у процесса и откатить его к сохранённой точке.

Выбирают «жертву» так, чтобы потерять как можно меньше работы.

Итог

• Deadlock обнаруживается как цикл в графе ожидания (для ресурсов с одним экземпляром).
• Поиск цикла обходом в глубину находит взаимоблокировку и её участников.
• Алгоритм банкира избегает deadlock, выдавая ресурсы лишь при безопасном состоянии.
• Безопасное состояние — есть порядок, в котором все процессы завершатся.
• Обнаруженную взаимоблокировку разрывают завершением процесса или откатом.