Wzmianka o zakleszczeniu (ang. deadlock, inne tłumaczenia: blokada, impas, zastój) pojawiła się przy okazji synchronizacji procesów. W tym module, zjawisko zakleszczenie zostanie omówione w odniesieniu do zasobów systemu komputerowego. Przy odpowiednim uogólnieniu pojęcia zasób, w zakresie tym mieszczą się również zagadnienia zakleszczenia, związane z synchronizacją procesów.
Na wstępie warto przybliżyć nieformalnie, na czym to zjawisko polega. Proces w systemie, ze względu na działania innych procesów lub brak takich działań, nie może kontynuować przetwarzania, gdyż niedostępny jest jakiś niezbędny zasób. W odniesieniu do wspomnianego zakleszczenia w wyniku synchronizacji procesów — proces może czekać na jakiś sygnał synchronizujący (podniesienie semafora, zwolnienie zamka, obudzenie na zmiennej warunkowej itp.). Proces, potencjalnie udostępniający zasób (podnoszący semafor, zwalniający zamek itp.), z podobnych powodów może również zostać zablokowany i nie wykonać oczekiwanej operacji. Jeśli w ten sposób pewna grupa procesów blokuje się wzajemnie, to mamy do czynienia z zakleszczeniem.
Wykład rozpoczyna się od przypomnienia klasyfikacji zasobów systemu (odzyskiwalne i nieodzyskiwalne). Następnie omawiane są warunki konieczne wystąpienia zakleszczenia oraz ich interpretacje w kontekście obu rodzajów zasobów. Dalej omawiana jest grafowa reprezentacja stanu systemu, ułatwiająca jego analizę pod kątem zjawisk związanych z zakleszczeniem. Na końcu omawiane są zdarzenia w systemie istotne dla analizy zakleszczenia, na bazie których sformułowana jest definicja zakleszczenia.
Model systemu na potrzeby analizy problemu zakleszczenia obejmuje procesy i zasoby. Zasób, dokładniej jego rodzaj lub typ, może być reprezentowany przez wiele jednorodnych jednostek, np. pamięć jako zasób może być reprezentowana w formie jednostek zwanych stronami, paragrafami, bajtami, zależnie od sposobu przydziału (alokacji). Traktowanie jednostek jako jednorodne lub różnorodne (jednostki różnych typów zasobów) zależy czasami do sposobu wykorzystania zasobu przez proces. Jeśli w systemie są dwie różne drukarki, np. laserowa, umożliwiający tylko wydruk czarno-biały oraz atramentowa, drukująca kolorowo, to tylko od oczekiwań procesów lub użytkowników zależy, czy są to jednorodne, czy różnorodne egzemplarze. Jeśli procesy żądają po prostu wydruku, niezależnie od jakości i kolorów, egzemplarze można traktować jako jednorodne. Jeśli natomiast pojawiają się żądania wydruku kolorowego, każda z tych drukarek jest innym rodzajem zasobu.
Analizując stan systemu zakłada się, że procesy kiedyś kończą swoje przetwarzanie. Istotnym pytaniem jest, co się dzieje z zasobami tych procesów po zakończeniu. W zależności od odpowiedzi na to pytanie rozróżnia się zasoby:
Przy tej okazji warto przypomnieć, że zasoby klasyfikuje się również jako współdzielone i wyłączne oraz wywłaszczalne i niewywłaszczalne. Jak się jednak okaże przy omawianiu warunków koniecznych wystąpienia zakleszczenia, problem dotyczy tylko zasobów wyłącznych i niewywłaszczalnych. Natomiast odzyskiwalność lub nieodzyskiwalność zasobów wpływa na sposób analizy stanu systemu i postępowania w rozwiązywaniu problemu zakleszczenia.
Założenie o stałej liczbie jednostek zasobów odzyskiwalnych jest konieczne w celu analizy możliwości systemu w zakresie obsługi żądań. Założenie to jest adekwatne dla typowych realiów funkcjonowania systemów komputerowych (nikt w trakcie działania systemu nie dokłada dynamicznie pamięci, czy procesora). Dynamiczne rozszerzenie dostępnych zasobów (np. dołożenie pamięci dyskowej) wymaga rekonfiguracji w związku z tym reinicjalizacji algorytmów zarządzania zasobami.
Proces może zażądać kilka jednostek zasobu w jednym zamówieniu, skierowanym do zarządcy zasobu. Można też rozważać system, w którym zamówienie ze strony procesu obejmuje jednostki zasobów różnych typów. Zarządca będzie utożsamiany z jądrem systemu operacyjnego. Po użyciu, a najpóźniej po zakończeniu swojego działania proces zwalnia te zasobu — oddaje je ponownie do dyspozycji zarządcy, który z kolei może przydzielić je innym procesom.
W stosunku do zasobów odzyskiwalnych używa się też terminu szeregowo - zwrotne (ang. serially reusable), w celu podkreślenia, że zasób może być wykorzystywany przez wiele procesów, ale nie w tym samym czasie.
W przypadku zasobów nieodzyskiwalnych warto podkreślić fakt, że ich egzemplarze są tworzone przez jakiś proces. Zasobem takim nie jest np. papier do drukarki, pomimo że ulega zużyciu. Po pierwsze — nie jest to zasób, którym w typowych systemach komputerowych zarządza system operacyjny. Po drugie — dostępność tego zasobu nie zależy w żaden sposób od bieżącego stanu jakiegokolwiek procesu. Żaden z procesów nie może go wyprodukować. W analizie zakleszczenia chodzi natomiast o ustalenie niezbędnych działań związanych z procesami, zmierzających do precyzyjnego zidentyfikowania przyczyny zakleszczenia i ewentualnego jej usunięcia lub niedopuszczenia do powstania.
Podobnie jak w przypadku zasobów odzyskiwalnych proces ubiega się o jednostki, składając zamówienie do zarządcy, albo realizując jakiś specyficzny protokół synchronizacji. Z punktu widzenia zarządcy lub innych współpracujących procesów przydział oznacza zużycie. Proces może natomiast wytworzyć jednostki danego zasobu i udostępnić je innym procesom, które tego zażądają. Na potrzeby analizy stanu zakleszczenia zakłada się, że jeśli proces, który tworzy dany zasób, nie jest zablokowany w oczekiwaniu na inne zasoby systemu, może wyprodukować nieograniczoną liczbę jednostek, czyli taką liczbę, jakiej oczekują inne procesu.
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.
Rozważmy graf składający się z wierzchołków i łuków, rozumianych jako uporządkowane pary wierzchołków. Podstawą definiowania istotnych dla zakleszczenia własności jest osiągalność wierzchołków. Wierzchołek u jest osiągalny z wierzchołka v wtedy i tylko wtedy, gdy istnieje w grafie skierowanym ścieżka rozpoczynająca się w wierzchołku v a kończąca w wierzchołku u.
Cykl w grafie oznacza, że istnieje ścieżka rozpoczynająca się i kończąca w tym samym wierzchołku, czyli jakiś wierzchołek jest osiągalny z samego siebie.
Supeł w grafie oznacza podzbiór wierzchołków, w którym każdy wierzchołek jest osiągalny z każdego innego, a jednocześnie z żadnego z tych wierzchołków nie jest osiągalny wierzchołek poza supłem. Jak łatwo zauważyć, supeł implikuje cykl.
W przedstawionym grafie jest cykl, obejmujący wierzchołki v2, v3 i v4. Nie ma tu natomiast supła, gdyż żaden wierzchołek nie jest osiągalny z wierzchołka v5, w związku z czym wierzchołek v5 nie może należeć do supła, ale wierzchołek v5 jest osiągalny z każdego innego wierzchołka.
W obu przedstawionych przykładach jest supeł. W przykładzie pierwszym obejmuje on wszystkie wierzchołki. W przykładzie drugim supeł tworzą wierzchołki v2, v3 i v4.
Przedstawiony graf reprezentuje stan systemu, w którym wystąpiło zakleszczenie. Każdy z procesów czeka na jakąś jednostkę zasobu Z1 lub Z2 , która jest zajęta przez inny proces. Nie ma jednak w systemie procesu, który mógłby się zakończyć, bo żaden nie ma wszystkich żądanych jednostek. Cechą szczególną grafu, reprezentującego ten stan jest cykl (P1 –Z1 – P2 –Z2 ).
W tym grafie występuje również supeł.
W grafie przedstawionym na slajdzie również jest cykl, obejmujący te same procesy i zasoby, co na poprzednim slajdzie. Różnica polega na tym, że występują dwie jednostki zasobu Z2, z których jedna przydzielona jest procesowi P3. Proces P3 ma zatem (na razie) przydzielone niezbędne egzemplarze (właściwie jeden egzemplarz zasobu Z2), więc być może się zakończy. Jeśli P3 niczego więcej nie zażąda i rzeczywiście się zakończy, zwolni jednostkę zasobu Z2, która będzie mogła zostać przydzielona procesowi P2. Przy takim scenariuszu, pomimo cyklu w grafie przydziału, nie dojdzie do zakleszczenia. W bieżącym stanie systemu nie można zatem stwierdzić zakleszczenia, co jednak nie wyklucza faktu, że może istnieć stan osiągalny systemu, w którym zakleszczenie wystąpi.
Kontynuując analizę poprzedniego przykładu, gdyby w trakcie przetwarzania procesu P3 okazało się, że do jego zakończenia potrzebna jest dodatkowo jedna jednostka zasobu Z1 , uzyskujemy stan przedstawiony na slajdzie. Jest to stan zakleszczenia. Interesującą własnością grafu przydziału, opisującego ten stan, jest supeł.
W grafie nie ma supła, jest tylko cykl. Proces P2 w jednym zamówieniu żąda 2 jednostek zasobu Z2. Nawet gdyby P3 się zakończył i zwolnił przydzieloną mu jednostkę zasobu Z2, i tak nie wystarczy to do zaspokojenia żądań pozostałych procesów. Wystąpiło więc zakleszczenie.
Przykład jest podobny do poprzedniego, ale proces P2 jednocześnie żąda jednostek dwóch różnych zasobów Z2 i Z3. Tak jak w poprzednim przypadku, nawet gdyby P3 się zakończył i zwolnił przydzieloną mu jednostkę zasobu Z2, i tak nie odblokuje to procesu P2, bo cały czas niedostępna jest jednostka zasobu Z3. Również występuje tu zakleszczenie.
Spostrzeżenia z poprzednich przykładów są podstawą do wyciągnięcia pewnych wniosków, prezentowanych najczęściej w formie twierdzeń.
W przypadku zasobów pojedynczych (posiadających tylko jedną jednostkę) warunkiem koniecznym i dostatecznym wystąpienia zakleszczenia jest cykl w grafie przydziału. Warto podkreślić, że ze względu na liczebność egzemplarzy dopuszczalne są w tym przypadku tylko żądania pojedyncze.
W przypadku systemu, gwarantującego natychmiastowy przydział, gdy analizowany stan jest zupełny, supeł w grafie przydziału jest warunkiem dostatecznym (ale nie koniecznym ) zakleszczenia.
W przypadku zasobów, posiadających kilka jednorodnych egzemplarzy, przydzielanych natychmiastowo w wyniku pojedynczych żądań, warunkiem koniecznym i dostatecznym zakleszczenia jest supeł w grafie przydziału. Cykl w tym przypadku jest tylko warunkiem koniecznym, co wynika z faktu, że jest warunkiem koniecznym powstania supła.
Konstrukcja grafu zasobów nieodzyskiwalnych jest niemal taka sama jak w przypadku grafu zasobów odzyskiwalnych. Różnica w stosunku do grafu zasobów odzyskiwalnych sprowadza się do interpretacji krawędzi, konkretnie krawędzi skierowanej od wierzchołka zasobu do wierzchołka procesu. Krawędź ta — nazywana krawędzią produkcji — oznacza, analogicznie do przypadku zasobu odzyskiwalnego, możliwość uwolnienia jednostki zasobu, co w tym przypadku interpretowane jest jako utworzenie takiej jednostki. W związku z tym krawędź produkcji skierowana jest od wierzchołka zasobu, a nie od kropki, reprezentującej jego egzemplarz. Poza tym, od zasobu mogą wychodzić krawędzie skierowane do różnych procesów, gdyż ten sam zasób może mieć wielu producentów. W systemie z zasobami odzyskiwalnymi też było to możliwe, jednak krawędzie wychodziły od różnych kropek, gdyż egzemplarz używany był w trybie wyłącznym.
W przypadku dostępu do zasobów nieodzyskiwalnych występują te same zdarzenia, które wyszczególnione zostały dla zasobów odzyskiwalnych. Różnica dotyczy jednak kontekstu zachodzenia tych zdarzeń. W przypadku zasobów nieodzyskiwalnych proces nabywający nie musi ich produkować (ani produkujący nabywać), podczas gdy w przypadku zasobów odzyskiwalnych po nabyciu jednostek przez proces oczekiwało się ich zwolnienia. W przypadku zasobów odzyskiwalnych zdarzenie d zachodziło zatem na ogół w następstwie zdarzenia a w tym samym procesie. W przypadku zasobów nieodzyskiwalnych odpowiadające sobie zdarzenia a i d będą zachodzić na ogół w różnych procesach.
W systemie z zasobami zużywalnymi zrealizowanie zamówienia oznacza usunięcie jednostki zasoby, czyli kropki reprezentującej tę jednostkę w grafie. Jeśli chodzi o tworzenie, to ograniczeniem jest przypadek, gdy proces tworzący czeka na realizację własnego zamówienia.
Przykład pokazuje współpracę dwóch procesów za pośrednictwem zasobu nieodzyskiwalnego Z1, który można utożsamiać np. z semaforem uogólnionym. Proces P2 potencjalnie podnosi ten semafor. Podniesienie o 1 jest pierwszym zdarzeniem w systemie. Drugim zdarzeniem jest próba opuszczenia go o 2, co powoduje zablokowanie procesu P1. Następnie następuje podniesienie o 2 (oczywiście przez proces P2), co umożliwia nabycie (czyli rzeczywiste opuszczenie) przez proces P1.
Analiza graf przydziału zasobów nieodzyskiwalnych jest trudniejsza, niż w przypadku zasobów odzyskiwalnych. Chociaż można wskazać pewne własności, które umożliwiałyby wykrycie np. stanu zakleszczenia, dotyczą one szczególnych przypadków. Trudno np. rozważać system z zasobami pojedynczymi. Jedyną sensowną metodą jest redukcja grafu przydziału, co zostanie przedstawione w następnym module. Ale i takie podejście nie zawsze gwarantuje precyzyjne określenia rzeczywistego stanu.
W przedstawionym przykładzie procesy P3 i P4 są zablokowane ze względu na niedostępność jednostek odpowiednio zasobu Z3 i Z4. Jednostki tych zasobów mogą zostać wyprodukowane odpowiednio przez procesy P1 i P2 pod warunkiem odblokowania tych procesów. Dalszy przebieg przetwarzania zależy od kolejności zdarzeń w systemie lub decyzji zarządcy zasobów. Przydzielając jednostkę zasobu Z1 procesowi P1 a jednostkę zasobu Z2 procesowi P2 (lub odwrotnie), system wchodzi w stan zakleszczenia, niezależnie od tego czy zasoby Z1 i Z2 są odzyskiwalne, czy nie. Przydzielenie jednostek obu zasobów jednemu z procesów doprowadzi do zakleszczenia drugiego. Na przykład, jeśli P1 uzyska jednostki obu zasobów wyprodukuje Z3, co odblokuje P3, a dalej umożliwi wyprodukowanie jednostki zasobu Z1. Dla P2 zabraknie jednak jednostki zasobu Z2. W przypadku zasobów odzyskiwalnych, odpowiednie jednostki zostałyby po prostu zwolnione po zakończeniu procesów — jednostka zasobu Z2 wróciłaby wówczas do systemu. Zgodnie z definicją zakleszczenia, każdy z procesów da się odblokować (nie ma więc zakleszczenia), ale odblokowanie P1 powoduje zakleszczenie P2 i P4, a odblokowanie P2 powoduje zakleszczenie P1 i P3.
Wyszczególnione własności podobne są do tych, które omówione zostały dla zasobów odzyskiwalnych.