Команда 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

}

Резюме

Последовательное выполнение некоторых действий, направленных на достижение определенной цели, называется активностью. Активности состоят из атомарных операций, выполняемых неразрывно, как единичное целое. При исполнении нескольких активностей в псевдопараллельном режиме атомарные операции различных активностей могут перемешиваться между собой с соблюдением порядка следования внутри активностей. Это явление получило название interleaving (чередование). Если результаты выполнения нескольких активностей не зависят от варианта чередования, то этот набор активностей называется детерминированным. В противном случае он носит названиенедетерминированного. Существует достаточное условие Бернстайна для определения детерминированности набора активностей, но оно накладывает очень жесткие ограничения на набор, требуя практически не взаимодействующих активностей. Про недетерминированный набор активностей говорят, что он имеет race condition (условие гонки, состязания). Устранение race condition возможно при ограничении допустимых вариантов чередований атомарных операций с помощью синхронизации поведения активностей. Участки активностей, выполнение которых может привести к race condition, называют критическими участками. Необходимым условием для устранения race condition является организация взаимоисключения на критических участках: внутри соответствующих критических участков не может одновременно находиться более одной активности.

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

Применение специальных команд процессора, выполняющих ряд действий как атомарную операцию, - Test-And-Set, Swap – позволяет существенно упростить алгоритмы, удовлетворяющие оставшимся условиям.