Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 70
Текст из файла (страница 70)
Кроме того, можно сохранять для каждого ресурса запросы, упорядоченные по размеру (числу единиц ресурса). Тогда следующий алгоритм сокращений, записанный на псевдокоде, имеет максимальное время выполнения, нропорциональное m x п.зТ0п ы б о р ^ б ы £ т у п и камиail Pe L do£ и пirl for a l l R,3 |CR,.P>| > 0 d oBe9•= г + |(R,.P)|Begin rFor a l l P, э 0 < | CP,.RP I <= ^ doBegin wt := w, - 1:If w, = 0 then L := L U {Pi}EndEndj g d l o c k :=N0t ( L - {PL P2Pn}):L — это текущий список процессов, которые могут выполнять редукцию граМожпо сказать, что L = {Р( | w,- = 0}.
Программа выбирает процесс Р из списка L,цесс Р сокращает граф, увеличивая число доступных единиц ij всех ресурсов Rj?определенных процессу Р, обновляет счетчик ожидания w( каждого процесса Pf,который сможет удовлетворить свой запрос на частный ресурс Щ, и добавляет Р-, к L,если счетчик ожидания становится нулевым.Методы обнаружения тупика по наличиюзамкнутой цепочки запросовСтруктура графа обеспечивает простое необходимое (но не достаточное) условиедля тупика.
Для любого графа G = <Х, Е> и вершины х I X пусть Р(х) обозначаетмножество вершин, достижимых из вершины х, то естьР(х) = { у | (х, у) I Е } U { z | (у, z) I Е & у I Р(х) }.Можно сказать, что в ориентированном графе потомством вершины х, обозначенным как Р(х), называется множество всех вершин, в которые ведут пути из х.Тогда если существует некоторая вершина х I X: х I Р(х), то в графе G имеетсяцикл.Первая теорема: цикл в графе повторно используемых ресурсов является необходимым условием тупика.Для доказательства этой теоремы (которое мы опустим 1 ) можно воспользоватьсяследующим свойством ориентированных графов: если ориентированный граф несодержит цикла, то существует линейное упорядочение вершин такое, что еслисуществует путь от вершины i к вершине], то i появляется перед] в этом упорядочении.торая теорема: если S не является состоянием тупика и S —2—> ST, где ST естьостояние тупика, в том и только в том случае, когда операция процесса Р: естьзапрос и Р; находится в тупике в S,,следует понимать таким образом, что тупик может быть вызван только приР°се, который не удовлетворен немедленно.
Учитывая эту теорему, можно сде, В Ь 1 в од, что проверка на тупиковое состояние может быть выполнена болееективно, если она проводится непрерывно, то есть по мере развития процесогДа надо применять редукцию графа только после запроса от некоторогоР" Ж е л а н и и его можно найти в [54].272Глава 8, Проблема тупиков и методы борьбы с нимипроцесса Р| и на любой стадии необходимо сначала попытаться сократить граф спомощью процесса Р ( . Если процесс Р; смог провести сокращение графа, то никакие дальнейшие сокращения не являются необходимыми.Ограничения, накладываемые на распределители, на число ресурсов, запрошенных одновременно, и на количество единиц ресурсов, приводят к более простымусловиям для тупика.Пучок, или узел, в ориентированном графе G = <Х, Е> — это подмножество вершин Z I X, таких что V х I Z, Р(х) = Z, то есть потомством каждой вершины из Zявляется само множество Z.
Каждая вершина в узле достижима из каждой другойвершины этого узла, и узел есть максимальное подмножество с этим свойством.Поясним сказанное рис. 8.10.Рис. 8.10. Пример узла в модели ХолтаСледует заметить, что наличие цикла — это необходимое, но не достаточноеусловие для узла. Так, на рис. 8.11 изображены два подграфа. Подграф а представляет собой пучок (узел), тогда как подграф б представляет собой цикл, ноузлом не является. В узел должны входить дуги, но они не должны из него выходить.Если состояние системы таково, что удовлетворены все запросы, которые могут быть удовлетворены, то существует простое достаточное условие существования тупика.
Эта ситуация возникает, если распределители ресурсов не откладывают запросы, которые могут быть удовлетворены, а выполняют их повозможности немедленно (большинство распределителей следуют именно этойдисциплине).Состояние называется фиксированньш, если каждый процесс, выдавший запрос,заблокирован.Третья теорема: если состояние системы фиксированное (все процессы, имеющие запросы, удовлетворены), то наличие узла в соответствующем графе повторно используемых ресурсов является достаточным условием тупика.Методы борьбы с тупикамиy3enZ = {Z 1 ,Z 2 ,Z 3 ,Z 4 }Цикл Z = {Zb Z 2 , Z 3 , Z 4 }, но не узелРис.
8 . 1 1 . Узел и цикл в ориентированном графеZYIS274Глава 8. Проблема тупиков и методы борьбы с нимиДля доказательства предположим, что граф содержит узел Z. Тогда все процессы вэтом узле должны быть заблокированы только по ресурсам, принадлежащим Zтак как никакие ребра не могут выходить из Z по определению. Аналогично, по тойже самой причине все распределенные ресурсы узла Z принадлежат процессам из Z.Наконец, все процессы в Z должны быть заблокированы согласно условию фиксированное™ и определению узла.
Следовательно, все процессы в узле Z должныбыть в тупике.Допустим, что каждый ресурс имеет единичную емкость (по одной единице ресурса), то есть IRJ = 1, (i = l, 2, ..., m). При этом ограничении наличие цикла такжестановится достаточным условием тупика.Четвертая теорема: граф повторно используемых ресурсов с единичной емкостью указывает на состояние тупика тогда и только тогда, когда он содержит цикл.Необходимость цикла доказывает первая теорема. Для доказательства достаточности допустим, что граф содержит цикл, и рассмотрим только лишь процессы иресурсы, принадлежащие циклу.
Так как каждая вершина-процесс должна иметьвходящее и исходящее ребра, она должна выдать запрос на некоторый ресурс, принадлежащий циклу, и должна удерживать некоторый ресурс, принадлежащий томуже циклу. Аналогично, каждый ресурс единичной емкости в цикле должен бытьзахвачен некоторым процессом. Следовательно, каждый процесс в цикле блокируется на ресурсе, который может быть освобожден только некоторым процессомиз этого цикла; поэтому процессы в цикле находятся в тупике.Чтобы обнаружить тупик в случае ресурса единичной емкости, мы должны простопроверить граф повторно используемых ресурсов на наличие циклов.Алгоритм обнаружения тупика по наличиюзамкнутой цепочки запросовИтак, распознавание тупика может быть основано на анализе модели распределения ресурсов. Один из алгоритмов, основанный на методе обнаружения замкнутой цепи запросов, был разработан сотрудниками фирмы IBM и применялся в одной из ОС этой компании.
Он использует информацию о состоянии системы,содержащуюся в двух таблицах: таблице текущего распределения (назначения)ресурсов RATBL и таблице заблокированных процессов PWTBL (для каждого видаресурса может быть свой список заблокированных процессов). При каждом запросе на получение или освобождение ресурсов содержимое этих таблиц модифицируется, а запрос анализируется в соответствии со следующим алгоритмом [22].1. Начало алгоритма. Приходит запрос от процесса с номером J на занятый ресурсс номером I.2.
Поместить номер ресурса I в таблицу PWTBL в строке с номером процесса J.3. Использовать I в качестве смещения в таблице RATBL, чтобы найти номер процесса К, который владеет ресурсом.4. Использовать К в качестве смещения в таблице PWTBL.5. Проверить, ждет ли процесс с номером К освобождения какого-либо ресурса сномером Г. Если нет, то перейти к шагу 6, в противном случае — к шагу 7.67Перевести процесс с номером J в состояние ожидания и выйти из алгоритма.Использовать Г в качестве смещения в таблице RATBL, чтобы найти помер К'блокирующего его процесса.8 Проверить, что К' = J.
Если нет, перейти к шагу 9, в противном случае — к ша-' гу П .9. Проверить, вся ли таблица PWTBL просмотрена. Если да, то перейти к шагу6, в противном случае — к шагу 10.10. Присвоить К := К' и перейти к шагу 4.П. Сделать вывод о наличии тупика с последующим восстановлением.12. Конец алгоритма.Для иллюстрации описанного алгоритма распознавания тупика рассмотрим следующую последовательность событий.1. Процесс Р1 занимает ресурс R1.2.
Процесс Р2 занимает ресурс R3.3. Процесс РЗ занимает ресурс R2.4. Процесс Р2 занимает ресурс R4.5. Процесс Р1 занимает ресурс R5.В результате таблица распределения ресурсов (RATBL) принимает такой вид,как показано в табл. 8.3.Таблица 8 . 3 . Таблица распределения ресурсовРесурсыПроцессыR1Р1R2РЗR3Р2R4Р2R5PJ6. Пусть процесс Р1 пытается занять ресурс R3, поэтому в соответствии с описанным алгоритмом J = 1,1 = 3, К = 2.
Процесс К не ждет никакого ресурса, поэтому процесс Р1 блокируется по ресурсу R3.7. Далее, пусть процесс Р2 пытается занять ресурс R2: J = 3,1 = 2, К = 3. Процессс номером К=3 не ждет никакого ресурса, поэтому процесс Р2 блокируется поресурсу R2.о- И наконец, пусть процесс РЗ пытается обратиться к ресурсу R5: J = 3, I = 5,К = 1, Г = 3, К' - 2, К' <> J, поэтомуберем К = 2, Г = 2, К" = 3.& этом случае К' = J, то есть тупик определен.
Таблица заблокированных процессов (PWTBL) теперь будет выглядеть так, как показано в табл. 8.4.Равенство J = К' означает, что существует замкнутая цепь взаимоисключающихи 05кидающих процессов, то есть выполняются все четыре условия существованиятУпика.276Глава 8. Проблема тупиков и методы борьбы с нимиТаблица 8.4. Таблица заблокированных ресурсовПроцессР1Р2РЗРесурсR3R2R5)Для описанного нами примера можно построить модель Холта, как показано нарис. 8.12.
Здесь пронумерованы дуги запросов, которые процессы последовательно генерировали в соответствии с нашим примером. Из рисунка сразу видно, чтов результате такой последовательности запросов образовалась замкнутая цепочка: (8, 5, 6, 2, 7, 3), что и говорит о существовании тупика.R5RiРис. 8.12.
Граф распределения ресурсовРаспознавание тупика требует дальнейшего восстановления вычислений.Восстановление можно интерпретировать как запрет постоянного пребыванияв опасном состоянии. Существуют следующие методы восстановления:а принудительный перезапуск системы, характеризующийся потерей информации обо всех процессах, существовавших до перезапуска;•принудительное завершение процессов, находящихся в тупике;Q принудительное последовательное завершение процессов, находящихся в тупике, с последующим вызовом алгоритма распознавания после каждого завершения до исчезновения тупика;• перезапуск процессов, находящихся в тупике, с некоторой контрольной точки,то есть из состояния, предшествовавшего запросу на ресурс;Q перераспределение ресурсов с последующим последовательным п е р е з а п у с кпроцессов, находящихся в тупике.Контрольные вопросы и задачи277Основные издержки восстановления составляют потери времени на повторныевычисления, которые могут оказаться весьма существенными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
