Zakleszczenie (lub zakleszczenie , impas w języku angielskim) jest zjawiskiem, które może wystąpić w programowania współbieżnego . Zakleszczenie występuje, gdy konkurencyjne procesy czekają na siebie. Proces może się również spodziewać sam. Procesy zatrzymane w tym stanie są trwale zablokowane, więc jest to katastrofalna sytuacja. Mechanizmy prowadzące do zjawiska impasu były badane głównie przez Edwarda Coffmana Jr.
Sytuacja zakleszczenia zasobu może wystąpić wtedy i tylko wtedy, gdy wszystkie poniższe warunki są jednocześnie spełnione w systemie:
Te cztery stany są znane jako „warunki Coffmana” z ich pierwszego opisu w artykule Edwarda G. Coffmana Jr. z 1971 roku.
Chociaż te warunki są wystarczające, aby wywołać zakleszczenie w systemach zasobów z pojedynczą instancją, wskazują one tylko na możliwość zakleszczenia w systemach z wieloma wystąpieniami zasobów.
Konkretny przykład zakleszczenia może wystąpić, gdy dwa lekkie procesy ( angielski wątek ) próbują uzyskać dwa muteksy w innej kolejności. Na przykład z dwoma muteksami ( M1 i M2 ), dwoma lekkimi procesami ( P1 i P2 ) i następującą sekwencją operacji:
W tej sytuacji dwa lekkie procesy są trwale zablokowane.
Zakleszczeń można uniknąć, jeśli pewne informacje są znane z wyprzedzeniem podczas przydzielania zasobów. Dla każdego przydziału zasobów system sprawdza, czy wejdzie w stan „niebezpieczny”, to znaczy stan, który może spowodować zakleszczenie. System pozytywnie reaguje tylko na żądania, które prowadzą do „bezpiecznych” stanów. Aby móc zdecydować, czy następny stan będzie bezpieczny, czy nie, system musi zawsze znać liczbę i rodzaj istniejących, dostępnych i żądanych zasobów. Klasycznym algorytmem do wykrywania zakleszczeń z wyprzedzeniem jest algorytm bankiera . Wymaga to znajomości z wyprzedzeniem ograniczeń w wykorzystaniu zasobów. Jednak w przypadku wielu systemów niemożliwe jest wcześniejsze poznanie wymagań każdego procesu. Oznacza to, że uniknięcie impasu jest często niemożliwe.
Algorytmy Wait / Die i Wound / Wait to dwie inne metody unikania, które wykorzystują technikę łamania symetrii. W tych dwóch algorytmach bierzemy pod uwagę wiek procesów i wyróżniamy stary proces ( A ) i młody proces ( J ).
Wiek procesu można określić na podstawie sygnatury czasowej ( sygnatura czasowa w języku angielskim) podczas tworzenia. Mniejsze daty należą do starszych procesów, większe do młodszych.
Czekaj / giń | Rana / Czekaj | |
---|---|---|
A potrzebuje zasobu należącego do J. | A czeka | J umiera |
J potrzebuje zasobu należącego do A. | Umiera | J Czekaj |
Ważne jest, aby zdać sobie sprawę, że proces może znajdować się w niepewnym stanie, niekoniecznie prowadząc do impasu. Pojęcie bezpiecznego i niebezpiecznego stanu odnosi się tylko do tego, czy system wpada w zakleszczenie, czy nie. Na przykład, jeśli proces żąda zasobu A, co powoduje niezabezpieczony stan, ale zwalnia zasób B, aby uniknąć cyklicznego oczekiwania, wówczas stan jest niezabezpieczony, ale system nie jest zakleszczony.
Jedną z metod jest zawsze nabywanie muteksów w tej samej kolejności. Rzeczywiście, jeśli kilka lekkich procesów musi uzyskać kilka blokad, aby wykonać swoją pracę, jeśli pozyskują blokady w innej kolejności, możliwe jest, że zawieszają się podczas sekwencji pobierania (jak w poprzednim przykładzie).
Ważne jest również przyjrzenie się priorytetom procesów. Rzeczywiście, jeśli na przykład proces o wysokim priorytecie wykorzystuje blokadę wspólną z procesem o niskim priorytecie (patrz także inwersja priorytetu ), możliwe jest uzyskanie sytuacji blokujących. Jednym z rozwiązań tego rodzaju problemu jest używanie blokad tylko między procesami o tym samym priorytecie.