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

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

Передмова

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

Псевдокод

flag[0] := false flag[1] := false turn := 0 // or 1
p0: flag[0] := true while flag[1] = true { if turn ≠ 0 { flag[0] := false while turn ≠ 0 { } flag[0] := true } } // критична секція ... turn := 1 flag[0] := false // решта коду	p1: 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 машинах, обладнаних такими центральними процесорами, без використання бар'єрів пам'яті.

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

Реалізація на C++

bool threads[2];
int turn;
void func(int thread_id)
{
    threads[thread_id] = true;
    while (threads[1-thread_id])
    {
        // Сюди ми потрапляємо коли ще хтось виявив бажання увійти в критичну секцію 
        // Якщо черга наша, тоді інший процес має відмовитись від свого бажання
        if (turn != thread_id)
        {
            // Наступний рядок обов'язковий, щоб інший процес міг вийти із зовнішнього циклу
            threads[thread_id] = false;
            // Якщо черга не наша, очікуємо...
            while (turn != thread_id) {}
            threads[thread_id] = true;
        }
    }
    critical_function();
    // Ресурс нам більше не потрібен
    turn = 1-thread_id;
    threads[thread_id] = false;
}

Узагальнення

Дейкстра змінив алгоритм надавши можливість підтримки до 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.