Основы современных операционных систем. Лекция 13

(C) В.О. Сафонов, 2010
Тупики (deadlocks)
Модель системы
Характеристики тупиков
Обработка тупиков
Предотвращение тупиков
Как избежать тупиков
Обнаружение тупиков
Восстановление после выхода из тупика
Комбинированный подход к обработке тупиков

(C) В.О. Сафонов, 2010
Проблема тупиков
Тупик - множество заблокированных процессов, каждый из которых владеет некоторым ресурсом и ожидает ресурса, которым владеет какой-либо другой процесс из этого множества
Пример
Система имеет два внешних устройства.
P1 и P2 – каждый пользуется некоторым устройством и требует использования другого устройства.
Пример
семафоры A и B, инициализированные 1
P1 P2
wait (A); wait(B)
wait (B); wait(A)

(C) В.О. Сафонов, 2010
Модель системы
Типы ресурсов - R1, R2, . . ., Rm
Процессор, память, устройства ввода-вывода
Каждый тип ресурса Ri имеет Wi экземпляров.
Каждый процесс использует ресурс с помощью одним из следующих способов:
request (запрос)
use (использование)
release (освобождение)

(C) В.О. Сафонов, 2010
Характеристики тупика
Тупик может возникнуть, если одновременно выполняются четыре условия:
Взаимное исключение: Только один процесс в каждый момент времени может получить доступ к ресурсу
Удержание и ожидание: процесс, удерживающий один ресурс, ожидает приобретения других ресурсов, которыми обладают другие процессы.
Отсутствие прерываний: ресурс может быть освобожден процессом только добровольно, когда процесс завершает свою работу.
Циклическое ожидание: существует множество процессов {P0, P1, …, P0} , таких, что P0 ожидает ресурса, которым обладает P1, P1 ожидает ресурса, которым обладает P2, … , Pn–1 ожидает ресурса, которым обладает Pn , а Pn ожидает ресурса, которым владеет P0.

(C) В.О. Сафонов, 2010
Граф распределения ресурсов
Множество вершин V и множество дуг E.
V подразделяется на два типа вершин:
P = {P1, P2, …, Pn}, множество всех процессов в системе.
R = {R1, R2, …, Rm}, множество всех ресурсов в системе.
Дуга типа “запрос” (request edge) – направленная дуга P1 → Rj
Дуга типа “присваивание” (assignment edge) – направленная дуга Rj → Pi

(C) В.О. Сафонов, 2010
Граф распределения ресурсов (продолжение)
Процесс
Тип ресурса, имеющий 4 экземпляра
Pi запрашивает экземпляр ресурса Rj
Pi удерживает экземпляр ресурса Rj
Pi
Pi

(C) В.О. Сафонов, 2010
Пример графа распределения ресурсов

(C) В.О. Сафонов, 2010
Граф распределения ресурсов с тупиком

(C) В.О. Сафонов, 2010
Граф распределения ресурсов с циклом, но без тупика

(C) В.О. Сафонов, 2010
Основные утверждения (факты)
Граф не содержит циклов ⇒ тупиков нет.
Граф содержит цикл ⇒
Если ресурсов каждого типа только по одному экземпляру, то тупик.
Если ресурсов по несколько экземпляров, то возможность тупика.

(C) В.О. Сафонов, 2010
Методы обработки тупиков
Убедиться в том, что система никогда не войдет в состояние тупика.
Допустить, чтобы система могла входить в состояние тупика, но затем восстанавливалась (recover).
Игнорировать эту проблему, но претендовать на то, что в системе тупики невозможны ☺ (используется практически во всех ОС, включая UNIX).

(C) В.О. Сафонов, 2010
Предотвращение тупиков
Ограничить методы запросов
Взаимное исключение – не требуется для разделяемых ресурсов; должно соблюдаться только для не разделяемых ресурсов.
Удержание и ожидание – необходимо гарантировать, чтобы, когда процесс запрашивает некоторый ресурс, он не владел бы никакими другими ресурсами.
Либо требовать от процессов, чтобы они запрашивали и приобретали все необходимые ресурсы до начала их исполнения, либо требовать, чтобы процесс, запрашивающий ресурс, ничем больше не обладал.
Приводит к недостаточному использованию ресурсов; возможна ситуация “голодания” (starvation).

(C) В.О. Сафонов, 2010
Предотвращение тупиков (продолжение)
Отсутствие перераспределения ресурсов –
Если процесс, обладающий некоторыми ресурсами, запрашивает другой ресурс, который не может быть ему немедленно выделен, то все ресурсы, которыми он обладает, должны быть освобождены.
Перераспределяемые ресурсы добавдяются к списку ресурсов, которые ожидает процесс.
Процесс будет перезапущен только в случае, если он может вновь получить все старые ресурсы, которыми он обладал, а также все новые ресурсы, которые он запрашивает.
Циклическое ожидание – ввести общую нумерацию (упорядочение) всех типов ресурсов, и потребовать, чтобы процесс запрашивал ресурсы только в порядке возрастания номеров.

(C) В.О. Сафонов, 2010
Как избежать тупиков
Данные методы требуют, чтобы система обладала дополнительной априорной информацией
Самая простая и полезная модель требует, чтобы каждый процесс указывал максимальный объем ресурсов каждого типа, которые могут ему понадобиться (как в ранних ОС – паспорт задачи и т.д. ).
Алгоритм избежания тупиков динамически анализирует состояние распределения ресурсов, чтобы убедиться, что никогда не может возникнуть ситуация циклического ожидания.
Состояние распределения ресурсов определяется как объем доступных и распределенных ресурсов, а также максимальные требования процессов.