Определение тупика

Более точное определение тупика требует использования математической модели ВС.

Определим систему как пару

S = { s, p },

где s = {S₁, S₂,...} - множество состояний системы, p = { p₁, p₂,...} - множество процессов, протекающих в системе.

В системе, которая определяется таким образом, процесс p_i Î p представляет собой частичную функцию, отображающую состояния системы в непустые подмножества ее же состояний:

p_i: s ® { s }.

Процесс p_i может быть определен не для всех состояний.

Если p_i определен на состоянии S_l, то p_i(S_l) - область его значений, то есть процесс p_i может изменить состояние системы из S_l в состояние S_k Î p_i(S_l). Для перевода системы из состояния S_l в состояние S_k процесс должен выполнить некоторую операцию. Для обозначения перевода процессом p_i системы S из состояния S_l в состояние S_k введем обозначение

p_i

S_l ® S_k.

Состояние системы может измениться только при выполнении процессом одной из следующих операций:

– запрос на ресурс;

– приобретение ресурса;

– освобождение ресурса.

Введем еще одно обозначение: нотация

_*

S_l ® S_n

означает

(a) S_l = S_n или

p_i

(b) $ p_i: S_l ® S_n или

p_{i *}

(c) $ S_k & $ p_i: (S_l ® S_k) & (S_k ® S_n).

То есть система может быть переведена из состояния S_l в состояние S_n посредством h операций (h ³ 0), которые могут быть выполнены m различными процессами (m ³ 0).

Используя введенные обозначения, определим состояние тупика.

Процесс p_i заблокирован в состоянии S_l, если не существует ни одного такого состояния S_k, что

p_i

S_l ® S_k.

То есть заблокированный процесс не может выполнить никакой операции по изменению состояния системы.

Процесс p_i находится в тупике в состоянии S_l, если для любого состояния S_k, такого что

_*

S_l ® S_k

процесс p_i будет заблокирован в этом состоянии. То есть процесс находится в тупике в состоянии S_l, если он заблокирован в этом состоянии и останется заблокированным в любом другом состоянии S_k, в которое система может перейти из этого состояния S_l при выполнении любых операций любыми другими процессами (процесс останется заблокированным, как бы ни изменялось состояние системы в будущем).

Состояние S_l называется тупиковым, если существует процесс p_i, находящийся в тупике в этом состоянии.

Состояние S_l называется безопасным, если любое состояние S_k, такое что

_*

S_l ® S_k,

не будет состоянием тупика.

Система может быть представлена в виде графа, вершины которого соответствуют состояниям системы, а дуги показывают возможные переходы системы из одного состояние в другое при выполнении процессами перечисленных выше операций.

Рассмотрим пример системы, в которой есть как тупиковое, так и безопасное состояние. Пусть s = {S₁, S₂, S₃, S₄, S₅} - множество состояний системы, p = {p₁, p₂} - множество выполняющихся в ней процессов (рис.2.9).

p₁ p₂

p₂ p₁

S₁ S₂ p₁ S₃ S₄ p₁ S₅

Рис.3.9. Пример системы с тупиковым и безопасным состоянием

Состояние S₁ является состоянием тупика. Состояния S₄ и S₅ являются безопасными состояниями. Состояния S₂ и S₃ не являются безопасными состояниями, но не являются и тупиковыми.