Dekkerův algoritmus je prvním známým správným řešením problému vzájemného vyloučení v paralelním programování . Edsger Dijkstra uvádí ve své práci o meziprocesové komunikaci nizozemského matematika T. Dekkera jako autora tohoto algoritmu [1] . Umožňuje dvěma vláknům provádění sdílet nesdílený zdroj bez konfliktů, přičemž ke komunikaci používá pouze sdílenou paměť .
Pokud se dva procesy pokusí vstoupit do kritické sekce současně, algoritmus to umožní pouze jednomu z nich, podle toho, na koho je v tu chvíli řada. Pokud jeden proces již vstoupil do kritické sekce, druhý počká, dokud ji první neopustí. To se provádí pomocí dvou příznaků (indikátorů „záměru“ vstoupit do kritické sekce) a proměnné turn (označující, o který proces se jedná).
| flag[0] := false příznak[1] := nepravda turn := 0 // nebo 1 | |
| p0: flag[0] := true while flag[1] = true { if turn = 1 { flag[0] := false while turn = 1 {} flag[0] := true } } // kritická sekce ... otočení := 1 flag[0] := false // konec kritické sekce ... | p1: flag[1] := true while flag[0] = true { if turn = 0 { příznak[1] := nepravda while turn = 0 {} flag[1] := true } } // kritická sekce ... otočení := 0 příznak[1] := nepravda // konec kritické sekce ... |
Procesy oznamují svůj záměr vstoupit do kritické sekce; toto je kontrolováno vnější smyčkou "while". Pokud žádný jiný proces nedeklaroval takový záměr, je bezpečné vstoupit do kritické sekce (bez ohledu na to, kdo je na řadě). Vzájemné vyloučení bude stále zaručeno, protože žádný proces nemůže vstoupit do kritické sekce, dokud není nastaven tento příznak (za předpokladu, že alespoň jeden proces vstoupí do smyčky while). Zaručuje také pokrok, protože se nebude čekat, až proces opustí „záměr“ vstoupit do kritické sekce. V opačném případě, pokud byla nastavena jiná procesní proměnná, zadejte smyčku "while" a proměnná turn bude indikovat, kdo smí vstoupit do kritické sekce. Proces, jehož řada nedorazila, opouští záměr vstoupit do kritické sekce, dokud nepřijde řada na něj (vnitřní smyčka „zatímco“). Proces, který je na řadě, opustí smyčku while a vstoupí do kritické sekce.
Dekkerův algoritmus zaručuje vzájemné vyloučení , nemožnost uváznutí nebo zablokování. Podívejme se, proč je poslední vlastnost pravdivá. Řekněme, že p0 zůstane navždy uvnitř smyčky „while flag[1]“. Protože nemůže dojít k uváznutí, dříve nebo později p1 dosáhne svého kritického úseku a nastaví otáčku = 0 (hodnota otáčky zůstane konstantní, dokud se nepostoupí p0). p0 opustí vnitřní smyčku "while turn = 1" (pokud tam byla). Poté nastaví příznak[0] na hodnotu true a počká, až příznak[1] bude nepravdivý (protože turn = 0, cyklus while nikdy neprovede). Když se p1 příště pokusí vstoupit do kritické sekce, bude nucen provést akce ve smyčce "while flag[0]". Konkrétně nastaví příznak[1] na hodnotu false a provede smyčku "while turn = 0" (protože turn zůstává 0). Když příště řízení přejde na p0, opustí smyčku "při příznaku[1]" a vstoupí do kritické sekce.
Pokud je algoritmus upraven tak, aby se akce ve smyčce "while flag[1]" prováděly bez kontroly podmínky "turn = 0", pak bude možnost zavěšení ( anglicky hladovění ). Proto jsou nezbytné všechny kroky algoritmu.
Jednou z výhod algoritmu je, že nevyžaduje speciální příkazy „ over-set “ – atomické operace čtení, aktualizace a zápisu – a v důsledku toho je snadno přenosný napříč různými programovacími jazyky a počítačovými architekturami. Nevýhodou je jeho použitelnost pouze na případ se dvěma procesy a použití čekací smyčky pozastavení procesu: použití čekací smyčky znamená, že procesy by měly strávit minimální množství času uvnitř kritické sekce.
Moderní operační systémy poskytují synchronizační primitiva, která jsou obecnější a flexibilnější než algoritmus Dekker. Je však třeba poznamenat, že při absenci skutečné simultánnosti mezi dvěma procesy budou operace vstupu a výstupu kritické sekce velmi efektivní při použití tohoto algoritmu.
Mnoho moderních mikroprocesorů provádí instrukce mimo pořadí, dokonce i pořadí přístupu do paměti nemusí být respektováno (viz pořadí přístupu do paměti ). Algoritmus nebude fungovat na strojích SMP vybavených takovými procesory, pokud nebudou použity paměťové bariéry .
Optimalizační kompilátory navíc dokážou provést takové transformace programu, že daný algoritmus přestane fungovat bez ohledu na problémy hardwarové platformy. Takový kompilátor může zjistit, že indikátorové proměnné flag[0] a flag[1] nejsou čteny uvnitř smyčky. Poté pomocí procesu zvaného odstranění invariantu ze smyčky odstraní zápisy do těchto proměnných z generovaného kódu operace, přičemž je považuje za nadbytečné. Pokud kompilátor zjistí, že proměnná turn se ve vnitřní smyčce nikdy nemění, může provést podobnou konverzi, což má za následek potenciální nekonečnou smyčku . Pokud dojde k některé z těchto transformací, algoritmus přestane fungovat bez ohledu na hardwarovou architekturu. Programovací jazyk může poskytovat klíčová slova (směrnice), která zakazují kompilátoru provádět popsané optimalizace pro zadanou proměnnou.