The design of the UNIX Operating System 27 страница
Отсюда же вытекает выполнение условия ограниченного ожидания. Так как в процессе ожидания разре-шения на вход процесс P0 не изменяет значения переменных, он сможет начать исполнение своего кри-тического участка после не более чем одного прохода по критической секции процесса P1.
Алгоритм булочной (Bakery algorithm)
Алгоритм Петерсона дает нам решение задачи корректной организации взаимодействия двух процессов. Давайте рассмотрим теперь соответствующий алгоритм для n взаимодействующих процессов, который получил название алгоритм булочной, хотя применительно к нашим условиям его следовало бы скорее назвать алгоритм регистратуры в поликлинике. Основная его идея выглядит так. Каждый вновь прибы-
|
|
|
| Основы операционных систем | 56 |
вающий клиент (он же процесс) получает талончик на обслуживание с номером. Клиент с наименьшим номером на талончике обслуживается следующим. К сожалению, из-за неатомарности операции вычис - ления следующего номера алгоритм булочной не гарантирует, что у всех процессов будут талончики с разными номерами. В случае равенства номеров на талончиках у двух или более клиентов первым об-служивается клиент с меньшим значением имени (имена можно сравнивать в лексикографическом по-рядке). Разделяемые структуры данных для алгоритма – это два массива
|
|
|
|
|
|
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, выполните самостоятельно в каче-стве упражнения.
Аппаратная поддержка взаимоисключений
Наличие аппаратной поддержки взаимоисключений позволяет упростить алгоритмы и повысить их эф-фективность точно так же, как это происходит и в других областях программирования. Мы уже обраща-лись к общепринятому hardware для решения задачи реализации взаимоисключений, когда говорили об использовании механизма запрета/разрешения прерываний.
Многие вычислительные системы помимо этого имеют специальные команды процессора, которые по-зволяют проверить и изменить значение машинного слова или поменять местами значения двух машин-ных слов в памяти, выполняя эти действия как атомарные операции. Давайте обсудим, как концепции таких команд могут использоваться для реализации взаимоисключений.
Команда Test-and-Set (проверить и присвоить 1)
О выполнении команды Test-and-Set, осуществляющей проверку значения логической переменной с од-новременной установкой ее значения в 1, можно думать как о выполнении функции
int Test_and_Set (int *target){ int tmp = *target;
*target = 1; return tmp;
}
| Основы операционных систем | 57 |
С использованием этой атомарной команды мы можем модифицировать наш алгоритм для переменной-замка, так чтобы он обеспечивал взаимоисключения
shared int lock = 0;
while (some condition) { while(Test_and_Set(&lock));
critical section lock = 0;
remainder section
}
К сожалению, даже в таком виде полученный алгоритм не удовлетворяет условию ограниченного ожида-ния для алгоритмов. Подумайте, как его следует изменить для соблюдения всех условий.
Команда Swap (обменять значения)
Выполнение команды Swap, обменивающей два значения, находящихся в памяти, можно проиллюстри-ровать следующей функцией:
Дата добавления: 2021-01-21; просмотров: 160; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!