Алгоритм Петерсона

Алгоритм Петерсона (или решение Петерсона ) — это алгоритм параллельного программирования для взаимного исключения , который позволяет двум или более процессам совместно использовать одноразовый ресурс без конфликтов, используя для связи только общую память . Он был сформулирован Гэри Л. Петерсоном в 1981 году. ^[1] Хотя первоначальная формулировка Петерсона работала только с двумя процессами, алгоритм можно обобщить для более чем двух процессов. ^[2]

Алгоритм

Алгоритм использует две переменные: flagи turn. Значение flag[n]указывает true, что процесс nхочет войти в критическую секцию . Вход в критическую секцию предоставляется процессу P0, если P1 не хочет входить в свою критическую секцию или если P1 отдал приоритет P0, установив turnзначение 0.

Алгоритм удовлетворяет трем основным критериям решения проблемы критического сечения. Условие while работает даже с вытеснением. ^[1]

Тремя критериями являются взаимное исключение, прогресс и ограниченное ожидание. ^[3]

Поскольку turnможет принимать одно из двух значений, его можно заменить одним битом, а это означает, что алгоритму требуется всего три бита памяти. ^[4]^{: 22}

Взаимное исключение

P0 и P1 никогда не могут находиться в критической секции одновременно. Если P0 находится в критической секции, то flag[0]это правда. Кроме того, либо flag[1]есть false(это означает, что P1 покинул свою критическую секцию), либо turnесть 0(это означает, что P1 только сейчас пытается войти в критическую секцию, но любезно ждет), либо P1 находится на метке P1_gate(пытается войти в свою критическую секцию, после установки flag[1], trueно до установки turnи 0ожидания). Итак, если оба процесса находятся в своих критических участках, то мы заключаем, что состояние должно удовлетворять flag[0]и flag[1]и turn = 0и turn = 1. Ни одно состояние не может удовлетворять обоим turn = 0и turn = 1, поэтому не может быть состояния, в котором оба процесса находятся в своих критических секциях. (Это изложение аргумента, который был строго сформулирован в Schneider 1997. ^[5] ).

Прогресс

Прогресс определяется следующим образом: если ни один процесс не выполняется в своей критической секции и некоторые процессы желают войти в свои критические секции, то только те процессы, которые не выполняются в своих оставшихся секциях, могут участвовать в принятии решения о том, какой процесс войдет. его критический раздел следующий. Обратите внимание, что для процесса или потока оставшиеся разделы являются частями кода, не связанными с критическим разделом. Этот выбор нельзя откладывать на неопределенный срок. ^[3] Процесс не может немедленно повторно войти в критическую секцию, если другой процесс установил свой флаг, сообщающий, что он хотел бы войти в критическую секцию.

Ограниченное ожидание

Ограниченное ожидание, или ограниченный обход , означает, что количество раз, когда процесс будет обойден другим процессом после того, как он заявил о своем желании войти в критическую секцию, ограничено функцией количества процессов в системе. ^[3]^[4]^{: 11} В алгоритме Петерсона процесс никогда не будет ждать входа в критическую секцию дольше одного оборота.

Алгоритм фильтра: алгоритм Петерсона для более чем двух процессов.

Алгоритм фильтра обобщает алгоритм Петерсона на $N > 2$ процессов. ^[6] Вместо логического флага для каждого процесса требуется целочисленная переменная, хранящаяся в атомарном регистре с одной записью и несколькими устройствами чтения (SWMR) , и $N - 1$ дополнительных переменных в аналогичных регистрах. Регистры могут быть представлены в псевдокоде как массивы :

уровень: массив из N целых чиселLast_to_enter: массив из N − 1 целых чисел

Переменные уровня принимают значения до $N$ $- 1 , каждая из$ которых представляет отдельную «комнату ожидания» перед критической секцией. ^[6] Процессы продвигаются из одной комнаты в другую, заканчиваясь в комнате $N$ $- 1$ , которая является критической секцией. В частности, чтобы получить блокировку, выполняется процесс $i$ ^[4]^{: 22.}

