Algorytm Dekkera

Algorytm Dekkera jest pierwszym znanym poprawnym rozwiązaniem problemu wzajemnego wykluczania w programowaniu współbieżnym , w którym procesy komunikują się tylko za pośrednictwem pamięci współdzielonej. Rozwiązanie przypisuje się holenderskiemu matematykowi Th. J. Dekker autorstwa Edsgera W. Dijkstry w niepublikowanej pracy na temat opisów procesów sekwencyjnych oraz jego rękopisie dotyczącym współpracujących procesów sekwencyjnych. Pozwala dwóm wątkom współdzielić zasób jednorazowego użytku bez konfliktów, używając tylko pamięci współdzielonej do komunikacji.

Pozwala uniknąć ścisłej przemiany naiwnego algorytmu turowego i był jednym z pierwszych algorytmów wzajemnego wykluczania , które zostały wynalezione.

Przegląd

Jeśli dwa procesy spróbują wejść do sekcji krytycznej w tym samym czasie, algorytm zezwoli na wejście tylko jednemu procesowi, w zależności od tego, czyja jest kolej . Jeśli jeden proces znajduje się już w sekcji krytycznej, drugi proces będzie zajęty czekaniem na zakończenie pierwszego procesu. Odbywa się to za pomocą dwóch flag, want_to_enter[0] i want_to_enter[1] , które wskazują na zamiar wejścia do sekcji krytycznej ze strony odpowiednio procesów 0 i 1 oraz zmiennego zwrotu wskazującego, kto ma pierwszeństwo między te dwa procesy.

Algorytm Dekkera

Algorytm Dekkera można wyrazić w pseudokodzie w następujący sposób. 

zmienne chce_wprowadzić : tablica 2 wartości boolowskich turn : integer chce_wprowadzić[0] ← false chce_wprowadzić[1] ← false turn ← 0 // lub 1
 
