Операция проверки и установки

Многие компьютеры имеют аппаратные операции, которые позволяют проверять и устанавливать содержимое слова (операция Test and Set Lock). Логику работы этой операции можно описать следующим образом:

function Test_and_Set(var target:Boolean):Boolean;

Begin

Test_and_Set:= target;

target:= true;

end;

Главная отличительная особенность этой команды – ее выполнение не может быть прервано. Если предпринимается попытка одновременного выполнения двух таких команды (на разных процессорах), то они будут выполнены последовательно, в порядке, определяемом аппаратурой. Такой прием называется блокировкой памяти.

Если наша компьютерная система поддерживает такую команду, то мы можем организовать взаимное исключение, объявив переменную lock с начальным значением false. Пусть у нас имеется n процессов. Тогда структура процесса может быть следующей:

Repeat

...

while Test_and_Set(lock) do

no-op;

критический участок

lock:= false;

...

until false;

Этот алгоритм, однако, не удовлетворяет условию ограниченного ожидания.

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

var waiting: array [0..n-1] of Boolean;

lock: Boolean;

Все они проинициализированы значением false.

Тогда структура процесса будет следующей:

var j: 0..n-1;

key: Boolean;

...

Repeat

waiting[i]:= true;

key:= true;

while waiting[i] and key do

key:= Test_and_Set(lock);

waiting[i]:= false;

критический участок

j:= (j + 1) mod n;

while (j <> i) and not waiting[j] do

j:= (j + 1) mod n;

if i = j then

lock:= false;

Else

waiting[i]:= false;

...

until false;

Процесс может войти в критический участок, если значение waiting[i] или key ложно. Переменная key получит значение false только если операция Test_and_Set выполнена. Процесс, первым выполнивший эту операцию, найдет это значение, равным false и войдет в критический участок, остальные процессы должны ждать. Переменная waiting[i] получит значение false только, когда другой процесс выйдет из критического участка, и только это обеспечивает требование взаимного исключения. Ограниченное ожидание обеспечивается за счет циклического просмотра, а освобождение критического участка – установкой значения переменной lock в false.

Семафоры

Традиционное решение того, как обеспечить взаимно исключающий доступ к общим ресурсам, состоит в использовании семафоров. Впервые семафоры были предложены Эдсгеном Дейкстрой для операционной системы THE.

Семафор – это переменная целого типа, которая, кроме начальной инициализации допускает только две простых операции: wait и signal.

Классическое определение этих операций:

wait(s): while s <= 0 do no-op;

s:= S – 1;

 

Signal(s): s:= S + 1;

Модификации значения семафора этими операциями выполняются неделимо. Пока один процесс модифицирует семафор, ни один другой процесс не имеет доступа к этому семафору. Кроме того, в случае wait(s) проверка значения семафора и его модификация также должны выполняться неделимо.

Такие семафоры называют счетными или считающими.

Использование семафоров

Рассмотрим использование семафоров для организации критических участков для n процессов . Эти процессы разделяют семафор mutex, инициализированный значением 1.

Схема работы процесса выглядит следующим образом:

Repeat

.....

wait(mutex);

критическая секция

signal(mutex);

....

until false;

Можно применять семафоры и для решения других задач синхронизации. Например, рассмотрим два параллельно выполняемых процесса , в котором имеется оператор , и , в котором имеется оператор . Предположим, что оператор должен выполняться после оператора . Можно решить эту задачу путем использования общего семафора synch, инициализированного нулем.

Процесс будет содержать последовательность операторов:

S₁;

signal(synch);

Процесс будет содержать последовательность операторов:

wait(synch);

S₂;

Так как начальное значение семафора равно нулю, оператор будет выполняться только после оператора .

Реализация семафоров

Главным недостатком приведенного определения семафора является наличие цикла для организации ожидания. Пока один процесс выполняет свой критический участок, все остальные должны циклически выполнять вход в критический участок. Такое решение снижает эффективность работы. Во избежание этого, необходимо модифицировать описание семафора. Когда процесс выполняет операцию wait(s), а значение семафора меньше нуля, он должен перейти в состояние ожидания, то есть он должен себя заблокировать. Для этого процесс должен поместить себя в очередь, ассоциированную с данным семафором, изменить свое состояние и передать управление планировщику. Заблокированный процесс может быть возобновлен, когда несколько процессов выполнят операцию signal. При этом должна быть выполнена операция пробуждения (wakeup), перемещающая процесс в очередь готовых заданий.

Реализацию семафора можно определить следующим образом:

type semaphore = record

value: integer;

L: list of processes;

end;

Каждому семафору соответствует целое значение и список процессов.

wait(s): s.value:= s.value – 1;

if s.value < 0 then

Begin

add this process to s.L;

block;

end;

signal(s): s.value:= s.value + 1;

if s.value <= 0 then

Begin

remove a process P from s.L;

wakeup(P);

end;

Очередь ожидающих процессов может обслуживаться по методу FIFO или с помощью любой другой стратегии.

Тупики и зависания

Реализация семафоров с очередью может привести к тому, что два или более процессов могут неопределенно долго ожидать события, которое может быть инициировано только одним из этих ожидающих процессов. Таким событием является выполнение операции signal. В случае возникновения такой ситуации, говорят, что процессы находятся в тупике (deadlock).

Для иллюстрации рассмотрим два процесса, P₀ и P₁, имеющих доступ к двум семафорам S и Q, первоначально установленным в 1.

P0 wait(S) wait(Q) . . . signal(Q) signal(S)

P1 wait(Q) wait(S) . . . signal(S) signal(Q)

Предположим, что процесс P₀ выполнил wait(S), затем процесс P₁ выполнил wait(Q). Когда процесс P₀ выполнит wait(Q), он будет ожидать, пока процесс P₁ выполнит операцию signal(S). Аналогично, процесс P₁ будет ожидать, пока процесс P₀ выполнит операцию signal(Q). Поскольку эти операции не могут быть выполнены, процессы P₀ и P₁ находятся в тупике.

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

Другой опасностью являются так называемые зависания (starvation), когда процесс находится в очереди к семафору неопределенно долгое время. Такая ситуация может, например, возникнуть, если очередь к семафору организована по методу LIFO.