Алгоритм пекарни Лампорта — это компьютерный алгоритм , разработанный ученым-компьютерщиком Лесли Лэмпортом в рамках его длительного исследования формальной правильности параллельных систем , который предназначен для повышения безопасности при использовании общих ресурсов среди нескольких потоков посредством взаимного исключения .
В информатике обычно несколько потоков одновременно обращаются к одним и тем же ресурсам. Повреждение данных может произойти, если два или более потока попытаются выполнить запись в одну и ту же ячейку памяти или если один поток прочитает ячейку памяти до того, как другой закончит запись в нее. Алгоритм пекарни Лампорта — один из многих алгоритмов взаимного исключения , предназначенных для предотвращения одновременного входа параллельных потоков в критические участки кода, чтобы исключить риск повреждения данных.
Лэмпорт представил пекарню с нумерационной машиной на входе, чтобы каждому покупателю присваивался уникальный номер. Цифры увеличиваются на единицу по мере того, как покупатели входят в магазин. Глобальный счетчик отображает номер клиента, который обслуживается в данный момент. Все остальные клиенты должны ждать в очереди, пока пекарь не закончит обслуживать текущего клиента и не отобразится следующий номер. Когда покупатель закончил делать покупки и избавился от своего номера, продавец увеличивает номер, позволяя обслуживать следующего покупателя. Этот покупатель должен вытащить еще один номер из нумерационной машины, чтобы снова совершить покупку.
Согласно аналогии, «клиенты» — это потоки, обозначаемые буквой i , полученные из глобальной переменной.
Из-за ограничений компьютерной архитектуры некоторые части аналогии Лэмпорта нуждаются в небольшой модификации. Возможно, что один и тот же номер n будет получен более чем одним потоком, когда они его запросят; этого нельзя избежать. Следовательно, предполагается, что идентификатор потока i также является приоритетным. Меньшее значение i означает более высокий приоритет, и потоки с более высоким приоритетом войдут в критическую секцию первыми.
Критическая секция — это часть кода, которая требует монопольного доступа к ресурсам и может выполняться только одним потоком за раз. В аналогии с пекарней, когда покупатель торгует с пекарем, другие должны ждать.