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