algorytm.org

Algorytm Peterson'a dla 2 procesów

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Peterson'a dla 2 procesów
Ocena użytkowników:***** / 5
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 lipca 2005 21:02

Algorytm ten rozwiązuje problem wzajemnego wykluczania. Zastanówmy się najpierw kiedy możemy mieć do czynienia z problemem tego typu. Na przykład załóżmy, że pan Kowalski ma konto w banku na którym jest 1000 PLN. Załóżmy, również że poszedł on do bankomatu wypłacić 100 PLN. W tym samym czasie na jego konto pan Nowak przesyła 500 PLN, które jest mu winny. Co może się wówczas stać? A więc bankomat odczytuje z serwera bankowego stan konta pana Kowalskiego i zapisuje w swojej pamięci 1000 PLN, w tym samym czasie, w odległej kasie pan Nowak wpłaca 500 PLN. I tutaj również komputer przy stanowisku, gdzie pan Nowak wpłaca pieniądze odczytuje z serwera bankowego stan konta 1000 PLN. Pan Kowalski w tej chwili odbiera swoje 100 PLN z bankomatu, który przesyła do serwera bankowego nowy stan konta 1000-100=900 PLN. W tym samym czasie pan Nowak dokonał wpłaty i komputer przesyła do serwera nowy stan konta 1000+500=1500 PLN. W sytuacji tej stan konta pana Kowalskiego wynosi 1500 PLN, a nie tak jak powinno być 1400 PLN. Dlaczego tak się stało? Otóż dwa procesy (bankomat i komputer przy stanowisku) miały jednoczesny dostęp do wspólnych danych (serwer bankowy), taki dostęp do wspólnej pamięci nazywać będziemy sekcją krytyczną. Problem zostałby rozwiązany pomyślnie, gdyby dostęp do wspomnianej sekcji krytycznej byłby wzajemnie wykluczony. Najpierw bankomat 1000-100=900, następnie wpłata 900+500=1400. lub odwrotnie. Zapiszmy teraz problem wzajemnego wykluczania w sposób formalny:
Dany jest zbiór procesów sekwencyjnych komunikujących się przez wspólną pamięć. Każdy z procesów zawiera sekcję krytyczną, w której następuje dostęp do wspólnej pamięci. Procesy te są procesami cyklicznymi. Zakłada sie ponadto:
  • zapis i odczyt wspólnych danych jest operacją niepodzielną, a próba jednoczesnych zapisów lub odczytów realizowana jest sekwencyjnie w nieznanej kolejności sekcje krytyczne nie mają priorytetu
  • względne prędkości wykonywania procesów są nieznane
  • proces może zostać zawieszony poza sekcją krytyczna
  • procesy realizujące instrukcje poza sekcją krytyczną nie mogą uniemożliwiać innym procesom wejścia do sekcji krytycznej
  • procesy powinny uzyskać dostęp do sekcji krytycznej w skończonym czasie

Założenia dotyczące algorytmu są następujące:
Algorytm pozwala rozwiązać problem wzajemnego wykluczania dla 2 procesów.
Do komunikacji między dwoma równolegle wykonującymi się procesami służą 2 współdzielone zmienne:
flag[1..2] - wartość TRUE dla flag[1] oznacza, że proces pierwszy chce wejść lub wszedł do sekcji krytycznej, wartość TRUE dla flag[2] oznacza, że proces drugi chce wejść lub wszedł już do sekcji krytycznej,
turn - wartość 1 gdy pierszeństwo ma proces pierszy i 2 gdy pierszenstwo ma proces drugi.
Algorytm Peterson'a dla 2 procesów ma następującą postać (processone i processtwo wykonywane są równolegle):
procedure processone;
begin
 while true do
  begin
   {część prgramu przed sekcją krytyczną}
   flag[1]:=true;
   turn:=2;
   repeat
    whose:=turn;
    other:=flag[2];
   until (whose=1 or not other)
   {sekcja krytyczna}
   flag[1]:=false;
   {pozostała część programu}
  end;
end;
procedure processtwo;
begin
 while true do
  begin
   {część prgramu przed sekcją krytyczną}
   flag[2]:=true;
   turn:=1;
   repeat
    whose:=turn;
    other:=flag[1];
   until (whose=1 or not other)
   {sekcja krytyczna}
   flag[2]:=false;
   {pozostała część programu}
  end;
end;
Na początku zmienna flag[1..2] ma wartość false, zmienna turn ma wartość 1 albo 2. Zmienne whose oraz other są zmiennymi lokalnymi procesów. Proces, który chce wejść do sekcji krytycznej, ustawia flagę (dla procesu processone jest to flag[1], dla procesu processtwo jest to flag[2]), a następnie zmienną turn określającą pierszeństwo w dostępie do skcji krytycznej ustawia tak by dać pierszeństwo "rywalowi" (dla procesu processone jest to wartość 2, dla procesu processtwo jest to wartość 1). Następnie proces czeka w pętli repeat tak długo, aż nie otrzyma pierszeństwa wejścia (zmienna lokalna whose) lub proces rywal nie będzie ubiegał się o wejście do sekcji krytycznej (zaprzeczenie zmiennej lokalnej other).
Po wyjściu z sekcji krytycznej proces zdejmuje swoją flagę informującą o chęci wejścia lub fakcie przebywania w sekcji krytycznej (dla procesu processone jest to flag[1], dla procesu processtwo jest to flag[2]).

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++Linux
.cpp
.cpp
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 15 sierpnia 2012 18:12
Dodaj komentarz