Основы операционных систем Лекция 7 - 13.03.071 Лекция 7. Синхронизационные тупики Концепция ресурса Условия возникновения тупиков Основные направления. - презентация

1 Основы операционных систем Лекция Лекция 7. Синхронизационные тупики Концепция ресурса Условия возникновения тупиков Основные направления борьбы с тупиками Алгоритм страуса Обнаружение тупиков Восстановление после тупиков Способы предотвращения тупиков путем тщательного распределения ресурсов Предотвращение тупиков за счет нарушения условий возникновения тупиков Родственные проблемы

2 Основы операционных систем Лекция Введение (1) Были рассмотрены способы синхронизации процессов, которые позволяют процессам успешно кооперироваться Если средствами синхронизации пользоваться неосторожно, то могут возникнуть непредвиденные затруднения Предположим, что несколько процессов конкурируют за обладание конечным числом ресурсов

3 Основы операционных систем Лекция Введение (2) Если запрашиваемый процессом ресурс недоступен, то процесс переходит в состояние ожидания Если требуемый ресурс удерживается другим ожидающим процессом, то первый процесс не сможет сменить свое состояние В мультипрограммной системе процесс находится в состоянии тупика, дедлока (deadlock) или клинча, если он ожидает события, которое никогда не произойдет Системная тупиковая ситуация, или зависание системы является следствием того, что один или более процессов находятся в состоянии тупика

4 Основы операционных систем Лекция Введение (3) Лента Принтер Процесс 1 Процесс 2 Рассмотрим пример Предположим, что два процесса осуществляют вывод с ленты на принтер Один из них успел монополизировать ленту и претендует на принтер, а другой наоборот После этого оба процесса оказываются заблокированными в ожидании второго ресурса

5 Основы операционных систем Лекция Введение (4) Тупики также могут иметь место в ситуациях, не требующих выделенных ресурсов Например, в СУБД процессы могут блокировать записи, чтобы избежать эффекта состязаний Может получиться так, что один из процессов заблокировал записи, требуемые другому процессу и наоборот Таким образом, тупики могут иметь место, как на аппаратных, так и на программных ресурсах

6 Основы операционных систем Лекция Введение (5) Другой пример: возникновение тупика в системах спулинга Программа, осуществляющая вывод на печать, должна полностью сформировать свои выходные данные в промежуточном файле, после чего начинается реальная распечатка Задания могут оказаться в тупиковой ситуации, если буфер промежуточных файлов будет заполнен до того, как одно из заданий закончит свою работу Возможные решения: увеличить размер буфера, или не принимать дополнительные задания, если файл спулинга близок порогу насыщения

7 Основы операционных систем Лекция Введение (6) Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества и, следовательно, все процессы будут спать вместе Обычно событие, которого ждет процесс в тупиковой ситуации - освобождение ресурса

8 Основы операционных систем Лекция Введение (7) В лекции будут обсуждаться вопросы, обнаружения, предотвращения, обхода тупиков и восстановления после тупиков Рассматривается также тесно связанная проблема бесконечного откладывания, которое может происходить из-за дискриминационной политики планировщика ресурсов Во многих случаях цена борьбы с тупиками, которую приходится платить, высока Тем не менее, для ряда систем, например, для систем реального времени, нет иного выхода

9 Основы операционных систем Лекция Концепция ресурса(1) Концепция ресурса (1) Уже говорилось, что одна из основных функций ОС состоит в распределении ресурсов между процессами Ресурсами могут являться как устройства, так и данные Некоторые виды ресурсов могут использоваться процессами совместно, то есть быть разделяемыми устройствами (например, память, процессор, диски) Другие ресурсы являются выделенными, например, лентопротяжное устройство Чаще всего тупики возникают, когда процессу дается монопольный доступ к устройствам, файлам и другим ресурсам

