21. Модель системы с потребляемыми ресурсами (граф потребляемых ресурсов). Примеры.

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

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

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

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

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

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

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

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

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

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

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

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

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

CR = (N, E),

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

N =   

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

E  (    )  (  ),

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

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

• p_j - вершина, представляющая процесс p_j   в системе;

• для каждого ресурса R_i   существует непустое множество процессов-производителей этого ресурса  (R_i)   и граф ПР содержит дугу производителя ( R_i, p_j ) для каждого p_j   (R_i) по всем R_i  ;

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

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

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

Процесс 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.