Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.01.2024
Просмотров: 1013
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Рис. 7.5. Сеть Петри для системы двух взаимодействующих процессов
Эта сеть соответствует рассмотренному нами ранее примеру тупиковой ситуа- ции (см. рис. 7.2), которая возникает при взаимодействии процессов ПР1 и ПР2 во время передачи сообщений и потреблении ресурса R каждым из процессов. На- чальная маркировка для сети, показанной на рис. 7.5, будет равна (1,0,0,0,0,4,
0,0,1,0,0,0,0). Здесь позиция p
2
означает, что процесс ПР1 получил три единицы ре- сурса R. Дуга, соединяющая позицию p
6
(число маркеров в ней соответствует ко-
359
личеству доступных единиц ресурса R), имеет вес 3 и при срабатывании перехода
t
1
процесс ПР1 получает затребованные 3 единицы ресурса. Переход t
2
представля- ет посылку процессом ПР1 сообщения для ПР2; переход t
j
– приём этого сообще- ния. Появление маркера в позиции p
7
означает, что процесс ПР2 обработал сооб- щение и послал ответ процессу ПР1. Срабатывание перехода t
j
представляет воз- врат в систему трёх единиц ресурса, которыми владел процесс ПР1. Рассмотренная сеть не является живой, так как в ней всегда будут мертвы переходы t
3
,t
j
, t
6
, t
7 и t
8
.
Рис. 7.6. Сеть Петри для тупиковой ситуации на ресурсах типа SR
Примеру тупиковой ситуации, возникающему при работе с ресурсами типа
SR, который мы также уже рассматривали ранее (см. рис. 7.3), соответствует сеть
Петри, показанная на рис. 7.6.
В этой сети номера переходов соответствуют отмеченным номерам операто- ров, которые выполняют процессы ПР1 и ПР2, а позиции p
1
и р
2
– семафорам S
1
и
S
2
, над которыми выполняются Р- и V-операции. Сеть на рис. 7.6 также не является
360
живой, хотя для неё и существуют такие последовательности срабатывания пе- реходов, что тупиковой ситуации не наступит.
Алгоритм построения дерева достижимости изложен, например, в работе [64].
Вычислительные схемы
Вычислительная схема – это представление в графической форме асинхрон- ной системы, состоящей из набора операторов (процессов), которые воздействуют на множество «регистов» (данных). Каждая вычислительная схема определяется с помощью двух графов: графа потока данных и графа управления [89].
Граф потока данных (информационный граф) определяет входные и выход- ные данные для каждого оператора [18]. Дуга (R
i
S
k
) от регистра R
i к оператору S
k означает, что данные R
i являются элементом входных данных этого оператора; ду- га (S
k
R
j
) определяет данные R
j как выходные. Очевидно, что некоторые данные R
могут являться выходными для оператора S
i и входными для оператора S
j
. Пример графа потока данных для некоторой вычислительной схемы представлен на рис.
7.7, а; операторы и регистры данных представлены соответственно кружками и прямоугольниками.
Рис. 7.7. Пример вычислительной схемы: а – граф потока данных;
б – граф управления
361
Граф управления определяет последовательность выполнения операторов. Ка- ждый оператор (представлен кружком) связан с некоторым количеством управ-
ляющих счётчиков (представлены прямоугольниками). Каждый из управляющих счётчиков содержит неотрицательное целое число. Текущие значения счётчиков совместно со значениями данных на графе потока данных определяют состояние вычислительной схемы. Пример графа управления представлен на рис. 7.7, б. Если все счётчики, указывающие на оператор S (то есть входные счётчики), имеют не- нулевые значения, то говорят, что оператор S определен. В этом случае он может выполниться, изменив свои выходные регистры в соответствии с графом потока данных и изменив счётчики графа управления по следующему правилу:
значения всех выходных счётчиков оператора S уменьшаются на единицу, а значение выходных – увеличивается, причём для каждого выходного счётчика опе- ратора S приращение может быть своё, персональное, и определяется оно с по- мощью специальной функции от значений регистров.
Обратите внимание на сходство между графом управления и сетью Петри. Ес- ли под операторами и счётчиками понимать переходы и позиции, то единственным существенным различием между этими моделями будет зависимость приращения счётчика от входных данных оператора S.
Такая последовательность операторов S
1
, S
2
, ... , S
n
, ..., что каждый оператор S,
определён (то есть его входные счётчики не равны нулю) при тех значениях счёт- чиков, которые получаются в результате выполнения предшествующих опе- раторов, называется последовательностью исполнения схемы. Поскольку с опе- раторами не связано никакого особого отсчёта времени (подобно сетям Петри
1
), то порядок, в котором операторы будут выполняться, не всегда может быть пред- сказан. Любая допустимая последовательность исполнения является возможной последовательностью событий. Как мы уже знаем, для системы взаимодействую- щих параллельных процессов результаты вычислений зависят от последовательно-
1
Следует заметить, что к настоящему времени появилось большое количество различных модификаций исходной модели, называемой сетью Петри. Многие расширения и модификации базовой модели сетей Петри позволяют учи- тывать модельное время, дополнительные условия возбуждения и срабатывания переходов, отслеживать атрибуты при маркерах, их изменения и т. д., что позволяет получать более мощные средства моделирования параллельных процессов.
362
сти исполнения, если не обеспечить взаимное исключение для критических интер- валов. В случае, когда вычислительная схема вырабатывает одинаковые результа- ты для всех допустимых последовательностей исполнения, говорят, что она детер- минирована. Схема на рис. 7.7 является детерминированной.
Рассмотрим вычислительную схему на рис. 7.8. Операторы S
1
и S
2
как это вид- но из графа управления, выполняются параллельно и асинхронно. Очевидно, что значение регистра R
3
будет различным в зависимости от того, выполняется ли опе- ратор S
1
раньше или позже оператора S
2
. Поскольку граф управления здесь допус- кает последовательности исполнения, которые приводят к различным результатам,
то эта схема не детерминирована.
Говорят, что два оператора соперничают в регистре R, если один из них изме- няет R, а другой либо изменяет R, либо обращается к нему. Если два оператора, ко- торые соперничают в некотором регистре, могут быть выполнены в одно и то же время, то говорят, что в схеме существует условие соперничества и такая схема яв- ляется недетерминированной. Одна из возможных форм недетерминированного исполнения заключается в том, что схема может «зависнуть» (попасть в тупиковую ситуацию).
Рис. 7.8. Пример недетерминированной вычислительной схемы
К сожалению, вычислительные схемы, как и сети Петри, не являются конст- руктивной моделью (с точки зрения борьбы с тупиковыми ситуациями, возникаю- щими в операционных системах), несмотря на свою интуитивную привлекатель-
363
ность и возможность сделать вывод о возможности существования тупиков в той или иной системе [89]. Мы знаем, что возможность существования тупиковой си- туации в большинстве ОС существует. Но ведь это же не означает, что эти ОС
нельзя использовать. Важнее уметь обнаружить существование тупиковой ситуа- ции в конкретный момент времени и поправить ситуацию (насколько это возмож- но). Поэтому гораздо более продуктивной с этой точки зрения является модель
Холта.
Модель пространства состояний системы
Приведём еще одну формальную модель (она подробно рассмотрена в работе
[92]). Эта модель очень проста, однако она позволяет сформулировать, что нам нужно делать, чтобы не попасть в тупиковое состояние.
Пусть состояние операционной системы будет сводиться к состоянию различ- ных ресурсов в системе (свободны они или кому-то распределены). Состояние сис- темы изменяется процессами, когда они запрашивают, приобретают или освобож- дают ресурсы; это будут единственно возможные действия (точнее, мы принимаем во внимание только такие действия). Если процесс не блокирован в данном состоя- нии, он может изменить это состояние на новое. Однако, так как в общем случае невозможно знать заранее, какой путь может избрать произвольный процесс в сво- ей программе (это неразрешимая проблема!), то новое состояние может быть лю- бым из конечного числа возможных. Следовательно, процессы нами будут тракто- ваться как недетерминированные объекты. Введённые ограничения на известные понятия приводят нас к следующим формальным определениям:
♦ Система есть пара <σ, π>, где
σ – множество состояний системы {S
1
, S
2
, S
3
, ... , S
n
};
π – множество процессов {P
1
, Р
2
, Р
3
, ... , Р
k
}.
♦ Процесс Р
i есть частичная функция, отображающая состояние системы в не- пустые подмножества её же состояний. Это обозначается так:
P
i
:
σ→{σ}
364
Если P
i определён на состоянии S, то область значений Р
i
, обозначается как
P
i
(S). Если S
k
∈ P
i
(S
e
), то мы говорим, что P
i может изменить состояние S
e в со- стояние S
k посредством операции, и используем обозначение S
e
→
i
P
S
k
Наконец, запись S
e
S
w обозначает, что
S
e
= Sw или
S
e
→
i
P
S
w для некоторого i или
S
e
→
i
P
S
k для некоторого i и S
k
, и S
k
→
•
S
w
Другими словами, система может быть переведена посредством п
≥ 0 опера- ций с помощью т
≥0 различных процессов из состояния S
e в состояние S
w
Мы говорим, что процесс заблокирован в данном состоянии, если он не может изменить состояние, то есть в этом состоянии процесс не может ни затребовать, ни получать, ни освобождать ресурсы. Поэтому справедливо будет записать следую- щее:
♦ Процесс P
i заблокирован в состоянии S
e
, если не существует ни одного со- стояния S
k
, такого что S
e
→
i
P
S
k
(P
i
(S
e
) =
∅).
Далее, мы говорим, что процесс находится в тупике в данном состоянии S
e
,
если он заблокирован в состоянии S
e и если вне зависимости от того, какие опера- ции (изменения состояний) произойдут в будущем, процесс остается заблокиро- ванным. Поэтому дадим еще одно определение:
♦ Процесс P
i находится в тупике в состоянии S
e
, если для всех состояний S
k
,
таких что S
e
→
•
S
k
, процесс P
i блокирован в S
k
Приведём пример. Определим систему <
σ, π>:
σ = {S
1
, S
2
, S
3
, S
4
};
π = {P
1
, Р
2
};
P
1
(S
1
) = {S
2
, S
3
}; P
2
(S
l
) = {S
3
};
P
l
(S
2
) =
∅ ; P
2
(S
2
) = {S
1
, S
4
};
P
l
(S
3
) = {S
4
}; P
2
(S
3
) =
∅;
P
1
(S
4
) = {S
3
}; P
2
(S
4
) =
∅.
Некоторые возможные последовательности изменений для этой системы тако- вы:
365
S
1
→
1
P
S
3
; S
2
→
2
P
S
4
; S
1
→
•
S
4
Последовательность S
1
→
•
S
4
может быть реализована, например, следую- щим образом: S
1
→
1
P
S
2
; S
2
→
2
P
S
4 или же S
1
→
1
P
S
3
; S
3
→
1
P
S
4
Заметим, что процесс Р
2
находится в тупике как в состоянии S
3
, так и в состоя- нии S
4
; для последнего случая S
2
→
2
P
S
4
или S
2
→
2
P
S
1
и процесс P
1
не ста- новится заблокированным ни в S
4
, ни в S
1
Диаграмма переходов этой системы изображена на рис. 7.9.
Рис. 7.9. Пример системы <
σ, π> на 4 состояния
♦ Состояние S называется тупиковым, если существует процесс Р
i
, находя- щийся в тупике в состоянии S.
Теперь мы можем сказать, что тупик предотвращается, по определению, при введении такого ограничения на систему, чтобы каждое её возможное состояние не было тупиковым состоянием.
Введем еще одно определение.
♦ Состояние S
i есть безопасное состояние, если для всех S
k
, таких что
S
i
→
•
S
k
, S
k не является тупиковым состоянием.
Рассмотрим ещё один пример системы <
σ, π>. Граф её состояний приведен на рис. 7.10. Здесь состояния S
2
и S
3
являются безопасными; из них система никогда не сможет попасть в тупиковое состояние. Состояния S
1
и S
4
могут привести как к безопасным состояниям, так и к опасному состоянию S
5
. Состояние S
6
и S
7
являет- ся тупиковым.
366
Рис. 7.10. Пример системы <
σ, π> с безопасными, опасными и тупиковым состояниями
Наконец, в качестве ещё одной простейшей системы вида <
σ, π> приведём пример тупика с SR-ресурсами, уже рассмотренный нами в этой главе ранее. Опре- делим следующим образом состояния процессов P
1
и Р
2
, которые используют ре- сурсы R
1
и R
2
Таблица 7.1. Состояния процессов Р
1
и Р
2
Состояния для процесса Р
1
Состояния для процесса Р
2 0
Не содержит никаких ресурсов
0
Не содержит никаких ресурсов
1 Запросил ресурс R
2
, не держит никаких ресурсов
1 Запросил ресурс R
1
, не держит никаких ресур- сов
2
Держит ресурс R
2 2
Держит ресурс R
1 3
Запросил ресурс R
1
, держит ресурс R
2 3
Запросил ресурс R
2
, держит ресурс R
1 4
Держит ресурсы R
1
и R
2 4
Держит ресурсы R
1
и R
2 5
Держит ресурс R
2
после освобождения ресурса R
1 5 Держит ресурс R
2
после освобождения ресурса
R
1
Пусть состояние системы S
ij означает, что процесс P
1
находится в состоянии
S
i
, а процесс Р
2
– в состоянии Sj. Возможные изменения в пространстве состояний этой системы изображены на рис.7.11. «Вертикальными» стрелками показаны воз- можные переходы из одного состояния в другое для процесса P
1
, а «горизонталь- ными» – для процесса Р
2
. В данной системе имеются три опасных состояния. По- пав в любое из них, мы неминуемо перейдем в тупиковое состояние.
367
Рис. 7.11. Пример системы
Теперь, когда мы знаем понятия надежного, опасного и безопасного состоя- ний, можно рассмотреть и методы борьбы с тупиками.
Методы борьбы с тупиками
Проблема тупиков является чрезвычайно серьезной и сложной. В настоящее время разработано несколько подходов и методов разрешения этой проблемы, од- нако, ни один из них нельзя считать панацеей. В некоторых случаях цена, которую приходится платить за то, чтобы сделать систему свободной от тупиков, слишком высока. В других случаях, например в системах управления процессами реального времени, просто нет иного выбора, поскольку возникновение тупика может при- вести к катастрофическим последствиям.
Проблема борьбы с тупиками становится всё более актуальной и сложной по мере развития и внедрения параллельных вычислительных систем. При проектиро- вании таких систем разработчики стараются проанализировать возможные непри- ятные ситуации, используя специальные модели и методы. Борьба с тупиковыми ситуациями основывается на одной из трех стратегий:
Эта сеть соответствует рассмотренному нами ранее примеру тупиковой ситуа- ции (см. рис. 7.2), которая возникает при взаимодействии процессов ПР1 и ПР2 во время передачи сообщений и потреблении ресурса R каждым из процессов. На- чальная маркировка для сети, показанной на рис. 7.5, будет равна (1,0,0,0,0,4,
0,0,1,0,0,0,0). Здесь позиция p
2
означает, что процесс ПР1 получил три единицы ре- сурса R. Дуга, соединяющая позицию p
6
(число маркеров в ней соответствует ко-
359
личеству доступных единиц ресурса R), имеет вес 3 и при срабатывании перехода
t
1
процесс ПР1 получает затребованные 3 единицы ресурса. Переход t
2
представля- ет посылку процессом ПР1 сообщения для ПР2; переход t
j
– приём этого сообще- ния. Появление маркера в позиции p
7
означает, что процесс ПР2 обработал сооб- щение и послал ответ процессу ПР1. Срабатывание перехода t
j
представляет воз- врат в систему трёх единиц ресурса, которыми владел процесс ПР1. Рассмотренная сеть не является живой, так как в ней всегда будут мертвы переходы t
3
,t
j
, t
6
, t
7 и t
8
.
Рис. 7.6. Сеть Петри для тупиковой ситуации на ресурсах типа SR
Примеру тупиковой ситуации, возникающему при работе с ресурсами типа
SR, который мы также уже рассматривали ранее (см. рис. 7.3), соответствует сеть
Петри, показанная на рис. 7.6.
В этой сети номера переходов соответствуют отмеченным номерам операто- ров, которые выполняют процессы ПР1 и ПР2, а позиции p
1
и р
2
– семафорам S
1
и
S
2
, над которыми выполняются Р- и V-операции. Сеть на рис. 7.6 также не является
360
живой, хотя для неё и существуют такие последовательности срабатывания пе- реходов, что тупиковой ситуации не наступит.
Алгоритм построения дерева достижимости изложен, например, в работе [64].
Вычислительные схемы
Вычислительная схема – это представление в графической форме асинхрон- ной системы, состоящей из набора операторов (процессов), которые воздействуют на множество «регистов» (данных). Каждая вычислительная схема определяется с помощью двух графов: графа потока данных и графа управления [89].
Граф потока данных (информационный граф) определяет входные и выход- ные данные для каждого оператора [18]. Дуга (R
i
S
k
) от регистра R
i к оператору S
k означает, что данные R
i являются элементом входных данных этого оператора; ду- га (S
k
R
j
) определяет данные R
j как выходные. Очевидно, что некоторые данные R
могут являться выходными для оператора S
i и входными для оператора S
j
. Пример графа потока данных для некоторой вычислительной схемы представлен на рис.
7.7, а; операторы и регистры данных представлены соответственно кружками и прямоугольниками.
Рис. 7.7. Пример вычислительной схемы: а – граф потока данных;
б – граф управления
361
Граф управления определяет последовательность выполнения операторов. Ка- ждый оператор (представлен кружком) связан с некоторым количеством управ-
ляющих счётчиков (представлены прямоугольниками). Каждый из управляющих счётчиков содержит неотрицательное целое число. Текущие значения счётчиков совместно со значениями данных на графе потока данных определяют состояние вычислительной схемы. Пример графа управления представлен на рис. 7.7, б. Если все счётчики, указывающие на оператор S (то есть входные счётчики), имеют не- нулевые значения, то говорят, что оператор S определен. В этом случае он может выполниться, изменив свои выходные регистры в соответствии с графом потока данных и изменив счётчики графа управления по следующему правилу:
значения всех выходных счётчиков оператора S уменьшаются на единицу, а значение выходных – увеличивается, причём для каждого выходного счётчика опе- ратора S приращение может быть своё, персональное, и определяется оно с по- мощью специальной функции от значений регистров.
Обратите внимание на сходство между графом управления и сетью Петри. Ес- ли под операторами и счётчиками понимать переходы и позиции, то единственным существенным различием между этими моделями будет зависимость приращения счётчика от входных данных оператора S.
Такая последовательность операторов S
1
, S
2
, ... , S
n
, ..., что каждый оператор S,
определён (то есть его входные счётчики не равны нулю) при тех значениях счёт- чиков, которые получаются в результате выполнения предшествующих опе- раторов, называется последовательностью исполнения схемы. Поскольку с опе- раторами не связано никакого особого отсчёта времени (подобно сетям Петри
1
), то порядок, в котором операторы будут выполняться, не всегда может быть пред- сказан. Любая допустимая последовательность исполнения является возможной последовательностью событий. Как мы уже знаем, для системы взаимодействую- щих параллельных процессов результаты вычислений зависят от последовательно-
1
Следует заметить, что к настоящему времени появилось большое количество различных модификаций исходной модели, называемой сетью Петри. Многие расширения и модификации базовой модели сетей Петри позволяют учи- тывать модельное время, дополнительные условия возбуждения и срабатывания переходов, отслеживать атрибуты при маркерах, их изменения и т. д., что позволяет получать более мощные средства моделирования параллельных процессов.
362
сти исполнения, если не обеспечить взаимное исключение для критических интер- валов. В случае, когда вычислительная схема вырабатывает одинаковые результа- ты для всех допустимых последовательностей исполнения, говорят, что она детер- минирована. Схема на рис. 7.7 является детерминированной.
Рассмотрим вычислительную схему на рис. 7.8. Операторы S
1
и S
2
как это вид- но из графа управления, выполняются параллельно и асинхронно. Очевидно, что значение регистра R
3
будет различным в зависимости от того, выполняется ли опе- ратор S
1
раньше или позже оператора S
2
. Поскольку граф управления здесь допус- кает последовательности исполнения, которые приводят к различным результатам,
то эта схема не детерминирована.
Говорят, что два оператора соперничают в регистре R, если один из них изме- няет R, а другой либо изменяет R, либо обращается к нему. Если два оператора, ко- торые соперничают в некотором регистре, могут быть выполнены в одно и то же время, то говорят, что в схеме существует условие соперничества и такая схема яв- ляется недетерминированной. Одна из возможных форм недетерминированного исполнения заключается в том, что схема может «зависнуть» (попасть в тупиковую ситуацию).
Рис. 7.8. Пример недетерминированной вычислительной схемы
К сожалению, вычислительные схемы, как и сети Петри, не являются конст- руктивной моделью (с точки зрения борьбы с тупиковыми ситуациями, возникаю- щими в операционных системах), несмотря на свою интуитивную привлекатель-
363
ность и возможность сделать вывод о возможности существования тупиков в той или иной системе [89]. Мы знаем, что возможность существования тупиковой си- туации в большинстве ОС существует. Но ведь это же не означает, что эти ОС
нельзя использовать. Важнее уметь обнаружить существование тупиковой ситуа- ции в конкретный момент времени и поправить ситуацию (насколько это возмож- но). Поэтому гораздо более продуктивной с этой точки зрения является модель
Холта.
Модель пространства состояний системы
Приведём еще одну формальную модель (она подробно рассмотрена в работе
[92]). Эта модель очень проста, однако она позволяет сформулировать, что нам нужно делать, чтобы не попасть в тупиковое состояние.
Пусть состояние операционной системы будет сводиться к состоянию различ- ных ресурсов в системе (свободны они или кому-то распределены). Состояние сис- темы изменяется процессами, когда они запрашивают, приобретают или освобож- дают ресурсы; это будут единственно возможные действия (точнее, мы принимаем во внимание только такие действия). Если процесс не блокирован в данном состоя- нии, он может изменить это состояние на новое. Однако, так как в общем случае невозможно знать заранее, какой путь может избрать произвольный процесс в сво- ей программе (это неразрешимая проблема!), то новое состояние может быть лю- бым из конечного числа возможных. Следовательно, процессы нами будут тракто- ваться как недетерминированные объекты. Введённые ограничения на известные понятия приводят нас к следующим формальным определениям:
♦ Система есть пара <σ, π>, где
σ – множество состояний системы {S
1
, S
2
, S
3
, ... , S
n
};
π – множество процессов {P
1
, Р
2
, Р
3
, ... , Р
k
}.
♦ Процесс Р
i есть частичная функция, отображающая состояние системы в не- пустые подмножества её же состояний. Это обозначается так:
P
i
:
σ→{σ}
364
Если P
i определён на состоянии S, то область значений Р
i
, обозначается как
P
i
(S). Если S
k
∈ P
i
(S
e
), то мы говорим, что P
i может изменить состояние S
e в со- стояние S
k посредством операции, и используем обозначение S
e
→
i
P
S
k
Наконец, запись S
e
S
w обозначает, что
S
e
= Sw или
S
e
→
i
P
S
w для некоторого i или
S
e
→
i
P
S
k для некоторого i и S
k
, и S
k
→
•
S
w
Другими словами, система может быть переведена посредством п
≥ 0 опера- ций с помощью т
≥0 различных процессов из состояния S
e в состояние S
w
Мы говорим, что процесс заблокирован в данном состоянии, если он не может изменить состояние, то есть в этом состоянии процесс не может ни затребовать, ни получать, ни освобождать ресурсы. Поэтому справедливо будет записать следую- щее:
♦ Процесс P
i заблокирован в состоянии S
e
, если не существует ни одного со- стояния S
k
, такого что S
e
→
i
P
S
k
(P
i
(S
e
) =
∅).
Далее, мы говорим, что процесс находится в тупике в данном состоянии S
e
,
если он заблокирован в состоянии S
e и если вне зависимости от того, какие опера- ции (изменения состояний) произойдут в будущем, процесс остается заблокиро- ванным. Поэтому дадим еще одно определение:
♦ Процесс P
i находится в тупике в состоянии S
e
, если для всех состояний S
k
,
таких что S
e
→
•
S
k
, процесс P
i блокирован в S
k
Приведём пример. Определим систему <
σ, π>:
σ = {S
1
, S
2
, S
3
, S
4
};
π = {P
1
, Р
2
};
P
1
(S
1
) = {S
2
, S
3
}; P
2
(S
l
) = {S
3
};
P
l
(S
2
) =
∅ ; P
2
(S
2
) = {S
1
, S
4
};
P
l
(S
3
) = {S
4
}; P
2
(S
3
) =
∅;
P
1
(S
4
) = {S
3
}; P
2
(S
4
) =
∅.
Некоторые возможные последовательности изменений для этой системы тако- вы:
365
S
1
→
1
P
S
3
; S
2
→
2
P
S
4
; S
1
→
•
S
4
Последовательность S
1
→
•
S
4
может быть реализована, например, следую- щим образом: S
1
→
1
P
S
2
; S
2
→
2
P
S
4 или же S
1
→
1
P
S
3
; S
3
→
1
P
S
4
Заметим, что процесс Р
2
находится в тупике как в состоянии S
3
, так и в состоя- нии S
4
; для последнего случая S
2
→
2
P
S
4
или S
2
→
2
P
S
1
и процесс P
1
не ста- новится заблокированным ни в S
4
, ни в S
1
Диаграмма переходов этой системы изображена на рис. 7.9.
Рис. 7.9. Пример системы <
σ, π> на 4 состояния
♦ Состояние S называется тупиковым, если существует процесс Р
i
, находя- щийся в тупике в состоянии S.
Теперь мы можем сказать, что тупик предотвращается, по определению, при введении такого ограничения на систему, чтобы каждое её возможное состояние не было тупиковым состоянием.
Введем еще одно определение.
♦ Состояние S
i есть безопасное состояние, если для всех S
k
, таких что
S
i
→
•
S
k
, S
k не является тупиковым состоянием.
Рассмотрим ещё один пример системы <
σ, π>. Граф её состояний приведен на рис. 7.10. Здесь состояния S
2
и S
3
являются безопасными; из них система никогда не сможет попасть в тупиковое состояние. Состояния S
1
и S
4
могут привести как к безопасным состояниям, так и к опасному состоянию S
5
. Состояние S
6
и S
7
являет- ся тупиковым.
366
Рис. 7.10. Пример системы <
σ, π> с безопасными, опасными и тупиковым состояниями
Наконец, в качестве ещё одной простейшей системы вида <
σ, π> приведём пример тупика с SR-ресурсами, уже рассмотренный нами в этой главе ранее. Опре- делим следующим образом состояния процессов P
1
и Р
2
, которые используют ре- сурсы R
1
и R
2
Таблица 7.1. Состояния процессов Р
1
и Р
2
Состояния для процесса Р
1
Состояния для процесса Р
2 0
Не содержит никаких ресурсов
0
Не содержит никаких ресурсов
1 Запросил ресурс R
2
, не держит никаких ресурсов
1 Запросил ресурс R
1
, не держит никаких ресур- сов
2
Держит ресурс R
2 2
Держит ресурс R
1 3
Запросил ресурс R
1
, держит ресурс R
2 3
Запросил ресурс R
2
, держит ресурс R
1 4
Держит ресурсы R
1
и R
2 4
Держит ресурсы R
1
и R
2 5
Держит ресурс R
2
после освобождения ресурса R
1 5 Держит ресурс R
2
после освобождения ресурса
R
1
Пусть состояние системы S
ij означает, что процесс P
1
находится в состоянии
S
i
, а процесс Р
2
– в состоянии Sj. Возможные изменения в пространстве состояний этой системы изображены на рис.7.11. «Вертикальными» стрелками показаны воз- можные переходы из одного состояния в другое для процесса P
1
, а «горизонталь- ными» – для процесса Р
2
. В данной системе имеются три опасных состояния. По- пав в любое из них, мы неминуемо перейдем в тупиковое состояние.
367
Рис. 7.11. Пример системы
Теперь, когда мы знаем понятия надежного, опасного и безопасного состоя- ний, можно рассмотреть и методы борьбы с тупиками.
Методы борьбы с тупиками
Проблема тупиков является чрезвычайно серьезной и сложной. В настоящее время разработано несколько подходов и методов разрешения этой проблемы, од- нако, ни один из них нельзя считать панацеей. В некоторых случаях цена, которую приходится платить за то, чтобы сделать систему свободной от тупиков, слишком высока. В других случаях, например в системах управления процессами реального времени, просто нет иного выбора, поскольку возникновение тупика может при- вести к катастрофическим последствиям.
Проблема борьбы с тупиками становится всё более актуальной и сложной по мере развития и внедрения параллельных вычислительных систем. При проектиро- вании таких систем разработчики стараются проанализировать возможные непри- ятные ситуации, используя специальные модели и методы. Борьба с тупиковыми ситуациями основывается на одной из трех стратегий: