Graf przydziału zasobów (ang. system resource-allocation graph) bardzo dobrze nadaje się do opisywania zakleszczeń. Składnikami tego skierowanego grafu są [1]:

  1. wierzchołki W, składające się z węzłów:

  2. krawędzie K, które dzielimy na:

Ponadto zbiór procesów P na grafie przedstawia się w postaci kółek, zaś zbiór typów zasobów Z w postaci prostokątów. Każdy z typów zasobów Zy może mieć więcej niż jeden egzemplarz, zaznaczany jako kropka w prostokącie zasobu. Podczas gdy krawędź zamówienia dochodzi tylko do boku prostokąta zasobu, krawędź przydziału rozpoczyna się od konkretnego egzemplarza (czytaj kropki) typu zasobu wewnątrz prostokąta. Ilustruje to rysunek 5.3.

[Graf]

Rys. 5.3. Graf przydziału zasobów [1]

Sposób działań systemu odpowiadających zmianom krawędzi jest następujący:

  1. Zamówienie przez proces Px zasobu Zy powoduje pojawienie się krawędzi zamówienia.
  2. Realizacja zamówienia powoduje zamianę krawędzi zamówienia w krawędź przydziału.
  3. Brak jakiejkolwiek krawędzi oznacza, że proces zwolnił już niepotrzebny mu zasób.

Czytając o grafie przydziału zasobów, na pewno zastanawiacie się: co to ma wspólnego z zakleszczeniami? Jeśli graf zawiera cykle (pętle) może dojść do zakleszczeń, jeżeli nie zawiera cykli sytuacja taka jest niemożliwa. A czym jest cykl? Na rysunku 5.3. nie występuje żaden cykl. Jeżeli jednak wyobrazilibyśmy sobie sytuację, w której proces P3 zamawia zasób Z2 (pojawia się wtedy krawędź zamówienia P3 - Z2), to w tak zmodyfikowanym układzie występują dwa cykle:

Zakleszczeniem możemy określić sytuację, w której każdy z zasobów w cyklu ma tylko jeden egzemplarz. W przypadku natomiast, gdy któryś z zasobów w cyklu ma większą liczbę egzemplarzy niż 1 nie przesądza to o występowaniu zakleszczenia.

W przedstawionym powyżej grafie systemu, do zakleszczenia dojdzie na pewno, gdy proces P3 zechce skorzystać z zasobu Z2. Wzajemne wykluczanie to sytuacja, w której istnieje przynajmniej jeden zasób systemu, którego używa w określonym czasie tylko jeden proces.

Warunek negacji wzajemnego wykluczania byłby spełniony, a tym samym możliwe byłoby wykluczenie zakleszczenia, gdyby w systemie możliwe było stworzenie sytuacji, w której wszystkie zasoby byłyby dzielone [1]. Sytuacja taka jest jednak niemożliwa, gdyż niektóre z zasobów są niepodzielne z natury, np. skaner nie może być jednocześnie użytkowany przez kilka procesów. Warunek przetrzymywania i oczekiwania jest spełniony, gdy istnieje proces, któremu został przydzielony co najmniej jeden zasób. Ponadto proces ten oczekuje na przydział kolejnego zasobu, który jest używany przez inny proces [1].

Zapobiegniemy zakleszczeniu wtedy i tylko wtedy, gdy uda nam się dokonać negacji powyższego warunku. Musimy więc doprowadzić do sytuacji, w której proces zamawiający zasób nie posiada sam żadnych zasobów. Opiszemy pokrótce dwa protokoły realizujące takie założenie [1]:

  1. Należy umieścić wywołania funkcji systemowych, opisujących zamówienia zasobów dla procesu, za wywołaniami wszystkich innych funkcji systemu.

  2. Umożliwić procesowi zamawianie zasobów wtedy i tylko wtedy, gdy proces nie posiada żadnych zasobów (przed zamówieniem nowych zasobów proces musi oddać wszystkie zasoby, z których w danej chwili korzysta).

Podstawową wadą obu powyższych rozwiązań jest to, że wykorzystanie zasobów może być zaskakująco małe, gdyż niemożliwe będzie korzystanie z dużej części przydzielonych zasobów przez długi czas. Drugą z wad opisanych protokołów jest możliwość wystąpienia głodzenia. Proces, który chce skorzystać z "rozchwytywanego" zasobu może czekać do nieskończenie długo tylko dlatego, że zasób ten będzie ciągle w posiadaniu innego procesu. Z brakiem wywłaszczeń mamy do czynienia wtedy, gdy zasób może zostać zwolniony tylko w wyniku działań procesu, który go przetrzymuje.

Zapobieżenie wystąpieniu braku wywłaszczeń jest realizowalne jedynie w przypadku, gdy możliwe stanie się zwolnienie zasobu (niekoniecznie przez sam proces) w wyniku zakończenia działania procesu. Rozwiązanie problemu przynosi jeden z dostępnych protokołów. W protokole tym zgłoszenie przez proces zapotrzebowania na zasób, który nie może zostać procesowi przydzielony, powoduje utratę wszystkich dotychczasowych zasobów tego procesu [1] (zasoby te są niejawnie dopisywane do listy innych zasobów, na które dany proces czeka). Wznowienie procesu, nastąpi dopiero wówczas, gdy możliwe stanie się przywrócenie dawnych zasobów oraz dodanie tych, które zamawiał. Warunek czekania cyklicznego występuje wtedy i tylko wtedy, gdy istnieje zbiór procesów czekających P={P0, P1, ..., Pn}, takich że P0 oczekuje na zasób będący w posiadaniu procesu P1, P1 zaś czeka na zasób, który jest w posiadaniu procesu P2, ..., a Pn oczekuje na zwolnienie zasobu przez proces P0 [1].

Najbardziej popularnym sposobem uniknięcia czekania cyklicznego jest uporządkowanie wszystkich typów zasobów i dopilnowanie, by każdy z procesów otrzymywał te zasoby rosnąco. Przyporządkowujemy więc jednoznacznie każdemu zasobowi należącemu do zbioru Z={Z0, Z1, ..., Zi} liczbę całkowitą (w celu określenia rosnącego porządku procesów) [1]. Na początku proces może zamówić dowolną liczbę egzemplarzy wybranego typu zasobu. Potem proces może zamawiać jedynie egzemplarze tych typów, które mają większe numery. Jeśli na przykład na początku proces zamówił zasób Z2, to później musi zamawiać zasoby Zx > Z2. Należy zaznaczyć przy tym, że możliwe jest zamówienie kilku egzemplarzy tego samego typu z użyciem jednego tylko zamówienia.

NASTĘPNA