Algorytm Petersona

Algorytm Petersona (lub rozwiązanie Petersona ) jest algorytmem programowania współbieżnego do wzajemnego wykluczania , który umożliwia dwóm lub większej liczbie procesów współdzielenie zasobu jednorazowego użytku bez konfliktów, używając tylko pamięci współdzielonej do komunikacji . Został sformułowany przez Gary'ego L. Petersona w 1981 roku. Chociaż oryginalne sformułowanie Petersona działało tylko z dwoma procesami, algorytm można uogólnić na więcej niż dwa.

Algorytm

0 Algorytm wykorzystuje dwie zmienne: flag i turn . Wartość flag [n] równa true wskazuje, że proces n chce wejść do sekcji krytycznej . Wejście do sekcji krytycznej jest przyznawane dla procesu P0, jeśli P1 nie chce wejść w jej sekcję krytyczną i jeśli P1 nadał priorytet P0 ustawiając zwrot na .

Algorytm Petersona

    
  bool  flaga  [  2  ]  =  {  fałsz  ,  fałsz  };  int  obrót  ;

      0  
   
                
         
             
         
         
         
         
         0   P0  :  flaga  [  ]  =  prawda  ;  P0_bramka  :  obrót  =  1  ;  while  (  flaga  [  1  ]  ==  true  &&  turn  ==  1  )  {  // czekanie zajęte  }  // sekcja krytyczna  ...  // koniec sekcji krytycznej  flaga  [  ]  =  false  ;

        
   0
          0      0
         
             
         
         
         
         
            P1  :  flaga  [  1  ]  =  prawda  ;  bramka_P1  :  obrót  =  ;  while  (  flaga  [  ]  ==  true  &&  turn  ==  )  {  // zajęte oczekiwanie  }  // sekcja krytyczna  ...  // koniec sekcji krytycznej  flaga  [  1  ]  =  false  ;

Algorytm spełnia trzy podstawowe kryteria rozwiązania problemu sekcji krytycznej. Warunek while działa nawet przy wywłaszczaniu.

Te trzy kryteria to wzajemne wykluczenie, postęp i ograniczone oczekiwanie.

Ponieważ turn może przyjąć jedną z dwóch wartości, można go zastąpić pojedynczym bitem, co oznacza, że algorytm wymaga tylko trzech bitów pamięci.

Wzajemne wykluczenie

0 P0 i P1 nigdy nie mogą znajdować się w sekcji krytycznej w tym samym czasie. Jeśli P0 znajduje się w swojej sekcji krytycznej, to flaga [0] jest prawdziwa. Ponadto albo flaga[1] jest fałszywa (co oznacza, że P1 opuścił sekcję krytyczną), albo zwrot jest (co oznacza, że P1 właśnie próbuje wejść do sekcji krytycznej, ale łaskawie czeka), albo P1 znajduje się na etykiecie P1_gate (próbuje wejść do swojej sekcji krytycznej, po ustawieniu flagi [1] na true , ale przed ustawieniem turn na 0 i zajęty czekaniem). Jeśli więc oba procesy znajdują się w swoich sekcjach krytycznych, dochodzimy do wniosku, że stan musi spełniać flag[0] i flag[1] oraz turn = 0 i turn = 1 . Żaden stan nie może spełnić jednocześnie warunku turn = 0 i turn = 1 , więc nie może istnieć stan, w którym oba procesy znajdują się w swoich sekcjach krytycznych. (To opisuje argument, który jest rygorystyczny w.)

Postęp

Postęp definiuje się następująco: jeśli żaden proces nie wykonuje się w swojej sekcji krytycznej, a niektóre procesy chcą wejść do swoich sekcji krytycznych, to tylko te procesy, które nie działają w swoich pozostałych sekcjach, mogą uczestniczyć w podejmowaniu decyzji, który proces wejdzie jego sekcja krytyczna jest następna. Należy zauważyć, że w przypadku procesu lub wątku pozostałe sekcje są częściami kodu niezwiązanymi z sekcją krytyczną. Tego wyboru nie można odkładać w nieskończoność. Proces nie może natychmiast ponownie wejść do sekcji krytycznej, jeśli drugi proces ustawił swoją flagę, aby powiedzieć, że chciałby wejść do swojej sekcji krytycznej.

Ograniczone czekanie

Ograniczone oczekiwanie lub ograniczone obejście oznacza, że liczba pominięć procesu przez inny proces po tym, jak zasygnalizował on chęć wejścia do sekcji krytycznej, jest ograniczona funkcją liczby procesów w systemie. W algorytmie Petersona proces nigdy nie będzie czekał dłużej niż jedną turę na wejście do sekcji krytycznej.

Algorytm filtra: algorytm Petersona dla więcej niż dwóch procesów

Migawka algorytmu filtra z 10 procesami w toku. Ostatnie wpisy są pogrubione i podkreślone. (Uwaga: w zależności od harmonogramu, ostatni wpis może nie być „poprawny”.) W dowolnym momencie aktualizacje tabeli mogą polegać na: wstawieniu nowego procesu na poziomie 0, zmianie na ostatni wpis na danym poziomie lub przeniesieniu procesu o jeden poziom wyżej (jeśli nie jest to ostatni wpis LUB nie ma innych procesów na jego własnym poziomie lub wyższym).

Algorytm filtra uogólnia algorytm Petersona na $N > 2$ procesy. Zamiast flagi logicznej wymaga zmiennej całkowitej na proces, przechowywanej w rejestrze atomowym dla jednego zapisu / wielu czytników (SWMR) oraz N $- 1$ dodatkowych zmiennych w podobnych rejestrach. Rejestry można przedstawić w pseudokodzie jako tablice :

level : tablica N liczb całkowitych last_to_enter : tablica N − 1 liczb całkowitych

Zmienne poziomu przyjmują wartości do $N -1$ , z których każda reprezentuje odrębną „poczekalnię” przed sekcją krytyczną. Procesy przechodzą z jednego pokoju do drugiego, kończąc w pokoju $N - 1$ , który jest sekcją krytyczną. W szczególności, aby uzyskać blokadę, proces $i$ jest wykonywany

 0  i ← Nr procesu  dla  ℓ  od  do  N − 1  wyłączny  poziom [i] ← ℓ last_to_enter[ℓ] ← i  while  last_to_enter[ℓ] = i  i  istnieje k ≠ i, takie, że poziom[k] ≥ ℓ  czekać

Aby zwolnić blokadę po wyjściu z sekcji krytycznej, proces $i$ ustawia level[i] na −1.

To, że ten algorytm osiąga wzajemne wykluczanie, można udowodnić w następujący sposób. Proces $i$ opuszcza wewnętrzną pętlę, gdy albo nie ma procesu o wyższym poziomie niż level[i] , więc następna poczekalnia jest wolna; lub, gdy i ≠ last_to_enter[ℓ] , więc inny proces dołączył do poczekalni. Zatem na poziomie zero, nawet jeśli wszystkie $N$ procesów miałoby wejść do poczekalni zero w tym samym czasie, nie więcej niż $N - 1$ przejdzie do następnego pokoju, a ostatni znajdzie się w pokoju jako ostatni. Podobnie na następnym poziomie $N - 2$ będzie postępować itd. , aż na poziomie końcowym tylko jeden proces będzie mógł opuścić poczekalnię i wejść do sekcji krytycznej, dając wzajemne wykluczenie.

W przeciwieństwie do dwuprocesowego algorytmu Petersona, algorytm filtra nie gwarantuje ograniczonego oczekiwania.

Notatka

Podczas pracy na poziomie sprzętowym algorytm Petersona zazwyczaj nie jest potrzebny do uzyskania dostępu atomowego. Niektóre procesory mają specjalne instrukcje, takie jak test-and-set lub Compare-and-swap , które poprzez zablokowanie magistrali pamięci mogą być wykorzystane do zapewnienia wzajemnego wykluczania w systemach SMP .

Większość nowoczesnych procesorów zmienia kolejność dostępu do pamięci, aby poprawić wydajność wykonywania (zobacz zamawianie pamięci , aby zapoznać się z dozwolonymi typami zmiany kolejności). Takie procesory niezmiennie dają pewien sposób wymuszania porządkowania w strumieniu dostępów do pamięci, zwykle za pomocą bariery pamięci . Implementacja algorytmów Petersona i pokrewnych na procesorach, które zmieniają kolejność dostępu do pamięci, generalnie wymaga użycia takich operacji do poprawnego działania, aby zapobiec wykonywaniu operacji sekwencyjnych w niewłaściwej kolejności. Należy zauważyć, że zmiana kolejności dostępu do pamięci może mieć miejsce nawet w przypadku procesorów, które nie zmieniają kolejności instrukcji (takich jak PowerPC procesor w konsoli Xbox 360 ). ^{[ potrzebne źródło ]}

Większość takich procesorów ma również gwarantowane działanie atomowe , takie jak XCHG na procesorach x86 i ładowanie łącza/warunkowe przechowywanie na architekturach Alpha , MIPS , PowerPC i innych. Instrukcje te mają na celu zapewnienie sposobu na wydajniejsze tworzenie prymitywów synchronizacji, niż można to zrobić przy użyciu czystych podejść do pamięci współdzielonej.

Zobacz też

przypisy

Linki zewnętrzne

https://elixir.bootlin.com/linux/latest/source/arch/arm/mach-tegra/sleep.S Implementacja algorytmu Petersona