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

350
ПР2: WAIT_MESSAGE (ПР1, сообщение, MB);
REQUEST (R, 2);
ОБРАБОТКА СООБЩЕНИЯ;
RELEASE (R, 2);
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
обращаются к ресурсам следующим образом [37] (рис. 7.3):
Процесс ПР1 Процесс ПР2
: :
1: P(S2); 5: P(S1);
: :
2: P(S1); 6: P(S2);
: :
3: V(S1); 7: V(S1);
: :
4: V(S2); 8: V(S2);
: :
Рис. 7.3. Пример последовательности операторов для двух процессов, которые могут привести к тупиковой ситуации

351
Здесь несущественные (с точки зрения обращения к ресурсам) детали опуще- ны. Считаем, что оба семафора первоначально установлены в единицу. Простран- ство возможных вычислений приведено на рис. 7.4.
Горизонтальная ось задаёт выполнение процесса ПР1, вертикальная – ПР2.
Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам 1– 4
процесса ПР1. Аналогично горизонтальные линии, пронумерованные от 5 до 8, со- ответствуют операторам 5 – 8 программы ПР2. Точка на плоскости определяет со- стояние вычислений в некоторый момент времени. Так, точка А соответствует си- туации, при которой ПР1 начал исполнение, но не достиг оператора 1, а ПР2 вы- полнил оператор 6, но не дошел до оператора 7. По мере выполнения точка будет двигаться горизонтально вправо, если исполняется ПР1, и вертикально вверх, если исполняется ПР2.
Интервалы исполнения, во время которых ресурсы 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
заблокируется в точке Х при выполнении оператора 2, а процесс ПР2 заблокирует- ся в точке Y при выполнении оператора 6. При этом процесс ПР1 ждёт, когда про- цесс ПР2 выполнит оператор 7, а ПР2 ждёт, когда ПР1 выполнит оператор 4. Оба процесса будут находиться в тупике, ни ПР1, ни ПР2 не могут закончить выполне- ние. При этом все ресурсы, которые получили ПР1 и ПР2, становятся недоступны-

352
ми для других процессов, что резко снижает возможности вычислительной систе- мы по обслуживанию их. Отметим одно очень важное обстоятельство: тупик будет неизбежным, если вычисления зашли в прямоугольник D, являющийся критическим состоянием.
Рис. 7.4. Пространство состояний системы двух параллельных конкурирующих процессов
Для того чтобы возник тупик, необходимо, чтобы одновременно выполнялись четыре условия [37, 92]:
♦ взаимного исключения, при котором процессы осуществляют монопольный доступ к ресурсам;
♦ ожидания, при котором процесс, запросивший ресурс, ждёт до тех пор, пока запрос не будет удовлетворен, при этом удерживая ранее полученные ресурсы;
♦ отсутствия перераспределения, при котором ресурсы нельзя отобрать у про- цесса, если они ему уже выделены;
♦ кругового ожидания, при котором существует замкнутая цепь процессов,
каждый из которых ждёт ресурс, удерживаемый его предшественником в этой це- пи.
Проанализировав содержательный смысл этих четырех условий, легко убе- диться, что все они выполняются в точке Y (см. рис. 7.4).

353
Формальные модели для изучения проблемы
тупиковых ситуаций
Проблема борьбы с тупиками становится всё более актуальной и сложной по мере развития и внедрения параллельных вычислительных систем. При проектиро- вании таких систем разработчики стараются проанализировать возможные непри- ятные ситуации, используя специальные модели и методы.
Таких моделей много; к настоящему времени разработано несколько десятков различных моделей, предназначенных для анализа и моделирования систем с па- раллельными асинхронными процессами, для которых возможность возникновения тупиковых ситуаций является очень серьёзной проблемой. Изложение и сравни- тельный анализ этих моделей может составить большую монографию, поэтому здесь мы кратко рассмотрим только четыре из них – сети Петри, вычислительные схемы, модель пространства состояний и уже упомянутую нами модель Холта.
Сети Петри
Среди многих существующих методов описания и анализа параллельных сис- тем уже более 35 лет значительное место занимают сетевые модели, восходящие к сетям специального вида, предложенных в 1962 году Карлом Петри для моделиро- вания асинхронных информационных потоков в системах преобразования данных
[64].
Взаимодействие событий в параллельных асинхронных дискретных системах имеет, как правило, сложную динамическую структуру. Эти взаимодействия опи- сываются более просто, если указывать не непосредственные связи между собы- тиями, а те ситуации, при которых данное событие может реализоваться. При этом глобальные ситуации в системе формируются с помощью локальных операций, на- зываемых условиями реализации событий. Определённые сочетания условий раз- решают реализоваться некоторому событию (предусловия события), а реализация события изменяет некоторые условия (постусловия события), то есть события взаимодействуют с условиями, а условия – с событиями. Таким образом, предпола- гается, что для решения задач достаточно представить системы как структуры, об- разованные из элементов двух типов – событий и условий. Удобный формальный