p0: want_to_enter[0] ← true while want_to_enter[1] { if turn ≠ 0 { want_to_enter[0] ← false while turn ≠ 0 { // zajęty czekanie } chce_wejść [0] ← true } } // sekcja krytyczna ... turn ← 1 want_to_enter[0] ← false // reszta sekcji
 
p1: want_to_enter[1] ← true while want_to_enter[0] { if turn ≠ 1 { want_to_enter[1] ← false while turn ≠ 1 { // zajęte oczekiwanie } want_to_enter[1] ← true } } // sekcja krytyczna ... turn ← 0 want_to_enter[1] ← false // reszta sekcji

Procesy wskazują na zamiar wejścia do sekcji krytycznej, która jest testowana przez zewnętrzną pętlę while. Jeśli drugi proces nie zgłosił intencji, do sekcji krytycznej można bezpiecznie wejść niezależnie od aktualnej tury. Wzajemne wykluczanie będzie nadal gwarantowane, ponieważ żaden proces nie może stać się krytyczny przed ustawieniem swojej flagi (co oznacza, że ​​przynajmniej jeden proces wejdzie w pętlę while). Gwarantuje to również postęp, ponieważ nie nastąpi oczekiwanie na proces, który wycofał zamiar stania się krytycznym. Alternatywnie, jeśli ustawiono zmienną innego procesu, wprowadzona zostaje pętla while, a zmienna turn ustali, kto może stać się krytyczny. Procesy bez priorytetu wycofują zamiar wejścia do sekcji krytycznej do momentu ponownego nadania im priorytetu (wewnętrzna pętla while). Procesy z priorytetem przerwą pętlę while i wejdą do sekcji krytycznej.

Algorytm Dekkera gwarantuje wzajemne wykluczenie , wolność od impasu i wolność od głodu . Zobaczmy, dlaczego obowiązuje ostatnia właściwość. Załóżmy, że p0 utknęło w while want_to_enter[1] na zawsze. Istnieje wolność od impasu, więc ostatecznie p1 przejdzie do swojej sekcji krytycznej i ustawi obrót = 0 (a wartość zwrotu pozostanie niezmieniona, dopóki p0 nie będzie postępowało). W końcu p0 wyrwie się z wewnętrznej while turn ≠ 0 (jeśli kiedykolwiek się na niej utknęło). Następnie ustawi want_to_enter[0] na true i czeka, aż want_to_enter[1] zmieni się na false (ponieważ turn = 0 , nigdy nie wykona akcji w pętli while). Następnym razem, gdy p1 spróbuje wejść do swojej sekcji krytycznej, będzie zmuszone do wykonania akcji w swojej pętli while want_to_enter[0] . W szczególności ostatecznie ustawi want_to_enter[1] na false i utknie w pętli while turn ≠ 1 (ponieważ turn pozostaje 0). Następnym razem, gdy kontrola przejdzie do p0, wyjdzie z while want_to_enter[1] i wejdzie do swojej sekcji krytycznej.

Jeśli algorytm został zmodyfikowany przez wykonanie akcji w pętli while want_to_enter[1] bez sprawdzania, czy turn = 0 , to istnieje możliwość głodu. Zatem wszystkie kroki algorytmu są konieczne.

Notatki

Jedną z zalet tego algorytmu jest to, że nie wymaga on specjalnych instrukcji testowania i ustawiania (atomowego odczytu/modyfikacji/zapisu) i dlatego jest wysoce przenośny między językami i architekturami maszyn. Wadą jest to, że jest ograniczony do dwóch procesów i wykorzystuje zajęte oczekiwanie zamiast zawieszenia procesu. (Stosowanie zajętego oczekiwania sugeruje, że procesy powinny spędzać minimalną ilość czasu w sekcji krytycznej).

Nowoczesne systemy operacyjne zapewniają prymitywy wzajemnego wykluczania, które są bardziej ogólne i elastyczne niż algorytm Dekkera. Jednak w przypadku braku rzeczywistej rywalizacji między dwoma procesami wejście i wyjście z sekcji krytycznej jest niezwykle wydajne, gdy używany jest algorytm Dekkera.

Wiele nowoczesnych procesorów wykonuje swoje instrukcje w sposób poza kolejnością; nawet dostępy do pamięci mogą być zmieniane (zobacz porządkowanie pamięci ). Ten algorytm nie będzie działał na SMP wyposażonych w te procesory bez użycia barier pamięci .

Ponadto wiele kompilatorów optymalizujących może wykonywać przekształcenia, które spowodują niepowodzenie tego algorytmu niezależnie od platformy. W wielu językach kompilator może wykryć, że zmienne flag want_to_enter[0] i want_to_enter[1] nigdy nie są dostępne w pętli. Następnie może usunąć zapisy do tych zmiennych z pętli, używając procesu zwanego ruchem kodu niezmiennego w pętli . Wiele kompilatorów mogłoby również wykryć, że turn nigdy nie jest modyfikowana przez wewnętrzną pętlę i przeprowadzić podobną transformację, co dałoby potencjalną nieskończoną pętlę . Jeśli zostanie wykonana jedna z tych transformacji, algorytm zakończy się niepowodzeniem, niezależnie od architektury.

Aby złagodzić ten problem, zmienne lotne powinny być oznaczone jako modyfikowalne poza zakresem aktualnie wykonywanego kontekstu. Na przykład w języku C# lub Javie można by oznaczyć te zmienne jako „niestabilne”. Należy jednak zauważyć, że atrybut „volatile” języka C/C++ gwarantuje jedynie, że kompilator wygeneruje kod z odpowiednią kolejnością; nie zawiera niezbędnych barier pamięciowych , aby zagwarantować wykonanie tego kodu w odpowiedniej kolejności . Zmienne atomowe C++ 11 mogą być używane do zagwarantowania odpowiednich wymagań dotyczących porządku — domyślnie operacje na zmiennych atomowych są sekwencyjnie spójne, więc jeśli zmienne want_to_enter i turn są atomowe, naiwna implementacja „po prostu zadziała” . Alternatywnie, zamawianie można zagwarantować poprzez wyraźne użycie oddzielnych ogrodzeń, przy operacjach załadunku i przechowywania przy użyciu swobodnego zamawiania.

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Dekker%27s_algorithm&oldid=1123217173 ”