Algorytm Petersona

Algorytm Petersona
Rodzajwzajemne wykluczanie

Algorytm Petersonaalgorytm 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

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].

Przypisy

  1. a b c Maurice Herlihy, Nir Shavit: Sztuka programowania wieloprocesorowego". Warszawa: PWN, 2010. ISBN 978-83-01-16146-0.

Zobacz też

Linki zewnętrzne