Семафоры

Резюме

Remainder section

Critical section

Команда Swap (Обменять значения)

Remainder section

Critical section

lock = 0;

}

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

Выполнение команды 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);

lock = 0;

}

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

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

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

Глава 6. Механизмы синхронизации

Предыдущая глава | Программа курса | Следующая глава

Рассмотренные в конце предыдущей главы алгоритмы хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок включает в себя достаточно длительное вращение процесса в пустом цикле, вхолостую пожирая драгоценное время процессора. Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования. Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них — H — с высоким приоритетом, другой — L — с низким приоритетом. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритетный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все время своего CPU burst (если не появится процесс с еще большим приоритетом). Тогда в случае, когда процесс L находится в своей критической секции, а процесс H, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс H не может войти в критическую область, находясь в цикле, а процесс L не получает управления, чтобы покинуть критический участок.

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

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году.

Дата добавления: 2014-12-16