cz2 str2

GRAF PRZYDZIAŁU ZASOBÓW

Graf skierowany opisujący blokady..

Zbiór wierzchołków W składający się z podzbiorów:

P={ Pi, P2, •.., P_n} podzbiór procesów,

Z={ Zi, Z₂, ..., Z_ra} podzbiór typów zasobów.

Zbiór krawędzi skierowanych K:

Pi -> Zj oznacza, że proces Pj zamówił zasób Zj,

Z; -> Pj oznacza, źe zasób Z\ został przydzielony procesowi Pj.

z₄

Przykład grafu (oznaczenia na rys.: proces - O , zasób - □).

Warunek konieczny wystąpienia blokowania:

graf przydziału zasobów zawiera cykl.

W przypadku, gdy każdy typ zasobów zawiera tylko jeden egzemplarz, to cykl zawarty w grafie przydziału zasobów jest warunkiem koniecznym i dostatecznym.

Przykład grafti z blokadą

Przykład grafu z cyklem, ale bez blokady