10 Основы операционных систем Лекция Концепция ресурса(2) Концепция ресурса (2) Последовательность событий, требуемых для использования ресурса такова: (1) запросить (request) ресурс, (2) использовать (use) ресурс, (3) освободить (release) ресурс Если ресурса нет в наличии, когда он требуется, то процесс вынужден ждать В некоторых ОС процесс автоматически блокируется, когда получает отказ на запрос к ресурсу и просыпается, когда ресурс оказывается в наличии В других ОС отказ сопровождается возвратом ошибки, и вызывающий процесс должен закончиться или подождать немного и попытаться осуществить запрос вновь

11 Основы операционных систем Лекция Концепция ресурса(3) Концепция ресурса (3) Мы будем предполагать, что когда запрос отклонен, процесс переходит в состояние ожидания. Природа запроса сильно зависит от ОС В некоторых ОС имеется системный вызов request для прямого запроса на ресурс В других ОС единственными ресурсами, о которых знает ОС, являются специальные файлы, которые каждый раз имеет право открывать только один процесс Это делается обычным вызовом open Если файл уже используется, вызывающий процесс блокируется, пока ресурс не освободится

12 Основы операционных систем Лекция Условия возникновения тупиков (1) В 1971 г. Коффман, Элфик и Шошани (Coffman E. G., Jr., Elphick M., Shoshani A.) сформулировали следующие четыре условия для возникновения тупиков 1. Условие взаимного исключения (Mutual exclusion) Каждый ресурс выделен в точности одному процессу или доступен Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются

13 Основы операционных систем Лекция Условия возникновения тупиков (2) 2. Условие ожидания ресурсов (Hold and wait) Процессы удерживают выделенные им ресурсы, ожидая выделения дополнительных ресурсов (обычно удерживаемых другими процессами) 3. Условие неперераспределяемости (No preemtion) Ресурс не может быть принудительно забран у процесса Ресурс может быть освобожден только процессом, который его удерживает

14 Основы операционных систем Лекция Условия возникновения тупиков (3) 4. Условие кругового ожидания (Circular wait) Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи Для тупика необходимо выполнение всех четырех условий Тупик моделируется прямым графом, состоящим из узлов двух видов: прямоугольников процессов и эллипсов ресурсов Стрелки, направленные от ресурса к процессу, показывают, что ресурс выделен данному процессу

15 Основы операционных систем Лекция Основные направления борьбы с тупиками В связи с проблемой тупиков были выполнено много интересных исследований в области информатики и операционных систем. Основные направления борьбы с тупиками: 1. Игнорировать данную проблему 2. Обнаружение тупиков 3. Восстановление после тупиков 4. Предотвращение тупиков за счет тщательного выделения ресурсов или нарушения одного из условий возникновения тупиков

16 Основы операционных систем Лекция Алгоритм страуса(1) Алгоритм страуса (1) Простейший подход - игнорировать проблему тупиков Разные люди реагируют на тупики по-разному Математики считают, что тупики должны быть предотвращены любой ценой Инженеры задают вопрос: как часто возникает данная проблема и как часто система виснет по другим причинам? Если тупик встречается раз в пять лет, но аварийный останов системы по другим причинам - раз в месяц, инженер не захочет жертвовать производительностью или удобством, чтобы ликвидировать тупик

17 Основы операционных систем Лекция Алгоритм страуса(2) Алгоритм страуса (2) Например, в ядре ОС Unix имеется ряд массивов фиксированной размерности ОС потенциально страдает от тупиков, даже если они не обнаружены Например, суммарное число процессов в системе определяется размерностью таблицы процессов fork Если таблица заполнена, то для программы, которая делает вызов fork, резонно подождать некоторое время и попытаться осуществить этот вызов вновь fork Следует ли отказываться от вызова fork, чтобы решить эту проблему?

