Наличие аппаратной поддержки взаимоисключений позволяет упростить алгоритмы и повысить их эффективность точно так же, как это происходит и в других областях программирования. Мы уже обращались к общепринятому hardware для решения задачи реализации взаимоисключений, когда говорили об использовании механизма запрета/разрешения прерываний.
Многие вычислительные системы помимо этого имеют специальные команды процессора, которые позволяют проверить и изменить значение машинного слова или поменять местами значения двух машинных слов в памяти, выполняя эти действия как атомарные операции. Давайте обсудим, как концепции таких команд могут использоваться для реализации взаимоисключений.
Команда 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
}
К сожалению, даже в таком виде полученный алгоритм не удовлетворяет условию ограниченного ожидания для алгоритмов. Подумайте, как его следует изменить для соблюдения всех условий.
Команда Swap (обменять значения)
Выполнение команды Swap, обменивающей два значения, находящихся в памяти, можно проиллюстрировать следующей функцией:
void Swap (int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
Применяя атомарную команду Swap, мы можем реализовать предыдущий алгоритм, введя дополнительную логическую переменную key, локальную для каждого процесса:
shared int lock = 0;
int key;
while (some condition) {
key = 1;
do Swap(&lock,&key);
while (key);
critical section
lock = 0;
remainder section
}