Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 65
Текст из файла (страница 65)
Одной из них является модель повторно использумых ресурсов Холта [54]. Согласно этой модели система представляется как на о(множество) процессов и набор ресурсов, причем каждый из ресурсов состоит249Ппимеры тупиковых ситуаций и причины их возникновенияфиксированного числа единиц. Любой процесс может изменять <, состояние системыпутем выдачи запроса на получение или освобождение единицы ресурса.В графической форме процессы и ресурсы представляются квадратами и кружками соответственно. Каждый кружок содержит некоторое количество маркеров(фишек) в соответствии с существующим количеством единиц этого ресурса.
Дуга,указывающая из «процесса» на «ресурс», означает запрос одной единицы этогоресурса. Дуга, указывающая из «ресурса» на «процесс», представляет выделениересурса процессу. Поскольку каждая единица любого ресурса типа SR может бытьвыделена одновременно не более чем одному процессу, то число дуг, исходящихиз ресурса к различным процессам, не может превышать общего числа единиц этого ресурса. Такая модель называется графом повторно используемых ресурсов.Пример одного из состояний системы из двух процессов с ресурсами типа SR представлен на рис.
8.1.Пр2Пр1R2Рис. 8.1. Пример модели ХолтаПусть процесс Пр1 запрашивает две единицы ресурса R1 и одну единицу ресурсаR2. Процессу Пр2 принадлежат две единицы ресурса R1, и ему нужна одна единица R2. Предположим, что процесс Пр1 получил запрошенную им единицу R2. Еслипринято правило, по которому процесс должен получить все запрошенные им ресурсы прежде, чем освободить хотя бы один из них, то удовлетворение запросаПр1 приведет к тупиковой ситуации: Пр1 не сможет продолжиться до тех пор, покаПр2 не освободит единицу ресурса R1, а процесс Пр2 не сможет продолжиться дотех пор, пока Пр1 не освободит единицу R2. Причиной этого тупика являются неупорядоченные попытки процессов войти в критическую секцию, связанную с выделением соответствующей единицы ресурса.Примеры тупиковых ситуацийпричины их возникновенияияпонимания основных причин возникновения тупиков рассмотрим несколькоР°стых характерных примеров.250Глава 8.
Проблема тупиков и метЬды б о р ь б ы с нимиПример тупика на ресурсах типа CRПусть имеется три процесса Пр1, Пр2 и ПрЗ, которые вырабатывают сообщенияMl, M2 и МЗ соответственно. Эти сообщения представляют собой ресурсы типаCR. Пусть процесс Пр1 является потребителем сообщения МЗ, процесс Пр2 должен получить сообщение Ml, а ПрЗ ожидает сообщение М2 от процесса Пр2. Таким образом, каждый из этих трех процессов является и поставщиком, и потребителем одновременно, и вместе они образуют кольцевую систему (рис. 8.2) передачисообщений через почтовые ящики (ПЯ).Рис.
8.2. Кольцевая схема взаимодействия процессовЕсли связь с помощью этих сообщений со стороны каждого процесса устанавливается в порядке, представленном в листинге 8.1, то никаких проблем не возникает.Однако перестановка этих двух процедур в каждом из процессов вызывает тупик(листинг 8.2).Листинг 8 . 1 . Вариант псевдокода без тупиковой ситуацииПр1:ПОСЛАТЬ СООБЩЕНИЕ (Пр2.
Ml. ПЯ2):ЖДАТЬ СООБЩЕНИЕ (ПрЗ. МЗ. ПЯ1);Пр2:ПОСЛАТЬ СООБЩЕНИЕ (ПрЗ. М2. ПЯЗ):ЖДАТЬ СООБЩЕНИЕ (Пр1. Ml, ПЯ2);ПрЗ:ПОСЛАТЬ СООБЩЕНИЕ (Пр1. МЗ. ПЯ1):ЖДАТЬ СООБЩЕНИЕ (Пр2. М2. ПЯЗ):251Примеры тупиковых ситуаций и причины их возникновенияЛистинг 8.2. Вариант псевдокода с тупиковой ситуациейПр1:ЖДАТЬ СООБЩЕНИЕ (ПрЗ. МЗ. ПЯ1):ПОСЛАТЬ СООБЩЕНИЕ (Пр2, Ml. ПЯ2);Пр2:ЖДАТЬ СООБЩЕНИЕ (Пр1, Ml. ПЯ2);ПОСЛАТЬ СООБЩЕНИЕ (ПрЗ. М2. ПЯЗ);ПрЗ:ЖДАТЬ СООБЩЕНИЕ (Пр2. М2. ПЯЗ);ПОСЛАТЬ СООБЩЕНИЕ (Пр1. МЗ. ПЯ1):В самом деле, во втором варианте ни один из процессов не сможет послать сообщение до тех пор, пока сам его не получит, а это событие никогда не произойдет, поскольку ни один процесс не может этого сделать.Пример тупика на ресурсах типа CR и SRПусть некоторый процесс Пр1 должен обменяться сообщениями с процессом Пр2и каждый из них запрашивает некоторый ресурс R, причем Пр1 требует три единицы этого ресурса для своей работы, а Пр2 — две единицы и только на время обработки сообщения.
Всего же имеется только четыре единицы ресурса R. Запроси освобождение ресурса можно реализовать через соответствующий монитор с процедурами REQUESTER, N) — запрос N единиц ресурса R, и RELEASE(R, N) —освобождение (возврат) N единиц ресурса R. Обмен сообщениями будем осуществлять черезпочтовый ящик MB. Фрагменты программ Пр1 и Пр2 приведены в листинге 8.3.Листинг 8.3. Пример тупика на ресурсах CR и SRПр1:REQUEST ( R, 3 ):SEND_MESSAGE ( Пр2. сообщение, MB ):WAIT_ANSWER ( ответ.
MB );RELEASE ( R. 3 );WAIT_MESSAGE ( Пр1, сообщение. MB );REQUEST ( R. 2 ):ОБРАБОТКА СООБЩЕНИЯ:RELEASE ( R, 2 ):продолжениеti>Глава 8. Проблема тупиков и методы борьбы с нимы252Листинг 8.3 {продолжение)SEND_ANSWER-( ответ. MB ):Увы, эти два процесса всегда будут попадать в состояние тупика. Действительнопроцесс Пр2, выполняясь первым, сначала будет ожидать сообщения от процессаПр1, после чего будет заблокирован при запросе ресурса R, часть которого окажетсяуже отданной процессу Пр1. Процесс Пр1, завладев частью ресурса R, будет заблокирован ожиданием ответа от Пр2, которого никогда не получит, так как для этогоПр2 нужно получить ресурс R, находящийся в распоряжении Пр1. Тупика можноизбежать лишь при условии, что на время ожидания ответа от Пр2 процесс Пр1 отдаст хотя бы одну из единиц ресурса R, которыми он владеет. В данном примере, каки в предыдущем, причиной тупика являются ошибки программирования.Пример тупика на ресурсах типа SRПредположим, что существуют два процесса Пр1 и Пр2, разделяющих два ресурсатипа SR: R1 и R2.
Пусть взаимное исключение доступов к этим ресурсам реализуется с помощью семафоров S1 и S2 соответственно. Процессы Пр1 и Пр2 обращаютсяк ресурсам так, как показано на рис. 8.3 [17].Процесс Пр 1Процесс Пр 21:PCS2):(5):PCS1);2:PCS1):(6):P(S2);3:VCS1);(7):V(S1);4:V(S2);(8):V(S2):Рис. 8.3. Пример последовательности операторов для двух процессов,которые могут привести к тупиковой ситуацииЗдесь несущественные детали (с точки зрения обращения к ресурсам) опущены.Считаем, что оба семафора первоначально установлены в единицу.
Пространствовозможных состояний приведено на рис. 8.4.Горизонтальная ось задает выполнение процесса Пр1, вертикальная — процессПр2. Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам1-4 процесса Пр1; аналогично горизонтальные линии, пронумерованные от 5 до •соответствуют операторам 5-8 программы Пр2. Точка на плоскости онределясостояние вычислений в некоторый момент времени. Так, точка А соответствуситуации, при которой процесс Пр1 начал исполнение, но не достиг оператора ^а процесс Пр2 выполнил оператор 6, но не дошел до оператора 7. По мере выпо253рримеры тупиковых ситуаций и причины их возникновениянения точка будет двигаться горизонтально вправо, если исполняется процесс Пр1,и вертикально вверх, если исполняется процесс Пр2.Пр211!!ГГА1!7• АчYIСD^5!"1 "";!12тнгг-j!34— • Пр1Рис.
8.4. Пространство состояний системы двух параллельных конкурирующих процессовИнтервалы исполнения, во время которых ресурсы R1 и R2 используются каждым процессом, показаны с помощью фигурных скобок. Линии 1-8 делят пространство вычислений на 25 областей, каждая из которых соответствует определенномусостоянию в распределении ресурсов в процессе вычислений.
Закрашенные серым цветом состояния являются недостижимыми из-за взаимного исключенияпроцессов Пр1 и Пр2 при доступе к ресурсам R1 и R2.Рассмотрим последовательность исполнения 1-2-5-3-6-4-7-8, представленную траекторией Т1. Когда процесс Пр2 запрашивает ресурс R1 (оператор 5), ресурс недоступен (оператор выполнен, семафор закрыт).
Поэтому процесс Пр2 заблокирован в точке В. Как только процесс Пр1 достигнет оператора 3, процесс Пр2Деблокируется по ресурсу R1. Аналогично в точке С процесс Пр2 будет заблокирован при попытке доступа к ресурсу R2 (оператор 6). Как только процесс Пр1Достигнет оператора 4, процесс Пр2 деблокируется по ресурсу R2.Если же, например, выполняется последовательность 1-5-2-6, то процесс ПР1 заолокируется в точке X при выполнении оператора 2, а процесс Пр2 заблокируется вТочке Y при выполнении оператора 6. При этом процесс ПР1 ждет, когда процесс Пр2выполнит оператор 7, а Пр2 ждет, когда Пр1 выполнит оператор 4. Оба процесса буДУт находиться в тупике, ни Пр1, ни Пр2 не смогут закончить выполнение. При этомВсе ресурсы, которые получили оба процесса, становятся недоступными для других254Глава 8.
Проблема тупиков и методы борьбы с нимипроцессов, что резко снижает возможности вычислительной системы по их обслуживанию. Отметим одно очень важное обстоятельство: тупик будет неизбежным, есливычисления зашли в прямоугольник D, являющийся опасным состоянием.Исследования проблемы тупиков показали, что для возникновения тупиковойситуации необходимо одновременное выполнение следующих четырех условий [ 1754]:•условия взаимного исключения, при котором процессы осуществляют монопольный доступ к ресурсам;•условия ожидания, при котором процесс, запросивший ресурс, ждет до тех пор,пока запрос не будет удовлетворен, при этом удерживая ранее полученные ресурсы;•условия отсутствия перераспределения, при котором ресурсы нельзя отобратьу процесса, если они ему уже выделены;Q условия кругового ожидания, при котором существует замкнутая цепь процессов, каждый из которых ждет ресурс, удерживаемый его предшественником в цепи.Проанализировав содержательный смысл этих четырех условий, легко убедиться,что все они выполняются в точке Y (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
