Zakleszczenie

Proste zakleszczenie dwóch zadań

Zakleszczenie, blokada wzajemna (ang. deadlock) – sytuacja, w której co najmniej dwie różne akcje czekają na siebie nawzajem, więc żadna nie może się zakończyć.

W przetwarzaniu współbieżnym pojęcie zakleszczenia pojawia się, kiedy żaden z procesów nie napotyka warunków do przejścia do innego stanu (jak jest to opisane w automacie skończonym), przy czym kanały komunikacyjne pozostają puste.

Powstawanie zakleszczenia

Problem zakleszczenia występuje w wielozadaniowych systemach operacyjnych, gdzie wiele zadań w tym samym czasie konkuruje o wyłączny dostęp do zasobów. Zjawisko jest również ważne w systemach zarządzania na przykład bazami danych. W pierwszym przypadku zasobami są struktury danych (często powiązane z fizycznymi urządzeniami takimi jak na przykład karta dźwiękowa lub magistrala), w drugim przypadku zasobami są obiekty bazy danych, na przykład relacje (tabele) lub poszczególne krotki. Zakleszczeniu mogą ulec zadania takie jak na przykład procesy lub wątki a w bazach danych poszczególne transakcje. Przykładem zakleszczenia w świecie fizycznym jest korek drogowy na skrzyżowaniu, z którego żaden samochód nie może zjechać, gdyż jest blokowany przez pozostałe.

Najprostsze zakleszczenie powstaje dla dwóch procesów. Każdy z nich utrzymuje w swojej wyłącznej dyspozycji pewien zasób i jednocześnie czeka na zwolnienie innego zasobu zajętego przez drugi z procesów. Druga możliwość wystąpienia jest taka, iż dwa lub większa liczba procesów czeka na zwolnienie zasobu w łańcuchu cyklicznym.

Do zakleszczenia dojdzie, jeśli spełnione będą cztery warunki:

1. Wzajemne wykluczenie - w danym czasie tylko jedno zadanie może korzystać z danego zasobu; w ogólności warunkiem do zakleszczenia jest też sytuacja w której do zasobu jest możliwy jednoczesny równoległy dostęp wielu zadań, lecz liczba jednocześnie zadanych żądań do zasobu jest większa od liczby maksymalnych równoległych dostępów do zasobu, które mogą zostać obsłużone;
2. Trzymanie zasobu i oczekiwanie - zadanie utrzymuje jeden z zasobów, ale do ukończenia pracy niezbędne jest także zaalokowanie zasobów innego typu;
3. Cykliczne oczekiwanie - zadania w taki sposób żądają zasobów, że powstaje cykliczny graf skierowany;
4. Brak wywłaszczania z zasobu - zadania dobrowolnie nie rezygnują z przydzielonych im zasobów; zwolnienie zasobów możliwe jest po zakończeniu zadania.

Jeśli system nie dysponuje żadnym mechanizmem, który może poradzić sobie z powstałą sytuacją, to następuje permanentne "zawieszenie" się zadań tworzących cykl. Możliwe jest wywłaszczenie zadania z zasobów przez system operacyjny, jednak może to powodować problemy z synchronizacją (np. wprowadzenie w stan nieprzewidziany przez projektanta).

Zapobieganie, unikanie, wykrywanie i likwidowanie zakleszczeń

W zależności od tego, czy w danym systemie doszło do zakleszczenia można podjąć trzy rodzaje akcji: zapobiegać zakleszczeniom, unikać ich oraz je wykrywać i likwidować.

Zapobieganie zakleszczeniom

Kluczowy i najważniejszy w zapobieganiu zakleszczeniom jest etap projektowania aplikacji oraz systemu.

Zakleszczenie na pewno nie wystąpi, jeśli chociaż jeden z czterech wymienionych warunków dotyczących zakleszczenia nie zostanie spełniony.

1. Wzajemne wykluczenie - usunięcie warunku wzajemnego wykluczania oznacza, iż żaden proces nie może mieć wyłącznego dostępu do zasobu. Okazuje się to niemożliwe dla zasobów, które nie korzystają ze spoolingu. Dla tych zaś, które korzystają, zakleszczenie może w dalszym ciągu zajść. Algorytmy, które pozwalają uniknąć wzajemnego wykluczenia są nazywane algorytmami nieblokującymi synchronizacji. Przeważnie nie jest możliwe zapobieżenie sytuacji wzajemnego wykluczania, ponieważ obsługa urządzeń w większości przypadków realizowana jest w trybie wyłączności;
2. Trzymanie zasobu i oczekiwanie - zadanie może rozpocząć działanie dopiero w momencie dostępności wszystkich zasobów niezbędnych do jego zakończenia lub zadanie zwalnia wszystkie zajmowane zasoby przed żądaniem tych, które potrzebują (rozwiązanie niepraktyczne). Metoda ta jest podatna na zagłodzenie, dla procesów które żądają wielu zasobów. Środkiem zaradczym może być tymczasowe zwiększanie priorytetu takiego procesu po odrzuceniu żądania przydziału zasobu;

   

   Odpowiednia kolejność alokowania zasobów pozwala uniknąć zakleszczenia

