Jednoczesne zaistnienie wszystkich warunków koniecznych nie musi oznaczać wystąpienia zakleszczenia. Niespełnienie natomiast któregoś z tych warunków oznacza brak ryzyka zakleszczenia, co jest podstawą metod zapobiegania zakleszczeniom.
Graf przydziału zasobów jest wygodną formą graficzną reprezentacji stanu sytemu na potrzeby analizy zjawisk związanych z zakleszczeniem. Poza tym można wykazać na podstawie pewnych własności tego grafu, że wystąpił pewien szczególny stan, np. właśnie stan zakleszczenia lub zagrożenia, co w połączeniu z powszechnie znanymi algorytmami analizy grafów ułatwia wykrywanie takich stanów.
Graf przydziału zasobów odzyskiwalnych (krótko graf zasobów odzyskiwalnych, graf przydziału lub graf alokacji) jest to skierowany graf dwudzielny, w którym jedną grupę wierzchołków tworzą procesy, a drugą zasoby. Krawędzie skierowane od procesów do zasobów reprezentują zamówienia, a krawędzie skierowane od zasobów (ich jednostek) do procesów reprezentują przydział.
Przedstawiony graf reprezentuje stan systemu z dwoma procesami P1 i P2 oraz dwoma rodzajami zasobów: Z1 i Z2 . Zasób Z1 składa się z jednego egzemplarza a zasób Z2 z dwóch. Krawędź skierowana od jednostki zasobu Z2 do wierzchołka procesu P1 oznacza, że jednostka ta przydzielona jest procesowi P1. Podobnie druga jednostka zasobu Z2 przydzielona jest procesowi P2. Jedyna jednostka zasobu Z1 przydzielona jest procesowi P2. Z faktu, że żadna krawędź skierowana nie wychodzi z wierzchołka procesu P2, wynika, że nie potrzebuje on innych zasobów do kontynuacji przetwarzania. Krawędź skierowana od wierzchołka proces P1 do wierzchołka zasobu Z1 oznacza zamówienie procesu P1 na jednostkę zasobu Z1. Ponieważ nie ma wolnej jednostki zasobu Z1, proces P1 musi czekać na jej zwolnienie.
Jak wspomniano przy omawianiu współbieżności, stan systemu zmienia się pod wpływem zdarzeń, związanych z działaniem procesów. Z punktu widzenia zagadnień związanych z realizacją dostępu do zasobów istotne są zdarzenia: zamówienia jednostki zasobu, nabycia zamówionej jednostki i zwolnienia nabytej jednostki. Zamówienie oraz zwolnienie są zdarzeniami, które wynikają z przetwarzania procesu. Nabycie jest zdarzeniem w procesie Pi , którego wystąpienie uwarunkowane jest dostępnością jednostek zasobu. Brak wolnych jednostek uniemożliwia zajście tego zdarzenia i powoduje wstrzymanie (zablokowanie) procesu.
Skutkiem wystąpienia zdarzenia w systemie jest zmiana stanu i związana z tym transformacja grafu przydziału.
Jeśli zawsze zamawiana jest jedna jednostka zasobu, w grafie zasobów odzyskiwalnych występuje zawsze pojedyncza krawędź zamówienia. Mówi się wówczas o żądaniach pojedynczych.
W przypadku żądania kilku jednostek w jednym zamówienia możne wystąpić kilka równoległych krawędzi zamówienia.
W pierwszym z przedstawionych stanów dopuszczalne jest zdarzenie zwolnienia jednostek zasobów przydzielonych procesowi P2 , gdyż proces P1 jest wstrzymany ze względu na niedostępność jednostki zasobu Z1 . Zakładając, że jednostki zwalniane są pojedynczo i najpierw zwolniona zostaje jednostka zasobu Z1 , uzyskujemy następny stan reprezentowany przez kolejny graf przydziału. W stanie tym dopuszczalne są już dwa zdarzenia:
Niezależnie od tego, które z wymienionych zdarzeń zajdzie jako pierwsze, w osiągniętym stanie dopuszczalne jest drugie zdarzenie. Transformację można by więc kontynuować aż do osiągnięcia stanu zwolnienia wszystkich jednostek zasobów Z1 i Z2 , przechodząc przez różne stany pośrednie, zależnie od kolejności zdarzeń dopuszczalnych. Narysowanie całej takiej sieci przejść pozostawia się jako ćwiczenie.
Przedstawiony przykład obrazuje funkcjonowanie procesu w systemie z dwoma jednostkami zasobu odzyskiwalnego. Proces Pi, ubiegając się o jednostki zasobu, zmieniają swój stan. Możliwe stany procesu są następujące:
W stanie si4 proces nie może zażądać kolejnej jednostki, ponieważ przekroczyłby możliwości systemu. Może natomiast zwolnić jedną jednostkę, wracając do stanu si2. W stanie si2 również może zwolnić jedną jednostkę. W stanie si2 dopuszczalne są więc dwa zdarzenia — zwolnienie jednostki lub zamówienie następnej.
Przykład kolejny obrazuje funkcjonowanie dwóch procesów — Pi oraz Pj, rywalizujących o zasoby. Zmiany stanu procesu Pi pokazane są w poziomie, a procesu Pj w pionie. Stan systemu, na który składa się stan sik proces Pi oraz stan sjl procesu Pj, oznaczony został jako σkl.
Wobec rywalizacji dwóch procesów o zasoby pewne stany jednego procesu są nieosiągalne, jeśli określony stan osiągnął drugi proces. Na przykład: stan σ42 oznaczałby, że proces Pi ma przydzielone dwie jednostki zasobu, a Pj — jedną jednostkę, podczas gdy system dysponuje w sumie dwoma jednostkami.
Na slajdzie przedstawiona jest kontynuacja grafu przejść między stanami, przy czym dla poprawy czytelności zrobiona została „zakładka”, polegająca na powtórzeniu stanów σ02, σ12, σ22, σ32, które pojawiły się również na slajdzie poprzednim.
Na bazie rozważanego modelu przetwarzania współbieżnego zdefiniowane zostanie zakleszczenie procesu. Wcześniej jednak wymagane jest zdefiniowanie wstrzymania procesu.
Przykładem stanu systemu, w którym wstrzymany jest proces Pi jest σ32 w poprzednim przykładzie. Jedyne dopuszczalne zdarzenia w tym stanie związane są z procesem Pj , który może zwolnić przydzieloną jednostkę, albo zażądać następnej. W stanie σ41 zablokowany jest z kolei proces Pj , gdyż zażądał on pierwszej jednostki zasobu, podczas gdy obie przydzielone są procesowi Pi. Pj musi więc czekać na zwolnienie przynajmniej jednej z jednostek przez Pi.
Przykładem zakleszczenia z kolei jest stan σ33, w którym żadne zdarzenie nie jest dopuszczalne. Jest to zatem zakleszczenie obu procesów, czyli całego systemu.
Odnosząc zjawisko zakleszczenia do grafu przydziału, należy wyodrębnić pewne własności tego grafu, ułatwiające stwierdzenie stanu zakleszczenia.
Własnością systemu, która przejawia się w grafie przydziału, podlegającym analizie, jest natychmiastowość przydziału. Oznacza ona, że jeśli zamawiane egzemplarze zasobu są dostępne (wolne), to są przydzielane bez żadnej zwłoki. Stan systemu, w którym przydzielono wszystkie dostępne egzemplarze, zamówione przez procesy, określany będzie jako zupełny (ang. expedient). Graf przedstawiony na slajdzie nie reprezentuje takiego stanu, gdyż jedna z dwóch jednostek zasobu Z2 pozostaje wolna, a ubiegają się o nią dwa procesy.