Blokada (zakleszczenie) w programie: geneza, wykrywanie i zapobieganie

Zakleszczenie (ang. deadlock) jest pojęciem opisującym sytuację, w której co najmniej dwie różne akcje czekają na siebie nawzajem, więc żadna nie może się zakończyć. Zakleszczenie może być zobrazowane przykładem ludzi rysujących wykresy. Dwie osoby pragną narysować wykres, do czego jest potrzebna linijka i ołówek. W momencie, kiedy jedna z nich zabierze ołówek, druga zaś linijkę dochodzi do sytuacji konfliktowej. Pierwsza osoba potrzebuje linijki, drugi zaś ołówka. Oba żądania nie mogą być spełnione – powstaje zakleszczenie, które to zazwyczaj jest kłopotliwe, gdyż nie ma pewnych i zawsze sprawdzonych rozwiązań, ażeby go uniknąć.

W telekomunikacji 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.

Jednakże pojęcie zakleszczenia jest szczególnie ważne i powszechnie stosowane w informatyce.

Problem zakleszczenia występuje w wielozadaniowych systemach operacyjnych, gdzie wiele zadań w tym samym czasie konkuruje o wyłączny dostęp do zasobów. 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 równorzędnym, 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.

W ogólności do zakleszczenia na pewno dojdzie, jeśli spełnione będą cztery warunki:

1. Wzajemne wykluczenie - w danym czasie tylko jedno zadanie może z niego korzystać; 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).

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
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 konkretnej, niecyklicznej kolejności. 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. Wywłaszczanie 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.

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.