Algorytm ten jest uogólnieniem algorytmu Dekker'a na większą liczbę procesów i wykorzystuje się go do rozwiązania problemu wzajemnego wykluczania. Z zagadnieniem tym mamy do czynienia na przykład, gdy równolegle wykonywane procesy korzystają ze wspólnej pamięci. Przeprowadźmy symulację działania dwóch równolegle wykonywanych programów, z których jeden zwiększa wartość współdzielonej zmiennej w o 2, a drugi o 3 (wartość początkowa w to 0). Najpierw obydwa procesy pobierają wartość zmiennej w po czym pierwszy zwiększa jej wartość o 2 (0+2=2), a drugi o 3 (0+3=3). Po wykonaniu operacji procesy odsyłają wyniki. Jeżeli proces pierwszy zapisze swój wynik szybciej do zmiennej współdzielonej końcowym wynikiem będzie 3, jeżeli wolniej niż proces drugi w wyniku otrzymamy 2. W przypadku, gdy procesy wykonają obliczenia w sposób, który wykluczy jednoczesny dostęp do zmiennej współdzielonej wynik będzie prawidłowy.

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 oczyt 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 uzyskac dostep 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 n procesów.
Do komunikacji między równolegle wykonującymi się procesami służą 2 współdzielone zmienne:
  flag[1..n] - która dla każdego procesu przyjmuje trzy możliwe wartości: 0 - proces znajduje się poza sekcją krytyczną, 1 - proces ubiega się o wejscie do sekcji krytycznej, 2 - proces albo jest w drugim etapie ubiegania się o dostęp do sekcji krytycznej, albo wykonuje zadania w sekcji krytycznej,
  turn - określa, który z procesów ma pierszeństwo wejścia do sekcji krytycznej.
Algorytm Dijkstry ma następującą postać (zmienna i przyjmuje wartość będącą numerem procesu, czyli w procesie pierwszym 1, w procesie drugim 2, ...):
procedure process_i;
var //zmienne lokalne procesu
test, k, other, temp: integer;
begin
  while true do
   begin
   {część prgramu przed sekcją krytyczną}
  L: flag[i]:=1;
   other:=turn;
   while other<>i do
    begin
    test:=flag[other];
    if test=0 then turn:=i;
    other:=turn;
    end;
   flag[i]:=2;
   for k:=1 to n do
    if k<>i then
     begin
     test:=flag[k];
     if test=2 then goto L;
     end;
   {sekcja krytyczna}
   flag[i]:=0;
   {pozostała część programu}
   end;
end;


W algorytmie tym wejście do sekcji krytycznej odbywa się dwuetapowo. Najpierw proces, ustawia swoją flagę na wartość 1. Następnie sprawdza, który z procesów ma pierwszeństwo wejścia sekcji krytycznej. Jeżeli jest nim właśnie on, przechodzi do drugiego etapu (ustawia swoją flagę na wartość 2), w przeciwnym wypadku czeka, aż proces, który ma pierwszeństwo wyjdzie z sekcji krytycznej (pierwsza pętla while). Jeżeli proces, który miał pierwszeństwo nie znajduje się już w sekcji krytycznej, proces ubiegający się o wejście do niej ustawia pierwszeństwo na siebie (instrukcja if w pierwszej pętli while).
W drugim etapie proces sprawdza flagi wszystkich pozostałych procesów. Jeżeli wykryje, że któryś z procesów dostał się razem z nim do drugiego etapu następuje powrót do etapu pierwszego (instrukcja goto). Jeżeli natomiast proces ten jest jedynym procesem w drugim etapie, może on wejść do sekcji krytycznej.
Po wyjściu z sekcji krytycznej proces zdejmuje falgę (ustawia wartość zmiennej współdzielonej flag[i], na wartość 0), ustępując tym samym miejsce procesom czekającym w pierwszym etapie.
W skrajnym przypadku proces może nie uzyskać dostępu do sekcji krytycznej, gdyż inne (szybsze) procesy mogą go blokować w pierwszej z pętli while.

Komentarze