Изменения
→Определения
'''Критическая секция''' (англ. ''critical section'') — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.
}}
==Проблема==
Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов: как можно управлять доступом нескольких процессов к общему ресурсу, когда каждый процесс нуждается в исключительном контроле над этим ресурсом при выполнении своей работы? Решение — делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. И контролировать доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс.
Успешное решение этой проблемы должно иметь по крайней мере три свойства:
;Exit :Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.
Если процесс хочет войти в критический раздел, он должен сначала выполнить раздел <tex>try </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>
'''shared int''' want[2]
'''shared int''' victim
'''def''' lock:
want[id] = true
victim = id
'''while''' want[1-id] '''and'''
victim == id:
'''pass'''
'''def''' unlock:
want[id] = false
===Корректность алгоритма===
=====Взаимное исключение=====
Потоки <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>
'''shared int''' level[N]
'''shared int''' victim[N]
'''def''' lock:
'''for''' j = 1..N-1: <font color=green>//Для входа в CS надо пройти на N-1 уровней</font>
level[id] = j <font color=green>//Обобщаем want на уровень j: level[id] >= j</font>
victim[j] = id <font color=green>//Своя жертва на каждом уровне</font>
'''while''' '''exist''' k: k != id '''and''' <font color=green>//Для прохода на следующий уровень соревнуемся со всеми другими потоками</font>
level[k] >= j '''and'''
victim[j] == id:
'''pass'''
'''def''' unlock:
level[id] = 0
===Алгоритм Лампорта (вариант <tex>1</tex>)===
Алгоритм Лампорта – алгоритм разделения общих ресурсов между несколькими потоками обладающий взаимным исключением. Опубликован Лесли Лампортом в 1974 году. <ref>[http://lamport.azurewebsites.net/pubs/bakery.pdf? A New Solution of Dijkstra's Concurrent Programming Problem]</ref> Гарантирует взаимное
исключение, отсутствие блокировки и линейное ожидание.
=====Аналогия=====
Алгоритм реализует идею пекарни с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.
Пусть покупатели это потоки, получившие номера <tex>i</tex>.
=====Критическая секция=====
Когда поток хочет войти в критическую секцию, он должен проверить номера <tex>n</tex>, полученные другими потоками, и убедиться, что у него меньший номер. В случае совпадения <tex>n</tex> у двух или нескольких потоков, в критическую секцию входит поток с наименьшим номером потока <tex>i</tex>.
(n<sub>a</sub>, i<sub>a</sub>) < (n<sub>b</sub>, i<sub>b</sub>),
что эквивалентно:
(n<sub>a</sub> < n<sub>b</sub>) or ((n<sub>a</sub> == n<sub>b</sub>) and (i<sub>a</sub> < i<sub>b</sub>))
Когда поток заканчивает работу в критической секции, он освобождает номер ''n'' и выходит из критической секции.
=====Псевдокод=====
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
'''shared boolean''' want[N] '''init''' false
'''shared int''' label[N] '''init''' 0
'''def''' lock:
want[id] = true
label[id] = '''max'''(label) + 1
'''while''' '''exists''' k: k != id '''and'''
want[k] '''and'''
(label[k], k) < (label[id], id) :
'''pass'''
'''def''' unlock:
want[id] = false
Обладает свойством первый пришел, первый обслужен (<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>2</tex>)===
Еще одна реализация алгоритма Лампорта. Метки тоже могут быть бесконечными, несмотря на то, что мы их и сбрасываем при выходе из критической секции.
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
'''shared boolean''' want[N] '''init''' false
'''shared int''' label[N] '''init''' 0
'''def''' lock:
want[id] = true
label[id] = '''max'''(label!='''inf''') + 1
want[id] = false
'''while''' '''exists''' k: k != id '''and'''
(want[k] '''or'''
(label[k], k) < (label[id], id)) :
'''pass'''
'''def''' unlock:
label[id] = '''inf'''
==См. также==
* [[Алгоритм_Лампорта_взаимного_исключенияСтек_Трайбера]]
== Источники информации ==
* [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]
[[Категория: Параллельное программирование]]