18 Основы операционных систем Лекция Алгоритм страуса(3) Алгоритм страуса (3) Максимальное число открытых файлов ограничено размером таблицы дескрипторов; с ними может произойти аналогичная ситуация Пространство выгрузки на диске - другой ограниченный ресурс Фактически, любая таблица в ОС - конечный ресурс. Подход Unix состоит в том, чтобы игнорировать данную проблему: пользователи предпочтут случайный тупик нелепым правилам, заставляющим их иметь один процесс, один открытый файл и т.п. Сталкиваемся с нежелательным выбором между строгостью и удобством

19 Основы операционных систем Лекция Обнаружение тупиков (1) Обнаружение тупика - это установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в эту ситуацию Как правило, алгоритмы обнаружения применяются, когда выполнены первые три необходимых условия возникновения тупиковой ситуации Затем проверяется наличие режима кругового ожидания При этом активно используются графы распределения ресурсов

20 Основы операционных систем Лекция Обнаружение тупиков (2) Рассмотрим модельную ситуацию: ARS Процесс A удерживает ресурс R и ожидает ресурс S BT Процесс B претендует на ресурс T CS Процесс C претендует на ресурс S DUS T Процесс D удерживает ресурс U и ожидает ресурсы S и T ET V Процесс E удерживает ресурс T и ожидает ресурс V FWS Процесс F удерживает ресурс W и ожидает ресурс S GVU Процесс G удерживает ресурс V и ожидает ресурс U Является ли данная ситуация тупиковой, и если да, то какие процессы в ней участвуют?

21 Основы операционных систем Лекция Обнаружение тупиков (3) Для ответа на этот вопрос можно сконструировать граф ресурсов Видно, что имеется цикл, моделирующий условие кругового ожидания, и процессы D,E,G в тупиковой ситуации Наличие тупика легко обнаружить визуально, но нужны также формальные алгоритмы, реализуемые на компьютере

22 Основы операционных систем Лекция Восстановление после тупиков (1) Предположим, что алгоритм обнаружения справился со своей задачей и обнаружил тупик Что делать дальше? Один из путей - восстановиться и заставить систему работать дальше Обсудим различные способы восстановления после тупиков Систему, оказавшуюся в тупике, можно вывести из него, нарушив одно из условий его существования При этом, возможно, несколько процессов частично или полностью потеряют результаты проделанной работы

23 Основы операционных систем Лекция Восстановление после тупиков (2) Сложность восстановления обусловлена рядом факторов: в большинстве систем нет достаточно эффективных средств для приостановки процесса, вывода его из системы и последующего возобновления если даже такие средства есть, то их использование требует затрат и внимания оператора для восстановления после серьезного тупика может потребоваться много работы

24 Основы операционных систем Лекция Восстановление после тупиков (3) Восстановление при помощи перераспределения ресурсов Один из способов восстановления - принудительный вывод некоторого процесса из системы для последующего использования его ресурсов Для определения того, какой процесс выводить из системы, зачастую требуются усилия оператора В некоторых случаях может оказаться возможным временно забрать ресурс у его текущего владельца и передать его другому процессу

25 Основы операционных систем Лекция Восстановление после тупиков (4) Восстановление при помощи перераспределения ресурсов Например, чтобы отобрать принтер у процесса, производящего на него вывод, оператор может собрать напечатанные бумаги и сложить в стопку Затем процесс может быть приостановлен и принтер передан другому процессу После его завершения бумага может быть возвращена в принтер, и первый процесс возобновится Возможность забрать ресурс у процесса, дать его другому процессу и затем вернуть его назад без нанесения ущерба сильно зависит от природы ресурса Подобное восстановление часто затруднительно, если не невозможно

26 Основы операционных систем Лекция Восстановление после тупиков (5) Восстановление через откат В ряде систем реализованы средства рестарта с контрольной точки (сохраненного состояния системы в некоторый момент времени) Там, где эти средства не предусмотрены, их должны организовать разработчики прикладных программ Если проектировщики системы знают, что тупик вероятен, они могут периодически организовывать для процессов контрольные точки

