Операционные системы. Лекция 7
Дедлок (тупиковая ситуация)
- условия возникновения
- решение проблемы дедлоков
- стратегия предотвращения дедлоков
- стратегия обхода дедлоков
- стратегия распознавания дедлоков
- методы восстановления
1
Дедлок(тупик) – это ситуация , при которой
множество
параллельных
процессов
находятся в состоянии бесконечного ожидания
ресурсов из за неправильного распределения
запросов на ресурсы
Простой пример дедлока:
Процесс P1 использует R1 и запрашивает R2
Процесс P2 использует R2 и запрашивает
R1
2
Условия возникновения дедлока
Условие взаимного исключения, при котором
процессы осуществляют монопольный доступ к
ресурсам.
Ожидание. Процесс, запросивший ресурс, будет
ждать, пока запрос не будет удовлетворен,
продолжая удерживать все остальные ресурсы,
которые он уже получил.
Отсутствие перераспределения. Никакие ресурсы
нельзя отобрать у процесса, если они ему уже
выделены.
Условие
кругового
ожидания.
Существует
замкнутая цепь процессов, каждый из которых ждет
ресурс, удерживаемый его предшественником в этой
цепи.
3
Стратегия предотвращения дедлоков
Косвенный метод
Основан на предотвращении одного из первых трёх
условий возникновения
1.
Условие
взаимного
исключения
можно
предотвратить неограниченным выделением ресурсов
2. Ожидание можно исключить предварительным
выделением ресурсов(процесс должен потребовать все
ресурсы заранее, и он не может начать выполнение до тех
пор, пока они ему не будут выделены)
3. Отсутствие перераспределения можно исключить,
позволяя ОС отнимать у процесса ресурсы
4
Стратегия предотвращения дедлоков
Прямой метод
Основан на предотвращении кругового ожидания
Круговое ожидание можно исключить, предотвращая
образование цепи используя иерархическое выделение
ресурсов:
1. Все ресурсы образуют иерархию
2. Процесс, затребовавший ресурс на одном уровне, может затем
потребовать ресурс только на более высоком уровне;
3. Процесс может освободить ресурс на данном уровне только после
освобождения всех ресурсов на более высоких уровнях;
4. После того как процесс получил, а потом освободил ресурсы
данного уровня, он может снова запросить ресурсы на том же самом
уровне.
Предварительное выделение ресурсов – частный случай
иерархического выделения, если есть единственный уровень
ресурсов
5
Стратегия обхода дедлоков
Вход в дедлок можно предотвратить, если у
системы
есть
информация
о
последовательности
запросов
ресурсов,
связанных с каждым параллельным процессом.
Если процессы находятся в неопасном
состоянии, то существует по крайней мере
одна
последовательность
состояний,
которая
обходит
опасные
состояния
системы.
Решение задачи – контролируемое выделение
ресурсов(алгоритм банкира)
6
Стратегия распознавания дедлоков
Необходимо установить, существуют ли процессы,
находящиеся в состоянии дедлока.
Чтобы выполнить эти вычисления, ОС должна:
вести список тех ресурсов, которые ждет каждый
заблокированный процесс
вести список тех процессов, которые удержат каждый
ресурс
Алгоритм распознавания замкнутых цепей можно
выполнять с любой нужной частотой:
всякий раз, когда запрос на ресурс отклоняется
через заданные интервалы времени
Стоимость стратегии распознавания дедлока зависит
от того, насколько часто выполняется алгоритм
распознавания
7
Методы восстановления
• Принудительное завершение всех процессов и запуск
ОС заново(самый простой метод восстановления)
• Принудительное
завершение
всех
процессов,
находящихся в дедлоке(менее радикальный метод)
• Принудительное завершение процессов, находящихся
в дедлоке, по одному и после каждого завершения
вызывать алгоритм выявления дедлока до тех пор,
пока дедлок не исчезнет.
Основная «цена» восстановления от дедлока – это
потеря
времени,
существенными.
которые
могут
быть
8
