Изменения

Перейти к: навигация, поиск

Алгоритмы взаимного исключения

374 байта убрано, 20:35, 30 сентября 2018
Алгоритм Лампорта (вариант 1)
Алгоритм пекарни Лампорта алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован Лесли Лампортом в 1974 году.
=====Аналогия=====
Лампорт предлагает рассмотреть пекарню Алгоритм реализует идею пекарни с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.
Пусть покупатели это потоки, получившие номера <tex>i</tex> от глобальной переменной. При наличии нескольких потоков, получивших номер <tex>n</tex> при входе в критическую секцию, поток с меньшим номером <tex>i</tex> будет иметь больший приоритет при обслуживании (входе в критическую секцию).
=====Критическая секция=====
Когда поток хочет войти в критическую секцию, он должен проверить номера <tex>n</tex>, полученные другими потоками, и убедиться, что у него меньший номер. В случае совпадения <tex>n</tex> у двух или нескольких потоков, в критическую секцию входит поток с наименьшим номером потока<tex>i</tex>.
272
правки

Навигация