302
правки
Изменения
→Алгоритмы взаимного исключения
==Алгоритмы взаимного исключения==
===Алгоритм Петерсонадля <tex>2</tex> потоков===Простейший алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в <tex>1981</tex> г. Хотя изначально был сформулирован для 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] && want[1] && waiting == 0 && waiting == 1</tex>, но такого не может быть одновременно и мы пришли к противоречию.=====Свобода от взаимной блокировки=====Для того, чтобы оба процесса находились в ожидании, необходимы противоположные значения переменной <tex>waiting</tex>, что невозможно.=====Свобода от голодания=====Возможна ситуация, когда один процесс будет несколько раз подряд захватывать себе критическую секцию, а другой, изъявивший желание попасть туда, будет ждать. В алгоритме Петерсона процесс не будет ждать дольше, чем один вход в критическую секцию: после выполнения <tex>unlock()</tex> и повторного захода в <tex>lock()</tex> процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс. ===Алгоритм Петерсона для <tex>N</tex> потоков===
Перед тем как начать исполнение критической секции кода, поток должен вызвать процедуру <tex>lock()</tex> со своим номером в качестве параметра. Она должна организовать ожидание потоком своей очереди входа в критическую секцию. После исполнения критической секции и выхода из неё поток вызывает другую процедуру <tex>unlock()</tex>, после чего уже другие потоки смогут войти в критическую область. Посмотрим, как реализуется этот общий принцип алгоритмом Петерсона.
