Операционные системы. Тупики

1.

Операционные
Системы
Тупики
КРСУ, Бишкек, Гайдамако В.В.

2.

Преамбула - ресурсы
Выгружаемый ресурс можно
безболезненно забрать у владеющего им
процесса (пример – память)
Невыгружаемый ресурс нельзя забрать у
текущего владельца, не уничтожив
результаты работы (пример – во время
записи забрать управление CD диском –
он будет испорчен). Взаимоблокировки
возникают при доступе к невыгружаемым
ресурсам
КРСУ, Бишкек, Гайдамако В.В.

3.

Доступ к ресурсам
Запрос ресурса (request, open)
Использование ресурса
Возврат ресурса
Если ресурс недоступен, запрашивающий
процесс вынужден ждать. В некоторых ОС
– блокируется и возобновляется после
освобождения ресурса или
Вызывающий процесс сам повторяет
попытку позже
КРСУ, Бишкек, Гайдамако В.В.

4.

Проблемы
если средствами синхронизации пользоваться неосторожно,
то могут возникнуть непредвиденные затруднения.
Предположим, что несколько процессов конкурируют за
обладание конечным числом ресурсов. Если запрашиваемый
процессом ресурс недоступен, процесс переходит в
состояние ожидания. В случае если требуемый ресурс
удерживается другим ожидающим процессом, то первый
процесс не сможет сменить свое состояние. Такая ситуация
называется тупиком. Говорят, что в мультипрограммной
системе процесс находится в состоянии тупика, дедлока
(deadlock) или клинча, если он ожидает события, которое
никогда не произойдет. Системная тупиковая ситуация или
зависание системы является следствием того, что один или
более процессов находятся в состоянии тупика.
КРСУ, Бишкек, Гайдамако В.В.

5.

Пример тупика
КРСУ, Бишкек, Гайдамако В.В.

6.

Пример
Тупики также могут иметь место в ситуациях, не
требующих выделенных ресурсов. Например, в
системах управления базами данных процессы
могут локализовать записи, чтобы избежать гонок
(см. главу "Синхронизация процессов"). В этом
случае может получиться так, что один из
процессов заблокировал записи, требуемые
другому процессу, и наоборот. Т.о. тупики могут
иметь место, как на аппаратных, так и на
программных ресурсах.
КРСУ, Бишкек, Гайдамако В.В.

7.

Пример
Другой пример - возникновение тупика в системах спулинга.
Режим спулинга - ввод-вывод с буферизацией информации,
предназначенной для печати, на диске, и организации
очереди на печать, часто применяется для повышения
производительности системы. Программа, осуществляющая
вывод на печать, должна полностью сформировать свои
выходные данные в промежуточном файле, после чего
начинается реальная распечатка. В итоге, несколько заданий
может оказаться в тупиковой ситуации, если
предусмотренная емкость буфера для промежуточных
файлов будет заполнена до того, как одно из заданий
закончит свою работу. Возможные решения: увеличить
размер буфера, или не принимать дополнительные задания,
если файл спулинга близок к какому то порогу насыщения,
например, заполнен на 75%.
КРСУ, Бишкек, Гайдамако В.В.

8.

Определение
Определение. Множество процессов находится в
тупиковой ситуации, если каждый процесс из
множества ожидает события, которое только
другой процесс данного множества может
вызвать.
Так как все процессы чего-то ожидают, то ни один
из них не сможет инициировать событие, которое
разбудило бы другого члена множества и,
следовательно, все процессы будут спать
вместе. Обычно событие, которого ждет процесс
в тупиковой ситуации - освобождение ресурса.
КРСУ, Бишкек, Гайдамако В.В.

9.

Условия взаимоблокировки
(Коффман)
Условие взаимного исключения (mutual
exclusion)
Условие удержания и ожидания
(Hold&wait)
Условие невозможности принудительной
выгрузки (невытесняемость) ресурса (nonpreemtable resourses)
Условие циклического ожидания
Для тупика должны выполняться все 4 условия
КРСУ, Бишкек, Гайдамако В.В.

10.

Моделирование – направленные
графы процесс-ресурс
a)
b)
c)
Ресурс R занят (стрелка к процессу)
Процесс B запросил ресурс S
Тупик (процесс D владеет ресурсом T и
запрашивает ресурс U, занятый
процессом C, ожидающим ресурс T)

11.

Что делать? Стратегии
Пренебрежение – алгоритм страуса
Обнаружение и восстановление
Динамическое избегание возникновения
тупика с помощью тщательного
распределения ресурсов
Предотвращение с помощью атаки одного
из условий возникновения
КРСУ, Бишкек, Гайдамако В.В.

