Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом был нарушен принцип взаимного исключения, что потенциально может привести к не желаемым последствиям.
Блокирующие переменные.
При использовании блокирующих переменных с каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным ресурсом), и значение 0, если ресурс занят.
Реализация критических секций с использованием блокирующих переменных
На рисунке показан фрагмент алгоритма процесса, использующего блокирующую переменную F(D) для реализации взаимного исключения доступа к разделяемому ресурсу D. Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется. Если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.
Блокирующие переменные могут использоваться не только при доступе к разделяемым данным, но и при доступе к разделяемым ресурсам любого вида. Если все потоки написаны с учетом вышеописанных соглашений, то взаимное исключение гарантируется. При этом потоки могут быть прерваны ОС в любой момент и в любом месте, в том числе в критической секции.
Поэтому для реализации пинципа блокирующих переменных в системе команд многих компьютеров предусмотрена единая, неделимая команда анализа и присвоения значения блокирующей переменной.
Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Для устранения этого недостатка во многих ОС предусматриваются специальные системные вызовы для работы с критическими секциями. Подобный механизм взаимного исключния реализован в ОС Windows NT.
Обобщением блокирующих переменных являются семафоры Дейкстры. Вместо двоичных используются переменные, принимающие только неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, называются семафорами.Доступ любого процесса к семафору, за исключением момента его синхронизации, может осуществляться только через две атомарные (неделимые) операции P и V Пусть целая, неотрицательная переменная S представляет собой семафор.
Доступ любого процесса к этой переменной может осуществляться только через две атомарные операции V(S) и P(S), определяемые следующим образом.
V(S) : переменная S увеличивается на 1 одним неделимым действием. К переменной S нет доступа другим процессам во время выполнения этой операции.
P(S) : уменьшение S на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае процесс, вызывающий операцию P, ждет, пока это уменьшение станет возможным (т.е. блокируется). Успешная проверка и уменьшение также является неделимой операцией. Никакие прерывания во время выполнения примитивов V и P недопустимы.
P(S): if S >=1 then S:=S-1
else WAIT(S) {остановить процесс и поместить его в очередь
ожидания к семафору S}
V(S): ifS<0 then RELEASE(S); {поместить один из ожидающих
процессов очереди
семафора S в очередь готовых процессов}
S:=S+1;
Эта запись означает следующее.
Пытаясь пройти через семафор (выполнение операции P над семафором S), процесс пробует вычесть из его значения 1.Проверить значение семафора S. Если это значение больше или равно 1, процесс проходит сквозь семафор успешно (семафор открыт). Если переменная равна нулю (семафор закрыт), процесс останавливается и ставится в очередь до тех пор, пока S не станет больше 0
Закрытие семафора соответствует захвату ресурса, доступ к которому контролируется этим семафором. Процесс, закрывший семафор, захватывает ресурс. Если ресурс захвачен, остальные процессы вынуждены ждать его освобождения.
Закончив работу с ресурсом (выполнение операция V), процесс увеличивает значение семафора на единицу, открывая его. При этом первый из стоявших в очереди процессов активизируется, вычитает из значения семафора единицу и снова закрывает семафор. Если же очередь была пуста, то ничего не происходит, просто семафор остается открытым. Тогда первый процесс, подошедший к семафору, успешно пройдет через него. Это действительно похоже на работу железнодорожного семафора, контролирующего движение поездов по одноколейной ветке.
В момент создания семафор может быть инициализирован любым неотрицательным значением:
Наиболее простым случаем семафора являетсядвоичный семафор. Начальное значение переменная такого семафора может принимать только значения 1 и 0. Двоичный семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только одна программа.
Реализация P- и V-операций для однопроцессороной системы:
type Semaphore = record
счетчик : integer;
указатель : pointer; нетипизированный указатель
end;
var S : Semaphore;
begin
procedure P (var S:Semaphore);
begin
ЗАПРЕТИТЬ ПРЕРЫВАНИЯ;
if S.счетчик >=1
then S.счетчик:=S.счетчик-1
else WAIT(S);{вставить обратившийся процесс в список по
S.указатель и установить на процессор
готовый к выполннию процесс}
РАЗРЕШИТЬ ПРЕРЫВАНИЯ;
end;
procedure V (var S:Semaphore);
begin
ЗАПРЕТИТЬ ПРЕРЫВАНИЯ;
ifS.счетчик<0 then RELEASE(S); {деблокировать первый
процесс из списка по
S.указатель}
S:=S+1;
РАЗРЕШИТЬ ПРЕРЫВАНИЯ;
end;
procedure InitSem (var S:Semaphore);
begin
S.счетчик:=1;
S.указатель:=nil; нулевой указатель
end;
end.
Проанализируем на двух конкурирующих процессах ПР1 и ПР2 использование разработанных семафорных примитивов для решения проблемы критической секции.
var S: Semaphore;
begin
InitSem(S);
parbegin
ПР1: while true do
begin
P(S);
CS1 {критическая секция процесса ПР1}
V(S)
end
and
ПР2: while true do
begin
P(S);
CS2 {критическая секция процесса ПР2}
V(S)
end
parend
end.
Начальное значение семафора S равно 1. Если процессы ПР1 и ПР2 попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать тоько одному из них. Пусть ПР2 в некоторый момент это сделал. Тогда он закрывает семафор (S=0) после чего выполняется его критическая секция. Если в это время процесс ПР1 попытается выпонить примитив P(S), то он будет заблокирован на семафоре S. Тем самым будет гарантировано взаимное искючение.
После выполнения своей критической секции ПР2 выполнит операцию V(S). При этом семафор откроется (S=S+1), а процесс ПР1 переведется в очередь готовности. Если через некотрое время ПР1 будет активизирован, он успешно выполнит P(S) и войде в свою критическую секцию.
Семафоры общего вида (N-ичный семафор) могут принимать любые неотрицательные значения. Это соответствует случаю, когда несколько процессов могут работать с ресурсом одновременно, или когда ресурс состоит из нескольких независимых, но равноценных частей - например, несколько одинаковых принтеров.
При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значения, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса.
В связи с проблемой тупиков были выполнено много интересных исследований в области информатики и операционных систем.
Основные направления борьбы с тупиками:
- игнорировать данную проблему
- обнаружение тупиков,
- распознавание тупиков и восстановление системы после тупиков.
