4.11 Семафоры

Все описанные выше ключевые понятия, относящиеся к взаимо­исключению, Дейкстра суммировал в своей концепции семафоров (Di65).

Семафор - это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных опе­раций Р и V и операции инициализации, которую назы­вают "инициализациясемафора".

Виды семафоров: Двоичные и Считающие.

Двоичные семафоры могут прини­мать только значения 0 и 1. Считающие семафоры (семафоры со счетчиками) могут принимать неотрицательные целые значения.

Операция Р над семафором записывается как P(S) и выполняется следующим образом:

если S > О

то S:= S – 1

иначе (ожидать на S)

Операция V над семафором S записывается как V(S) и выпол­няется следующим образом:

если (один или более процессов ожидают на S)

то (разрешить одному из этих процессов продолжить работу)

иначе S := S + 1

Мы будем предполагать, что очередь процессов, ожидающих на S, обслуживается в соответствии с дисциплиной "первый пришед­ший обслуживается первым" (FIFO).

Подобно операции проверки и установки testandset, операции Р и V являются неделимыми.

Участки взаимоисключения по сема­фору S в процессах обрамляются операциями P(S) и V(S).

Если од­новременно несколько процессов попытаются выполнить операцию P(S), это будет разрешено только одному из них, а остальным при­дется ждать.

Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно. Как правило, они реализуются в ядре операционной системы, где осуществляется управление сме­ной состояния процессов.

На рис. 4.9 приводится пример того, каким образом можно обеспечить взаимоисключение при помощи семафоров.

Здесь при­митив Р (активный) – эквивалент для "входвзаимоисключения",

примитив V (активный) – для "выходвзаимоисключения".

program примерсемафораодин;

var активный: семафор;

procedure процессодин;

begin

while истина do

begin

предшествующиеоператорыодин;

Р(активный);

критическийучастокодин;

V (активный);

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

предшествующиеоператорндва;

Р(активный);

критическийучастокдва;

V (активный);

прочиеоператорыдва

end

end;

begin

инициализациясемафора(активный,1),

p

Рис. 4.9 Обеспечение взаимоисключения при помощи семафора и примитивов Р и V.

arbegin

процессодин;

процессдва

parend

ends

4.12 Синхронизация процессов при помощи семафоров

Когда процесс выдает запрос ввода-вывода, он блокирует себя в ожидании завершения соответствующей операции ввода-вывода. Заблокированный процесс должен быть активизирован каким-либо другим процессом. Подобное взаимодействие может служить при­мером функций, относящихся к протоколу блокирования/возобновления.

Рассмотрим более общий случай, когда одному процессу необ­ходимо, например, чтобы он получал уведомление о наступлении некоторого события. Предположим, что какой-либо другой процесс может обнаружить, что данное событие произошло. Программа рис. 4.10 показывает, каким образом при помощи семафора можно реализовать простой механизм синхронизации (блокирования/во­зобновления) для двух процессов.

program блокированиевозобновления;

var событие: семафор;

procedure процессодин;

begin

предшествующиеоператорыодин;

Р(событие);

прочиеоператорыодин

end;

procedure процессдва;

begin

предшествующиеоператорыдва;

V(событие);

прочиеоператорыдва

end;

begin

инициализадйясемафора (событие, 0);

p

Рис. 4.10 Синхронизация блокирования/возобновление процессов при помощи семафоров.

arbegin

процессодин;

процессдва

parend

end;

Здесь "процессодин" выполняет некоторые "предшествующие операторыодин", а затем операцию Р (событие). Ранее при инициализа­ции семафор был установлен в нуль, так что "процессодин" будет ждать. Со временем "процессдва" выполнит операцию V (событие), сигнализируя о том, что данное событие произошло. Тем самым, "процессодин" получает возможность продолжить свое выполнение.

Отметим, что подобный механизм будет выполнять свои функ­ции даже в том случае, если "процессдва" обнаружит наступление события и просигнализирует об этом еще до того, как "процессодин", выполнит операцию Р (событие); при этом семафор переключится из 0 в 1, так что операция Р (событие) просто произведет обратное переключение, из 1 в 0, и "процессодин" продолжит свое выполнение без ожидания.