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

Алгоритм Деккера — это первый известный алгоритм взаимного исключения (mutual exclusion) для двух процессов или потоков, работающих с общей памятью и не использующих специальных атомарных инструкций процессора. Разработан нидерландским математиком и программистом Теодорусом Йозефом Деккером (Theodorus Jozef Dekker) в начале 1960-х годов. Алгоритм решает классическую проблему критической секции, гарантируя, что только один из двух процессов может находиться в своём критическом участке кода в любой момент времени, при этом исключая взаимную блокировку (deadlock) и обеспечивая прогресс (liveness).

История

Проблема синхронизации доступа к общим ресурсам возникла на заре развития многозадачных операционных систем. В 1965 году Эдсгер Дейкстра в своей статье «Cooperating sequential processes» описал несколько алгоритмов взаимного исключения, среди которых алгоритм Деккера был представлен как первое корректное решение для двух процессов. Дейкстра отмечал, что алгоритм был предложен Деккером в ходе личной переписки. Впоследствии алгоритм стал классическим примером в учебной литературе по операционным системам и параллельному программированию, демонстрируя принципы программного управления доступом к разделяемым данным без аппаратной поддержки.

Принцип работы

Алгоритм предназначен для двух потоков (назовём их P0 и P1), которые могут выполняться асинхронно. Каждый поток имеет свой собственный флаг (flag), который он устанавливает, когда хочет войти в критическую секцию. Кроме того, используется общая переменная-очередь (turn), которая указывает, чья сейчас очередь, если оба потока одновременно пытаются войти в критическую секцию.

Переменные

Для работы алгоритма необходимы три разделяемые переменные:

• flag[0] — булева переменная, показывающая, намерен ли поток 0 войти в критическую секцию.
• flag[1] — булева переменная, показывающая, намерен ли поток 1 войти в критическую секцию.
• turn — целочисленная переменная, принимающая значения 0 или 1, указывающая, какой поток имеет приоритет при одновременном запросе.

Псевдокод

Для потока i (i = 0 или 1, другой поток обозначается j = 1 - i):

`` flag[i] = true while (flag[j] == true) { if (turn != i) { flag[i] = false while (turn != i) { // ожидание } flag[i] = true } } // Критическая секция turn = j flag[i] = false // Остальная часть (некритическая секция) ``

Пошаговое описание

1. Намерение: Поток i устанавливает свой флаг в true, сигнализируя о желании войти в критическую секцию.
2. Проверка соперника: Поток проверяет флаг другого потока. Если он равен false, поток немедленно входит в критическую секцию.
3. Конфликт: Если оба флага равны true, возникает конкуренция. Тогда поток i проверяет переменную turn:

• Если turn == i, поток остаётся в цикле ожидания, пока другой поток не выйдет из критической секции и не изменит turn.
• Если turn != i, поток i временно снимает свой флаг (устанавливает false), уступая дорогу, и ждёт, пока turn не станет равным i. После этого он снова устанавливает флаг и повторяет проверку.

1. Выход: После завершения критической секции поток устанавливает turn в значение другого потока, передавая ему приоритет, и сбрасывает свой флаг в false.

Свойства

Алгоритм Деккера гарантирует выполнение трёх основных требований к решению проблемы критической секции:

• Взаимное исключение (Mutual Exclusion): В любой момент времени только один поток может находиться в критической секции. Это достигается за счёт комбинации флагов и переменной turn.
• Прогресс (Progress): Если ни один поток не находится в критической секции, а один или оба потока хотят в неё войти, то решение о том, кто войдёт, принимается только на основе флагов и переменной turn, и не может быть отложено бесконечно. Алгоритм не позволяет одному потоку бесконечно блокировать другого, если тот не входит в критическую секцию.
• Ограниченное ожидание (Bounded Waiting): Существует гарантия, что каждый поток, желающий войти в критическую секцию, получит доступ после конечного числа попыток. В алгоритме Деккера это обеспечивается переменной turn, которая передаёт приоритет другому потоку после выхода из критической секции.

Критика и ограничения

Несмотря на свою историческую важность, алгоритм Деккера имеет несколько существенных недостатков, которые ограничивают его практическое применение в современных системах:

• Ограничение на два потока: Алгоритм работает только для двух процессов. Для большего количества потоков требуются более сложные решения, такие как алгоритм Петерсона (обобщение для n потоков) или алгоритм булочной (Lamport's bakery algorithm).
• Зависимость от модели памяти: Алгоритм предполагает последовательную согласованность памяти (sequential consistency), которая не гарантируется на современных многоядерных процессорах с оптимизациями компилятора и процессора (например, переупорядочивание инструкций). На практике для корректной работы требуются барьеры памяти (memory barriers) или атомарные операции.
• Активное ожидание (Busy waiting): Потоки, ожидающие доступа к критической секции, постоянно выполняют проверки в цикле, что приводит к неэффективному использованию процессорного времени. В современных системах это решается с помощью примитивов синхронизации, таких как мьютексы и семафоры, которые переводят поток в состояние ожидания.
• Сложность для понимания: Логика алгоритма, особенно обработка случая одновременного запроса, нетривиальна, что делает его уязвимым для ошибок при реализации.

Применение

В современных операционных системах и языках программирования алгоритм Деккера не используется напрямую. Вместо него применяются аппаратные атомарные инструкции (например, compare-and-swap, test-and-set), которые позволяют реализовать эффективные и масштабируемые примитивы синхронизации. Однако алгоритм остаётся важным педагогическим инструментом для изучения проблем параллелизма, взаимного исключения и основ программной синхронизации. Он демонстрирует, как можно решить задачу без специальной аппаратной поддержки, и служит отправной точкой для понимания более сложных алгоритмов.

Интересные факты

• Алгоритм Деккера является одним из первых примеров программного решения проблемы взаимного исключения, предшествовавшим появлению аппаратных атомарных операций.
• Теодорус Деккер, работавший в компании Philips, опубликовал алгоритм в неформальной заметке, которая позже была популяризирована Дейкстрой.
• В 1970-х годах Гэри Петерсон предложил упрощённый вариант алгоритма для двух потоков, который также известен как алгоритм Петерсона. Он считается более изящным и простым для понимания, хотя и не лишён тех же фундаментальных ограничений.

Источники

• Dijkstra, E. W. (1965). "Cooperating sequential processes". Technical Report EWD-123, Eindhoven University of Technology.
• Tanenbaum, A. S., & Bos, H. (2015). "Modern Operating Systems" (4th ed.). Pearson.
• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). "Operating System Concepts" (10th ed.). Wiley.