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