4.2.4. Аппаратная реализация взаимного исключения

Аппаратным средством реализации взаимного исключения являются неделимые команды, осуществляющие проверку переменной и присваивание ей значения. Примером является команда проверить-и-установить (TS - Test-and-Set), которая может быть определена так, как показано на рис.4.13.

function testset (var i : integer ): boolean;

begin

if i = 0 then

begin

i := 1;

testset := true

end

else testset := false

end.

Рис. 4.13.

Указанная команда проверяет значение своего аргумента i. Если это значение равно 0, то команда устанавливает его в 1 и возвращает значение true (истина), в противном случае величина аргумента не изменяется, и возвращается значение false (ложь) - и все это в рамках одной непрерывной операции. Пример использования команды проверки и установки для реализации взаимного исключения приведен на рис.4.14.

Глобальная переменная bolt устанавливается равной 0. Единственным процессом, имеющим возможность войти в свою критическую секцию является тот, который считывает значение bolt равное 0. Все остальные процессы, пытающиеся войти в свои критические интервалы, переводятся в состояние ожидающий. Когда первый процесс покидает свой критический интервал, он переустанавливает bolt в 0. В этот момент одному (и только одному) из ожидающих процессов разрешается доступ в его критическую секцию.

Program TS_example;

Var bolt: integer;

Procedure Process P(i: integer);

begin

repeat

while testset(bolt) do

begin

< критический интервал >;

bolt := 0 ;

< остальная часть программы >

end

until false

end ;

Begin

bolt := 0 ;

Process P(1) ;

Process P(2)

End .

Рис. 4.14.

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

4.2.5. Семафоры

Для устранения трудностей, возникающих при реализации взаимного исключения, Дейкстра ввел две операции, названные P (от голландского слова Proberen - проверять) и V (от голландского слова Verhogen - увеличивать). Эти операции работают с переменной S, которая совместно используется параллельными процессами и служит для их синхронизации. Указанная переменная называется семафором. (Она также получила название «элементарное средство взаимного исключения»). В наиболее простом варианте семафор может принимать два значения : 0 и 1. Такие семафоры называются двоичными. Более сложные считающие семафоры (семафоры со счетчиками) могут принимать неотрицательные целые значения.

С каждым семафором связывается список (­не обязательно очередь) процессов, ожидающих разрешения пройти семафор. Операционная система может выполнять три действия над процессами. Она может назначить для исполнения готовый процесс. Она может заблокировать исполняющийся процесс и поместить его в список, связанный с конкретным семафором. Она может деблокировать процесс, тем самым переводя его в готовое к исполнению состояние и позволяя ему когда-нибудь возобновить исполнение. Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс.

Операции Р и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.

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

S := S - 1;

if S < 0 then

begin

блокировать обратившийся процесс по S

end;

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

S := S + 1;

if S <= 0 then

begin

разрешить процессу, ожидающему на S, продолжить работу

end;

При этом не определяется, какой из нескольких ожидающих процессов будет деблокирован. (Предполагается, что очередь процессов, ожидающих на S, обслуживается с дисциплиной «первый пришедший обслуживается первый»).

Аналогично операции проверки и установки Test-and-Set операции P и V являются неделимыми. Критические секции в процессах обрамляются операциями P(S) и V(S). Если одновременно несколько процессов попытаются выполнить операцию P(S), это будет разрешено только одному из них, а остальным придется ждать.

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

Program Semaphore_example ;

Var S: semaphore;

Procedure Process P1;

begin

repeat

P(S) ;

< критический интервал >;

V(S) ;

< остальная часть программы >

until false

end ;

Procedure Process P2;

begin

repeat

P(S) ;

< критический интервал >;

V(S) ;

< остальная часть программы >

until false

end ;

Begin

S := 1 ;

Process P1 ;

Process P2

End .

Рис. 4.15. Реализация взаимного исключения

при помощи семафора и команд P и V

Для процессов, совместно выполняющих общую работу, недостаточно того, что они взаимно исключают друг друга при работе с общими переменными; им необходимо еще передавать друг другу информацию. Минимальной единицей передаваемой информации является простой временной сигнал. Основное требование в этом случае состоит в том, что процессу предоставляется возможность ждать (быть заблокированным), пока другой процесс не сообщит ему о свершении определенного события. При помощи семафора можно реализовать простой механизм синхронизации (блокирования - возобновления) для двух процессов (рис.4.16).

Program Synchronization ;

Vаг S : semaphor ;

Pгосеdure Process_P1 ;

begin

repeat

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

P(S) ;

< остальная часть программы >

until false

end ;

Pгосеdure Process_P2 ;

begin

repeat

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

V(S) ;

< остальная часть программы >

until false

end ;

Begin

S := 0 ;

Process_P1 ;

Process_P2

End .

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

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