algorytm.org

Algorytm Dekker'a

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 Dekker'a
Ocena użytkowników:***** / 11
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 lipca 2005 20:40

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 stonowisku) 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 się 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żą 3 współdzielone zmienne:
favoredprocess - określa, który proces ma pierszeństwo wejścia do sekcji krytycznej,
p1wantstoenter - wartość TRUE jeśli proces P1 ubiega się o wejście do sekcji krytycznej,
p2wantstoenter - wartość TRUE jeśli proces P2 ubiega się o wejście do sekcji krytycznej,

Algorytm Dekker'a ma następującą postać (processone i processtwo wykonywane są równolegle):
procedure processone;
begin
  while true do
   begin
   {część programu przed sekcją krytyczną}
   p1wantstoenter:=true;
   while p2wantstoenter do
    if favoredprocess=2 then
     begin
     p1wantstoenter:=false;
     while favoredprocess=2 do;
     p1wantstoenter:=true;
     end
   {sekcja krytyczna}
   favoredprocess=2;
   p1wantstoenter:=false;
   {pozostała część programu}
  end;
end;
procedure processtwo;
begin
  while true do
   begin
   {część programu przed sekcją krytyczną}
   p2wantstoenter:=true;
   while p1wantstoenter do
    if favoredprocess=1 then
     begin
     p2wantstoenter:=false;
     while favoredprocess=1 do;
     p2wantstoenter:=true;
     end
   {sekcja krytyczna}
   favoredprocess=1;
   p2wantstoenter:=false;
   {pozostała część programu}
  end;
end;
Na początku zmienne p1wantstoenter oraz p2wantstoenter mają wartość false, zmienna favoredprocess ma wartość 1 albo 2. Proces, który chce wejść do sekcji krytycznej, ustawia flagę (dla procesu processone jest to p1wantstoenter, dla procesu processtwo jest to p2wantstoenter). Następnie sprawdza czy drugi proces, również ustawił flagę, jeżeli nie jest ona ustawiona to proces może wejśc do sekcji krytycznej, w przeciwnym wypadku oznacza to, że drugi proces chce również wejść do sekcji krytycznej lub już w niej się znajduje. Jeżeli tak to proces ubiegający się o wejście zdejmuje flagę informującą o chęci wejścia do sekcji krytycznej i sprawdza, który z procesów ma pierszeństwo (najbardziej zagnieżdżona pętla while) i czeka tam tak długo, aż pierszeństwo będzie mu udzielone. Jeżeli otrzyma pierszeństwo (wyjdzie z najbardziej zagnieżdżonej pętli while) z powrotem ustawia flagę informującą drugi proces, że chce wejść do sekcji krytycznej, a następnie ponownie sprawdza wartość flagi drugiego procesu dla procesu processone jest to p1wantstoenter, dla procesu processtwo jest to p2wantstoenter).
Po wyjściu z sekcji krytycznej proces udziela pierszeństwo drugiemu procesowi, (processone favoredprocess:=2 a processtwo favoredprocess:=1) następnie zdejmuje flage informującą o chęci wejścia lub byciu w sekcji krytycznej

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:11
Dodaj komentarz