Algorytm Petersona

Algorytm Petersona – algorytm przetwarzania współbieżnego, zapewniający wzajemne wykluczenie, umożliwiające dwóm procesom lub wątkom bezkonfliktowy dostęp do współdzielonego zasobu (sekcji krytycznej). Algorytm został opracowany przez Gary'ego L. Petersona w 1981 roku. Algorytm Petersona zapewnia wzajemne wykluczanie tylko dla dwóch procesów, istnieje jednak uogólniona postać algorytmu do zastosowania z wieloma procesami: algorytm piekarniany^[1].

Algorytm[edytuj | edytuj kod]

zainteresowany[0] = false;
zainteresowany[1] = false;
czyja_kolej;

P0: zainteresowany[0] = true;
    czyja_kolej = 1;
    while (zainteresowany[1] && czyja_kolej == 1)
    {
        // czekaj
    }
    // sekcja krytyczna
    ...
    // koniec sekcji krytycznej
    zainteresowany[0] = false;

P1: zainteresowany[1] = true;
    czyja_kolej = 0;
    while (zainteresowany[0] && czyja_kolej == 0)
    {
        // czekaj
    }
    // sekcja krytyczna
    ...
    // koniec sekcji krytycznej
    zainteresowany[1] = false;

Z każdym wątkiem jest skojarzone pole w tablicy zainteresowany, które jest ustawiane w true, gdy wątek chce wejść do sekcji krytycznej. Dodatkowo wykorzystywane jest pole czyja_kolej przechowujące informacje o tym, który proces ma pierwszeństwo wykonania sekcji krytycznej. Wejście do sekcji krytycznej jest udostępniane wątkowi P0, jeżeli P1 nie jest zainteresowany jej wykonaniem, bądź da pierwszeństwo wstępu wątkowi P0^[1].

Algorytm Petersona zapewnia wzajemne wykluczanie, brak zagłodzenia oraz zakleszczenia^[1].