Пекарский алгоритм Лэмпорта — это компьютерный алгоритм , разработанный учёным-компьютерщиком Лесли Лэмпортом в рамках его длительного исследования формальной корректности параллельных систем , который предназначен для повышения безопасности использования общих ресурсов несколькими потоками посредством взаимного исключения .
В информатике часто бывает так, что несколько потоков одновременно обращаются к одним и тем же ресурсам. Повреждение данных может произойти, если два или более потоков попытаются записать данные в одну и ту же ячейку памяти или если один поток считывает данные из ячейки памяти до того, как другой закончит запись в нее. Алгоритм Lamport's bakery — один из многих алгоритмов взаимного исключения , разработанных для предотвращения одновременного входа параллельных потоков в критические разделы кода, чтобы исключить риск повреждения данных.
Лампорт представил себе пекарню с нумерационной машиной у входа, чтобы каждому клиенту присваивался уникальный номер. Номера увеличиваются на единицу, когда клиенты входят в магазин. Глобальный счетчик отображает номер клиента, который в данный момент обслуживается. Все остальные клиенты должны ждать в очереди, пока пекарь не закончит обслуживать текущего клиента и не отобразится следующий номер. Когда клиент заканчивает делать покупки и избавляется от своего номера, продавец увеличивает номер, позволяя обслужить следующего клиента. Этот клиент должен вытянуть еще один номер из нумерационной машины, чтобы снова сделать покупки.
Согласно аналогии, «клиенты» — это потоки, обозначенные буквой i , полученной из глобальной переменной.
Из-за ограничений компьютерной архитектуры некоторые части аналогии Лампорта требуют незначительной модификации. Возможно, что более чем один поток получит одно и то же число n , когда они его запросят; этого нельзя избежать (без предварительного решения проблемы взаимного исключения, что является целью алгоритма). Поэтому предполагается, что идентификатор потока i также является приоритетом. Более низкое значение i означает более высокий приоритет, и потоки с более высоким приоритетом войдут в критическую секцию первыми.
Критическая секция — это та часть кода, которая требует эксклюзивного доступа к ресурсам и может быть выполнена только одним потоком за раз. В аналогии с пекарней, когда клиент торгует с пекарем, другие должны ждать.
Когда поток хочет войти в критическую секцию, он должен проверить, настала ли его очередь сделать это. Он должен проверить номер n каждого другого потока, чтобы убедиться, что у него наименьший номер. В случае, если другой поток имеет тот же номер, поток с наименьшим i войдет в критическую секцию первым.
В псевдокоде это сравнение между потоками a и b можно записать в виде:
// Пусть n a - номер клиента для потока a , и// i a - номер потока для потока a , тогда(н а , я а ) < (н б , я б )
что эквивалентно:
(n a < n b ) или ((n a == n b ) и ( ia < i b ))
Как только поток завершает свою критическую работу, он избавляется от своего номера и переходит в некритическую секцию .
Некритическая секция — это часть кода, которая не требует исключительного доступа. Она представляет собой некоторое потокоспецифичное вычисление, которое не мешает ресурсам и выполнению других потоков.
Эта часть аналогична действиям, которые происходят после совершения покупок, например, возвращение сдачи в кошелек.
В оригинальной статье Лэмпорта входящая переменная известна как выбор , и применяются следующие условия:
В этом примере все потоки выполняют одну и ту же "главную" функцию Thread . В реальных приложениях разные потоки часто имеют разные "главные" функции.
Обратите внимание, что, как и в оригинальной статье, поток проверяет себя перед входом в критическую секцию. Поскольку условия цикла будут оценены как ложные , это не вызовет большой задержки.
// объявление и начальные значения глобальных переменных Ввод : массив [ 1. . NUM_THREADS ] из bool = { false }; Число : массив [ 1. . NUM_THREADS ] целого числа = { 0 }; блокировка ( целое число i ) { Ввод [ i ] = true ; Число [ i ] = 1 + макс ( Число [ 1 ], ..., Число [ NUM_THREADS ]); Ввод [ i ] = false ; для ( целое число j = 1 ; j <= NUM_THREADS ; j ++ ) { // Подождите, пока поток j получит свой номер: пока ( Ввод [ j ]) { /* ничего */ } // Подождать, пока все потоки с меньшими номерами или с одинаковыми // число, но с более высоким приоритетом, завершают свою работу: while (( Число [ j ] != 0 ) && (( Число [ j ], j ) < ( Число [ i ], i ))) { /* ничего */ } } } разблокировать ( целое число i ) { Число [ i ] = 0 ; } Поток ( целое число i ) { в то время как ( правда ) { замок ( я ); // Критическая секция располагается здесь... разблокировать ( i ); // некритическая секция... } }Каждый поток записывает только свое собственное хранилище, только чтение является общим. Примечательно, что этот алгоритм не построен поверх какой-либо низкоуровневой «атомарной» операции, например, сравнения и обмена . Исходное доказательство показывает, что для перекрывающихся чтений и записей в одну и ту же ячейку хранилища только запись должна быть корректной. [ необходимо разъяснение ] Операция чтения может возвращать произвольное число. Следовательно, этот алгоритм можно использовать для реализации взаимного исключения в памяти, в которой отсутствуют примитивы синхронизации, например, простой диск SCSI, общий для двух компьютеров.
Необходимость переменной Entering может быть неочевидной, поскольку нет «блокировки» вокруг строк 7–13. Однако предположим, что переменная была удалена и два процесса вычислили одно и то же Number[i]. Если процесс с более высоким приоритетом был вытеснен до установки Number[i], процесс с низким приоритетом увидит, что другой процесс имеет номер ноль, и войдет в критическую секцию; позже процесс с высоким приоритетом проигнорирует equal Number[i]для процессов с более низким приоритетом и также войдет в критическую секцию. В результате два процесса могут войти в критическую секцию одновременно. Алгоритм пекарни использует переменную Entering , чтобы назначение в строке 6 выглядело как атомарное; процесс i никогда не увидит число, равное нулю, для процесса j , который собирается выбрать то же число, что и i .
При реализации псевдокода в системе с одним процессом или в кооперативной многозадачности лучше заменить разделы "ничего не делать" кодом, который уведомляет операционную систему о необходимости немедленного переключения на следующий поток. Этот примитив часто называют yield.
Алгоритм пекарни Лампорта предполагает последовательную модель памяти согласованности. Немногие, если таковые имеются, языки или многоядерные процессоры реализуют такую модель памяти. Поэтому правильная реализация алгоритма обычно требует вставки ограждений для предотвращения переупорядочивания. [1]
Мы объявляем N числом процессов и предполагаем, что N — натуральное число.
КОНСТАНТА NПРЕДПОЛАГАЕМ N \in NatМы определяем P как множество {1, 2, ... , N} процессов.
П == 1..НПеременные num и flag объявлены как глобальные.
--алгоритм AtomicBakery {переменная num = [i \in P |-> 0], флаг = [i \in P |-> FALSE];Следующее определение LL(j, i)истинно тогда и только тогда, когда <<num[j], j>> меньше или равно <<num[i], i>> в обычном лексикографическом порядке .
определить { LL(j, i) == \/ num[j] < num[i] \/ /\ число[i] = число[j] /\ j =< я }Для каждого элемента в P существует процесс с локальными переменными unread, max и nxt. Шаги между последовательными метками p1, ..., p7, cs считаются атомарными. Оператор с устанавливает id для недетерминированного выбранного элемента множества S, а затем выполняет тело. Шаг, содержащий оператор await expr, может быть выполнен только тогда, когда значение expr равно TRUE .(x \in S) { body }
процесс (p \in P) переменные непрочитанные \в SUBSET P, макс \в Нат, nxt \in P;{p1: пока (ИСТИНА) { непрочитано := P \ {self} ; макс := 0; флаг[self] := ИСТИНА;p2: пока (непрочитано # {}) { с (i \in непрочитано) { непрочитано := непрочитано \ {i}; если (число[i] > макс) { макс := число[i]; } } };p3: num[self] := max + 1;p4: флаг[self] := ЛОЖЬ; непрочитано := P \ {self} ;p5: пока (непрочитано # {}) { с (i \in непрочитано) { nxt := i ; }; ждем ~ флаг[nxt];p6: ожидание \/ num[nxt] = 0 \/ LL(self, nxt) ; непрочитано := непрочитано \ {nxt}; } ;cs: пропустить ; \* критический раздел;p7: num[self] := 0; }}}Мы используем класс AtomicIntegerArray не из-за его встроенных атомарных операций, а потому, что его методы get и set работают как изменчивые чтения и записи. В рамках модели памяти Java это гарантирует, что записи немедленно видны всем потокам.
AtomicIntegerArray ticket = new AtomicIntegerArray ( threads ); // тикет для потоков в очереди, n - количество потоков // Java инициализирует каждый элемент 'ticket' значением 0 AtomicIntegerArray входящий = new AtomicIntegerArray ( threads ); // 1, когда поток входит в линию // Java инициализирует каждый элемент 'entering' значением 0 public void lock ( int pid ) // идентификатор потока { ввод . set ( pid , 1 ); целочисленный максимум = 0 ; для ( int i = 0 ; i < потоки ; i ++ ) { int current = билет . получить ( i ); если ( текущий > макс .) { макс = ток ; } } билет . набор ( pid , 1 + max ); ввод . set ( pid , 0 ); для ( int i = 0 ; i < билет . длина (); ++ i ) { если ( я != pid ) { while ( entry . get ( i ) == 1 ) { Thread . yield (); } // ждем, пока другой поток выберет билет пока ( билет.получить ( i ) ! = 0 && ( билет.получить ( i ) < билет.получить ( pid ) || ( билет . получить ( i ) == билет . получить ( pid ) && i < pid ))) { Thread . yield (); } } } // Критическая секция располагается здесь...}публичная разблокировка void ( int pid ) { билет.set ( pid , 0 ) ; }