Алгоритм Деккерса - Dekkers algorithm

Алгоритм Деккера это первое известное правильное решение взаимное исключение проблема в параллельное программирование. Решение приписывается нидерландский язык математик Чт. Дж. Деккер к Эдсгер В. Дейкстра в неопубликованной статье о последовательном описании процессов[1] и его рукопись о взаимодействующих последовательных процессах.[2] Он позволяет двум потокам совместно использовать одноразовый ресурс без конфликтов, используя только Общая память для общения.

Он избегает строгого чередования наивного алгоритма очередности и был одним из первых алгоритмы взаимного исключения быть изобретенным.

Обзор

Если два процесса пытаются войти в критическая секция при этом алгоритм будет пропускать только один процесс, в зависимости от того, чья очередь это. Если один процесс уже находится в критической секции, другой процесс будет занято ждать для выхода первого процесса. Это делается с помощью двух флагов, want_to_enter [0] и want_to_enter [1], которые указывают на намерение войти в критическую секцию со стороны процессов 0 и 1 соответственно, а переменная повернуть это указывает, кто имеет приоритет между двумя процессами.

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

Алгоритм Деккера можно выразить в виде псевдокод, следующее.[3]

    переменные want_to_enter: массив из 2 логических значений turn: integer want_to_enter [0] ← false want_to_enter [1] ← false turn ← 0 // или 1
p0: want_to_enter [0] ← true, пока want_to_enter [1] {если поворот ≠ 0 {want_to_enter [0] ← false, пока поворот ≠ 0 {// занято, ожидание} want_to_enter [0] ← true}} // критическая секция ... Turn ← 1 want_to_enter [0] ← false // остаток раздела
p1: want_to_enter [1] ← true, пока want_to_enter [0] {если поворот ≠ 1 {want_to_enter [1] ← false, пока поворот ≠ 1 {// занято, ожидание} want_to_enter [1] ← true}} // критическая секция ... turn ← 0 want_to_enter [1] ← false // остаток раздела

Процессы указывают на намерение войти в критическую секцию, которая проверяется внешним циклом while. Если другой процесс не отметил намерение, в критическую секцию можно безопасно войти независимо от текущего хода. Взаимное исключение по-прежнему будет гарантировано, поскольку ни один процесс не может стать критическим до установки своего флага (подразумевается, что хотя бы один процесс войдет в цикл while). Это также гарантирует прогресс, поскольку не произойдет ожидания процесса, который отказался от намерения стать критическим. В качестве альтернативы, если была установлена ​​переменная другого процесса, вводится цикл while, и переменная поворота устанавливает, кому разрешено стать критическим. Процессы без приоритета откажутся от своего намерения войти в критическую секцию до тех пор, пока им снова не будет предоставлен приоритет (внутренний цикл while). Процессы с приоритетом выйдут из цикла while и войдут в свою критическую секцию.

Алгоритм Деккера гарантирует взаимное исключение, свобода от тупик, и свобода от голодание. Посмотрим, почему последнее свойство выполняется. Предположим, p0 навсегда застрял внутри цикла «while want_to_enter [1]». Существует свобода от тупиковой ситуации, поэтому в конечном итоге p1 перейдет к своему критическому участку и установит turn = 0 (и значение поворота останется неизменным, пока p0 не прогрессирует). В конце концов p0 вырвется из внутреннего цикла «while Turn ≠ 0» (если он когда-либо застрял на нем). После этого он установит want_to_enter [0] в значение true и перейдет в режим ожидания, пока want_to_enter [1] не станет false (поскольку turn = 0, он никогда не будет выполнять действия в цикле while). В следующий раз, когда p1 попытается войти в свою критическую секцию, он будет вынужден выполнить действия в своем цикле «while want_to_enter [0]». В частности, он в конечном итоге установит want_to_enter [1] в значение false и застрянет в цикле «while turn ≠ 1» (поскольку поворот остается 0). В следующий раз, когда управление перейдет к p0, он выйдет из цикла «while want_to_enter [1]» и войдет в его критическую секцию.

Если алгоритм был изменен путем выполнения действий в цикле «while want_to_enter [1]» без проверки, если turn = 0, то есть вероятность голодания. Таким образом, все шаги в алгоритме необходимы.

Примечания

Одним из преимуществ этого алгоритма является то, что он не требует специальных испытать и установить (атомарное чтение / изменение / запись), поэтому его можно легко переносить между языками и машинными архитектурами. Одним из недостатков является то, что он ограничен двумя процессами и использует занято ожиданием вместо приостановки процесса. (Использование ожидания при занятости предполагает, что процессы должны проводить минимальное количество времени внутри критической секции.)

Современные операционные системы предоставляют примитивы взаимного исключения, которые являются более общими и гибкими, чем алгоритм Деккера. Однако в отсутствие реальной конкуренции между двумя процессами вход и выход из критической секции чрезвычайно эффективны при использовании алгоритма Деккера.

Многие современные Процессоры выполнять их инструкции не по порядку; даже доступ к памяти может быть переупорядочен (см. порядок памяти ). Этот алгоритм не работает SMP машины, оснащенные этими процессорами, без использования барьеры памяти.

Кроме того, многие оптимизирующие компиляторы могут выполнять преобразования, которые приведут к сбою этого алгоритма независимо от платформы. Во многих языках компилятор может обнаружить, что переменные флага want_to_enter [0] и want_to_enter [1] никогда не доступны в цикле. Затем он может удалить записи в эти переменные из цикла, используя процесс, называемый движение кода с инвариантным циклом. Многие компиляторы также могут обнаружить, что повернуть переменная никогда не изменяется внутренним циклом и выполняет аналогичное преобразование, что приводит к потенциальному бесконечный цикл. Если любое из этих преобразований выполнено, алгоритм выйдет из строя независимо от архитектуры.

Чтобы решить эту проблему, летучий переменные должны быть помечены как изменяемые вне области текущего выполняемого контекста. Например, в C # или Java эти переменные можно пометить как «изменчивые». Однако обратите внимание, что атрибут «volatile» C / C ++ гарантирует только то, что компилятор генерирует код с правильным порядком; он не включает необходимые барьеры памяти чтобы гарантировать порядок исполнение этого кода. C ++ 11 атомарные переменные могут использоваться, чтобы гарантировать соответствующие требования к порядку - по умолчанию операции с атомарными переменными последовательно согласованы, поэтому, если переменные want_to_enter и turn являются атомарными, наивная реализация будет «просто работать». В качестве альтернативы порядок может быть гарантирован путем явного использования отдельных ограждений, а операции загрузки и хранения - с использованием упрощенного порядка.

Смотрите также

Рекомендации

  1. ^ Дейкстра, Эдсгер В. За последовательным фургоном (EWD-35) (PDF). Архив Э.В. Дейкстры. Центр американской истории, Техасский университет в Остине. (транскрипция ) (без даты, 1962 или 1963); английский перевод О последовательности описания процессов
  2. ^ Дейкстра, Эдсгер В. Взаимодействующие последовательные процессы (EWD-123) (PDF). Архив Э.В. Дейкстры. Центр американской истории, Техасский университет в Остине. (транскрипция ) (Сентябрь 1965 г.)
  3. ^ Алагарсамы, К. (2003). «Некоторые мифы об известных алгоритмах взаимного исключения». Новости ACM SIGACT. 34 (3): 94–103. Дои:10.1145/945526.945527.