Алгоритм Деккера (Glikjnmb :yttyjg)

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

Введение

Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов «намерения» войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).

Псевдокод

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

p0:

     flag[0] := true
     while flag[1] = true {
         if turn = 1 {
            flag[0] := false
            while turn = 1 {
                // холостое ожидание
            }
            flag[0] := true
         }
     }
 
    // критическая секция
    ...
    turn := 1
    flag[0] := false
    // конец критической секции
    ...

p1:

     flag[1] := true
     while flag[0] = true {
         if turn = 0 {
             flag[1] := false
             while turn = 0 {
                 // холостое ожидание
             }
             flag[1] := true
         }
     }

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

Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти (вне зависимости от того, чья сейчас очередь). Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага (подразумевается, что, по крайней мере, один процесс войдёт в цикл «while»). Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь (внутренний цикл «while»). Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.

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

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

Особенности

Одним из преимуществ алгоритма является то, что он не требует специальных команд «проверить-установить» — атомарных операций чтения, модификации и записи — и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость только к случаю с двумя процессами и использование ждущего цикла^[англ.] вместо приостановки процесса: использование ждущего цикла предполагает, что процессы должны проводить минимальное количество времени внутри критической секции.

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

Многие современные микропроцессоры исполняют инструкции не по порядку, даже порядок доступа к памяти может не соблюдаться (см. упорядоченность доступа к памяти^[англ.]). Алгоритм не будет работать на SMP-машинах, оборудованных такими процессорами, если не использовать барьеры памяти.

Кроме того, оптимизирующие компиляторы могут проводить такие преобразования программы, что данный алгоритм перестанет работать независимо от проблем аппаратной платформы. Такой компилятор может обнаружить, что индикаторные переменные flag[0] и flag[1] не читаются внутри цикла. Тогда, с помощью процесса, который называется выносом инварианта из цикла^[англ.], он удалит из генерируемого кода операции записи в эти переменные, посчитав их избыточными. Если компилятор обнаружит, что переменная turn никогда не изменяется во внутреннем цикле, то он может выполнить аналогичное преобразование, что приведёт к потенциальному бесконечному циклу. Если будет сделано любое из этих преобразований, алгоритм перестанет работать вне зависимости от аппаратной архитектуры. Язык программирования может предусматривать ключевые слова (директивы), запрещающие компилятору производить описанные оптимизации для указанной переменной.

См. также

Имеется викиучебник по теме «Реализации алгоритмов/Алгоритм Деккера»

Примечания

↑ E.W. Dijkstra, Cooperating Sequential Processes Архивная копия от 4 февраля 2010 на Wayback Machine, 1965.

[1] E.W. Dijkstra, Cooperating Sequential Processes Архивная копия от 4 февраля 2010 на Wayback Machine, 1965.

[1]