Kontrastujące algorytmy Petersona i Dekkera

Próbuję zrozumieć algorytmy Petersona i Dekkera, które są bardzo podobne i wykazują wiele symetrii.

Próbowałem sformułować algorytmy w nieformalnym języku w następujący sposób:

Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

Różnica wydaje się być punktem, w którym "You can enter next."występuje i faktem "if it's your turn I don't want to enter any more."występującym w Dekker.

W algorytmie Petersona oba procesy wydają się dominujące. Wydaje się, że proces wkracza do krytycznej sekcji, chyba że przyszła kolej na drugą.

I odwrotnie, w algorytmie Dekkera oba procesy wydają się uległy i uprzejmy. Jeśli oba procesy chcą wejść do sekcji krytycznej, a przyszła kolej na drugą, proces decyduje, że nie chce już wchodzić. (Czy jest to potrzebne do wolności głodowej? Dlaczego?)

Czym dokładnie różnią się te algorytmy? Wyobrażam sobie, że kiedy oba procesy próbują wejść do sekcji krytycznej, u Petersona proces mówi „Wchodzę”, podczas gdy w Dekker proces mówi „Możesz wejść”. Czy ktoś może wyjaśnić zachowanie procesów w każdym algorytmie? Czy mój sposób wyrażenia tego w sposób nieformalny jest prawidłowy?

Twoje nieformalne opisy algorytmów są wspaniałe.

Myślę, że w obu przypadkach autor starał się znaleźć najprostsze rozwiązanie, jakie mogli wymyślić, gwarantujące zarówno wzajemne wykluczenie, jak i swobodę impasu. Żaden algorytm nie jest głodny ani sprawiedliwy.[wyd .: jak wskazano w komentarzach, algorytm Petersona jest wolny od głodu i sprawiedliwy]. Rozwiązanie Dekkera było pierwszym algorytmem wzajemnego wykluczania, w którym zastosowano instrukcje ładowania i przechowywania. Został wprowadzony w Dijkstra, Edsger W .; „Współpracujące procesy sekwencyjne”, w: F. Genuys, red., Programming Languages: NATO Advanced Study Institute , s. 43–112, Academic Press, 1968 . Jeśli przeczytasz ten artykuł, zobaczysz, że Dijkstra przeszedł przez szereg prób, rozpoznając problem z każdą z nich, a następnie dodając nieco więcej do następnej wersji. Część nieefektywności jego algorytmu wynika z faktu, że zaczyna on od algorytmu wykonywania zmian, a następnie próbuje go zmodyfikować, aby umożliwić postęp procesów w dowolnej kolejności. (Nie tylko 0,1,0,1 ...)

Algorytm Petersona został opublikowany w 1981 r., Po ponad dekadzie doświadczenia i perspektywy z perspektywy algorytmu Dekkera. Peterson chciał znacznie prostszego algorytmu niż Dekker, aby dowód poprawności był znacznie łatwiejszy. Widać, że czuł frustrację ze strony społeczności związanej z tytułem swojego artykułu. Peterson, GL; „Mity na temat problemu wzajemnego wykluczenia”, Inf. Proc. Łotysz. , 12 (3): 115–116, 1981. Bardzo szybka lektura i bardzo dobrze napisane. (I drobne uwagi na temat metod formalnych są bezcenne). Artykuł Petersona omawia także proces, w którym zbudował swoje rozwiązanie z prostszych prób. (Ponieważ jego rozwiązanie jest prostsze, wymagało mniej etapów pośrednich.) Zauważ, że główna różnica (to, co nazywasz „dominacją”, a nie „uległością”) polega na tym, że Peterson zaczął od nowa (nie od algorytmu skrętów, z którym zaczął Dijkstra) ) jego pętla oczekiwania jest prostsza i bardziej wydajna. Zdaje sobie sprawę, że może po prostu uciec od prostych testów w pętli, podczas gdy Dijkstra musiał się wycofywać i za każdym razem ponawiać.

Wydaje mi się, że muszę też wspomnieć o klasycznym dokumencie Lamport Bakery: Lamport, Leslie; „Nowe rozwiązanie problemu współbieżnego programowania Dijkstry”, Comm ACM 17 (8): 453–455, 1974 . Algorytm Bakery jest prawdopodobnie prostszy niż algorytm Dekkera (i na pewno prostszy w przypadku więcej niż 2 procesorów) i jest specjalnie zaprojektowany, aby był odporny na uszkodzenia. Wspominam o tym z dwóch powodów. Po pierwsze, ponieważ zawiera trochę historii na temat definicji problemu wzajemnego wykluczenia i próbuje go rozwiązać do 1974 r. Po drugie, ponieważ algorytm Bakery pokazuje, że atomowość sprzętu nie jest wymagana do rozwiązania problemu wzajemnego wykluczenia.

