Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

376
Теорема о тупике. Состояние S есть состояние тупика тогда и только тогда,
когда граф повторно используемых ресурсов в состоянии S не является полностью сокращаемым.
Доказательство.
а) Предположим, что состояние S есть состояние тупика и процесс P
i находит- ся в тупике в S. Тогда для всех S
j
, таких что S
→

•
S
j процесс Р
i заблокирован в S
j
(по определению). Так как сокращения графа идентичны для серии операций про- цессов, то конечное несокращаемое состояние в последовательности сокращений должно оставить процесс P
i блокированным. Следовательно, граф не является пол- ностью сокращаемым.
б) Предположим, что S не является полностью сокращаемым. Тогда существу- ет процесс P
i
, который остаётся заблокированным при всех возможных последова- тельностях операций редукции в соответствие с леммой. Так как любая последова- тельность операций редукции графа повторно используемых ресурсов, оканчи- вающаяся несокращаемым состоянием, гарантирует, что все ресурсы типа SR, ко- торые могут когда-либо стать доступными, в действительности освобождены, то процесс P
i навсегда заблокирован и, следовательно, находится в тупике.
Следствие 1. Процесс Р
i не находится в тупике тогда и только тогда, когда се- рия сокращений приводит к состоянию, в котором Р
i
, не заблокирован.
Следствие 2. Если S есть состояние тупика (по ресурсам типа SR), то по край- ней мере два процесса находятся в тупике в S.
Из теоремы о тупике непосредственно следует и алгоритм обнаружения тупи- ков. Нужно просто попытаться сократить граф по возможности эффективным спо- собом; если граф полностью не сокращается, то начальное состояние было состоя- нием тупика для тех процессов, вершины которых остались в несокращенном гра- фе. Рассмотренная нами лемма позволяет удобным образом упорядочивать сокра- щения.
Граф повторно используемых ресурсов может быть представлен или матрица- ми, или списками. В обоих случаях экономия памяти может быть достигнута ис- пользованием взвешенных ориентированных мультиграфов (слиянием определён-

377
ных дуг получения или дуг запроса между конкретным ресурсом и данным процес- сом в одну дугу с соответствующим весом, определяющим количество единиц ре- сурса).
Рассмотрим вариант с матричным представлением. Поскольку граф двудоль- ный, он представляется двумя матрицами размером n
×m. Одна матрица – матрица
распределения D = ||d ij
||, в которой элемент d ij отражает количество единиц R
j ре- сурса, распределенного процессу Р
i то есть d ij
= |(Rj, Р;)|, где (R
j
, P
i
) – это дуга меж- ду вершинами R
j и P
i
, ведущая из R
j в Р
i
. Вторая матрица – матрица запросов N =
||n ij
||, где n ij
= |(Р
i
, R
j
)|.
В случае использования связанных списков для отображения той же структу- ры можно построить две группы списков. Ресурсы, распределенные некоторому процессу P
i
, связаны с P
i указателями:
P
i
→(R
x
, d x
)
→ (R
y
, d y
)
→... →(R
z
, d z
), где R
j
– вершина, представляющая ресурс,
и d j
– вес дуги, то есть d j
= |(R
j
, P
i
)|.
Подобным образом и ресурсы, запрошенные процессом Р
i
, связаны вместе.
Аналогичные списки создаются и для ресурсов (списки распределенных и за- прошенных ресурсов).
R
i
→(P
u
, n u
)
→ (P
v
, n v
)
→... →(P
w
, n w
), где n j
= |(P
j
, R
j
)|.
Для обоих представлений удобно также иметь одномерный массив доступных единиц ресурсов (r
1
, r
2
, ..., r m
), где r i
указывает число доступных (нераспределённых единиц ресурса R
i
,
то есть r i
= |Ri| –
Σ|(R
i
, P
k
)|.
Простой метод прямого обнаружения тупика заключается в просмотре по по- рядку списка (или матрицы) запросов, причём, где возможно, производятся сокра- щения дуг графа до тех пор, пока нельзя будет сделать более ни одного сокраще- ния. При этом самая плохая ситуация возникает, когда процессы упорядочены в некоторой последовательности P
1
, Р
2
, ... , Р
n
, а единственно возможным порядком сокращений является обратная последовательность, то есть Р
n
, P
n-1
, ..., P
2
, Р
1
, а также в случае, когда процесс запрашивает все m ресурсов. Тогда число проверок процессов равно n + (n-1) + ... + 1
=
n
×(n+1)/2,

378
причём каждая проверка требует испытания m ресурсов. Таким образом, вре- мя выполнения такого алгоритма в наихудшем случае пропорционально m
×n
2
Более эффективный алгоритм может быть получен за счёт хранения некоторой дополнительной информации о запросах. Для каждой вершины процесса Р
i опреде- ляется так называемый счётчик ожиданий w i
, отображающий количество ресурсов
(не число единиц ресурса), которые в какое-то время вызывают блокировку про- цесса. Кроме этого, можно сохранять для каждого ресурса запросы, упорядоченные по размеру (числу единиц ресурса). Тогда следующий алгоритм сокращений, запи- санный на псевдокоде, имеет максимальное время выполнения, пропорциональное m
×n.
For all P
∈
∈
∈
∈ L do
Begin for all Rj
∋∋∋∋ |(R
j
, P)| > 0 do
Begin r j
:= r j
+ |(R
j
, P)|;
For all P
i
∋∋∋∋ 0 < |(P
i
, R
j
)| <= r j
do
Begin w i
:= w i
– 1;
If w i
= 0 then L := L
∪ {Pi}
End
End
End
Deadlock := Not (L = {P
1
, P
2
, ... , P
n
});
Здесь
L
– это текущий список процессов, которые могут выполнять редукцию графа. Можно сказать, что
L := {Р
i
w i
= 0}
. Программа выбирает процесс Р из списка
L, процесс Р сокращает граф, увеличивая число доступных единиц r j
всех ресурсов
R
j
, распределенных процессу Р, обновляет счётчик ожидания w i
каждого процесса
Р
i который сможет удовлетворить свой запрос на частный ресурс R
j
, и добавляет Р
i к L, если счётчик ожидания становится нулевым.
Методы обнаружения тупика по наличию замкнутой цепочки запросов
Структура графа обеспечивает простое необходимое (но не достаточное) ус- ловие для тупика. Для любого графа G =<Х, Е> и вершины х
∈ Х пусть Р(х) обо- значает множество вершин, достижимых из вершины х, то есть
Р(х) = { у
(х, у) ∈ Е } ∪ { z(у, z) ∈ Е & у ∈ Р(х)}.

379
Можно сказать, что в ориентированном графе потомством вершины х, кото- рое мы обозначаем как Р(х), называется множество всех вершин, в которые ведут пути из х.
Тогда если существует некоторая вершина х
∈ Х : х ∈ Р(х), то в графе G име- ется цикл.
Теорема 1. Цикл в графе повторно используемых ресурсов является необхо- димым условием тупика.
Для доказательства этой теоремы (которое мы опустим, указав, что при жела- нии его можно найти в работе [45]) можно воспользоваться следующим свойством ориентированных графов: если ориентированный граф не содержит цикла, то су- ществует линейное упорядочение вершин, такое, что если существует путь от вер- шины i к вершине j, то i появляется перед j в этом упорядочении.
Теорема 2. Если S не является состоянием тупика и S
→

i
P
S
T
, где S
T
есть со- стояние тупика в том и только в том случае, когда операция процесса Р
i есть запрос и Р
i находится в тупике в S
T
Это следует понимать таким образом, что тупик может быть вызван только при запросе, который не удовлетворён немедленно. Учитывая эту теорему, можно сделать вывод, что проверка на тупиковое состояние может быть выполнена более эффективно, если она проводится непрерывно, то есть по мере развития процессов.
Тогда надо применять редукцию графа только после запроса от некоторого процес- са Р
i и на любой стадии необходимо сначала попытаться сократить с помощью процесса Р
i
Если процесс Р
i смог провести сокращение графа, то никакие дальней- шие сокращения не являются необходимыми.
Ограничения, накладываемые на распределители, на число ресурсов, запро- шенных одновременно, и количество единиц ресурсов, приводят к более простым условиям для тупика.
Пучок (или узел) в ориентированном графе G = <Х, Е> – это подмножество вершин Z
⊆ X, таких что ∀ х ∈ Z, Р(х) = Z, то есть потомством каждой вершины из
Z является само множество Z. Каждая вершина в узле достижима из каждой другой

380
вершины этого узла, и узел есть максимальное подмножество с этим свойством.
Поясним сказанное рис. 7.12.

381
ния тупика. Эта ситуация возникает, если распределители ресурсов не откладыва- ют запросы, которые могут быть удовлетворены, а выполняют их по возможности немедленно (большинство распределителей следует этой дисциплине).
Состояние называется фиксированным, если каждый процесс, выдавший за- прос, заблокирован.
Теорема 3. Если состояние системы фиксированное (все процессы, имеющие запросы, удовлетворены), то наличие узла в соответствующем графе повторно ис- пользуемых ресурсов является достаточным условием тупика.
Доказательство. Предположим, что граф содержит узел Z. Тогда все процес- сы в этом узле должны быть заблокированы только по ресурсам, принадлежащим
Z, так как никакие ребра не могут выходить из Z по определению. Аналогично, по той же самой причине все распределенные ресурсы узла Z принадлежат процессам из Z. Наконец, все процессы в Z должны быть заблокированы согласно условию фиксированности и определению узла. Следовательно, все процессы в узле Z
должны быть в тупике.
Допустим, что каждый ресурс имеет единичную ёмкость (по одной единице ресурса), то есть |R
j
| = 1, (i = 1, 2, ..., m). При этом ограничении наличие цикла так- же становится достаточным условием тупика.
Теорема 4. Граф повторно используемых ресурсов с единичной ёмкостью ука- зывает на состояние тупика тогда и только тогда, когда он содержит цикл.
Доказательство. Необходимость цикла доказывает теорема 1. Для доказа- тельства достаточности допустим, что граф содержит цикл, и рассмотрим только лишь процессы и ресурсы, принадлежащие циклу. Так как каждая вершина–про- цесс должна иметь входящее и исходящее ребро, она должна иметь выданный за- прос на некоторый ресурс, принадлежащий циклу, и должна удерживать некото- рый ресурс, принадлежащий тому же циклу. Аналогично, каждый ресурс единич- ной ёмкости в цикле должен быть захвачен некоторым процессом. Следовательно,
каждый процесс в цикле блокируется на ресурсе, который может быть освобождён только некоторым процессом из этого цикла; поэтому процессы в цикле находятся в тупике.

382
Чтобы обнаружить тупик в случае ресурса единичной ёмкости, мы должны просто проверить граф повторно используемых ресурсов на наличие циклов.
Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов
Итак, распознавание тупика может быть основано на анализе модели распре- деления ресурсов. Один из алгоритмов, основанный на методе обнаружения замк- нутой цепи запросов, был разработан сотрудниками фирмы IBM; этот алгоритм использовался в одной из ОС этой компании. Он использует информацию о со- стоянии системы, содержащуюся в двух таблицах: таблице текущего распреде- ления (назначения) ресурсов RATBL и «таблице» заблокированных процессов
PWTBL (для каждого вида ресурса может быть свой список заблокированных про- цессов). При каждом запросе на получение или освобождении ресурсов содержи- мое этих таблиц модифицируется, а при запросе – анализируется в соответствии со следующим алгоритмом, который описан по пунктам [49].
1 Запрос от процесса J на занятый ресурс I.
2 Поместить номер ресурса I в PWTBL в строке с номером процесса J.
3 Использовать I в качестве смещения в RATBL, чтобы найти номер процесса
К, который владеет ресурсом.
4 Использовать К в качестве смещения в PWTBL.
5 Проверить, ждёт ли процесс К освобождения какого-либо ресурса I’. Если нет, то перейти к шагу 6, в противном случае – к шагу 7.
6 Перевести J в состояние ожидания и выйти из алгоритма.
7 Использовать I’ в качестве смещения в RATBL, чтобы найти номер блоки- рующего его процесса К'.
8 Проверить К' = J. Если нет, то перейти к шагу 9, в противном случае – к шагу
11.
9 Проверить, вся ли таблица PWTBL просмотрена. Если да, то перейти к шагу
6, в противном случае – к шагу 10.
10 Присвоить К:= К' и перейти к шагу 4.
11 Вывод о наличии тупика с последующим восстановлением.

383 12 Конец алгоритма.
Для иллюстрации описанного алгоритма распознавания тупика рассмотрим следующую последовательность событий:
1 Процесс Р1 занимает ресурс R1.
2 Процесс Р2 занимает ресурс R3.
3 Процесс РЗ занимает ресурс R2.
4 Процесс Р2 занимает ресурс R4.
5 Процесс Р1 занимает ресурс R5.
В результате таблица распределения ресурсов (RATBL) имеет следующий вид:
Таблица 7.3. Таблица распределения ресурсов RATBL
Ресурсы
Процессы
1 1
2 3
3 2
4 2
5 1
1 Пусть процесс Р1 пытается занять ресурс R3, поэтому в соответствии с опи- санным алгоритмом J = 1, I = 3, К = 2. Процесс К не ждёт никакого ресурса I’, по- этому процесс Р1 блокируется по ресурсу R3.
2 Далее, пусть процесс Р2 пытается занять ресурс R2.
J = 3, I = 2, К = 3.
Процесс К не ждёт никакого ресурса, поэтому процесс Р2 блокируется по ре- сурсу R2.
3 И наконец, пусть процесс РЗ пытается обратиться к ресурсу R5.
J = 3, I = 5, К = 1, I’ = 3, К’ = 2, K'< > J, поэтому берём К = 2, I’ = 2, К' = 3.