Sr-7-wyk-2.0-Slajd29

From Studia Informatyczne

Graf przydziału zasobów

Graf przydziału zasobów


Do ilustracji i analizy zakleszczeń można posłużyć się tzw. grafami przydziału zasobów (ang. system resorce-allocation graph ). Zbiór wierzchołków takiego grafu podzielony jest na dwa zbiory: zbiór procesów oraz zbiór zasobów. Łuk, który biegnie od procesu Pi do zasobu Zj oznacza że proces chce użyć tego zasobu i czeka na niego. Jeżeli natomiast łuk biegnie od zasobu Zj do procesu Pi , oznacza to, że zasób został przydzielony procesowi. Stąd też krawędzie tego typu zwaną są odpowiednio: krawędzią zamówienia (ang. request edge ) oraz krawędzią przydziału (ang. assignment edge ).

Na podstawie grafu przydziału zasobów można wykazać, że jeżeli w grafie nie występują cykle, to w systemie reprezentowanym przez ten graf nie ma zakleszczeń. W przeciwnym wypadku może pojawić się zakleszczenie.

W grafie przydziału zasobów na rysunku dla uproszczenia zasoby oznacza się prostokątami, a procesy kółkami. Egzemplarze zasobów rozróżnia się dodatkowo kropkami wewnątrz prostokątów (zasobów); gdy proces wysyła zamówienie na zasób, oznaczamy to krawędzią zamówienia dochodzącą do brzegu prostokąta, natomiast gdy proces otrzymuje przydział, to jest to konkretny egzemplarz zasobu i krawędź przydziału rozpoczyna się od kropki (egzemplarza zasobu).


<< Poprzedni slajd | Spis treści | Następny slajd >>