3. Cykliczne oczekiwanie - ustalenie określonej kolejności w jakiej muszą wystąpić żądania przydzielania konkretnych zasobów (zasoby są numerowane, indeksowane lub priorytetyzowane co określa jedyną możliwą kolejność ich zajmowania). Zapobieganie cyklicznemu oczekiwaniu pozwala procesom na oczekiwanie na zasoby, zapewniając jednakże, iż nie ma ono charakteru cyklicznego. Jednym z podejść jest przypisanie pierwszeństwa do każdego z zasobów i zmuszenie procesów do zajmowania zasobów zgodnie z wzrastającym pierwszeństwem. Jeśli proces zajmuje zasoby i najwyższym priorytetem tych zasobów jest m, to proces ten nie może żądać dostępu do innych zasobów o priorytecie niższym niż m. Implikuje to fakt, iż zasoby będą przyznawane w konkretnej, niecyklicznej kolejności. Drugim podejściem jest wyrażenie zgody na zajmowanie tylko jednego zasobu przez proces; jeśli proces żąda innego zasobu, musi wcześniej zwolnić aktualnie zajmowany. Niespełnienie warunku cyklicznego oczekiwania zapewniają algorytmy, które zawierają wyłączanie przerwań podczas sekcji krytycznych, wykorzystujące hierarchię do ustalenia częściowego porządku zasobów oraz wykorzystujące rozwiązanie Dijkstry (problem ucztujących filozofów);
4. Brak wywłaszczania zasobu – rozwiązaniem najprostszym jest arbitralne zakończenie zadania; przy tym rozwiązaniu system powinien kierować się "minimalizowaniem strat" np. przez wybieranie takich procesów, które mają bardzo krótki czas uruchomienia; znacznie trudniejsze, ze względu na spójność struktur danych związanych z zasobem. Algorytmami, które pozwalają na wywłaszczanie są blokuj-zwolnij, czekaj-zwolnij oraz algorytmy optymistycznej kontroli zbieżności.

Unikanie zakleszczeń

Uniknięcie zakleszczenia może być realizowane, jeśli w systemie operacyjnym, nadzorującym pracę procesów, zaimplementowany jest odpowiedni mechanizm dostępu do zasobów. Oznacza to, iż pewna informacja o procesie winna być dostępna przed przydzieleniem zasobu. Dla każdego żądania dostępu do zasobu system sprawdza czy przyznanie zasobu powodować będzie stan niebezpieczny, tzn. taki, który może powodować powstanie zakleszczenia. System przyznaje zasoby tylko w przypadku, gdy implikować to będzie stan bezpieczny. System winien być w stanie przewidzieć czy następny stan będzie bezpiecznym czy też niebezpiecznym. Jedynym znanym algorytmem, który jest używany do uniknięcia zakleszczenia jest algorytm bankiera, który wymaga ażeby użycie limitów zasobów było znane z wyprzedzeniem. Problemem jest fakt, iż, wiele systemów nie udostępnia informacji kiedy każdy z procesów będzie żądał zasobów. Powoduje to sytuację, w której uniknięcie zakleszczenia jest często niemożliwe.

Istnieją jeszcze dwa inne algorytmy unikania zakleszczeń, tj. Czekaj/Giń oraz Rań/Czekaj. W obu algorytmach wyróżnia się proces starszy S oraz młodszy M. Wiek procesu może być określany poprzez znacznik czasowy przyznawany w trakcie tworzenia procesu. Mniejsze znaczniki sprawiają, iż procesy są starsze, z kolei większe oznaczają młodsze procesy.

	Czekaj/Giń	Rań/Czekaj
S wymaga zasobów przetrzymywanych przez M	S czeka	M umiera
M wymaga zasobów przetrzymywanych przez S	M umiera	M czeka

Należy zaznaczyć, iż proces może być w stanie niebezpiecznym, ale nie spowoduje w rezultacie zakleszczenia. Idea stanów bezpiecznych/niebezpiecznych odnosi się jedynie do możliwości wejścia systemu w stan zakleszczenia lub nie. Przykładowo proces wymagający zasobów A mógłby spowodować stan niebezpieczny, jednakże zwolnienie B mogłoby zapobiec cyklicznemu czekaniu – system jest w stanie niebezpiecznym, choć nie doszło do zakleszczenia.

Wykrywanie i likwidowanie zakleszczeń

Często występuje sytuacja, w której zarówno unikanie, jak i zapobieganie zakleszczeniom nie może być użyte. Wykrycie zakleszczenia oraz zrestartowanie procesów może również prowadzić do usunięcia zakleszczeń. Jest to stosunkowo łatwe do wykonania od momentu zajęcia przez procesy zasobów lub na podstawie planera systemu operacyjnego.

Wykrywanie możliwości wystąpienia zakleszczenia przed jego pojawieniem jest znacznie trudniejsze, oraz w rzeczywistości często nierozstrzygalne, gdyż problem stopu może być rozpoznany jako scenariusz zakleszczenia. Mimo tego, w pewnych specyficznych rodzajach środowisk, korzystając z odpowiednich technik, rozpoznanie zakleszczeń może być rozstrzygalne. Ogólnie rzecz biorąc nie jest możliwym rozróżnienie algorytmów, które jedynie czekają na zestaw określonych okoliczności do wystąpienia zakleszczenia oraz tych, które nigdy się nie kończą z powodu zakleszczenia. Jednakże system kontrolujący procesy i zasoby może mieć zaimplementowaną politykę ochrony, w przypadku, gdy do zakleszczenia w systemie już doszło. Do realizowania tego typu kontroli mogą być wykorzystywane programowe, bądź sprzętowe systemy watchdog czy protokół pułapu priorytetu, które monitorują stan uruchomionych procesów i w przypadku braku reakcji uruchamiają, odpowiednie dla danej sytuacji, procedury.

Zakleszczenia rozproszone

Zakleszczenia rozproszone mogą występować w systemach rozproszonych, gdzie wykorzystywane są transakcje rozproszone lub kontrola zbieżności. Każde z zakleszczeń rozproszonych może być wykrywane budując globalny graf typu wait-for z lokalnych grafów tego typu bądź poprzez algorytmy rozproszone.