302
правки
Изменения
→Алгоритм Лампорта (вариант 1)
===Алгоритм Лампорта (вариант <tex>1</tex>)===
Алгоритм пекарни Лампорта алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован Лесли Лампортом в 1974 году. Гарантирует взаимноеисключение, отсутствие блокировки и отсутствие голодания.
=====Аналогия=====
Алгоритм реализует идею пекарни с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.
want[id] = false
Обладает свойством первый пришел, первый обслужен (<tex>FCFS</tex>), за счет того, что поток <tex>P</tex> выполнивший <tex>doorway (DW)</tex> до потока <tex>Q</tex>, имеет более ранний номер в очереди. Но метки должны быть бесконечными (их можно заменить на конечные метки).
=====Взаимное исключение=====
'''Случай 2:''' <tex>(label[k], k) >= (label[id], id)</tex>
*Но значит другой поток зашел по <tex>want[id] == false</tex> выполнив свой <tex>doorway</tex> до потока <tex>id</tex> - противоречие.
===Алгоритм Лампорта (вариант <tex>2</tex>)===
