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

Флаги готовности

Строгое чередование

Попробуем решить задачу сначала для двух процессов. Очередной подход будет также использовать общую для них обоих переменную с начальным значением 0. Только теперь она будет играть не роль замка для критического участка, а явно указывать, кто может следующим войти в него. Для i-го процесса это выглядит так:

shared int turn = 0; while (some condition) { while(turn!= i); critical section turn = 1-i; remainder section }

Очевидно, что взаимоисключение гарантируется, процессы входят в критическую секцию строго по очереди: P₀, P₁, P₀, P₁, P₀,... Но наш алгоритм не удовлетворяет условию прогресса. Например, если значение turn равно 1, и процесс P₀ готов войти в критический участок, он не может сделать этого, даже если процесс P₁ находится в remainder section.

Недостаток предыдущего алгоритма заключается в том, что процессы ничего не знают о состоянии друг друга в текущий момент времени. Давайте попробуем исправить эту ситуацию. Пусть два наших процесса имеют разделяемый массив флагов готовности входа процессов в критический участок

shared int ready[2] = {0, 0};

Когда i-й процесс готов войти в критическую секцию, он присваивает элементу массива ready[i] значение равное 1. После выхода из критической секции он, естественно, сбрасывает это значение в 0. Процесс не входит в критическую секцию, если другой процесс уже готов к входу в критическую секцию или находится в ней.

while (some condition) { ready[i] = 1; while(ready[1-i]); critical section ready[i] = 0; remainder section }

Полученный алгоритм обеспечивает взаимоисключение, позволяет процессу, готовому к входу в критический участок, войти в него сразу после завершения эпилога в другом процессе, но все равно нарушает условие прогресса. Пусть процессы практически одновременно подошли к выполнению пролога. После выполнения присваиванияready[0]=1 планировщик передал процессор от процесса 0 процессу 1, который также выполнил присваивание ready[1]=1. После этого оба процесса бесконечно долго ждут друг друга на входе в критическую секцию. Возникает ситуация, которую принято называть тупиковой (deadlock)

Первое решение проблемы, удовлетворяющее всем требованиям и использующее идеи ранее рассмотренных алгоритмов, было предложено датским математиком Деккером (Dekker). В 1981 году Петерсон (Peterson) предложил более изящное решение. Пусть оба процесса имеют доступ к массиву флагов готовности и к переменной очередности.

shared int ready[2] = {0, 0}; shared int turn; while (some condition) { ready[i] = 1; turn =1-i; while(ready[1-i] && turn == 1-i); critical section ready[i] = 0; remainder section }

При исполнении пролога критической секции процесс P_i заявляет о своей готовности выполнить критический участок и одновременно предлагает другому процессу приступить к его выполнению. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда следует после другого. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.

Давайте докажем, что все пять наших требований к алгоритму действительно удовлетворяются.

Удовлетворение требований 1 и 2 очевидно.

