Реализации алгоритмов/Алгоритм Деккера
Внешний вид
Алгоритм Деккера — первое известное корректное решение проблемы взаимного исключения в параллельном программировании. Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации. Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов «намерения» войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).
C++
[править] // entrance_intents - булевый массив; turn - целое
for (i = 0; i < NUM_THREADS; ++i) entrance_intents[i] = false
turn = 0 // or NUM_THREADS-1
Pi:
bool do_not_enter = false;
entrance_intents[i] = true;
for (unsigned int j = 0; j < NUM_THREADS; ++j)
if (j != i && entrance_intents[j] == true) {
do_not_enter = true;
break;
}
while (do_not_enter || turn != i) {
if (turn != i) {
entrance_intents[i] = false;
while (turn != i) {
// ждущий цикл (busy wait)
}
entrance_intents[i] = true;
}
do_not_enter = false;
for (unsigned int j = 0; j < NUM_THREADS; ++j)
if (j != i && entrance_intents[j] == true) {
do_not_enter = true;
break;
}
}
// критическая секция
...
turn = (i+1) % NUM_THREADS;
entrance_intents[i] = false;
// другие секции