27 Основы операционных систем Лекция Восстановление после тупиков (7) Восстановление через откат Когда тупик обнаружен, видно, какие ресурсы вовлечены в цикл кругового ожидания Чтобы произвести восстановление, процесс, который владеет таким ресурсам, должен быть откачен к моменту времени, предшествующему его запросу на этот ресурс По всей видимости, это самый эффективный способ приостановки и возобновления

28 Основы операционных систем Лекция Восстановление после тупиков (8) Восстановление через ликвидацию одного из процессов Грубый, но простейший способ устранить тупик состоит в том, чтобы насильственно ликвидировать один или несколько процессов Например, можно убить процесс, который находится в цикле графа Тогда при удаче остальные процессы смогут выполняться Если это не помогает, то можно ликвидировать еще один процесс

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

30 Основы операционных систем Лекция Способы предотвращения тупиков путем тщательного распределения ресурсов (1) Целью предотвращения тупиков является обеспечение условий, исключающих возможность возникновения тупиковых ситуаций. Предоставляя ресурс в распоряжение процесса, система должна принять решение, безопасно это или нет Возникает вопрос: есть ли такой алгоритм, который помогает всегда избегать тупиков и делать правильный выбор?

31 Основы операционных систем Лекция Способы предотвращения тупиков путем тщательного распределения ресурсов (2) Ответ - да, мы можем избегать тупиков, но только, если определенная информация известна заранее Рассмотрим пути предотвращения тупиков за счет тщательного распределения ресурсов Один из алгоритмов предотвращения тупиков базируется на концепции безопасных состояний

32 Основы операционных систем Лекция Способы предотвращения тупиков путем тщательного распределения ресурсов (3) Предотвращение тупиков и алгоритм банкира Можно избежать тупиковой ситуации, если рациональным образом использовать ресурсы, придерживаясь определенных правил Среди алгоритмов такого рода наиболее известен алгоритм банкира, предложенный Дейкстрой Он имитирует действия банкира, который, располагая некоторым источником капитала, принимает ссуды и выдает платежи n Предположим, что у системы в наличии n устройств, например лент

33 Основы операционных систем Лекция Способы предотвращения тупиков путем тщательного распределения ресурсов (4) Предотвращение тупиков и алгоритм банкира Суть алгоритма состоит в следующем: n ОС принимает запрос от процесса, если его максимальная потребность не превышает n Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени Выделение устройств возможно, только если состояние системы остается надежным

34 Основы операционных систем Лекция Текущее количество Максимальная потребность Первый пользователь 14 Второй пользователь 46 Третий пользователь 58 Способы предотвращения тупиков путем тщательного распределения ресурсов (5) Предотвращение тупиков и алгоритм банкира Рассмотрим пример надежного состояния для системы с тремя пользователями и 12-ю устройствами, где 10 устройств задействовано, а 2 имеется в наличии; пусть текущая ситуация такова: Это состояние надежно Последующие действия системы могут быть таковы Вначале удовлетворить запросы второго пользователя и дождаться, когда он выполнит свою работу и освободит свои 6 устройств Затем можно обслужить остальных пользователей Система удовлетворяет только те запросы, которые оставляют ее в надежном состоянии и отклоняет остальные Термин ненадежное состояние означает, что при некоторой последовательности событий система может зайти в тупик

35 Основы операционных систем Лекция Способы предотвращения тупиков путем тщательного распределения ресурсов (6) Недостатки алгоритма банкира У алгоритма банкира имеются серьезные недостатки, из-за которых может потребоваться другой подход для решения проблемы тупиков: Алгоритм исходит из фиксированного количества ресурсов Требуется, чтобы число работающих пользователей оставалось постоянным Требуется, чтобы распределитель гарантированно удовлетворял запросы за конечный период времени; для реальных систем нужны более конкретные гарантии

