Algorytm Petersona – Wikipedia

Posted on by
before-content-x4

W informatyce, Algorytm Petersona jest algorytmem wzajemnego wykluczenia do konkurencyjnego programowania. Ten algorytm opiera się na aktywnym podejściu oczekującym i gwarantuje, że będzie bez głodu i bez interbock [[[ Pierwszy ] . Składa się z dwóch części: protokołu wejścia w sekcji krytycznej i protokołu wyjściowego. Przedstawiony algorytm to wersja, która może działać z dwoma wątkami. Został opublikowany przez Gary Peterson w 1981 roku.

after-content-x4

Podstawową zasadą algorytmu Petersona jest to, że każdy wątek będzie miał dostęp do sekcji krytycznej i że wątek może wprowadzić sekcję krytyczną tylko wtedy, gdy jest bezpłatny.

Każdy wątek ma unikalny identyfikator. Według konwencji uważamy, że dwa zastosowane wątki będą nosić identyfikatory 0 I Pierwszy . W swojej podstawowej implementacji z 2 procesami algorytm używa Tabela dwóch wartości logicznych Aby wskazać, czy jeden z wątków jest obecnie zainteresowany wprowadzeniem sekcji krytycznej. On też używa Inna zmienna Aby wskazać, który wątek ma obecnie dostęp do obszaru krytycznego.

Ważną szczególnością tego algorytmu jest to, że wykorzystuje on dwie różne zmienne do kontrolowania dostępu do strefy krytycznej.

Początkowy algorytm dla 2 procesów [[[ modyfikator |. Modyfikator i kod ]

Poniżej Wants_ tron jest obraz dwóch logicznych, wskazujących dla każdego procesu (0 i 1), jeśli chce wejść do sekcji krytycznej. Zmienna wycieczka Wskazuje, kto jest zakrętem, aby wykonać sekcję krytyczną.

after-content-x4
// inicjalizacja  Bool  Wants_ tron [[[ 2 ];  Wants_ tron [[[ 0 ]  =  FAŁSZ ;  veut_entrer[1] = false;
int tour;

// Wątek wykonania n ° 0  T0 :  Wants_ tron [[[ 0 ]  =  PRAWDA ;   wycieczka  =  Pierwszy ;      while (veut_entrer[1] && tour == 1) {} // attente     // Début de la section critique     ...
    // fin de la section critique
    veut_entrer[0] = false;

// Wątek wykonania N ° 1  P1 :  Wants_ tron [[[ Pierwszy ]  =  PRAWDA ;   wycieczka  =  0 ;      while (veut_entrer[0] && tour == 0) {} // attente     // Début de la section critique     ...
    // fin de la section critique
    veut_entrer[1] = false;

Przykład w Javie [[[ modyfikator |. Modyfikator i kod ]

Oto pseudo-kod algorytmu napisany w Javie [[[ Pierwszy ] . Dwa wątki mają 0 i 1 identyfikator, mogą uzyskać swój identyfikator, dzwoniąc ThreadId.get () . 

klasa  Peterson  przybory  Zamek  {   // indeks lokalnych wątków, jest wart 0 lub 1   prywatny  Boolean [] []  flaga  =  nowy  Boolean [[[ 2 ] ;   prywatny  int  ofiara ;   publiczny  próżnia  zamek ()  {   int  I  =  Nić . Dostawać ();   int j = 1 - i;         drapeau[i] = true;                      // je suis intéressé
        victime = i;                            // il va en premier
        while (drapeau[j] && victime == i) {}   // j'attends
    }
    public void unlock() {
        int i = ThreadID.get();
        drapeau[i] = false;                     // je ne suis plus intéressé
    }
}

Przykład aplikacji w C (z księgarnią ‘ pthread ‘) [[[ modyfikator |. Modyfikator i kod ] 

#włączać   #włączać    #Define pthread_function (FCT) (void *( *) (void *)) fct   #define FALSE 0
#define  TRUE 1

// Utilisons l'algorithme de Peterson, 1981
typedef struct {
    // On a besoin d'un tableau de la même taille 
    // que le nombre de thread qu'on doit gérer
    int veut_entrer[2];
    int tour;
    int shared_value;
} Peterson_two_thread_struct;

void thread_num_zero(Peterson_two_thread_struct *ptt)
{
    ptt->veut_entrer[0] = TRUE;
    ptt->tour = 1;
    
    while (ptt->veut_entrer[1] && ptt->tour == 1) {} // On attends
    
    // Section critique
    for (int i = 0; i < 100; i++) {
        ptt->shared_value++;
        printf("[0] shared_value = %in", ptt->shared_value);
    }
    
    // Fin de la section critique
    ptt->veut_entrer[0] = FALSE;
}

void thread_num_one(Peterson_two_thread_struct *ptt)
{
    ptt->veut_entrer[1] = TRUE;
    ptt->tour = 0;
    
    while (ptt->veut_entrer[0] && ptt->tour == 0) {} // On attends
    
    // Section critique
    for (int i = 0; i < 100; i++) {
        ptt->shared_value++;
        printf("[1] shared_value = %in", ptt->shared_value);
    }
    
    // Fin de la section critique
    ptt->veut_entrer[1] = FALSE;
}

int main(int argc, const char * argv[]) {
    
    pthread_t pthread_0, pthread_1;

    Peterson_two_thread_struct ptt_struct;
    ptt_struct.veut_entrer[0] = FALSE;
    ptt_struct.veut_entrer[1] = FALSE;
    ptt_struct.shared_value = 0;
    
    printf("START : shared_value = %in", ptt_struct.shared_value);
    
    int ret0 = pthread_create(&pthread_0, NULL, PTHREAD_FUNCTION(thread_num_zero), &ptt_struct);
    int ret1 = pthread_create(&pthread_1, NULL, PTHREAD_FUNCTION(thread_num_one), &ptt_struct);
    
    // Si le système ne peut plus créer de threads (lisez le manuel)
    if(ret0 != 0 || ret1 != 0)
    {
        printf("Errorn");
        printf("Thread "thread_num_zero" error : %i n", ret0);
        printf("Thread "thread_num_one" error : %i n", ret1);
        return -1;
    }
    
    pthread_join(pthread_0, NULL);
    pthread_join(pthread_1, NULL);
    
    printf("END : shared_value = %in", ptt_struct.shared_value);
    
    return 0;
}

Algorytm spełnia kilka właściwości, takich jak wzajemne wykluczenie, brak głodu i interpretacja.

Oto osiągnięcia, które dowodzą tych właściwości. Uwaga: polegają na kodzie przykładu w Javie.

Wzajemne wykluczenie [[[ modyfikator |. Modyfikator i kod ]

Algorytm Petersona spełnia własność wzajemne wykluczenie .

Dowód . Załóżmy, że nie spełnia to wzajemnego wykluczenia. Rozważ najnowsze wykonania wątków A I B Zanim przecinają się odpowiednio na poziomie swojej krytycznej sekcji Cs A I Cs B . Sprawdzając kod, zauważamy, że:

pisać A (Flaga [a] = PRAWDA ) ⇒ Napisz A (Ofiara = A ) ⇒ Przeczytaj A (flaga[ B ]) ⇒ Przeczytaj A (ofiara) ⇒ Cs A , (1) Napisz B (Flaga [B] = PRAWDA ) ⇒ Napisz B (Ofiara = B ) ⇒ Przeczytaj B (flaga[ A ]) ⇒ Przeczytaj B (ofiara) ⇒ Cs B (2)

Przypuszczam, że A jest ostatnim wątkiem, który napisał na polu ofiar, to przypuszczenie ma niewielki wpływ na ogólność algorytmu. Więc możemy napisać:

pisać B (Ofiara = B ) ⇒ Napisz A (Ofiara = A ) (3)

Równanie (3) zakłada to A zaobserwował zmienną ofiary w (1). Jak A Dlatego wszedł do swojej strefy krytycznej A koniecznie to zaobserwowałem Flaga [b] był Faux . Więc mamy :

pisać A (Ofiara = A ) ⇒ Przeczytaj A (flaga[ B ] == Faux ) (4)

Łącząc równania (2) i (4) razem, otrzymujemy:

pisać B (flaga[ B ] = PRAWDA ) ⇒ Napisz B (Ofiara = B ) ⇒ Napisz A (Ofiara = A ) ⇒ Przeczytaj A (flaga[ B ] == Faux ). (5)

Dzięki regułom przechodności zaangażowania (⇒) możemy przepisać (5) w:

pisać B (flaga[ B ] = PRAWDA ) ⇒ Przeczytaj A (flaga[ B ] == Faux ).

Który stanowi sprzeczność. Rzeczywiście, żadne inne pisanie Flaga [b] Nie można było przeprowadzić przed egzekucją sekcji krytycznej. W związku z tym podstawowa hipoteza jest błędna, a algorytm Petersona dobrze spełnia właściwość wzajemnego wykluczenia. □

Brak głodu [[[ modyfikator |. Modyfikator i kod ]

Algorytm Petersona spełnia własność brak głodu .

Dowód . Załóżmy, że tak nie jest. Istnieje zatem co najmniej jeden z dwóch wątków, który działa wiecznie bez wchodzenia w sekcję krytyczną. Załóżmy, że tak jest A (Dowód jest podobny, jeśli zakłada się, że tak jest B ). A Dlatego wykonuje linię While (flaga [j] && victim == i) {} w pętli, a zatem czeka Flaga [j] stać się Faux , albo ofiara Być równe B .

Co robi B chwila A Wykonaj ten wiersz kodu? Musi wielokrotnie wchodzić i wydostawać się z krytycznego obszaru. Więc to znaczy B Umieść zmienną ofiara ma B Ilekroć chce wejść do sekcji krytycznej. Dlatego zmienna ofiara jest zawsze równy B I nigdy nie zmienia wartości. Jeśli tak jest, A może następnie wyjść z pętli, ponieważ spełnione jest jeden z dwóch warunków. Jest to zatem sprzeczność.

Jeśli to nie to, to dlatego B utknął również w pętli, czekając na wejście do strefy krytycznej, czekając na bycie flaga [a] stać się Faux Albo ofiara lub A . Więcej ofiara nie może być warte obu A I B . Jest to zatem również sprzeczność. W związku z tym podstawową hipotezą jest fałszywa, a algorytm spełnia właściwość braku głodu. □

Nieobecność d’Alloklocage (impas) [[[ modyfikator |. Modyfikator i kod ]

Algorytm Petersona spełnia własność nieobecność d’Olloklocage .

Dowód . Jak już wykazał, że algorytm spełnia własność braku głodu i że własność braku głodu jest silniejszą właściwością niż brak interbocka, wówczas algorytm jest gwarantowany nie do przełomu. □

  1. ↑ A et b (W) Maurice Herlihy , Nir Shavit , Victor Luchangco i Michael Włócznia W Sztuka programowania wieloprocesorowego , Morgan Kaufmann, 2 To jest wyd. (ISBN 978-0-12-415950-1 ) W P. 27-28

after-content-x4