Модель системы для исследования проблемы тупика

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

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

Состояние системы представляется графом типа “процесс-ресурс”. Свойства графа, представляющего состояние системы, зависят от типов ресурсов, имеющихся в системе. Для простоты предположим, что множество процессов и множество ресурсов в системе постоянны.

Рассмотрим графовую модель для системы с повторно используемыми ресурсами.

Повторно используемый ресурс (ПИР или ресурс типа SR) - это ресурс, состоящий из конечного множества идентичных единиц со следующими свойствами:

– число единиц ресурса постоянно;

– отсутствует возможность разделения ресурса (параллельного использования одних и тех же единиц ресурса несколькими процессами) - ресурс захватывается процессом, которому он выделен, в монопольное использование;

– процесс может освободить только те единицы ресурса, которые ему были ранее распределены по его запросам.

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

– request (R_i, k) - запрос процесса p_j, выполняющего данную операцию, на k единиц ресурса R_i;

– приобретение ресурса (выделение ресурса процессу p_j в соответствии с выполненным им ранее запросом);

– release (R_i, k) - освобождение процессом p_j k единиц ранее выделенного ему ресурса R_i.

Операции запроса на ресурс и освобождения ресурса выполняются процессом, а операция выделения ресурса - системой в ответ на запрос, сделанный процессом.

Граф ПИР (SR-граф) - ориентированный двудольный граф

SR = (N, E),

где N есть множество вершин:

N = p È r

(p = { p₁, p₂,..., p_n}- конечное множество вершин, представляющих процессы в ВС, r = { R₁, R₂,..., R_m} - множество вершин, соответствующих SR-ресурсам ВС; p Ç r = Æ), а E - множество дуг графа:

E Í (p ´ r) È (r ´ p),

причем элементы графа обладают следующими свойствами:

¨ R_i - вершина, представляющая повторно используемый ресурс R_i Î r, имеет пометку - пару (c_i, t_i), где c_i - емкость данного ресурса, а t_i - количество единиц ресурса, доступных для распределения (свободных) в данный момент;

¨ p_j - вершина, представляющая процесс p_j Î p в системе;

¨ p_j ^k R_i - ребро (p_j, R_i) с весом | (p_j, R_i) | = k, представляющее вы полненный процессом p_j Î p, но пока не удовлетворенный запрос на k единиц повторно используемого ресурса R_i Î r;

¨ R_i ^k p_j - ребро (R_i, p_j) с весом | (R_i, p_j) | = k, представляющее все распределения ресурса R_i Î r процессу p_j Î p по его удовлетворенным запросам;

¨ каждый запрос, выполняемый процессом p_j Î p на ресурс R_i Î r должен удовлетворять ограничению:

| (R_i, p_j) | + | (p_j, R_i) | £ c_i,

то есть сумма выполненных распределений и запросов конкретного ресурса относительно любого из процессов не может превышать количества единиц ресурса, имеющихся в системе для всех i и j (i = 1, m, j = 1, n); в противном случае запрос считается ошибочным и не может быть выполнен;

¨ в общей сложности в системе для каждого ресурса R_i Î r может быть сделано не более чем c_i назначений, то есть

n

å | (R_i, p_j) | £ c_i

j = 1

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

Пусть система находится в состоянии S_l. Процесс p_j может запросить любое число ресурса R_i, удовлетворяющее приведенному выше ограничению, с помощью операции request (R_i, r). Выполнение процессом запроса приведет к появлению в SR-графе дополнительного ребра запроса с соответствующим весом r. Новый граф представляет состояние системы S_k, такое что

p_j

S_l ® S_k.

Операция приобретения процессом p_j ресурса R_i по запросу, представленному ребром (p_j, R_i), может быть выполнена, если

n

| (p_j, R_i) | + å | (R_i, p_h) | £ c_i

h = 1

или

| (p_j, R_i) | £ t_i

n

(где t_i = c_i - å | (R_i, p_h) |).

h = 1

Выполнение этой операции для процесса, которому еще не был распределен ресурс R_i, приведет к удалению дуги (p_j, R_i), представлявшей удовлетворенный запрос, и появлению новой дуги (R_i, p_j) с весом, равным весу удаленной дуги запроса (дуга запроса “обращается” - меняется ее направление). В том случае, если данный ресурс уже был выделен процессу, увеличивается вес уже существующей дуги (R_i, p_j), представляющей распределение данного ресурса этому процессу. При этом в любом случае уменьшается величина t_i (то есть сокращается количество доступных для распределения единиц распределенного ресурса) на величину удовлетворенного запроса.

Операция освобождения release (R_i, r) процессом p_j r единиц ресурса R_i может быть выполнена тогда и только тогда, когда процесс не имеет неудовлетворенных запросов (в графе ПИР нет дуг, исходящих из вершины, представляющей данный процесс) и имеет в своем распоряжении ресурс R_i (есть дуга с положительным весом не меньшим чем r: | (R_i, p_j) | ³ r).

В результате освобождения ресурса новое состояние системы представляется графом ПИР, в котором изменилась пометка вершины, соответствующей ресурсу R_i (величина t_i увеличилась на количество освобожденных процессом единиц ресурса: t_i:= t_i + r), и либо изменился вес дуги (R_i,p_j), показывающей распределение данного ресурса процессу p_j (вес уменьшается на количество освобожденных единиц ресурса: |(R_i,p_j)|:= |(R_i,p_j)| - r), либо (если процесс освободил ресурс полностью (вес |(R_i,p_j)| равнялся r)) дуга (R_i, p_j) удаляется из графа.

Рассмотрим примеры.

Пример 1. Пусть в системе есть два процесса P1 и P2 и два единичных повторно используемых ресурса R1 и R2. Процессы имеют следующее описание:

Процесс 1	Процесс 2
process P1; begin... request (R1, 1); ... request (R2, 1); ... release (R2, 1); ... release (R1, 1); ... end.	process P2; begin... request (R2, 1); ... request (R1, 1); ... release (R2, 1); ... release (R1, 1); ... end.

Предположим, что процессы выполняют свои операции над ресурсами в порядке, который приводит к изменению состояний системы, показанному последовательно изменяемыми графами ПИР, приведенными на рис.2.10. Последний граф ПИР соответствует тупиковому состоянию системы S7 (процессы P1 и P2 взаимно блокируют друг друга). Другая последовательность выполнения операций могла бы позволить процессам успешно завершиться.

Пример 2. В системе выполняются n процессов и существует разделяемый повторно используемый ресурс R емкости m. Описание программы каждого процесса выглядит следующим образом:

process P1;

begin...

request ( R, 1 );

...

request ( R, 1 );

...

release ( R, 1 );

...

release ( R, 1 );

...

End.

(1, 1) (1, 1) (1, 0)

R1 R1 R1

S1: S2: 1 S3: 1