Zakleszczenie
Z Wikipedii
Zakleszczenie (ang. deadlock) jest pojęciem z teorii gier 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
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 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.
Najprostsze zakleszczenie powstaje dla dwóch procesów. Każdy z nich utrzymuje w swojej wyłącznej dyspozycji pewnien 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 doprowadzi pięć kroków:
- wzajemne wykluczenie,
- trzymanie zasobu i oczekiwanie,
- cykliczne oczekiwanie,
- brak wywłaszczania z zasobu,
- brak mechanizmu ratunkowego.
Wzajemne wykluczenie to uzyskanie dostępu do zasobu w taki sposób, że w danym czasie więcej procesów nie ma już dostępu do tego zasobu. Następnie zasób jest trzymany przez pewien czas przez proces, który zaczyna oczekiwać na dostępność kolejnego ale zajętego zasobu. Zasób jest trzymany przez proces, który również oczekuje na jakiś zasób. Jeśli pojawi się oczekiwanie cykliczne z udziałem co najmniej dwóch procesów, wszystkie procesy będą w stanie oczekiwania i żaden nie będzie oddawał zasobu. Wiele systemów operacyjnych umożliwia wywłaszczenie procesu z zasobu, jednak to rozwiązanie może powodować kolejne problemy (np. wprowadzenie procesu w stan nieprzewidziany przez jego projektanta). System kontrolujący procesy i zasoby może mieć zaimplementowaną politykę ochrony przed takimi sytuacjami.
[edytuj] Unikanie
Istnieją sposoby zapobiegania zakleszczeniom. Opierają się one na specjalnych politykach dostępu do zasobów w skład których wchodzą algorytmy takie jak protokół pułapu priorytetu.
Jednak przede wszystkim, aby uniknąć zakleszczenia, programy muszą mieć właściwą konstrukcję. Właściwa konstrukcja oznacza w tym przypadku poprawną synchronizację w dostępie do zasobów, co w szczególności dotyczy problemu oczekiwania cyklicznego wymienionego na powyższej liście. Aby nie pojawiło się oczekiwanie cykliczne, dla wszystkich zadań musi być ustalona taka sama kolejność zajmowania zasobów.
Z zakleszczeniem, które już zaistniało może radzić sobie watchdog realizowany przez system operacyjny lub sprzęt kontrolujący działanie procesów. Może on po prostu zrestartować cały system lub, w bardziej skomplikowanych rozwiązaniach - arbitralnie zakończyć jeden lub więcej z zakleszczonych procesów, lub arbitralnie wymusić wywłaszczenie zadania lub zadań z zasobu.
