ЗНАЕТЕ ЛИ ВЫ?

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



Многие компьютеры имеют аппаратные операции, которые позволяют проверять и устанавливать содержимое слова (операция 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;

whilewaiting[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 dono-op;

s := S – 1;

 

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

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

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

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

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

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

Repeat

. . . . .

wait(mutex);

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

signal(mutex);

. . . .

untilfalse;

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

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

S1;

signal(synch);

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

wait(synch);

S2;

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

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

Главным недостатком приведенного определения семафора является наличие цикла для организации ожидания. Пока один процесс выполняет свой критический участок, все остальные должны циклически выполнять вход в критический участок. Такое решение снижает эффективность работы. Во избежание этого, необходимо модифицировать описание семафора. Когда процесс выполняет операцию 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).

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

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

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

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

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





Последнее изменение этой страницы: 2016-08-16; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.219.31.204 (0.01 с.)