i ← ProcessNo для ℓ от 0 до N - 1 исключая уровень[i] ← ℓ Last_to_enter[ℓ] ← я while last_to_enter[ℓ] = i и существует k ≠ i, такой что level[k] ≥ ℓ подождите

Чтобы снять блокировку при выходе из критической секции, процесс $i$ устанавливает level[i] в −1.

То, что этот алгоритм обеспечивает взаимное исключение, можно доказать следующим образом. Процесс $i$ выходит из внутреннего цикла, когда нет процесса с более высоким уровнем, чем level[i] , поэтому следующая комната ожидания свободна; или, когда i ≠ Last_to_enter[ℓ] , другой процесс присоединился к его комнате ожидания. Тогда на нулевом уровне, даже если все $N$ процессов войдут в нулевую комнату ожидания одновременно, не более $N$ $- 1$ перейдут в следующую комнату, причем последний из них окажется последним, вошедшим в комнату. Аналогично, на следующем уровне будет продолжаться $N$ $- 2$ и т. д. , пока на конечном уровне только одному процессу не будет разрешено покинуть зал ожидания и войти в критическую секцию, что дает взаимное исключение. ^[4]^{: 22–24}

В отличие от алгоритма Петерсона с двумя процессами, алгоритм фильтра не гарантирует ограниченного ожидания. ^[4]^{: 25–26}

Примечание

При работе на аппаратном уровне алгоритм Петерсона обычно не требуется для достижения атомарного доступа. Некоторые процессоры имеют специальные инструкции, такие как test-and-set или Compare-and-swap , которые, блокируя шину памяти, можно использовать для обеспечения взаимного исключения в SMP- системах.

Большинство современных процессоров переупорядочивают доступ к памяти для повышения эффективности выполнения ( типы разрешенного переупорядочения см. в разделе « Упорядочение памяти» ). Такие процессоры всегда предоставляют какой-то способ принудительно упорядочить поток обращений к памяти, обычно с помощью инструкции барьера памяти . Реализация алгоритмов Петерсона и связанных с ним алгоритмов на процессорах, которые изменяют порядок доступа к памяти, обычно требует использования таких операций для правильной работы, чтобы предотвратить выполнение последовательных операций в неправильном порядке. Обратите внимание, что изменение порядка доступа к памяти может происходить даже на процессорах, которые не меняют порядок инструкций (например, процессор PowerPC в Xbox 360 ). ^{[ нужна цитата ]}

Большинство таких процессоров также имеют своего рода гарантированную атомарную работу , например, XCHGна процессорах x86 и условную загрузку/сохранение на Alpha , MIPS , PowerPC и других архитектурах. Эти инструкции предназначены для более эффективного создания примитивов синхронизации, чем это можно сделать с помощью подходов с использованием только общей памяти.

Смотрите также

Сноски

^ ab GL Peterson: «Мифы о проблеме взаимного исключения», Information Processing Letters 12 (3) 1981, 115–116.
^ Как обсуждалось в «Обзоре операционных систем» , январь 1990 г. («Доказательство алгоритма взаимного исключения», М. Хофри).
^ abc Зильбершац. Концепции операционных систем: седьмое издание. Джон Уайли и сыновья, 2005, стр. 194.
^ abcde Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы . Springer Science & Business Media. ISBN 978-3642320279.
^ Ф. Б. Шнайдер, О параллельном программировании , Springer Verlag, 1997, страницы 185–196.
^ аб Херлихи, Морис ; Шавит, Нир (2012). Искусство многопроцессорного программирования . Эльзевир. стр. 28–31. ISBN 9780123977953.

Внешние ссылки

https://elixir.bootlin.com/linux/v5.6.19/source/arch/arm/mach-tegra/sleep-tegra20.S#L120 Пример алгоритма Петерсона, ранее использовавшегося в ядре Linux (удален в версии 5.7). ).