12.

Функции ОС
Обнаружение
Восстановление
Предотвращение
Избежание
КРСУ, Бишкек, Гайдамако В.В.

13.

Обнаружение для одного ресурса
каждого типа
Процессы: A-G
Ресурсы: R-W
Строим граф процесс-ресурс (а), ищем
циклы (б)

14.

Обнаружение для одного ресурса
каждого типа – алгоритм поиска циклов
Список узлов графа L, на ребрах ставится метка «уже
проверено»
1.N – начальный узел, список L пуст, ребра не маркированы
2.Текущий узел добавляем в список (в конец), проверяем весь
список – есть ли данный узел, если есть – обнаружен цикл,
завершаем
3.Для данного узла смотрим, выходит ли из него хотя бы одно
немаркированное ребро. Если да – шаг 4, нет – шаг 5
4.Случайным образом выбираем любое исходящее
немаркированное ребро и отмечаем его. По нему переходим к
следующему узлу и шаг 2
5.Зашли в тупик графа – дальше хода нет. Удаляем последний
узел из списка и возвращаемся к предыдущему узлу.
Обозначаем его следующим узлом и шаг 2. Если это начальный
узел – тупиков нет, завершение

15.

Обнаружение при наличии нескольких
ресурсов одного типа
N процессов, m – число классов ресурсов, в системе Ei
(1<=i<=m) экземпляров ресурсов каждого класса. E – вектор
существующих ресурсов, А – вектор доступных ресурсов, С –
матрица текущего распределения, R - матрица запросов
Важно:

16.

Обнаружение при наличии нескольких
ресурсов одного типа, алгоритм
Для векторов: А<=В тогда и только тогда, когда Ai<=Bi для всех 1<=i<=m
В исходном положении все процессы немаркированы, если
процесс может закончить работу, он маркируется
Алгоритм:
1.Ищем немаркированный процесс Pi, для которого Ri<=A (то
есть ищем процесс, который может доработать до конца, все
нужные ему ресурсы свободны)
2.Если нашли, прибавляем Ci к вектору A, маркируем процесс и
шаг 1 (процесс отдаст свои ресурсы после завершения)
3.Если таких процессов нет, все немаркированные процессы в
тупике, завершение

17.

Обнаружение при наличии нескольких
ресурсов одного типа, пример
4 класса ресурсов (мл, плоттеры, сканеры, CD)
Здесь тупика нет – процесс 3 может отработать, вернуть ресурсы и
все процессы завершатся.
Но если предположить, что процессу 3 понадобится еще и CD R3=(2101) – тогда мы в тупике

18.

Когда производить
обнаружение тупиков?
Каждый раз при запросе ресурса
Проверять систему через каждые k минут
Проверять систему, когда нагрузка
процессора меньше заданного значения
(при большом количестве тупиков нагрузка
на процессор упадет)
КРСУ, Бишкек, Гайдамако В.В.

19.

Восстановление – принудительная
выгрузка ресурса
Предположим, что тупик обнаружен. Как
восстановить систему и привести ее в рабочее
состояние?
Если можно забрать у процесса ресурс, а потом
отдать его и с наименьшими потерями продолжить
работу – так и сделаем (пример с принтером –
откладываем отпечатанные процессом листы в
сторону, даем отпечатать другому процессу, потом
продолжаем работу с прерванного места)
Возможность этого сильно зависит от свойств
ресурсов. К сожалению, в большинстве случаев не
сработает

20.

Восстановление - откат
Если предполагается, что может возникнуть тупик,
расставляем контрольные точки (checkpoints)
Состояние системы в контрольной точке
записывается в файл и впоследствии может быть
восстановлено из этого файла
Каждая контрольная точка записывается отдельно
Для выхода из тупика процесс (один из) откатывается
на контрольную точку до тупика, результаты работы
после КТ теряются
Остальные процессы продолжают работу
Остановленный
процесс запускается с
контрольной точки

21.

Восстановление через
уничтожение процесса
Простейший выход – выбрать жертву и
уничтожить один (или несколько) из
процессов, находящихся в тупике
Там, где возможно, завершать нужно
процесс, который можно просто запустить
сначала (компиляция, импорт из
текстового файла)

22.

Избежание (обход) тупиков. Траектория
ресурсов – графическое представление
Система с двумя процессами А,В и двумя
ресурсами – принтером и плоттером. Ось Х
– команды А, ось У – команды В
А – К1-К3 – запрос и освобождение
принтера, К2 –К4 запрос и освобождение
плоттера
В – К5-К7 – плоттер, К6-К8 -принтер

