Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Деккера

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

Введение

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

Псевдокод

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

     flag := true
     while flag = true {
         if turn ≠ 0 {
             flag := false
             while turn ≠ 0 {
             }
             flag := true
         }
     }
 
    // критическая секция
    ...
    turn := 1
    flag := false
    // конец критической секции
    ...

     flag := true
     while flag = true {
         if turn ≠ 1 {
             flag := false
             while turn ≠ 1 {
             }
             flag := true
         }
     }

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

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

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

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