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

1.

Восстановление после взаимоблокировки
Чиркин К.Д., гр.16ВВ1

2.

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

3.

Взаимоблокировка?
Thread 1
Thread 2
Object 1
Object 2
DEADLOCK

4.

Чтобы восстановиться после взаимоблокировки, нужно её обнаружить.
Для этого необходимо:
1. Отслеживать выделение ресурсов (какой процесс каким ресурсом
владеет)
2. Отслеживать поступающие запросы (какой процесс какой ресурс
ожидает)
На основе этих данных строится граф “Процесс-ресурс”. Если в нем
обнаруживаются циклы, то это свидетельствует о взаимоблокировке.

5.

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

6.

Пример взят из книги: “Э. Таненбаум, Современные операционные системы, 4-е издание”

7.

Способы восстановления после взаимоблокировки
1. Уничтожение одного /всех процессов, участвующих в тупике
• Можно продолжать уничтожать процессы, пока тупик не
распадется
• Все вычисления уничтоженных процессов придется повторить
• Грубо, но эффективно
2. Перераспределение ресурсов между процессами вплоть до
разрушения тупика
• Ресурсы отбираются у владельцев и отдаются другим процессам
3. Откат выбранного процесса к некоторой контрольной контрольной
точке или к началу (partial or total partial or total
rollback)

8.

Спасибо за внимание!