Algorytm Petersona
| ||
| Rodzaj | wzajemne wykluczanie | |
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
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].