302
правки
Изменения
→Алгоритмы взаимного исключения
===Алгоритм Лампорта (вариант <tex>1</tex>)===
Алгоритм пекарни Лампорта алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован Лесли Лампортом в 1974 году.
Лампорт предлагает рассмотреть пекарню с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.
Пусть покупатели это потоки, получившие номера <tex>i</tex> от глобальной переменной. При наличии нескольких потоков, получивших номер <tex>n</tex> при входе в критическую секцию, поток с меньшим номером <tex>i</tex> будет иметь больший приоритет при обслуживании (входе в критическую секцию).
Ключевое свойство: если поток <tex>P</tex> выполнил <tex>doorway (DW)</tex> до потока <tex>Q</tex>, то у него более ранний номер очереди.
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
'''def''' unlock:
want[id] = false
Обладает свойством первый пришел, первый обслужен (FCFS). Это сильнее чем линейное ожидание, cамое сильное свойство прогресса.
===First Come First Served (FCFS)===
Требование <tex>First Come First Served</tex> формализуется так:
#Метод <tex>lock</tex> должен состоять из двух последовательных секций.
'''def''' lock():
'''doorway'''
'''waitnig'''
#Секция <tex>doorway</tex> должны быть <tex>wait free</tex>, то есть выполняться за конечное число шагов, независимо от других потоков.
#Секция <tex>waiting</tex> должна выполнять условие: Если <tex>DW_i \rightarraow DW_j</tex>, то <tex>res(WT_i) \rightarraow res(WT_j)</tex>.
===Алгоритм Лампорта (вариант <tex>2</tex>)===
Обладает всеми свойствами классического варианта, но дополнительно позволяет решить проблему с бесконечными метками.
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
