Algorytmy zapobiegania zakleszczeniom
W informatyce algorytmy zapobiegania zakleszczeniu są używane w programowaniu współbieżnym , gdy wiele procesów musi uzyskać więcej niż jeden współdzielony zasób . Jeśli co najmniej dwa współbieżne procesy uzyskują wiele zasobów bez rozróżnienia, może wystąpić sytuacja, w której każdy proces ma zasób potrzebny innemu procesowi. W rezultacie żaden z procesów nie może uzyskać wszystkich potrzebnych mu zasobów, więc wszystkie procesy są blokowane przed dalszym wykonywaniem. Taka sytuacja nazywana jest zakleszczeniem . Algorytm zapobiegania zakleszczeniom organizuje wykorzystanie zasobów przez każdy proces, aby zapewnić, że przynajmniej jeden proces zawsze jest w stanie uzyskać wszystkie potrzebne zasoby. Jednym z takich przykładów algorytmu impasu jest algorytm Bankera.
Przegląd
| Nazwa | Warunki Coffmana | Opis |
|---|---|---|
| Algorytm bankiera | Wzajemne wykluczenie | Algorytm bankiera to algorytm alokacji zasobów i unikania impasu opracowany przez Edsgera Dijkstrę . |
| Zapobieganie blokadom rekurencyjnym | Wzajemne wykluczenie | Zapobiega to wielokrotnemu wprowadzaniu pojedynczego wątku do tego samego zamka. |
Rozproszony impas
Rozproszone zakleszczenia mogą wystąpić w systemach rozproszonych , gdy używane są transakcje rozproszone lub kontrola współbieżności . Rozproszone zakleszczenia można wykryć, konstruując globalny wykres oczekiwania , z lokalnych wykresów oczekiwania na detektor zakleszczeń lub za pomocą rozproszonego algorytmu, takiego jak pogoń za krawędzią.
Zakleszczenia fantomowe to zakleszczenia, które są wykrywane w systemie rozproszonym z powodu wewnętrznych opóźnień systemu, ale w rzeczywistości już nie istnieją w momencie wykrycia.
Zapobieganie impasowi
Istnieje wiele różnych sposobów na zwiększenie równoległości tam, gdzie blokady rekurencyjne w przeciwnym razie spowodowałyby zakleszczenia. Ale jest cena. A ta cena to albo wydajność/narzut, zezwolenie na uszkodzenie danych, albo jedno i drugie.
Niektóre przykłady obejmują: hierarchie blokad, zliczanie odwołań do blokad i wywłaszczanie (albo przy użyciu wersjonowania, albo zezwalające na uszkodzenie danych w przypadku wywłaszczania); algorytmy Wait-For-Graph (WFG) [1] , które śledzą wszystkie cykle powodujące zakleszczenia (w tym zakleszczenia tymczasowe); oraz algorytmy heurystyczne, które niekoniecznie zwiększają równoległość w 100% miejsc, w których możliwe są zakleszczenia, ale zamiast tego kompromis, rozwiązując je w wystarczającej liczbie miejsc, w których wydajność/obciążenie vs równoległość jest akceptowalna.
Rozważmy sytuację „kiedy dwa pociągi zbliżają się do siebie na skrzyżowaniu”. Prewencja just-in-time działa jak osoba stojąca na skrzyżowaniu (strażnik przejazdu) z zwrotnicą, która wpuszcza tylko jeden pociąg na „super tory”, które przejeżdżają nad innymi czekającymi pociągami.
- W przypadku blokad nierekurencyjnych blokadę można wprowadzić tylko raz (gdzie dwukrotne wprowadzenie pojedynczego wątku bez odblokowania spowoduje zakleszczenie lub wyrzuci wyjątek, aby wymusić zapobieganie cyklicznemu oczekiwaniu).
- W przypadku blokad rekurencyjnych tylko jeden wątek może przejść przez blokadę. Jeśli jakiekolwiek inne wątki wejdą do blokady, muszą poczekać, aż początkowy wątek, który przeszedł, zakończy n liczbę wejść.
Tak więc problem z pierwszym polega na tym, że w ogóle nie zapobiega zakleszczeniu. Drugi nie zapobiega rozproszonemu zakleszczeniu. Ale drugi jest przedefiniowany, aby zapobiec scenariuszowi impasu, którego pierwszy nie rozwiązuje.
Rekurencyjnie przez blokadę może przejść tylko jeden wątek. Jeśli inne wątki wejdą do blokady, muszą czekać, aż początkowy wątek, który przeszedł, zakończy n liczbę razy. Ale jeśli liczba wątków, które wchodzą w blokowanie, jest równa liczbie zablokowanych, przypisz jeden wątek jako super-wątek i pozwól mu działać tylko (śledząc liczbę wejść/wyjść z blokowania), aż do zakończenia.
Po zakończeniu superwątku warunek powraca do użycia logiki z blokady rekurencyjnej i wychodzącego superwątku
- określa się jako niebędący super-wątkiem
- powiadamia szafkę, że inne zablokowane, oczekujące wątki muszą ponownie sprawdzić ten warunek
Jeśli istnieje scenariusz impasu, ustaw nowy superwątek i postępuj zgodnie z tą logiką. W przeciwnym razie wznów regularne blokowanie.
Kwestie nieomówione powyżej
Wiele zamieszania kręci się wokół problemu zatrzymania . Ale ta logika nie rozwiązuje problemu zatrzymania, ponieważ warunki, w których występuje blokowanie, są znane, co daje konkretne rozwiązanie (zamiast wymaganego w innym przypadku rozwiązania ogólnego, którego wymaga problem zatrzymania). Mimo to ta szafka zapobiega wszystkim zakleszczeniom, biorąc pod uwagę tylko blokady przy użyciu tej logiki. Ale jeśli jest używany z innymi mechanizmami blokującymi, uruchomiona blokada nigdy się nie odblokowuje (wyjątek wyskakuje bez odblokowania, zapętla się w nieskończoność w zamku lub błąd kodowania zapomina o wywołaniu odblokowania), zakleszczenie jest bardzo możliwe. Zwiększenie warunku, aby je uwzględnić, wymagałoby rozwiązania problemu zatrzymania, ponieważ mielibyśmy do czynienia z warunkami, o których nic nie wiemy i których nie można zmienić.
Innym problemem jest to, że nie rozwiązuje problemu z tymczasowym zakleszczeniem (nie tak naprawdę zakleszczeniem, ale zabójcą wydajności), w którym dwa lub więcej wątków blokuje się na sobie, podczas gdy inny niepowiązany wątek jest uruchomiony. Te tymczasowe impasy mogą mieć wątek działający wyłącznie w nich, zwiększając równoległość. Ale ze względu na to, jak rozproszone wykrywanie zakleszczenia działa dla wszystkich blokad, a nie dla ich podzbiorów, niepowiązany działający wątek musi zostać zakończony przed wykonaniem logiki superwątku w celu usunięcia tymczasowego zakleszczenia.
Powyżej można zobaczyć scenariusz tymczasowej blokady na żywo. Jeśli inny niepowiązany uruchomiony wątek rozpocznie się przed zakończeniem pierwszego niepowiązanego wątku, nastąpi kolejny czas trwania tymczasowego zakleszczenia. Jeśli dzieje się to w sposób ciągły (niezwykle rzadkie), tymczasowy impas można przedłużyć do momentu tuż przed zakończeniem programu, kiedy inne niepowiązane wątki mają gwarancję zakończenia (ze względu na gwarancję, że jeden wątek zawsze będzie działał do końca).
Dalsza ekspansja
Można to dalej rozszerzyć, aby uwzględnić dodatkową logikę w celu zwiększenia równoległości, w przypadku gdy w przeciwnym razie mogłyby wystąpić tymczasowe zakleszczenia. Ale na każdym etapie dodawania większej logiki dodajemy więcej narzutów.
Oto kilka przykładów: rozszerzenie rozproszonego mechanizmu blokowania superwątków w celu uwzględnienia każdego podzbioru istniejących blokad; algorytmy Wait-For-Graph (WFG) [2] , które śledzą wszystkie cykle powodujące zakleszczenia (w tym zakleszczenia tymczasowe); i algorytmy heurystyczne, które niekoniecznie zwiększają równoległość w 100% miejsc, w których możliwe są tymczasowe zakleszczenia, ale zamiast tego kompromis, rozwiązując je w wystarczającej liczbie miejsc, w których wydajność/obciążenie vs równoległość jest akceptowalna (np. dla każdego dostępnego procesora pracuj nad znalezieniem zakleszczenia cykli mniej niż liczba procesorów + 1 głębokość).