Алгоритм пекарни Лампорта

Лампорт предлагает рассмотреть пекарню с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того, как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.

Пусть покупатели - это потоки, получившие номера i от глобальной переменной.

Из-за ограничений компьютерной архитектуры момент выдачи номерков должен быть немного модифицирован, так как возникает ситуация неоднозначности в случае, если сразу два или несколько покупателей (потоков) захотели получить номерок с номером n. При наличии нескольких потоков, получивших номер n при входе в критическую секцию, поток с меньшим номером i будет иметь больший приоритет при обслуживании (входе в критическую секцию).

Критическая секция — это часть кода, которая требует исключительного доступа к ресурсам, и одновременно может выполняться только одним потоком.

Когда поток хочет войти в критическую секцию, он должен проверить, может ли он это сейчас сделать. Поток должен проверить номера n, полученные другими потоками, и убедиться, что у него меньший номер. В случае совпадения n у двух или нескольких потоков, в критическую секцию входит поток с наименьшим i.

На псевдокоде это сравнение для потоков a и b может быть записано как:

(na, ia) < (nb, ib),

что эквивалентно:

(na < nb) or ((na == nb) and (ia < ib))

Когда поток заканчивает работу в критической секции, он освобождает номер n и входит в некритическую секцию.

Некритическая секция — это часть кода, не имеющая ресурсов, требующих исключительного доступа. Это код, который могут выполнять несколько потоков параллельно, не мешая друг другу.

Если вернуться к аналогии, то это часть действий, которые происходят после совершения покупки. Например, возврат сдачи в бумажник.

В оригинальной статье Лампорта к процессу и нумерующей (entering, choosing) переменной применяются следующие условия:

• Байтовые слова нумерующей переменной [i] и номера (number) [i] находятся в памяти процесса i и инициализированы нулём.
• Диапазон значений номера [i] неограничен.
• Процесс может упасть в любой момент. Предполагается, что при падении он немедленно идёт в некритическую секцию и прерывается. Может быть период, когда чтение из памяти процесса даёт произвольные значения. Но в конце концов любое чтение из памяти процесса должно возвращать ноль.

В примере ниже все потоки выполняют одну и ту же «главную» функцию Thread. В реальных приложениях разные потоки часто имеют разные «главные» функции. Как и в оригинальной статье, здесь потоки проверяют себя перед входом в критическую секцию. Так как условие цикла вернет false, проверка не даёт существенную задержку выполнения.

  // Объявление и инициализация значениями глобальных переменных
  Entering: array [1..NUM_THREADS] of bool = {false};
  Number: array [1..NUM_THREADS] of integer = {0};

  lock(integer i) {
      Entering[i] = true;
      Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
      Entering[i] = false;
      for (integer j = 1; j <= NUM_THREADS; j++) {
          // Ждём, пока поток j получит свой номер:
          while (Entering[j]) { /* ничего не делать */ }
          // Ждём, пока все потоки с меньшим номером или с таким же номером,
          // но с более высоким приоритетом, закончат свою работу:
          while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* ничего не делать*/ }
      }
  }
  
  unlock(integer i) {
      Number[i] = 0;
  }

  Thread(integer i) {
      while (true) {
          lock(i);
          // Выполнение критической секции...
          unlock(i);
          // Выполнение некритической секции...
      }
  }