Алгоритм Деккера
Алгоритм Деккера - первое известное корректное решение проблемы взаимного исключения в конкурентном программировании. Эдсгер Дейкстра ссылается на голландского математика Т. Деккера как на автора данного алгоритма в своей работе о межпроцессном взаимодействии[1]. Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации.
Введение
Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критческую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов "намерения" войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).
Псевдокод
flag[0] := false flag[1] := false turn := 0 // or 1 | |
p0:
flag[0] := true
while flag[1] = true {
if turn ≠ 0 {
flag[0] := false
while turn ≠ 0 {
}
flag[0] := true
}
}
// критическая секция
...
turn := 1
flag[0] := false
// конец критической секции
...
|
p1:
flag[1] := true
while flag[0] = true {
if turn ≠ 1 {
flag[1] := false
while turn ≠ 1 {
}
flag[1] := true
}
}
// критическая секция
...
turn := 0
flag[1] := false
// конец критической секции
|
Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти (вне зависимости от того, чья сейчас очередь). Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага (подразумевается, что, по крайней мере, один процесс войдёт в цикл «while»). Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь (внутренний цикл «while»). Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.
Алгоритм Деккера гарантирует взаимное исключение, невозможность возникновения deadlock или starvation. Рассмотрим, почему справедливо последнее свойство. Предположим, что p0 остался внутри цикла «while flag[1]» навсегда. Поскольку взаимная блокировка произойти не может, рано или поздно p1 достигнет своей критической секции и установит turn = 0 (значение turn будет оставаться постоянным пока p0 не продвигается). p0 выйдет из внутреннего цикла «while turn ≠ 0» (если он там находился). После этого он присвоит flag[0] значение true и будет ждать, пока flag[1] примет значение false (так как turn = 0, он никогда не выполняет действия в цикле «while»). В следующий раз когда p1 попытается войти в критическую секцию, он будет вынужден исполнить действия в цикле «while flag[0]». В частности, он присвоит flag[1] значение false и будет исполнять цикл «while turn ≠ 1» (так как turn остаётся равной 0). Когда в следующий раз управление перейдёт к p0, он выйдет из цикла «while flag[1]» и войдёт в критическую секцию.
Если модифицировать алгоритм так, чтобы действия в цикле «while flag[1]» выполнялись без проверки условия «turn = 0», то появится возможность starvation. Таким образом, все шаги алгоритма являются необходимыми.
Особенности
Одним из преимуществ алгоритма является то, что он не требует специальных Test-and-set (атомарная операция чтения, модификации и записи) инструкций и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость только к случаю с ровно двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).
Современные операционные системы предоставляют примитивы синхронизации более общие и гибкие по сравнению с алгоритмом Деккера. Тем не менее, следует заметить, что в случае отсутствия реальной конкуренции между двумя процессами, операции входа в критическую секцию и выхода из неё будут являться очень эффективными при использовании этого алгоритма.
Многие современные микропроцессоры исполняют инструкции не по порядку. Алгоритм не будет работать на SMP-машинах, оборудованных такими CPU, если не использовать барьеры памяти.
Примечания
- ↑ E.W. Dijkstra, Cooperating Sequential Processes, 1965.
См. также
| Программирование | Это незавершённая статья о программировании. Вы можете помочь проекту, исправив и дополнив её. |
ca:Algorisme de Dekker de:Dekker-Algorithmus en:Dekker's algorithm es:Algoritmo de Dekker fr:Algorithme de Dekker it:Algoritmo di Dekker ja:デッカーのアルゴリズム ko:데커의 알고리즘 pl:Algorytm Dekkera tr:Dekker algoritması
Если вам нравится SbUP.com Сайт, вы можете поддержать его - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 и ещё....
