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

Алгоритм пекарни Лампорта- алгоритм разделения общих ресурсов между несколькимипотокамипутёмвзаимного исключения. Опубликован учёным в области информатикиЛесли Лампортомв 1974 году.
В информатике часто встречается ситуация, когда нескольким потокам нужен доступ к одним и тем же ресурсам. Если два или несколько потоков попытаются писать в одну и ту же ячейку памяти или если один поток попытается прочитать то, что ещё не дописано другим потоком, может произойти повреждение данных. Алгоритм хлебопекарни Лампорта является одним из многих алгоритмов взаимного исключения, направленных на предотвращение одновременного пребывания параллельных потоков вкритических секцияхкода для исключения риска повреждения данных.
Лампорт предлагает рассмотреть пекарню с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того, как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.
Пусть покупатели - это потоки, получившие номераiот глобальной переменной.
Из-за ограничений компьютерной архитектуры момент выдачи номерков должен быть немного модифицирован, так как возникает ситуация неоднозначности в случае, если сразу два или несколько покупателей (потоков) захотели получить номерок с номеромn. При наличии нескольких потоков, получивших номерnпри входе в критическую секцию, поток с меньшим номеромiбудет иметь больший приоритет при обслуживании (входе в критическую секцию).
Критическая секция — это часть кода, которая требует исключительного доступа к ресурсам, и одновременно может выполняться только одним потоком.
Когда поток хочет войти в критическую секцию, он должен проверить, может ли он это сейчас сделать. Поток должен проверить номераn, полученные другими потоками, и убедиться, что у него меньший номер. В случае совпаденияnу двух или нескольких потоков, в критическую секцию входит поток с наименьшимi.
На псевдокоде это сравнение для потоковaиbможет быть записано как:
что эквивалентно:
Когда поток заканчивает работу в критической секции, он освобождает номерnи входит в некритическую секцию.
Некритическая секция — это часть кода, не имеющая ресурсов, требующих исключительного доступа. Это код, который могут выполнять несколько потоков параллельно, не мешая друг другу.
Если вернуться к аналогии, то это часть действий, которые происходят после совершения покупки. Например, возврат сдачи в бумажник.
В оригинальной статье Лампорта к процессу и нумерующей (entering, choosing) переменной применяются следующие условия:
В примере ниже все потоки выполняют одну и ту же «главную» функциюThread. В реальных приложениях разные потоки часто имеют разные «главные» функции.
Как и в оригинальной статье, здесь потоки проверяют себя перед входом в критическую секцию. Так как условие цикла вернетfalse, проверка не даёт существенную задержку выполнения.
Каждый поток пишет в свою собственную память, только операция чтения может выполняться в общей памяти. Интересно, что алгоритм не использует атомарных операций, таких каксравнение с обменом. Оригинальное доказательство показывает, что для перекрывающихся операций чтения и записи в одну и ту же ячейку только запись должна быть корректной. Операция чтения может вернуть произвольное значение. Поэтому этот алгоритм может быть использован для реализации мьютексов для памяти, которая не имеет синхронизирующих примитивов. Например, для простогоSCSI-диска, используемого двумя компьютерами одновременно.
Необходимость массиваEntering, возможно, не очевидна, так как в строках 7 — 13 псевдокода нет блокировок. Однако, допустим, что мы убрали этот массив, и два потока вычислили одно и то же значениеNumber[i]. Тогда, если поток с более высоким приоритетом был вытеснен перед вычислениемNumber[i], поток с меньшим приоритетом увидит, что первый процесс имеетNumber[i]= 0 и войдёт в критическую секцию. Затем первый, более приоритетный, процесс проигнорирует совпадение номеровNumber[i]и также войдёт в критическую секцию. В итоге два процесса будут одновременно выполнять критическую секцию.Enteringнужен для выполнения операции в строке 6 как атомарной. Процессiникогда не увидитNumber[j]= 0, у процессаj, который собирается взять то же число, что иi.
При реализации псевдокода в однозадачной илимногозадачнойсистеме лучше заменить слова «ничего не делать» уведомлением системе немедленно переключиться на следующий поток. Этот примитив часто называетсяyield.
Алгоритм пекарни Лампорта предполагает использование модели памяти споследовательной согласованностью. Немногие, если таковые имеются, языки или многоядерные процессоры реализуют такую модель памяти. Поэтому правильная реализация алгоритма обычно требует вставки ограждений, чтобы препятствовать переупорядочиванию.