Изменения
→Определения
'''Критическая секция''' (англ. ''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>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>),
что эквивалентно:
'''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'''
