Algorytm Dekkera

Algorytm Dekkera – pierwszy algorytm poprawnie rozwiązujący problem wzajemnego wykluczania się równolegle działających procesów. Tylko jeden z nich może w danej chwili wykonywać ich wspólną sekcję krytyczną (zob. programowanie współbieżne). Rozwiązanie to zostało przypisane holenderskiemu matematykowi T. J. Dekkerowi przez Edsgera Dijkstrę w jego manuskrypcie na temat współdziałania procesów sekwencyjnych^[1]. Algorytm pozwala dwóm wątkom na bezkonfliktową pracę na danych pochodzących z jednego źródła przy użyciu do komunikacji między nimi jedynie pamięci dzielonej.

Dwa procesy równoległe

W pascalowej implementacji algorytmu korzysta się ze wspólnych dla procesów zmiennych: flag1, flag2 (które oznaczają odpowiednio, że pierwszy lub drugi proces chce korzystać z zasobów), turn (zmienna decyduje, który proces wchodzi do sekcji krytycznej w wypadku, gdy oba deklarują chęć korzystania). Na początku zmienne ustawione są następująco:

flag1 := false;
flag2 := false;
turn := 1; {(lub 2, bez większego znaczenia)}

Ponieważ kod wejścia i wyjścia z sekcji krytycznej dla procesu drugiego różni się odpowiednio numerami flag, poniżej podany jest jedynie kod dla procesu 1.

//własne sprawy

flag1 := true;

while (flag2) do
begin
    if (turn <> 1)
    begin
        flag1 := false;
        while (turn <> 1) do
        begin
            //nie rób nic
        end;
        flag1 := true;
    end;
end;

//sekcja krytyczna

turn := 2;
flag1 := false;

Zobacz też

algorytm Petersona

Przypisy

↑ E.W. Dijkstra, Cooperating Sequential Processes, manuskrypt, 1965. Wyszukany 13 Maja 2009.

Linki zewnętrzne

Algorytm Dekkera

[1] E.W. Dijkstra, Cooperating Sequential Processes, manuskrypt, 1965. Wyszukany 13 Maja 2009.

[1]