Algorytm Petersona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Przypisy

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

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]