Дайте формальное определение системы с использованием математической (графовой) модели.
Более точное определение тупика требует использования математической модели ВС.
Определим систему как пару
где
= {S1 ,
S2 ,
...} – множество состояний системы,
= { p1 ,
p2 ,
...} – множество процессов, протекающих
в системе.
В
системе, которая определяется таким
образом, процесс pi
представляет собой частичную функцию,
отображающую состояния системы в
непустые подмножества ее же состояний:
pi
:
{
}.
Процесс pi может быть определен не для всех состояний.
Если
pi определен
на состоянии Sl,
то pi(Sl)
– область его значений, то есть процесс
pi может
изменить состояние системы из Sl
в состояние
Sk
pi(Sl
). Для перевода
системы из состояния Sl
в состояние
Sk процесс
должен выполнить некоторую операцию.
Для обозначения перевода процессом pi
системы
из
состояния Sl в
состояние Sk
введем
обозначение
pi
Sl
Sk.
Состояние системы может измениться только при выполнении процессом одной из следующих операций:
– запрос на ресурс;
– приобретение ресурса;
– освобождение ресурса.
Введем еще одно обозначение: нотация
*
Sl Sn
означает
(a) Sl = Sn или
pi
(b) pi : Sl Sn или
pi *
(c)
Sk
&
pi
:
(Sl
Sk)
& (Sk
Sn).
То есть система может быть переведена из состояния Sl в состояние Sn посредством h операций (h ≥ 0), которые могут быть выполнены m различными процессами (m ≥ 0).
Дайте формальное определение заблокированного процесса, процесса, находящегося в тупике.
Процесс pi заблокирован в состоянии Sl, если не существует ни одного та-кого состояния Sk , что
pi
S
l
Sk
.
То есть заблокированный процесс не может выполнить никакой операции по изменению состояния системы.
Процесс pi находится в тупике в состоянии Sl, если для любого состояния Sk, такого что
*
S l Sk
процесс pi будет заблокирован в этом состоянии. То есть процесс находится в тупике в состоянии Sl, если он заблокирован в этом состоянии и останется заблокированным в любом другом состоянии Sk, в которое система может перейти из этого состояния Sl при выполнении любых операций любыми другими процессами (процесс останется заблокированным, как бы ни изменялось состояние системы в будущем).
Состояние Sl называется тупиковым, если существует процесс pi, находящийся в тупике в этом состоянии.
Какое состояние системы является тупиковым?
Какое состояние называется безопасным?
Какое состояние называется выгодным?
Процесс pi заблокирован в состоянии Sl, если не существует ни одного та-кого состояния Sk , что
pi
S l Sk .
То есть заблокированный процесс не может выполнить никакой операции по изменению состояния системы.
Процесс pi находится в тупике в состоянии Sl, если для любого состояния Sk, такого что
*
S l Sk
процесс pi будет заблокирован в этом состоянии. То есть процесс находится в тупике в состоянии Sl, если он заблокирован в этом состоянии и останется заблокированным в любом другом состоянии Sk, в которое система может перейти из этого состояния Sl при выполнении любых операций любыми другими процессами (процесс останется заблокированным, как бы ни изменялось состояние системы в будущем).
Состояние Sl называется тупиковым, если существует процесс pi, находящийся в тупике в этом состоянии.
Р
P1
P2
ассмотрим пример системы, в которой есть как тупиковое. Пусть
= {S1, S2,
S3, S4,
S5} – множество
состояний системы,
= {p1, p2}
– множество выполняющихся в ней процессов
S1
S2
S3
S4
P2
S5
P1
P1
P1
Состояние S1 является состоянием тупика. Состояния S4 и S5 являются безопасными состояниями. Состояния S2 и S3 не являются безопасными состояниями, но не являются и тупиковыми