354
механизм для этого, предложенный Петри, был развит А. Холтом, который назвал его сетью Петри.
В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством пере- ходов и множеством позиций. Имеется несколько формальных представлений се- тей Петри:
♦ теоретико-множественное;
♦ графовое – бихроматический (двудольный ориентированный) граф и, соот- ветственно, графическое;
♦ матричное.
При использовании теоретико-множественного подхода к описанию сети Пет- ри (поскольку эта модель представляет и структуру, и функционирование системы)
она формально может быть определена как двойка вида: N =
〈S,М
0
〉. Здесь S – это структура сети, которая представляется двудольным ориентированным мультигра- фом S=(V, U), где V – вершины этого графа, U – его дуги. М
0
– начальное состояние сети Петри, которое также называется начальной маркировкой. В силу того, что граф S является двудольным, можно перейти к формальному описанию структуры сети Петри в виде тройки:
S
〈P,T,Y〉,
где Р – конечное множество позиций, Р ={p
i
},i = n
,
1 ; Т – конечное множество переходов, Т = {t
j
}, j = m
,
1
; Т
∪Р = V, Т∩Р = ∅, то есть Т и Р – это два типа вершин биграфа S; Y – конечное множество дуг, заданное отношениями между вершинами графа S : Y
∈ (Р * T)∪(T * Р).
Поскольку двудольный мультиграф S является ориентированным, то любой переход t
j
, j = m
,
1
соединяется с позициями р
i
∈ Р через входные и выходные дуги,
которые задаются через функцию предшествования В:(P * T)
→ {0,1, 2,...} и через функцию следования Е:(Т * Р)
→ {0,1,2..}, являющиеся отображениями из множе- ства переходов в комплекты позиций [64] (синонимом термина комплект является понятие мультимножества). Эти функции определяют комплекты позиций {р
i
}
∈P ,

355
связанных с переходом t
j
∈ Т через множество дуг {(p
i
,t
j
)
l
}, где l
≤{(p
i
,t
j
)
l
:i,j =
const}
≤W, и комплекты позиций {р
k
}
¢ P , связанных с переходом t
j
∈ Т через множество_дуг {(t
j
,p
k
)
l
}, где l
≤{(t
i
,p
k
)
l
: j,k = const}
≤W. Здесь W – мультичисло графа S; P – пространство комплектов, заданное на множестве функциями Е и В;
{(p
i
,t
j
)
v
} – v-я дуга, выходящая из позиции p
i
и входящая в переход t
j
, {(t
i
,p
k
)
v
– v-я дуга, выходящая из перехода t
j
и входящая в позицию p
k
.
Таким образом, теперь структура S сети Петри N может быть представлена как четверка: S(P,T,B,E). Представим множество позиций Р как объединение двух пе- ресекающихся множеств: P=I
œO; I›Oš. Здесь мы через I и О обозначим сле- дующие множества:
I =

m
j 1
=
I(t
j
); O =

m
j 1
=
O(t
j
),
где I(t
j
) = {p
i
:B(p
i
,t
j
)
‡ 1, i = n
,
1 }, j = m
,
1
; O(t
j
) = {p
k
:E(t
j
,p
k
)
‡ 1 k = n
,
1 }, j = m
,
1
;
(p
i
,t
j
) – дуга с весом w
≤ W, выходящая из вершины p
i
и входящая в вершину t
j
(t
j
,p
k
) – дуга с весом w
≤ W, выходящая из вершины t
j
и входящая в вершину p
k
то есть I(t
j
) и O(t
j
) – комплекты соответственно входных и выходных позиций пере- хода t
j
.
Элементы множества T обычно представляют собой те возможности (возмож- ные ситуации, условия), при которых могут быть реализованы интересующие нас процессы (действия).
Начальная маркировка М
0
(как и текущая маркировка М, которая соответству- ет некоторому состоянию сети в текущий момент модельного времени) определя- ется одномерной матрицей (вектором), число компонентов которого равно числу позиций сети п, п =|Р |, а значение i-го компонента, 1
≤ i ≤. п, есть натуральное чис- ло m(p
i
), которое определяет количество маркеров (меток) в позиции р
i
то есть
М
0
= (m
0
(p
1
), m
0
(p
2
), … , m
0
(p
n
));
М
= (m(p
1
), m(p
2
), … , m(p
n
)),
где m(p
1
) m(p
i
)
¢Z; Z – множество неотрицательных целых чисел. Маркировку
М можно представлять и как множество или комплект с той лишь только разницей,

356
что отсутствие некоторого элемента в множестве будем обозначать специальным элементом – нулём. В этом случае запись вида M
i
= M
i-1
– I(t) означает разность множеств и такое изменение маркировки, при котором на соответствующих местах вектора М
i
будут уменьшенные значения.
Передвижение маркеров по сети осуществляется посредством срабатывания её
переходов. Срабатывание возбужденного перехода, являющееся локальным актом,
в целом ведёт к изменению маркировки сети, то есть к изменению её состояния.
Таким образом, если в сети задано начальное маркирование М
0
, при котором хотя бы один переход возбуждён, то в ней начинается движение маркеров, отображаю- щее смену состояний сети. Переход t
j может сработать, если
p
i
¢I(t
j
): m(p
i
)
‡(р
i
, I(t
j
)) – w.
Переход, для которого выполняется это условие, называется возбуждённым.
Здесь запись вида #(р
i
, I(t
j
)) означает число появлений позиций р
i
во входном ком- плекте перехода t
j
оно, естественно, равно весу w, если вместо мультиграфа рас- сматривать взвешенный граф. При срабатывании перехода t
j
маркировка М
0
изме- няется на маркировку M
1
следующим образом: M
1
= М
0
– I(t
j
) + О(t
j
). Иначе говоря,
p
i
¢P: т
i
(р
i
) – т
0
(р
i
) - #(р
i
, I(t
j
)) + #(р
i
, О(t
j
)).
Из последнего выражения видно, что количество маркеров, которое переход t
j
изымает из своих входных позиций, может не равняться количеству маркеров, ко- торое этот переход помещает в свои выходные позиции, так как совсем не обяза- тельно, чтобы число входных дуг перехода равнялось числу его выходных дуг.
В графическом представлении сетей (оно наиболее наглядно и легко интер- претируемо) переходы изображаются вертикальными (или горизонтальными) план- ками (чёрточками), а позиции – кружками (рис. 7.5). Условия–позиции и события–
переходы связаны отношением непосредственной зависимости (непосредственной причинно-следственной связи), которое изображается с помощью направленных дуг, ведущих из позиций в переходы и из переходов в позиции. Позиции, из кото- рых ведут дуги на данный переход, называются его входными позициями, а пози- ции, на которые ведут дуги из данного перехода, – выходными позициями.

357
Выполнение условия изображается разметкой соответствующей позиции, а именно помещением числа n или изображением n маркеров (фишек) в то место, где
п > 0 – ёмкость условия.
Сети Петри могут быть использованы с точки зрения анализа системы на воз- можность возникновения в ней тупиковых ситуаций. Этот анализ проводится по- средством исследования пространства возможных состояний сети Петри. При этом под последним понимается множество возможных маркировок сети. Анализ сетей посредством матричных методов имеет множество проблем, поэтому в основном используется подход, основанный на построении редуцированного до дерева
1
гра- фа возможных маркировок [49]. В таком дереве вершины графа – это состояния
(маркировки) сети, а ветви дерева, помеченные соответствующими переходами се- ти, – это возможные изменения состояний сети, то есть срабатывания её переходов.
Если взять любую вершину в таком дереве (за исключением корневой), то путь к этой вершине от корня дерева (путь из начальной маркировки к заданной) будет представлять собой последовательность срабатывания переходов.
Говорят, что переход t
j
для разметки М является живым, если для всех разме- ток М'
∈ σ(М) существует последовательность срабатывания переходов, которая приводит к маркировке М' при которой переход t
j
может сработать. Сеть Петри на- зывается живой, если все её переходы живы; живучая разметка – это разметка, при которой каждый из её переходов сможет запускаться бесконечное число раз. Когда достигнута такая разметка, при которой ни один из переходов не может быть за- пущен, говорят, что сеть Петри завершилась (достигнута желаемая конечная мар- кировка) или же зависла (то есть имеет место тупиковая ситуация).
Сети Петри очень удобны для описания процессов синхронизации и альтерна- тив. Например, семафор может быть представлен входной позицией, связанной с несколькими взаимоисключающими переходами (критическими секциями). Сети
Петри позволяют моделировать асинхронность и недетерминизм параллельных не- зависимых событий, параллелизм конвейерного типа, конфликтные взаимодейст- вия между процессами. Сети Петри очень удобны для описания процессов синхро-
1
Напомним, что деревом в теории графов называют граф, не имеющий циклов.

358
низации и альтернатив. Например, семафор может быть представлен входной по- зицией, связанной с несколькими взаимоисключающими переходами (критически- ми секциями). Говорят, что два перехода конфликтуют, если они взаимно исклю- чают друг друга, то есть они не могут быть оба запущены одновременно. Два пере- хода, готовые к срабатыванию, находятся в конфликте, если они связаны с общей входной позицией.
В качестве примера рассмотрим рис. 7.5.