Изменения
→Определения
'''Критическая секция''' (англ. ''critical section'') — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.
}}
==Проблема==
Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов: как можно управлять доступом нескольких процессов к общему ресурсу, когда каждый процесс нуждается в исключительном контроле над этим ресурсом при выполнении своей работы? Решение — делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. И контролировать доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс.
Успешное решение этой проблемы должно иметь по крайней мере три свойства:
===Алгоритм Петерсона для <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>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>waiting</tex>, что невозможно.
=====Свобода от Отсутствие голодания=====
Возможна ситуация, когда один процесс будет несколько раз подряд захватывать себе критическую секцию, а другой, изъявивший желание попасть туда, будет ждать. В алгоритме Петерсона процесс не будет ждать дольше, чем один вход в критическую секцию: после выполнения <tex>unlock()</tex> и повторного захода в <tex>lock()</tex> процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс.
===Алгоритм Петерсона для <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амое сильное свойство прогрессаНо метки должны быть бесконечными (их можно заменить на конечные метки).
===First Come First Served (FCFS)==Взаимное исключение=====Требование Допустим, что два потока одновременно в <tex>CS</tex>. Значит поток <tex>id</tex> зашел в <tex>CS</tex> последним, в то время как другой поток <tex>First Come First Servedk != id</tex> формализуется так:#Метод уже был в <tex>lockCS</tex> должен состоять из двух последовательных секций. '''def''' lockНо зайти в <tex>CS</tex> можно если <tex>want[k] == false</tex> или <tex>(label[k], k) > (label[id], id):</tex>. '''doorwayСлучай 1:'''<tex>want[k] == false</tex> *Противоречие. '''waitnigСлучай 2:'''#Секция <tex>doorway</tex(label[k], k) > должны быть <tex>wait free= (label[id], id)</tex>, то есть выполняться за конечное число шагов, независимо от других потоков.#Секция *Но значит другой поток зашел по <tex>waitingwant[id] == false</tex> должна выполнять условие: Если выполнив свой <tex>DW_i \Rightarrow DW_jdoorway</tex>, то до потока <tex>res(WT_i) \Rightarrow res(WT_j)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]
[[Категория: Параллельное программирование]]