Изменения

;условие Условие корректности:#'''Взаимное исключение''' (англ. ''mutual exclusion''): только один поток может быть в критической секции.;условия Условия прогресса:#'''Отсутствие взаимоблокировок ''' (англ. ''deadlocks''): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время.#'''Отсутствие голодания ''' (англ. ''starvation-freedom''): если какой-то поток пытается войти в критическую секцию, то он войдет в критическую секцию за конечное время. Может быть последовательно усиленно, превращаясь в условие честности (англ. ''fairness'').#*Квадратичное ожидание (англ. ''quadratic wait'') — <tex>O(n^2)</tex> операций.#*Линейное ожидание (англ. ''linear wait'') — <tex>O(n)</tex> операций.#*Первый пришел, первый обслужен (англ. ''first come first served'')  Требование <tex>First Come First Served (FCFS)</tex> формализуется так:#Метод <tex>lock</tex> должен состоять из двух последовательных секций. '''def''' lock(): '''doorway''' '''waiting'''#Секция <tex>doorway</tex> должны быть <tex>wait free</tex>, то есть выполняться за конечное число шагов, независимо от других потоков.#Секция <tex>waiting</tex> должна выполнять условие: Если <tex>DW_i \Rightarrow DW_j</tex>, то <tex>res(WT_i) \Rightarrow res(WT_j)</tex>.

Простейший алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в <tex>1981</tex> г. <ref name="original">G. L. Peterson: "Myths About the Mutual Exclusion Problem", ''Information Processing Letters'' 12(3) 1981, 115–116</ref> While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.</ref> Хотя изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Гарантирует взаимное исключение, отсутствие взаимной блокировки и отсутствие голодания.

Принцип работы: перед тем как начать исполнение критической секции кода, поток должен вызвать процедуру <tex>lock()</tex> со своим номером в качестве параметра. Она должна организовать ожидание потоком своей очереди входа в критическую секцию. После исполнения критической секции и выхода из неё поток вызывает другую процедуру <tex>unlock()</tex>, после чего уже другие потоки смогут войти в критическую область. Посмотрим, как реализуется этот общий принцип Рассмотрим реализацию этого принципа алгоритмом Петерсона для двух потоков.

Потоки <tex>0</tex> и <tex>1</tex> никогда не могут попасть в критическую секцию в один момент времени: если <tex>0</tex> вошёл в секцию, он установил <tex>want[0]</tex> в <tex>true</tex>. Тогда либо <tex>want[1] = false</tex> (тогда поток <tex>1</tex> не в критической секции), либо <tex>waiting = 1</tex> (тогда поток <tex>1</tex> пытается войти в критическую секцию и крутится в цикле), либо поток <tex>1</tex> пытается войти в критическую секцию после установки <tex>want[1] = true</tex>, но до установки <tex>waiting</tex> и цикла. Таким образом, если оба процесса находятся в критической секции, должно быть <tex> want[0] \space and \space want[1] \space and \space waiting = 0 \space and \space waiting = 1 </tex>, но такого не может быть одновременно и мы пришли к противоречию. =====Свобода от Отсутствие взаимной блокировки=====

=====Свобода от Отсутствие голодания=====

Обобщение Алгоритм Петерсона для <tex>N</tex> потоков. Гарантирует взаимное исключение, отсутствие блокировки и отсутствие голодания. Но алгоритм не очень честный. "Невезучий " поток может ждать пока другие потоки <tex>O(N^2)</tex> раз войдут в критическую секцию (квадратичное ожидание).

Алгоритм пекарни Лампорта – алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключенияобладающий взаимным исключением. Опубликован Лесли Лампортом в 1974 году. <ref>[http://lamport.azurewebsites.net/pubs/bakery.pdf? A New Solution of Dijkstra's Concurrent Programming Problem]</ref> Гарантирует взаимноеисключение, отсутствие блокировки и линейное ожидание.=====Аналогия=====Алгоритм реализует идею пекарни с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.

Лампорт предлагает рассмотреть пекарню с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные Пусть покупатели ждутэто потоки, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа получившие номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь<tex>i</tex>.

Пусть покупатели это потоки=====Критическая секция=====Когда поток хочет войти в критическую секцию, получившие он должен проверить номера <tex>in</tex> от глобальной переменной. При наличии нескольких потоков, получивших полученные другими потоками, и убедиться, что у него меньший номер . В случае совпадения <tex>n</tex> при входе у двух или нескольких потоков, в критическую секцию, входит поток с меньшим наименьшим номером потока <tex>i</tex> будет иметь больший приоритет при обслуживании . (входе n_a, i_a) < (n_b, i_b),что эквивалентно: (n_a < n_b) or ((n_a == n_b) and (i_a < i_b))Когда поток заканчивает работу в критическую секцию)критической секции, он освобождает номер ''n'' и выходит из критической секции.

Обладает свойством первый пришел, первый обслужен (<tex>FCFS</tex>), за счет того, что поток <tex>P</tex> выполнивший <tex>doorway (DW)</tex> до потока <tex>Q</tex>, имеет более ранний номер в очереди. Это сильнее чем линейное ожиданиеНо метки должны быть бесконечными (их можно заменить на конечные метки). =====Взаимное исключение=====Допустим, cамое сильное свойство прогрессачто два потока одновременно в <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>.

===First Come First Served (FCFS)===Требование '''Случай 1:''' <tex>First Come First Servedwant[k] == false</tex> формализуется так:#Метод <tex>lock</tex> должен состоять из двух последовательных секций*Противоречие. '''def''' lock()Случай 2: '''doorway''' '''waitnig'''#Секция <tex>doorway</tex(label[k], k) > должны быть <tex>wait free= (label[id], id)</tex>, то есть выполняться за конечное число шагов, независимо от других потоков.#Секция *Но значит другой поток зашел по <tex>waitingwant[id] == false</tex> должна выполнять условие: Если выполнив свой <tex>DW_i \rightarraow DW_jdoorway</tex>, то до потока <tex>res(WT_i) \rightarraow res(WT_j)id</tex>- противоречие.

Обладает всеми свойствами классического вариантаЕще одна реализация алгоритма Лампорта. Метки тоже могут быть бесконечными, но дополнительно позволяет решить проблему с бесконечными меткаминесмотря на то, что мы их и сбрасываем при выходе из критической секции.

choosingwant[id] = true

choosingwant[id] = false

(choosingwant[k] '''or'''

* [[Алгоритм_Лампорта_взаимного_исключенияСтек_Трайбера]]