Алгоритм Декера

Якщо два процеси намагаються увійти до критичної секції одночасно, алгоритм дозволить увійти лише одному процесу, виходячи з того чия зараз черга. Якщо один з процесів знаходиться в критичній секції, другий буде в стані очікування доки перший процес не залишить критичну секцію. Це робиться шляхом використання двох прапорців, flag[0] і flag[1], які показують намір увійти до критичної секції, та змінну turn, яка показує який з процесів зараз пріоритетніший.

 flag[0] := false
 flag[1] := false
 turn := 0   // or 1

     flag[0] := true
     while flag[1] = true {
         if turn ≠ 0 {
             flag[0] := false
             while turn ≠ 0 {
             }
             flag[0] := true
         }
     }
 
    // критична секція
    ...
    turn := 1
    flag[0] := false
    // решта коду

     flag[1] := true
     while flag[0] = true {
         if turn ≠ 1 {
             flag[1] := false
             while turn ≠ 1 {
             }
             flag[1] := true
         }
     }

     // критична секція
     ...
     turn := 0
     flag[1] := false
     // решта коду

Процеси показують намір увійти до критичної секції, що перевіряється у зовнішньому циклі. Якщо інший процес не позначив свій намір, до критичної секції можна війти, попри те чия зараз черга. Взаємне виключення буде все одно гарантоване, тому що жоден процес не може увійти до критичної секції перед встановленням свого прапорця (тобто щонайменше один процес увійде в цикл while). Також це гарантує рух уперед через відсутність очікування процесу, який скасував намір увійти до критичної секції. Інакше, якщо змінна другого була встановлена, відбувається вхід до циклу while і змінна turn буде вказувати, кому дозволено увійти до критичної секції. Процес, чия черга не настала, полишає намір увійти до критичної секції доти, доки не настане його черга (внутрішній цикл while). Процеси, чия черга надійшла, виходять з циклу while і входять до своєї критичної секції.

Алгоритм Декера гарантує взаємне виключення, неможливість виникнення взаємних блокувань або ресурсного голоду. Якщо алгоритм був би змінений таким чином, щоб при виконанні дій всередині зовнішнього циклу while не перевірялась умова на рівність нулю змінної turn, тоді виникла б можливість ресурсного голоду. Таким чином всі кроки алгоритму необхідні.

Перевагою цього алгоритму є те, що він не вимагає особливої команди Test-and-set (атомарного читання-і-зміни) і, таким чином, легко переноситься між різними мовами і машинними архітектурами. Недоліком є те, що в оригіналі він призначений тільки для двох процесів, а також використовує стан очікування замість призупинення процесу. (Використання стану очікування означає, що процес має знаходитися якнайменше часу всередині критичної секції.)

Багато сучасних центральних процесорів виконують операції не послідовно (одна за одною), навіть звертання до пам'яті може здійснюватися зі зміною порядку операцій. Тому цей алгоритм не буде працювати на SMP машинах, обладнаних такими центральними процесорами, без використання бар'єрів пам'яті.

Сучасні операційні системи надають більш загальні та гнучкі примітиви взаємного виключення. Тим не менше, за відсутності реальної конкуренції між процесами, операції входу і виходу з критичної секції із використанням алгоритму Декера дуже ефективні.

Дейкстра змінив алгоритм надавши можливість підтримки до N процесів. Через необхідність попереднього визначення N новий варіант підходить для будь-якої кількості процесів, але не більше N, що робить його досить практичним.

На відміну від алгоритму Декера масив flag має розмір N і складається з елементів із трьома значеннями. Три значення описують відповідні ситуації: пасивний, процес наразі не має потреби критичній секції; із запитом, процес намагається увійти в критичну секцію; і активний, тобто процес виконує критичну секцію.

const int N = .. ;
enum F : int
{
  Passive,
  Requesting,
  Active
}
F[] flags = new F[N]; // всі встановлені як пасивні
int turn = 0;
void EnterCriticalRegion(int i)
{
  int j;
  do
  {
    flags[i] = F.Requesting; // показуємо нашу зацікавленість
    while(turn != i)  // очікуємо на свою чергу
      if (flags[turn] == F.Passive)
        turn = i;
    flags[i] = F.Active;  // анонсуємо входження
    // перевіряємо, що ніхто інший не увійшов
    for (j = 0;
         j < N && (j == i || flags[j] != F.Active);
         j==;);
  }
  while (j < N);
}

void LeaveCriticalRegion(int i)
{
  flags[i] = F.Passive;  // лиш вказуємо, що ми закінчили
}

Зауважимо, що так само як і базовий алгоритм Декера цей код не буде працювати з сучасними компіляторами і процесорами через високу ймовірність виконання не по черзі. Цей код лиш показує логічну послідовність.

• Joe Duffy. 2: Synchronization and Time // Concurrent Programming on Windows. — Addison-Wesley, 2008. — С. 52-53. — ISBN 978-0-321-4348-1.