23.

Избежание (обход) тупиков. Траектория
ресурсов – графическое представление
Каждая точка – совместное состояние двух
процессов

24.

Избежание (обход) тупиков. Безопасные
состояния
Состояние безопасно, если система не
находится в тупике и существует порядок
планирования, при котором каждый процесс
может работать до завершения, даже если
все процессы захотят сразу получить
максимально требуемое количество
ресурсов
Всего 10 экземпляров
ресурса, процессы
A,B,C, безопасно
Если процесс А после
а) запросит еще один
ресурс (А 4 9),
состояние небезопасно

25.

Избежание (обход) тупиков. Алгоритм банкира
для одного вида ресурсов
Проверяем, приводит ли выполнение запроса к
безопасному состоянию. Если нет – запрос
отклоняется. Проверка при каждом запросе на
ресурс
a) Безопасное
b) Безопасное
c) Небезопасное

26.

Избежание (обход) тупиков. Алгоритм банкира
для нескольких видов ресурсов
Обобщение алгоритма обнаружения тупика.
1.Ищем в матрице запросов строку Ri<=A. Если такой строки нет,
возможен тупик
2.Допускаем, что найденный процесс запросил все ресурсы и
завершается, помечаем его и прибавляем освобожденные ресурсы
к вектору А
3.Повторяем 1 и 2, пока все процессы не будут помечены.
Состояние безопасно
(процесс В может
завершиться. Если же
Е запросит еще один
сканер, А=(1 0 0 0) –
тупик. Запрос Е нужно
отложить

27.

Предотвращение тупиков. Взаимное
исключение
Достаточно нарушить одно из условий.
Если в системе нет ресурсов, требующих
эксклюзивного доступа – тупиков не будет.
Но природа ресурсов обычно как раз этого
требует – представьте принтер без
эксклюзивного доступа.
Подкачка – spooling – разрешаем печатать
только демону принтера, процессы сохраняют
свои файлы для печати на диске (в спул
директории)
КРСУ, Бишкек, Гайдамако В.В.

28.

Предотвращение тупиков. Hold&Wait
Требуем запрашивать все ресурсы до начала
работы. Если какие-то ресурсы заняты,
процесс ожидает
Не всегда (скорее всегда не) заранее
известны ресурсы которые потребуются
Ресурсы будут использоваться не оптимально
Модификация – процесс освобождает все
удерживаемые ресурсы перед тем, как
запросить новый, а затем пытается сразу
получить все необходимое
КРСУ, Бишкек, Гайдамако В.В.

29.

Предотвращение тупиков. Отсутствие
принудительной выгрузки
Или затруднительно, или вообще невозможно
КРСУ, Бишкек, Гайдамако В.В.

30.

Предотвращение тупиков.
Циклическое ожидание
1.
2.
Правило – процесс может обладать только
одним ресурсом в каждый момент времени
(не всегда удобно и приемлемо)
Нумерация ресурсов – каждому ресурсу
присваивается уникальный номер.
Запрашивать ресурсы можно только в
порядке возрастания или убывания.
КРСУ, Бишкек, Гайдамако В.В.

31.

Двухфазное блокирование
Базы данных – часто нужно заблокировать записи и
обновить сразу все (в одной или нескольких
таблицах), при одновременной работе нескольких
процессов высокая вероятность тупиков
Двухфазное блокирование - сначала пытаемся
заблокировать все нужные записи по одной за раз
Если получилось, делаем обновление и освобождаем
блокировки
Если какая-то запись уже заблокирована,
освобождаем все блокировки (в некоторых СУБД не
освобождаем) и начинаем снова
КРСУ, Бишкек, Гайдамако В.В.

32.

Тупики без ресурсов
Тупик может возникнуть «без ресурсов» –
при доступе к семафорам – вспомните
задачу ограниченного буфера – если
операции выполнялись в неправильном
порядке - тупик
КРСУ, Бишкек, Гайдамако В.В.

33.

Голодание
При доступе к ресурсам в динамичной системе
используется политика принятия решения о доступе
(основанная на приоритетах, размерах
процессов/файлов, положении головки диска и тп)
Применение такой политики может привести к долгому
простою некоторых процессов без их блокировки
Если при выборе жертвы для выхода из тупика берутся
в внимание какие-то факторы «стоимости» (например,
исходя из приоритетов), некоторые процессы постоянно
будут избираться жертвами при выходе их тупика
Голодания не возникает при дисциплине FIFO
КРСУ, Бишкек, Гайдамако В.В.