36 Основы операционных систем Лекция Способы предотвращения тупиков путем тщательного распределения ресурсов (7) Недостатки алгоритма банкира Требуется, чтобы клиенты гарантированно возвращали ресурсы; в реальных системах требуются гораздо более конкретные гарантии Требуется, чтобы пользователи заранее указали свои максимальные потребности в ресурсах; при динамическом распределении ресурсов трудно оценить максимальные потребности пользователей Рассмотрим другие способы предотвращения тупиков

37 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(1) Предотвращение тупиков за счет нарушения условий их возникновения (1) Как же может реальная система избежать тупиков, если отсутствует информация о будущих запросах? Для ответа на этот вопрос вернемся к четырем условиям возникновения тупиков Если удастся организовать работу системы так, что, по крайней мере, одно из этих условий не удовлетворялось, то тупик невозможен

38 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(1) Нарушение условия взаимного исключения Предотвращение тупиков за счет нарушения условий их возникновения (1) Нарушение условия взаимного исключения Если в системе отсутствуют выделенные ресурсы, то тупиков не будет Но разрешение двум процессам писать на один принтер в одно и то же время приведет к хаосу За счет организации спулинга одновременная печать для нескольких процессов становится возможной Единственным процессом, реально взаимодействующим с принтером, является демон принтера Это устраняет тупик для принтера

39 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(2) Нарушение условия взаимного исключения Предотвращение тупиков за счет нарушения условий их возникновения (2) Нарушение условия взаимного исключения К сожалению, не для всех устройств может быть организован спулинг (например, трудно представить таблицы процессов) Неприятным побочным следствием является потенциальная тупиковая ситуация из-за конкуренции за дисковое пространство для буфера спулинга Тем не менее, в той или иной форме эта идея применяется часто

40 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(3) Hарушение условия ожидания дополнительных ресурсов Предотвращение тупиков за счет нарушения условий их возникновения (3) Hарушение условия ожидания дополнительных ресурсов Хавендер (Havender) в 1968 г. предложил следующую стратегию: Каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполняться до тех пор, пока все они не будут ему предоставлены Если же процесс удерживает некоторые ресурсы и получает отказ в выделении дополнительных ресурсов, то он должен освободить свои первоначальные ресурсы и, при необходимости, запросить их снова вместе с дополнительными

41 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(4) Hарушение условия ожидания дополнительных ресурсов Предотвращение тупиков за счет нарушения условий их возникновения (4) Hарушение условия ожидания дополнительных ресурсов Таким образом, один из способов состоит в том, чтобы заставить все процессы запрашивать все требуемые ресурсы перед выполнением (все или ничего) Если система в состоянии выделить процессу все необходимое, он может работать до завершения Если хотя бы один из ресурсов занят, процесс будет ждать Подход не слишком привлекателен и приводит к снижению эффективности работы компьютера

42 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(5) Hарушение условия ожидания дополнительных ресурсов Предотвращение тупиков за счет нарушения условий их возникновения (5) Hарушение условия ожидания дополнительных ресурсов Редко бывает, чтобы все запрашиваемые устройства были необходимы программе одновременно Конечно, можно разделить программу на несколько шагов и выделять ресурсы отдельно для каждого шага программы, но основная проблема состоит в том, что многие процессы до начала работы не знают, сколько ресурсов им понадобится Если такая информация есть, то можно воспользоваться алгоритмом банкира Тем не менее, в некоторых пакетных ОС от пользователей требуется перечисление всех ресурсов, требуемых их программам

43 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(6) Нарушение принципа неперераспределяемости Предотвращение тупиков за счет нарушения условий их возникновения (6) Нарушение принципа неперераспределяемости В соответствии со вторым принципом Хавендера можно отбирать ресурсы у удерживающих их процессов до завершения этих процессов Если бы это было всегда возможно, то можно было бы добиться невыполнения третьего условия возникновения тупиков С проблемой отнятия ресурсов у удерживающих их процессов мы сталкивались в связи с восстановлением после разрушения тупика

