Основная проблема в том, что граф ∞, недостаточно информативна при всей сложности (чтобы найти причины тупика и блокировки нужно пройти всю цепочку).

20 МОДЕЛЬ СИСТЕМЫ С ПОВТОРНО ИСПОЛЬЗУЕМЫМИ РЕСУРСАМИ (ГРАФ ПОВТОРНО ИСПОЛЬЗУЕМЫХ РЕСУРСОВ).

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

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

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

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

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

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

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

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

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

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

SR = (N, E),

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

N = π ρ

(π = { p1 , p2 , ..., pn}- конечное множество вершин, представляющих процессы в ВС,

ρ = { R1 , R2 , ..., Rm} - множество вершин, соответствующих SR-ресурсам ВС; π ∩ ρ = ), а E - множество дуг графа:

E ( π × ρ ) (ρ × π),

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

♦Ri - вершина, представляющая повторно используемый ресурс Ri ρ, имеет пометку - пару (ci, ti ), где ci - емкость данного ресурса, а ti - количество единиц ресурса, доступных для распределения (свободных) в данный момент;

♦pj - вершина, представляющая процесс pj π в системе;

34

♦каждый запрос, выполняемый процессом pj π на ресурс Ri ρ должен удовлетворять ограничению:

| ( Ri, pj ) | + | ( pj , Ri ) | ≤ ci,

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

♦ в общей сложности в системе для каждого ресурса Ri ρ может быть сделано не более чем ci назначений, то есть

n

∑ | ( Ri, pj ) | ≤ ci j = 1

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

n

| ( pj , Ri ) | + ∑ | ( Ri, ph ) | ≤ ci h = 1

или

| ( pj , Ri ) | ≤ ti

n

(где ti = ci - ∑ | ( Ri, ph ) | ). h = 1

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

process P1 ; begin ...

request ( R, 1) ;

...

request ( R, 1) ;

...

release ( R, 1) ;

...

release ( R, 1) ;

...

end.

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

35

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

21. МОДЕЛЬ СИСТЕМЫ С ПОТРЕБЛЯЕМЫМИ РЕСУРСАМИ (ГРАФ ПОТРЕБЛЯЕМЫХ РЕСУРСОВ).

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

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

CR = (N, E),

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

N = π ρ

(π = { p1 , p2 , ..., pn}- конечное множество вершин, представляющих процессы в ВС, ρ = { R1 , R2 , ..., Rm} - конечное множество вершин, соответствующих CR-ресурсам ВС; π ∩ ρ = ), а E - множество дуг графа:

E ( π × ρ ) (ρ × π),

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

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

pj - вершина, представляющая процесс pj π в системе;

для каждого ресурса Ri ρ существует непустое множество процессовпроизводителей этого ресурса π (Ri) π и граф ПР содержит дугу производителя (

процессом pj π, но пока не удовлетворенный запрос на k единиц потребляемого

ресурса Ri ρ.

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

pj

Sl → Sk .

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

| ( pj , Ri ) | ≤ ti

(то есть в системе есть достаточное количество единиц ресурса для удовлетворения

36

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

ti := ti - | ( pj , Ri ) |.

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

Операция освобождения release (Ri, r) процессом pj r единиц ресурса Ri может быть выполнена тогда и только тогда, когда процесс не имеет неудовлетворенных запросов (в графе ПР нет дуг, исходящих из вершины, представляющей данный процесс) и процесс pj

является производителем этого ресурса (pj π(Ri)).

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

R2.

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

Предположим, что процесс 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 хотя бы одной единицы запрошенного ресурса.

37