Аппаратная поддержка взаимоисключений
Алгоритм булочной (Bakery algorithm)
Алгоритм Петерсона
Данный алгоритм был предложен Деккером и развит Петерсоном (1981). Он использует идеи предыдущих алгоритмов.
Пусть оба процесса имеют доступ к массиву флагов готовности и к переменной очередности. При исполнении пролога критической секции процесс Pi заявляет о своей готовности выполнить критический участок и одновременно предлагает другому процессу приступить к его выполнению. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда последует после другого. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.
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
}
Этот алгоритм удовлетворяет условиям 1-5
Основная идея алгоритма булочной выглядит так. Каждый вновь прибывающий клиент (процесс) получает талончик на обслуживание с номером. Клиент с наименьшим номером на талончике обслуживается следующим. К сожалению, из-за неатомарности операции вычисления следующего номера алгоритм булочной не гарантирует, что у всех процессов будут талончики с разными номерами. В случае равенства номеров на талончиках у двух или более клиентов первым обслуживается клиент с меньшим значением имени (имена можно сравнивать в лексикографическом порядке). Разделяемые структуры данных для алгоритма – это два массива
shared enum {false, true} choosing[n];
shared int number[n];
Изначально элементы этих массивов инициируются значениями false и 0соответственно. Введем следующие обозначения
(a,b) < (c,d), если a < c или если a == c и b < d
max(a0, a1, ...., an) – это число kтакое, что k >= aiдля всех i = 0, ...,n
Структура процесса Pi для алгоритма булочной приведена в виде
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
}
Этот алгоритм удовлетворяет условиям 1-5
Наличие аппаратной поддержки взаимоисключений позволяет упростить алгоритмы и повысить их эффективность точно так же, как это происходит и в других областях программирования. Многие КС помимо этого имеют специальные команды процессора, которые позволяют проверить и изменить значение машинного слова или поменять местами значения двух машинных слов в памяти, выполняя эти действия как атомарные операции. Концепции таких команд могут быть использованы для реализации взаимоисключений.