Loading AI tools
Z Wikipedii, wolnej encyklopedii
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.
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:
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).
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ć.
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].
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.
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 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.