Семафоры

Недостатки алгоритмов взаимоисключений

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

Команда 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, обменивающей два значения, находящихся в памяти, можно проиллюстрировать следующей функцией

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;

Swap(&lock,&key);

while (key);

critical section

lock = 0;

remainder section

}

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

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

 

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