Deadlock

Deadlock to zakleszczenie, w którym dwie transakcje wzajemnie blokują zasoby, których potrzebują do dalszego działania.

Deadlock jako cykl wzajemnych blokad

Deadlock, czyli zakleszczenie, występuje wtedy, gdy co najmniej dwa równoległe procesy lub transakcje zatrzymują się, ponieważ każdy z nich oczekuje na zasób zajmowany przez inny. W najprostszym przypadku transakcja A blokuje zasób X i czeka na zasób Y, a transakcja B blokuje zasób Y i czeka na zasób X. Żadna z nich nie może przejść do następnego kroku, ponieważ warunek potrzebny do kontynuowania zależy od zakończenia drugiej transakcji.

Zakleszczenie różni się od krótkiego oczekiwania na blokadę. Przy zwykłym blokowaniu jeden proces wykonuje pracę i po jej zakończeniu zwalnia zasób, więc drugi może kontynuować działanie. W deadlocku oczekiwanie tworzy zamknięty cykl. Sam upływ czasu nie rozwiązuje problemu, chyba że system ma mechanizm wykrywania zakleszczeń i przerywania jednej z uczestniczących operacji. Zasobami mogą być między innymi rekordy danych, strony tabel, pliki, uchwyty systemowe, obiekty synchronizacji albo urządzenia współdzielone przez procesy.

Jak powstaje zakleszczenie w równoległym przetwarzaniu

Do powstania deadlocku potrzebne jest jednoczesne spełnienie kilku warunków. Zasób musi być używany na wyłączność albo w sposób, który ogranicza dostęp innych procesów. Proces posiada już przynajmniej jeden zasób i oczekuje na kolejny. Zasobu nie można odebrać siłą bez przerwania lub wycofania pracy właściciela. Ponadto musi istnieć cykl oczekiwania, w którym każdy uczestnik czeka na zasób należący do następnego uczestnika.

W systemie bazodanowym typowy przebieg może wyglądać następująco: pierwsza transakcja modyfikuje wiersz oznaczony jako A, a następnie próbuje zmienić wiersz B. W tym samym czasie druga transakcja modyfikuje wiersz B i próbuje zmienić wiersz A. Jeżeli obie transakcje utrzymują blokady do czasu zatwierdzenia albo wycofania, każda z nich czeka na zwolnienie zasobu zablokowanego przez drugą. Podobny mechanizm może wystąpić przy kilku tabelach, różnych typach blokad lub pośrednich zasobach używanych przez indeksy.

Ryzyko rośnie, gdy operacje trwają długo, obejmują wiele rekordów albo uzyskują blokady w różnej kolejności. Problem może też wynikać z niejednolitego kodu: jedna ścieżka programu aktualizuje najpierw tabelę lub obiekt A, a druga najpierw obiekt B. Niewłaściwie dobrany poziom izolacji transakcji może zwiększać zakres i czas utrzymywania blokad, ale sama obecność blokad nie oznacza jeszcze deadlocku.

Wykrywanie, przerwanie i odróżnianie od zawieszenia

System zarządzający współbieżnością może wykrywać cykle w grafie oczekiwania. W takim grafie wierzchołki reprezentują transakcje lub procesy, a krawędź wskazuje, że jeden uczestnik czeka na zasób utrzymywany przez innego. Cykl oznacza możliwość wystąpienia zakleszczenia. Po wykryciu system zwykle wybiera jedną transakcję jako ofiarę, wycofuje ją lub przerywa, zwalniając posiadane zasoby. Pozostałe operacje mogą wtedy kontynuować pracę.

Wycofanie transakcji nie zawsze oznacza trwałą awarię aplikacji. Program musi jednak prawidłowo obsłużyć błąd i zdecydować, czy ponowić całą operację. Ponowienie powinno obejmować pełny zakres transakcji, a nie tylko ostatnie polecenie, ponieważ wcześniejsze działania mogły zostać cofnięte. W praktyce stosuje się ograniczoną liczbę prób, opóźnienie między próbami oraz logowanie identyfikatora transakcji, czasu trwania, kolejności operacji i zasobów objętych blokadą.

Deadlock należy odróżnić od blokady, która trwa długo, lecz ma przyczynę poza cyklem, na przykład od bardzo wolnej transakcji albo procesu, który nie zwolnił zasobu z powodu błędu. Podobne objawy może dawać przeciążenie procesora, oczekiwanie na operacje dyskowe, wyczerpanie pamięci lub niedostępność urządzenia. Wiarygodna diagnoza wymaga porównania czasu rozpoczęcia operacji, komunikatów systemowych, stanu procesów i informacji o oczekiwaniu na zasoby. Sam brak odpowiedzi interfejsu nie potwierdza deadlocku.

Zapobieganie niespójnej kolejności blokowania

Najczęściej stosowaną metodą ograniczania ryzyka jest ustalenie jednej kolejności pozyskiwania zasobów. Jeżeli wszystkie ścieżki wykonują operacje na obiektach w kolejności A, potem B, nie powstaje cykl wynikający wyłącznie z odwrotnego porządku blokowania. Transakcje powinny też być możliwie krótkie: należy ograniczać zakres pracy wykonywanej między rozpoczęciem a zatwierdzeniem oraz unikać oczekiwania na działania niezwiązane z transakcją, takie jak interakcja użytkownika lub powolna operacja sieciowa.

Pomocne jest przeglądanie zapytań i planów wykonania, właściwe indeksowanie oraz ograniczanie liczby rekordów objętych modyfikacją. Indeks nie usuwa deadlocku automatycznie, ale może skrócić wyszukiwanie i zmniejszyć liczbę blokowanych zasobów. W kodzie wielowątkowym podobną rolę odgrywa konsekwentne porządkowanie blokad, zwalnianie ich w każdej ścieżce zakończenia oraz unikanie zagnieżdżonych mechanizmów synchronizacji bez jasno określonej hierarchii.

Przy analizie komputera, na którym aplikacja regularnie przestaje odpowiadać, warto ustalić, czy problem dotyczy jednego programu, konkretnej operacji czy całego systemu. Należy zebrać moment wystąpienia zdarzenia, powtarzalne warunki, komunikaty aplikacji oraz informacje o obciążeniu procesora, pamięci i dysku. Warszawskie Pogotowie Komputerowe zajmuje się profesjonalną naprawą laptopów, komputerów PC i ich podzespołów, dlatego w przypadku objawów towarzyszących problemom programowym można rozpocząć od sprawdzenia ogólnego stanu sprzętu i środowiska pracy, bez utożsamiania każdego zawieszenia z deadlockiem.