Докажем выполнение условия взаимоисключения методом от противного. Пусть оба процесса одновременно оказались внутри своих критических секций. Заметим, что процесс P_i может войти в критическую секцию, только если ready[1-i] == 0 или turn == i. Заметим также, что если оба процесса выполняют свои критические секцииодновременно, то значения флагов готовности для обоих процессов совпадают и равны 1. Могли ли оба процесса войти в критические секции из состояния, когда они оба одновременно находились в процессе выполнения цикла while? Нет, так как в этом случае переменная turn должна была бы одновременно иметь значения 0 и 1 (когда оба процесса выполняют цикл, значения переменных измениться не могут). Пусть процесс P₀ первым вошел в критический участок, тогда процесс P₁ должен был выполнить перед вхождением в цикл while по крайней мере один предваряющий оператор (turn = 0;). Однако после этого он не может выйти из цикла до окончания критического участкапроцесса P₀, так как при входе в цикл ready[0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс P₀ не покинет свой критический участок. Мы пришли к противоречию. Следовательно, имеет место взаимоисключение.

Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс P₀. Заметим, что он не может войти в свою критическую секцию только при совместном выполнении условий ready[1] == 1 и turn == 1. Если процесс P₁ не готов к выполнению критического участка, то ready[1] == 0, и процесс P₀ может осуществить вход. Если процесс P₁ готов к выполнению критического участка, то ready[1] == 1 и переменная turn имеет значение 0 либо 1, позволяя процессу P₀ либо процессу P₁ начать выполнение критической секции. Если процесс P₁ завершил выполнение критического участка, то он сбросит свой флаг готовности ready[1] == 0, разрешая процессу P₀ приступить к выполнению критической работы. Таким образом, условие прогресса выполняется.

Отсюда же вытекает выполнение условия ограниченного ожидания. Так как в процессе ожидания разрешения на вход процесс P₀ не изменяет значения переменных, он сможет начать исполнение своего критического участка после не более чем одного прохода по критической секции процесса P₁.

Алгоритм булочной (Bakery algorithm)

Алгоритм Петерсона дает нам решение задачи корректной организации взаимодействия двух процессов. Давайте рассмотрим теперь соответствующий алгоритм для n взаимодействующих процессов, который получил название алгоритм булочной, хотя применительно к нашим условиям его следовало бы скорее назвать алгоритм регистратуры в поликлинике. Основная его идея выглядит так. Каждый вновь прибывающий клиент (он же процесс) получает талончик на обслуживание с номером. Клиент с наименьшим номером на талончике обслуживается следующим. К сожалению, из-за неатомарности операции вычисления следующего номера алгоритм булочной не гарантирует, что у всех процессов будут талончики с разными номерами. В случае равенства номеров на талончиках у двух или более клиентов первым обслуживается клиент с меньшим значением имени (имена можно сравнивать в лексикографическом порядке). Разделяемые структуры данных для алгоритма – это два массива

shared enum {false, true} choosing[n];shared int number[n];

Изначально элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения

(a,b) < (c,d), если a < c или если a == c и b < d max(a₀, a₁,...., a_n) – это число k такое, что k >= a_i для всех i = 0,...,n

Структура процесса P_i для алгоритма булочной приведена ниже

while (some condition) { choosing[i] = true; number[i] = max(number[0],..., number[n-1]) + 1; choosing[i] = false; for(j = 0; j < n; j++){ while(choosing[j]); while(number[j]!= 0 && (number[j],j) < (number[i],i)); } critical section number[i] = 0; remainder section }

Команда Test-and-Set (проверить и присвоить 1)

О выполнении команды Test-and-Set, осуществляющей проверку значения логической переменной с одновременной установкой ее значения в 1, можно думать как о выполнении функции

int Test_and_Set (int *target){ int tmp = *target; *target = 1; return tmp; }

С использованием этой атомарной команды мы можем модифицировать наш алгоритм для переменной-замка, так чтобы он обеспечивал взаимоисключения

shared int lock = 0; while (some condition) { while(Test_and_Set(&lock)); critical section lock = 0; remainder section }

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

Лекция 22

Рассмотрим два процесса: H c высоким приоритетом и L с низким. Правила планирования в этом случае запускают процесс H как только он оказывается в состоянии ожидания. В какой-то момент времени возможна ситуация, в которой процесс H попытается войти в критическую секцию, в которой уже находится L. H попадает в состояние активного ожидания. Но при этом в таком случае L никогда не будет предоставлено процессорное время и соответственно H всегда останется в цикле Такая ситуация называется: проблемой инверсии приоритетов.

Проблема производителя и потребителя.

Рассмотрим ситуацию когда два процесса совместно используют буфер ограниченного размера один из них (производитель) помещает данные в буфер, а другой (потребитель) считывает их. Проблемы возникают при попытке записать данные в полный буфер и считать их из пустого. Простое ожидание очистки или наполнения буфера приводят к состоянию состязания, так как в момент проверки состояния буфера в него могут быть дописаны и считаны данные. В 1965 году Эдгард Дейстрак предложил использовать целую переменную для подсчетов сигналов запуска (пробуждения). Был предложен новый тип переменных, так называемых семафоров, значение которых может быть нулем в результате отсутствия сигналов пробуждения или положительным числом соответствующим количеству отложенных сигналов пробуждения. Дейстрах предложил две операции down и up в оригинале названные им p и v соответственно. Эти операции являются…???…. операций sleep и wakeup. Операция down сравнивает значение семафора с нулем и, если оно больше нуля, то уменьшает его, возвращая управление вызывавшему процессу. Если же равно нулю – приводит процесс в состояние ожидания. Все операции проверки значения семафора его изменения и блокировка процесса выполняется как атомарное действие. Операция up увеличивает значение семафора, если с этим семафором связанны блокированные процессы, то один из них выбирается (обычно случайным образом) и ему разрешается завершить свою операцию down. Таким образом после операции up примененной к семафору, связанному с ожидающими процессами, значение семафора останется нулем, но количество ожидающих процессов останется уменьшиться. Значение операции семафора и активизация процессов тоже неделимы. С помощью семафоров достаточно просто решается проблема производителей и потребителей. Для этого используется три семафора: один для подсчета сегментов буфера, другой для подсчета пустых сегментов и третий для исключения совместного доступа к буферу производителя и потребителя. Последний семафор является двоичным.

Дата добавления: 2014-01-06