Реализации алгоритмов/Алгоритм Деккера

Алгоритм Деккера — первое известное корректное решение проблемы взаимного исключения в параллельном программировании. Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации. Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов «намерения» войти в критическую секцию) и переменной 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;
   // другие секции