WikiSort.ru - Не сортированное

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

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

Алгоритм

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

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

Реализация алгоритма

 0   // Объявление и инициализация значениями глобальных переменных
 1   Entering: array [1..NUM_THREADS] of bool = {false};
 2   Number: array [1..NUM_THREADS] of integer = {0};
 3 
 4   lock(integer i) {
 5       Entering[i] = true;
 6       Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
 7       Entering[i] = false;
 8       for (integer j = 1; j <= NUM_THREADS; j++) {
 9           // Ждём, пока поток j получит свой номер:
10           while (Entering[j]) { /* ничего не делать */ }
11           // Ждём, пока все потоки с меньшим номером или с таким же номером,
12           // но с более высоким приоритетом, закончат свою работу:
13           while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* ничего не делать*/ }
14       }
15   }
16   
17   unlock(integer i) {
18       Number[i] = 0;
19   }
20 
21   Thread(integer i) {
22       while (true) {
23           lock(i);
24           // Выполнение критической секции...
25           unlock(i);
26           // Выполнение некритической секции...
27       }
28   }

 1  ArrayList<Integer> ticket = new ArrayList<>(threads); // ticket for threads in line, n - number of threads
 2  // Java initializes each element of 'ticket' to 0
 3  
 4  ArrayList<Boolean> entering = new ArrayList<>(threads); // 1 when thread entering in line
 5  // Java initializes each element of 'entering' to 0
 6  
 7  public void lock(int pid) // thread ID
 8  {
 9      entering.set(pid, true);
10      int max = 0;
11      for (int i = 0; i < threads; i++)
12      {
13          int current = ticket.get(i);
14          if (current > max)
15          {
16              max = current;
17          }
18      }
19      ticket.set(pid, 1 + max); 
20      entering.set(pid, false);
21      for (int i = 0; i < ticket.length(); ++i)
22      {
23          if (i != pid)
24          {
25              while (entering.get(i) == 1) { Thread.yield(); } // wait while other thread picks a ticket
26              while (ticket.get(i) != 0 && ( ticket.get(pid) > ticket.get(i)  ||
27                      (ticket.get(pid) == ticket.get(i) && pid > i)))
28              { Thread.yield(); }
29          }
30      }
31      // The critical section goes here...
32  }
33 
34  public void unlock(int pid)
35  {
36    ticket.set(pid, 0);
37  }

Обсуждение

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

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

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

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

Примечания

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

Литература

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

Внешние ссылки

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

См. также

• Алгоритм Петерсона
• Алгоритм Деккера
• Семафор
• Мьютекс