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 sekwencyjnychE.W. Dijkstra, Cooperating Sequential Processes, manuskrypt, 1965. Wyszukany 13 Maja 2009.. 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
Linki zewnętrzne Algorytm Dekkera
Kategoria:Algorytmy przetwarzania współbieżnego