Изменения
→Определения
'''Критическая секция''' (англ. ''critical section'') — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.
}}
==Проблема==
Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов: как можно управлять доступом нескольких процессов к общему ресурсу, когда каждый процесс нуждается в исключительном контроле над этим ресурсом при выполнении своей работы? Решение — делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. И контролировать доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс.
'''def''' lock():
'''doorway'''
'''waitnigwaiting'''
#Секция <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>2</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>, после чего уже другие потоки смогут войти в критическую область. Посмотрим, как реализуется этот общий принцип Рассмотрим реализацию этого принципа алгоритмом Петерсона для двух потоков.
'''threadlocal int''' id <font color=green>// 0 or 1</font>
===Алгоритм Петерсона для <tex>N</tex> потоков===
Обобщение Алгоритм Петерсона для <tex>N</tex> потоков. Гарантирует взаимное исключение, отсутствие блокировки и отсутствие голодания. Но алгоритм не очень честный. "Невезучий " поток может ждать пока другие потоки <tex>O(N^2)</tex> раз войдут в критическую секцию (квадратичное ожидание).
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
===Алгоритм Лампорта (вариант <tex>1</tex>)===
Алгоритм пекарни Лампорта – алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключенияобладающий взаимным исключением. Опубликован Лесли Лампортом в 1974 году. <ref>[http://lamport.azurewebsites.net/pubs/bakery.pdf? A New Solution of Dijkstra's Concurrent Programming Problem]</ref> Гарантирует взаимноеисключение, отсутствие блокировки и линейное ожидание.=====Аналогия=====Алгоритм реализует идею пекарни с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
want[id] = false
Обладает свойством первый пришел, первый обслужен (<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>. '''Случай 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>2</tex>)===
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
'''shared int''' label[N] '''init''' 0
'''def''' lock:
label[id] = '''max'''(label!='''inf''') + 1
'''while''' '''exists''' k: k != id '''and'''
(choosingwant[k] '''or'''
(label[k], k) < (label[id], id)) :
'''pass'''
==См. также==
* [[Алгоритм_Лампорта_взаимного_исключенияСтек_Трайбера]]
== Источники информации ==
* [https://en.wikipedia.org/wiki/Mutual_exclusion Mutual exclusion]
* [https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm Lamports bakery algorithm]
* [http://lamport.azurewebsites.net/pubs/bakery.pdf Original lamports bakery algorithm]
* [https://en.wikipedia.org/wiki/Peterson%27s_algorithm Petersons algorithm]
[[Категория: Параллельное программирование]]
