Алгоритм Петерсона - Википедия - Petersons algorithm

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

Алгоритм

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

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

bool флаг[2] = {ложный, ложный};int повернуть;

P0:      флаг[0] = истинный;P0_gate: повернуть = 1;         пока (флаг[1] == истинный && повернуть == 1)         {             // занято ждать         }         // критическая секция         ...         // конец критического раздела         флаг[0] = ложный;

P1:      флаг[1] = истинный;P1_gate: повернуть = 0;         пока (флаг[0] == истинный && повернуть == 0)         {             // занято ждать         }         // критическая секция         ...         // конец критического раздела         флаг[1] = ложный;

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

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

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

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

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

Прогресс

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

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

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

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

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

level: массив из N целых чисел, last_to_enter: массив из N − 1 целых чисел

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

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

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

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

Можно также показать, что алгоритм не требует "голодания", что означает, что все процессы, входящие в цикл, в конечном итоге выходят из него (при условии, что они не остаются в критической секции бесконечно). Доказательство проводится индукцией по $N -1$ вниз. Процесс на $N -1$ находится в критическом разделе и по предположению выйдет из него. На всех нижних уровнях $ℓ$ , это невозможно для процесса $я$ ждать вечно, так как либо другой процесс $j$ войдет в зал ожидания, установка last_to_enter [ℓ] ← j и "освобождение" $я$ ; или этого никогда не происходит, но тогда все процессы $j$ которые также находятся в залах ожидания, должны быть на более высоких уровнях, и по индуктивной гипотезе они в конечном итоге завершат цикл и сбросят свои уровни, так что для всех $k \neq я$ , уровень [k] <ℓ и $я$ снова выходит из цикла.^[4]^:24–25

Свобода от голода на самом деле высшая живость гарантия того, что алгоритм дает; в отличие от двухпроцессного алгоритма Петерсона, алгоритм фильтрации не гарантирует ограниченного ожидания.^[4]^:25–26

Примечание

При работе на аппаратное обеспечение уровня, алгоритм Петерсона обычно не требуется для достижения атомарного доступа. У некоторых процессоров есть специальные инструкции, например испытать и установить или же сравнивать и менять местами, что, блокируя шину памяти, можно использовать для обеспечения взаимного исключения в SMP системы.

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

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

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

Сноски

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

внешняя ссылка

http://lxr.free-electrons.com/source/arch/arm/mach-tegra/sleep-tegra20.S Реализация алгоритма Петерсона

[original-1] а ^б Г. Л. Петерсон: «Мифы о проблеме взаимного исключения», Письма об обработке информации 12(3) 1981, 115–116

[2] Как обсуждалось в Обзор операционных систем, Январь 1990 г. («Доказательство алгоритма взаимного исключения», М. Хофри).

[Silberschatz.p194-3] а ^б ^c Зильбершац. Понятия операционных систем: седьмое издание. Джон Вили и сыновья, 2005 г., стр. 194

[raynal-4] а ^б ^c ^d ^е ^ж Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы. Springer Science & Business Media. ISBN 3642320279.

[Schneider.p185-5] Ф. Б. Шнайдер. О параллельном программировании, Sringer Verlag, 1997, страницы 185–196.

[art-6] а ^б Херлихи, Морис; Шавит, Нир (2012). Искусство многопроцессорного программирования. Эльзевир. п. 28–31. ISBN 9780123977953.

[1]

[2]

[3]

[4]

[5]

[6]