Алгоритм Деккера — первое известное правильное решение проблемы взаимного исключения в параллельном программировании , когда процессы взаимодействуют только через общую память. Решение приписывается голландскому математику Т. Дж. Деккер Эдсгера В. Дейкстры в неопубликованной статье об описании последовательных процессов [1] и его рукописи о взаимодействующих последовательных процессах . [2] Это позволяет двум потокам совместно использовать одноразовый ресурс без конфликтов, используя для связи только общую память .
Он позволяет избежать строгого чередования наивного алгоритма очередности и является одним из первых изобретенных алгоритмов взаимного исключения .
Если два процесса попытаются войти в критическую секцию одновременно, алгоритм разрешит вход только одному процессу, в зависимости от того, чья это очередь . Если один процесс уже находится в критической секции, другой процесс будет занят ожиданием выхода первого процесса. Это делается с помощью двух флагов, Want_to_enter[0] и Want_to_enter[1] , которые указывают на намерение войти в критическую секцию со стороны процессов 0 и 1 соответственно, и переменной поворот , которая указывает, кто имеет приоритет между два процесса.
Алгоритм Деккера можно выразить в псевдокоде следующим образом. [3]
Процессы указывают на намерение войти в критическую секцию, которая проверяется внешним циклом while. Если другой процесс не обозначил намерение, в критическую секцию можно безопасно войти независимо от текущего хода. Взаимное исключение по-прежнему будет гарантировано, поскольку ни один процесс не может стать критическим до установки своего флага (подразумевается, что хотя бы один процесс войдет в цикл while). Это также гарантирует прогресс, поскольку процессу, который отказался от намерения стать критическим, не придется ждать. Альтернативно, если была установлена переменная другого процесса, вводится цикл while, и переменная поворота определяет, кому разрешено стать критическим. Процессы без приоритета откажутся от своего намерения войти в критическую секцию до тех пор, пока им снова не будет предоставлен приоритет (внутренний цикл while). Процессы с приоритетом выйдут из цикла while и перейдут в свою критическую секцию.
Алгоритм Деккера гарантирует взаимное исключение , свободу от тупиковой ситуации и свободу от голода . Давайте посмотрим, почему сохраняется последнее свойство. Предположим, что p0 навсегда застрял внутри цикла while Wants_to_enter[1] . Существует свобода от тупиковой ситуации, поэтому в конечном итоге p1 перейдет к своей критической секции и установит поворот = 0 (и значение поворота останется неизменным до тех пор, пока p0 не будет прогрессировать). В конце концов p0 вырвется из внутреннего цикла while Turn ≠ 0 (если он когда-либо в нем застревал). После этого он установит для Want_to_enter[0] значение true и перейдет к ожиданию, пока Want_to_enter[1] станет ложным (поскольку Turn = 0 он никогда не будет выполнять действия в цикле while). В следующий раз, когда p1 попытается войти в свою критическую секцию, он будет вынужден выполнить действия из цикла while Wants_to_enter[0] . В частности, в конечном итоге он установит для Want_to_enter[1] значение false и застрянет в цикле while Turn ≠ 1 (поскольку Turn остается 0). В следующий раз, когда управление перейдет к p0, он выйдет из цикла while Wants_to_enter[1] и войдет в его критическую секцию.
Если алгоритм был изменен путем выполнения действий в цикле while Wants_to_enter[1] без проверки Turn = 0 , то существует вероятность голодания. Таким образом, все шаги алгоритма являются необходимыми.
Одним из преимуществ этого алгоритма является то, что он не требует специальных инструкций тестирования и установки (атомарного чтения/изменения/записи) и, следовательно, обладает высокой переносимостью между языками и машинными архитектурами. Одним из недостатков является то, что он ограничен двумя процессами и вместо приостановки процесса используется ожидание занятости . (Использование ожидания занятости предполагает, что процессы должны проводить минимальное количество времени внутри критической секции.)
Современные операционные системы предоставляют примитивы взаимного исключения, которые являются более общими и гибкими, чем алгоритм Деккера. Однако при отсутствии фактического конфликта между двумя процессами вход и выход из критической секции чрезвычайно эффективен при использовании алгоритма Деккера.
Многие современные процессоры выполняют свои инструкции вне очереди; даже доступ к памяти может быть переупорядочен (см. порядок доступа к памяти ). Этот алгоритм не будет работать на машинах SMP , оснащенных этими процессорами, без использования барьеров памяти .
Кроме того, многие оптимизирующие компиляторы могут выполнять преобразования, которые приведут к сбою этого алгоритма независимо от платформы. Во многих языках компилятор может обнаружить, что переменные-флаги Want_to_enter[0] и Want_to_enter[1] никогда не доступны в цикле. Затем он может удалить записи в эти переменные из цикла, используя процесс, называемый движением кода, инвариантного к циклу . Многие компиляторы также могли бы обнаружить, что переменная поворота никогда не изменяется во внутреннем цикле, и выполнить аналогичное преобразование, что приведет к потенциальному бесконечному циклу . Если любое из этих преобразований будет выполнено, алгоритм потерпит неудачу, независимо от архитектуры.
Чтобы облегчить эту проблему, изменчивые переменные должны быть помечены как изменяемые вне области текущего исполняемого контекста. Например, в C, C++, C# или Java эти переменные можно было бы пометить как «изменчивые». Однако обратите внимание, что атрибут C/C++ «летучий» гарантирует только то, что компилятор генерирует код с правильным порядком; он не включает необходимые барьеры памяти , чтобы гарантировать упорядоченное выполнение этого кода. Атомарные переменные C++11 могут использоваться для обеспечения соответствующих требований к порядку — по умолчанию операции с атомарными переменными являются последовательно согласованными, поэтому, если переменные Want_to_enter и Turn являются атомарными, наивная реализация будет «просто работать». Альтернативно, упорядочение может быть гарантировано за счет явного использования отдельных ограждений, а операции загрузки и сохранения используют смягченный порядок.