44 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(7) Нарушение принципа неперераспределяемости Предотвращение тупиков за счет нарушения условий их возникновения (7) Нарушение принципа неперераспределяемости Если процесс в течение некоторого времени использует некоторые ресурсы, а затем насильственно освобождает эти ресурсы, то он теряет всю работу, проделанную до настоящего момента Весь вопрос в цене данного решения, которая может быть слишком высокой, если подобная ситуация возникает часто Другим недостатком данной схемы может быть дискриминация отдельных процессов, у которых постоянно отбирают ресурсы

45 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(8) Нарушение условия кругового ожидания Предотвращение тупиков за счет нарушения условий их возникновения (8) Нарушение условия кругового ожидания Циклического ожидания можно избежать несколькими способами Один из них - действовать в соответствии с правилом, согласно которому каждый процесс может иметь только один ресурс в каждый момент времени Если нужен второй ресурс - освободи первый Очевидно, что для многих процессов это неприемлемо, например, для тех, которые распечатывают большие файлы с ленты на принтер

46 Основы операционных систем Лекция Предотвращение тупиков за счет нарушения условий их возникновения(9) Нарушение условия кругового ожидания Предотвращение тупиков за счет нарушения условий их возникновения (9) Нарушение условия кругового ожидания Другой способ - присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке возрастания номеров Тогда круговое ожидание возникнуть не может Небольшой вариацией этого алгоритма является нумерация в возрастающем порядке не ресурсов, а запросов процесса После последнего запроса и освобождения всех ресурсов можно разрешить процессу опять выполнить первый запрос Но очевидно, что невозможно найти порядок, который удовлетворит всех

47 Основы операционных систем Лекция Родственные проблемы (1) Тупики не ресурсного типа До сих пор все наше внимание было сконцентрировано на ресурсных тупиках Есть и другие тупиковые ситуации, например, когда один из процессов ждет чего-то от другого Это часто случается при некорректном использовании семафоров, когда один из процессов забывает открыть семафор для другого процесса

48 Основы операционных систем Лекция Родственные проблемы (2) Голод (starvation) Близкая к тупикам проблема – голод В динамических системах постоянно происходят запросы процессов к ресурсам Естественно, что должна быть реализована некоторая политика для принятия решения относительно того, кто получит ресурсы и когда Эта политика может быть дискриминационной по отношению к некоторым процессам, хотя формально они и не в тупике

49 Основы операционных систем Лекция Родственные проблемы (3) Голод (starvation) Например, несколько процессов конкурируют за принтер, и система выделяет его по принципу «первым печатать файл наименьшего размера» Этот подход увеличивает число счастливых пользователей принтера и кажется удовлетворительным Однако пользователь с большим файлом оказывается в состоянии бесконечного ожидания В данном случае голода можно избежать путем применения иной политики, например, FCFS (первый пришедший обслуживается первым)

50 Основы операционных систем Лекция Заключение (1) Возникновение тупиков является потенциальной проблемой любой операционной системы Тупики возникают, когда имеется группа процессов, каждый из которых пытается иметь монопольный доступ к некоторым ресурсам и претендует на ресурсы, принадлежащие другому процессу В итоге все эти процессы могут оказаться в состоянии бесконечного ожидания

51 Основы операционных систем Лекция Заключение (2) С тупиками можно бороться, можно их обнаруживать, избегать и восстанавливать систему после тупиков Однако цена подобных действий высока, и соответствующие усилия должны предприниматься только в тех системах, в которых игнорирование тупиковых ситуаций приводит к катастрофическим последствиям

52 Основы операционных систем Лекция Заключение (3) В будущих системах тупики станут более критичным фактором, поскольку Системы будущего будут в большей степени ориентированы на параллельную работу Будет преимущественно реализовываться динамическое распределение ресурсов Растет тенденция рассматривать данные как ресурс, в связи с чем количество ресурсов возрастет