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

Алгоритм пекарни Лампорта - алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован учёным в области информатики Лесли Лампортом в 1974 году^[1].

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

АлгоритмПравить

АналогияПравить

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

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

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

Критическая секцияПравить

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

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

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

(n_a, i_a) < (n_b, i_b),

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

(n_a < n_b) or ((n_a == n_b) and (i_a < i_b))

Когда поток заканчивает работу в критической секции, он освобождает номер 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);
          // Выполнение некритической секции...
      }
  }

Пример кода на Java Править

AtomicIntegerArray ticket = new AtomicIntegerArray(threads); // ticket for threads in line, n - number of threads
// Каждый элемент 'ticket' инициализируется со значением 0
 
AtomicIntegerArray entering = new AtomicIntegerArray(threads); // 1 when thread entering in line
// Каждый элемент 'entering' инициализируется со значением 0
 
public void lock(int pid) // ID потока
{
    entering.set(pid, 1);
    int max = 0;
    for (int i = 0; i < threads; i++)
    {
        int current = ticket.get(i);
        if (current > max)
        {
            max = current;
        }
    }
    ticket.set(pid, 1 + max); 
    entering.set(pid, 0);
    for (int i = 0; i < ticket.length(); ++i)
    {
        if (i != pid)
        {
            while (entering.get(i) == 1) { Thread.yield(); } //  Ждём, пока поток i получит свой номер
            while (ticket.get(i) != 0 && ( ticket.get(i) < ticket.get(pid) ||
                    (ticket.get(i) == ticket.get(pid) && i < pid)))
            { Thread.yield(); }
        }
    }
    // Выполнение критической секции
}

public void unlock(int pid)
{
  ticket.set(pid, 0);
}

ОбсуждениеПравить

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

Необходимость массива Entering, возможно, не очевидна, так как в строках 7 — 13 псевдокода нет блокировок. Однако, допустим, что мы убрали этот массив, и два потока вычислили одно и то же значение Number[i]. Тогда, если поток с более высоким приоритетом был вытеснен перед вычислением Number[i], поток с меньшим приоритетом увидит, что первый процесс имеет Number[i] = 0 и войдёт в критическую секцию. Затем первый, более приоритетный, процесс проигнорирует совпадение номеров Number[i] и также войдёт в критическую секцию. В итоге два процесса будут одновременно выполнять критическую секцию. Entering нужен для выполнения операции в строке 6 как атомарной. Процесс i никогда не увидит Number[j] = 0, у процесса j, который собирается взять то же число, что и i.

При реализации псевдокода в однозадачной или многозадачной системе лучше заменить слова «ничего не делать» уведомлением системе немедленно переключиться на следующий поток. Этот примитив часто называется yield.

Алгоритм пекарни Лампорта предполагает использование модели памяти с последовательной согласованностью. Немногие, если таковые имеются, языки или многоядерные процессоры реализуют такую модель памяти. Поэтому правильная реализация алгоритма обычно требует вставки ограждений, чтобы препятствовать переупорядочиванию^[2].

ПримечанияПравить

↑ Оригинал статьи (неопр.). Дата обращения: 3 ноября 2016. Архивировано 18 апреля 2007 года.
↑ Chinmay Narayan, Shibashis Guha, S.Arun-Kumar Inferring Fences in a Concurrent Program Using SC proof of Correctness (англ.) Архивная копия от 4 ноября 2016 на Wayback Machine

На своей странице publications page, Лампорт сделал несколько замечаний по алгоритму.

ЛитератураПравить

Э. Таненбаум. Современные операционные системы = Modern Operating Systems. — «Питер», 2004. — 1040 с. — ISBN 5-318-00299-4.

Внешние ссылкиПравить

Вариант Волласа алгоритма пекарни который преодолевает ограничения языка Javascript (англ.)
Алгоритм пекарни Лампрта (англ.)
Ещё одна реализация на JavaScript от a.in.the.k (англ.)

См. такжеПравить

[1] Оригинал статьи (неопр.). Дата обращения: 3 ноября 2016. Архивировано 18 апреля 2007 года.

[2] Chinmay Narayan, Shibashis Guha, S.Arun-Kumar Inferring Fences in a Concurrent Program Using SC proof of Correctness (англ.) Архивная копия от 4 ноября 2016 на Wayback Machine

[1]

[2]