P1 p2 p1 p2 p1 p2

R2 R2 R2

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

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

R1 R1 R1

S4: 1 S5: 1 S6: 1

P1 p2 p1 p2 p1 p2

R2 1 R2 1 1 R2 1

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

(1, 0)

R1

S7: 1 1

P1 p2

1 R2 1

(1, 0)

Рис.2.10. Изменение состояний системы при выполнении процессами операций над ресурсами:

_{P1 P1 P2 P2 P1 P2}

S1 ® S2 ® S3 ® S4 ® S5 ® S6 ® S7

S1 - начальное состояние системы до выполнения процессами запросов;

S2 - состояние системы после выполнения процессом P1 операции запроса ресурса request(R1,1);

S3 - состояние системы после выделения процессу P1 единицы ресурса R1;

S4 - состояние системы после выполнения процессом P2 операции запроса ресурса request(R2,1);

S5 - состояние системы после выделения процессу P2 единицы ресурса R2;

S6 - состояние системы после выполнения процессом P1 операции запроса ресурса request(R2,1);

S7 - состояние системы после выполнения процессом P2 операции запроса ресурса request(R1,1)

В случае, если m невелико (недостаточно для удовлетворения всех запросов от n процессов: m < n), система может попасть в тупиковое состояние, представленное графом ПИР на рис.2.11.

(m, 0)

R

1 1 1 1 1 1 1 1

p₁ p₂ p₃... p_n-1 p_n

Рис.2.11. Тупиковое состояние в системе с составным ресурсом

Для систем с потребляемыми ресурсами также можно ввести графовую модель для исследования проблемы тупика - граф потребляемых ресурсов (ПР).

Потребляемый ресурс (ресурс типа CR) - это ресурс, обладающий следующими свойствами:

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

– процесс-производитель увеличивает число единиц ресурса, освобождая одну или более единиц этого ресурса, которые он создает;

– процесс-потребитель уменьшает число единиц ресурса, запрашивая и приобретая одну или более единиц этого ресурса; приобретенные единицы ресурса не возвращаются в систему.

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

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

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

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

– ни одно состояние системы с ПР не является безопасным, так как все незаблокированные процессы могут последовательно запросить количество ресурсов, превышающее имеющиеся их запасы.

В системах с потребляемыми ресурсами должны быть известны их производители. Допустим, что процессы-производители для каждого потребляемого ресурса известны априори. Это значит, что множество процессов, которые могут выполнять операции освобождения ресурсов, определено и фиксировано.

При сформулированных ограничениях можно ввести определение графа ПР (CR-графа), представляющего состояние системы с потребляемыми ресурсами.

Граф потребляемых ресурсов - это ориентированный двудольный граф

CR = (N, E),

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

N = p È r

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

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

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

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

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

– для каждого ресурса R_i Î r существует непустое множество процессов-производителей этого ресурса p (R_i) Í p и граф ПР содержит дугу производителя (R_i, p_j) для каждого p_j Î p (R_i) по всем R_i Î r;

– R_i p_j - обозначение ребра (дуги) производителя ресурса R_i;

– ребра производителя являются постоянными в графе потребляемых ресурсов и никогда не уничтожаются;

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

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

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

p_j

S_l ® S_k.

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

| (p_j, R_i) | £ t_i

(то есть в системе есть достаточное количество единиц ресурса для удовлетворения запроса). При этом количество доступных единиц приобретаемого ресурса модифицируется (уменьшается на величину выполненного запроса):

t_i:= t_i - | (p_j, R_i) |.

Выполнение этой операции приведет к удалению дуги (p_j, R_i), представлявшей удовлетворенный запрос.

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

Рассмотрим пример. В системе есть два процесса P1 и P2 и два потребляемых ресурса R1 и R2. Процесс P1 является производителем ресурса R1 и для производства единицы ресурса R1 запрашивает единицу ресурса R2, процесс P2 - производитель R2, причем для освобождения единицы этого ресурса ему нужно потребить единицу ресурса R1. Первоначально в системе имеется k единиц ресурса R1 и ни одной единицы ресурса R2.

Описания процессов имеют вид:

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

Предположим, что процесс P1 первым подошел к выполнению операции запроса на единицу потребляемого ресурса R2. Так как в системе существует k единиц ресурса R1, но нет ни одной доступной единицы ресурса R2, то процесс P1 не сможет выполнить освобождение единицы ресурса R1, для которого он является производителем (условия выполнения операции освобождения ресурса требуют, чтоб у процесса-производителя не было неудовлетворенных запросов). Процесс P1 блокируется перед выполнением операции освобождения ресурса (по определению заблокированного процесса - он не может выполнить ни одной операции, изменяющей состояние системы). Процесс P1 будет заблокирован до появления в системе хотя бы одной единицы ресурса R2, который может быть произведен его производителем - процессом P2, то есть процесс P1 останется заблокированным в состоянии ожидания ресурса R2 до выполнения процессом P2 операции по освобождению единицы этого ресурса.

Процесс P2 не может быть заблокирован сразу, так как для его работы есть k единиц ресурса R1. Этот процесс, используя ресурс R1, может произвести k единиц ресурса R2, если за это время процесс P1 не использует ни одной единицы, процесс P2 перейдет в состояние ожидания (будет блокирован запросом на ресурс R1, производимый процессом P1) до освобождения процессом P1 хотя бы одной единицы запрошенного ресурса.

На рис.2.12 приведены графы потребляемых ресурсов, соответствующие следующей последовательности изменений состояния системы (S1 - начальное состояние):

_{P1 P2 P2 P2 P1 P1}

S1 ® S2 ® S3 ® S4 ® S5 ® S6 ® S7

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

В приведенном примере операции, выполняемые процессами приводят к следующим изменениям состояния системы:

S1 - начальное состояние системы до выполнения процессами запросов;

S2 - состояние системы после выполнения процессом P1 операции запроса ресурса request(R2,1);

S3 - состояние системы после выполнения процессом P2 операции запроса ресурса request(R1,1);

S4 - состояние системы после выделения процессу P2 единицы ресурса R1;

S5 - состояние системы после выполнения процессом P2 операции освобождения единицы ресурса R2 операцией release(R2,1);

S6 - состояние системы после выделения процессу P1 единицы ресурса R2;

S7 - состояние системы после выполнения процессом P1 операции освобождения единицы ресурса R1 операцией release(R1,1).

k k k

R1 R1 R1

S1: S2: S3: 1