Wreszcie, moim ulubionym jest Lamport, Leslie; „Szybki algorytm wzajemnego wykluczenia”, ACM Trans. Komp. Sys. , 5 (1): 1-11, 1987. W tym artykule Lamport starał się zoptymalizować rozwiązanie problemu wzajemnego wykluczenia w (powszechnym) przypadku, gdy nie ma sprzeczności w części krytycznej. Ponownie gwarantuje wzajemne wykluczenie i swobodę impasu, ale nie uczciwość. Jest to (uważam) pierwszy algorytm wzajemnego wykluczania wykorzystujący tylko normalne odczyty i zapisy, które mogą zsynchronizować N procesorów w czasie O (1), gdy nie ma rywalizacji. (Kiedy dochodzi do rywalizacji, opiera się ona na teście O (N).) Nieformalnie demonstruje, że najlepiej, co możesz zrobić w przypadku bez rywalizacji, jest siedem dostępów do pamięci. (Zarówno Dekker, jak i Peterson robią to z 4, ale mogą obsłużyć tylko 2 procesory, kiedy rozszerzysz ich algorytmy na N, będą musieli dodać dodatkowy dostęp O (N).)

Podsumowując: powiedziałbym, że sam algorytm Dekkera jest interesujący głównie z perspektywy historycznej. Artykuł Dijkstry wyjaśnił znaczenie problemu wzajemnego wykluczenia i wykazał, że można go rozwiązać. Ale przy wieloletniej perspektywie znaleziono prostsze (i bardziej wydajne) rozwiązania niż Dekker.

W poniższym artykule podajemy formalne modele algorytmów Petersona i Dekkera (i niektórych innych) oraz użyliśmy sprawdzania modelu, aby udowodnić ich właściwości. Proszę znaleźć nasze wyniki w poniższej tabeli (kolumny „Zakleszczenie” i „Rozbieżne” odnoszą się do naszych modeli, „ME” = PRAWDA oznacza, że ​​algorytm jest poprawny, „Wyprzedzanie” = PRAWDA oznacza, że ​​jest sprawiedliwy).

R. Meolic, T. Kapus, Z. Brezočnik. ACTLW - logika drzewa obliczeń oparta na akcji z operatorem, chyba że. Information Sciences, 178 (6), s. 1542–1557, 2008.

https://doi.org/10.1016/j.ins.2007.10.023

Peterson algorytm jest bardziej ściśle ciśnienie na wejściu do sekcji krytycznej, w której jako Dekker algorytm jest stosunkowo bardziej miękka i mniej agresywne. Aby to wyjaśnić, sprawdźmy przykład kultury irańskiej. Zanim przejdziemy do tego przykładu, warto wiedzieć, że irańczycy mają naprawdę miękkie zachowanie podczas wchodzenia gdzieś! Zgadnij, że dwóch irańskich mężczyzn wejdzie do domu, a ten dom ma tylko jedne drzwi.

Teraz wyobraź sobie dwóch mężczyzn z innej kultury ( Kultura Zombie ), którzy tak naprawdę nie dbają o siebie nawzajem, wchodząc gdzieś ( to kwestia szacunku, aby zapytać kogoś, czy chce wejść, czy nie ).

Aby wyjaśnić informacje o problemie, możemy powiedzieć, że:

• Dwóch Irańczyków = Dwa procesy wykorzystujące algorytm Dekkera
• Two Zombians = Dwa procesy wykorzystujące algorytm Petersona

Dowiedzmy się zatem, co zostało zrobione w każdym algorytmie ( kulturze ). Poniższe komentarze dotyczą pierwszego Irańczyka , który wejdzie do domu podczas korzystania z algorytmu Dekker :

p0:
   wants_to_enter[0] ← true // Goes through the house entrance
   while wants_to_enter[1] { // If the other man wants to enter too
      if turn ≠ 0 { // Then see if it is your turn or not
         wants_to_enter[0] ← false // If it is not your turn don't go furthur
         while turn ≠ 0 { // and wait until it is your turn
           // busy wait
         }
         wants_to_enter[0] ← true // when it is your turn go through the door
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false // Set the turn for the other man
   // remainder section

Mamy też dwóch Zombie, którzy wejdą do domu za pomocą algorytmu Petersona . Ten wygląda następująco:

P0:     
  flag[0] = true; // Goes through the house entrance
  turn = 1; // Set the turn for himself
  while (flag[1] && turn == 1) // Wait until the other one is going in
  {
   // busy wait
  }
   // critical section
      ...
   // end of critical section
  flag[0] = false; // Done going inside

Ważne jest, aby wspomnieć, że obaj nie będą wewnątrz, podczas gdy drugi robi tak ( Wzajemne wyłączające ), ale irańskie ludzie są znacznie bardziej miękkie.