302
правки
Изменения
→Алгоритмы взаимного исключения
===Алгоритм Лампорта (вариант <tex>1</tex>)===
Алгоритм пекарни Лампорта алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован Лесли Лампортом в 1974 году.
=====Аналогия=====
Лампорт предлагает рассмотреть пекарню с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.
Пусть покупатели это потоки, получившие номера <tex>i</tex> от глобальной переменной. При наличии нескольких потоков, получивших номер <tex>n</tex> при входе в критическую секцию, поток с меньшим номером <tex>i</tex> будет иметь больший приоритет при обслуживании (входе в критическую секцию).
=====Критическая секция=====
Когда поток хочет войти в критическую секцию, он должен проверить номера <tex>n</tex>, полученные другими потоками, и убедиться, что у него меньший номер. В случае совпадения <tex>n</tex> у двух или нескольких потоков, в критическую секцию входит поток с наименьшим номером потока<tex>i<tex>.
(n<sub>a</sub>, i<sub>a</sub>) < (n<sub>b</sub>, i<sub>b</sub>),
что эквивалентно:
(n<sub>a</sub> < n<sub>b</sub>) or ((n<sub>a</sub> == n<sub>b</sub>) and (i<sub>a</sub> < i<sub>b</sub>))
Когда поток заканчивает работу в критической секции, он освобождает номер ''n'' и выходит из критической секции.
Ключевое свойство: если поток <tex>P</tex> выполнил <tex>doorway (DW)</tex> до потока <tex>Q</tex>, то у него более ранний номер очереди.
