Zakleszczenie
Z Wikipedii
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ć. Gracze zdobyli pewne unikatowe warunki niezbędne do wykonania kolejnego ruchu, ale żaden nie ma wszystkich i gra nie może być kontynuowana.
Pojęcie zakleszczenia jest ważne i powszechnie stosowane w informatyce.
[edytuj] 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.
W ogólności do zakleszczenia na pewno dojdzie, jeśli spełnione będą cztery warunki:
- 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, o co najmniej jeden, od liczby maksymalnych równoległych dostępów do zasobu, które mogą zostać obsłużone;
- 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;
- Cykliczne oczekiwanie - zadania w taki sposób żądają zasobów, że powstaje cykliczny graf skierowany;
- 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).
[edytuj] Zapobieganie, unikanie i likwidowanie zakleszczeń
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.
- Wzajemne wykluczenie - nie jest możliwe całkowite zapobieżenie tej sytuacji, ponieważ obsługa urządzeń w większości przypadków realizowana jest w trybie wyłączności.
- 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. 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 - 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)
- 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, jest wywłaszczenie zadania bez kończenia go.
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. Przykładowym rozwiązaniem tego problemu może być deklarowanie przez uruchamiany program maksymalnej ilości zasobów określonego typu jakie może on zaalokować i przy wysunięciu żądania przydziału przez zasób - sprawdzenie, czy system po obsłużeniu tego przydziału będzie mógł normalnie funkcjonować.
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.
