Czy dwuprocesowy algorytm wzajemnego wykluczania Petersona uwzględnia procesy umierania?

9

Myślę, że w algorytmie Petersona dla wzajemnego wykluczenia , jeśli proces, który pierwszy wejdzie do sekcji krytycznej, umrze lub zostanie anulowany, drugi proces zapętli się na zawsze, czekając na wejście do sekcji krytycznej.

Na zdjęciu, jeśli proces 1 zostanie zatrzymany, pozostałe procesy za procesem 1 zostaną wykonane do miejsca, w którym proces 1 jest, ale następnie zapętli.

wprowadź opis zdjęcia tutaj

Co się stanie, jeśli proces, który dotrze do sekcji krytycznej, najpierw umrze, zanim ją opuści?

programming-languages concurrency mutual-exclusion ganadara
źródło
Zredagowałem twoje pytanie odpowiednio. Ponieważ nie skomentowałeś, jak rozszerzyć algorytm na więcej niż dwa procesy, zmieniłem tę część pytania; Myślę, że problem występuje już w wersji dwuprocesowej. Jednak wciąż nie rozumiem tego obrazu.
Raphael

Odpowiedzi:

1

Zależy to od sposobu implementacji blokad. Jeśli zrobisz to tak, jak w artykule z Wikipedii, tj. Pilnujesz sekcji krytycznej jednym logicznym na proces¹, z pewnością masz kłopoty. Jeśli jeden proces umiera, nigdy nie resetuje flagi, więc drugi proces zapętla się na zawsze.

W praktyce możesz zabezpieczyć swój kod przed wieloma sposobami umierania. Na przykład weźmy tę implementację w stylu Java:

flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

Dzięki temu flaga zostanie zresetowana bez względu na to, co dzieje się w sekcji krytycznej, o ile system obsługuje błąd. W Javie jest tak nawet w przypadku przepełnienia stosu i sterty. Jeśli więc proces nie zniknie dosłownie ( kill², awaria procesora, rozłączenie sieci, ...) jesteś bezpieczny. Zauważ, że większość niekrytycznych programów zawodzi w takich przypadkach - jak poradzić sobie z błędem, którego nie uruchamia? - w wielu przypadkach należy to zaakceptować. W razie potrzeby można obsługiwać niespójności po ponownym uruchomieniu.

Jeśli użyjesz odpowiednich blokad na poziomie języka, system wykonawczy może obsługiwać znikających właścicieli blokad, tj. Zwalniać blokady z martwymi właścicielami. Możesz to zasymulować samodzielnie, nadając każdemu procesowi przełącznik martwego człowieka, który inni mogą odczytać, lub sprawdź bezpośrednio, czy proces posiadania zamka jest nadal aktywny (jeśli system go obsługuje).

  1. To i tak nie jest dobrze skalowane.
  2. Myślę, że w Javie finalizepowinien działać nawet na kill, ale specyfikacja tego nie gwarantuje. kill -9jest prawdopodobnie wyrokiem śmierci za każde rozwiązanie wymagające procesu umierania, aby coś zrobić.
Raphael
źródło
1

Spójrz na założenia, w szczególności, że żaden proces nie pozostaje w krytycznej części w nieskończoność (co z pewnością obejmuje po prostu odejście). Nie sądzę, że istnieje sposób na rozwiązanie tego ogólnego problemu za pomocą dowolnego mechanizmu synchronizacji.

To rozwiązanie jest również tylko dla dwóch procesów, istnieją rozwiązania dla procesów wokół.n

vonbrand
źródło