Решение задачи передачи данных одного процесса другому при помощи монитора (случай информационной базы)

Begin

Begin

Begin

End.

Parend

End

End

Begin

While (true) do

Begin

End

Begin

While (true) do

Begin

Parbegin

Begin

Begin

Begin

Begin

Монитор, реализующий двоичный семафор.

Signal(переменная-условие)

Wait(переменная-условие)

Переменная-условие (condition variable) вводится для каждой причины, по которой процесс может быть переведен в состояние ожидания. Заметим, что эти переменные совершеннно не похожи на обычные переменные, с которыми мы привыкли иметь дело. Когда определяется переменная-условие, заводится очередь. Процесс, выдавший команду ожидания, включается в эту очередь, а процесс, выдавший команду сигнализации, тем самым позволяет ожидающему процессу выйти из очереди и войти в монитор (обслуживание очереди может, например, осуществляться с использованием дисциплины FIFO).

 

 

Рассмотрим монитор, с помощью которого реализуется алгоритм выполнения операций Р и V над семафором S. Этот алгоритм известен, как алгоритм Хоара5 .

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

 

 

Monitor Семафор;

S : integer;

S_POSITIVE: condition;{переменная-условие, которая указывает, когда

заблокированный процесс может продолжать работу}

procedure P;

if S<1 then Wait(S_POSITIVE);{ожидание выполнения условия}

S:=S-1

end;

procedure V;

S:=S+1;

if S=1 then Signal(S_POSITIVE);{сигнал о выполнении условия}

end;

S:=1

end;

Рассмотрим, каким образом, при помощи приведенного монитора Хоара можно организовать взаимоисключение двух процессов. Здесь вызовы процедур P или V монитора будем указывать как Семафор.Р или Семафор.V.

 

 

Процесс_Х:

Call (Cемафор.Р);

{Критический участок Процесса_Х};

Call(Семафор.V);

{Оставшиеся операторы Процесса_Х}

end;

Процесс_Y;

Call (Cемафор.Р);

{Критический участок Процесс_Y};

Call(Семафор.V);

{Оставшиеся операторы Процесса_Y}

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

 

Решение задачи передачи данных одного процесса другому при помощи монитора (случай кольцевого буфера)

 

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

Напомним, что реализация взаимодействия в паре “производитель-

потребитель” при помощи семафоров рассматривалась нами ранее, теперь же покажем каким образом для решения этой проблемы можно воспользоваться монитором. В качестве кольцевого буфера, куда процесс-производитель помещает данные, используем массив BUFFER заданного размера N.

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

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

Рассмотрим монитор Кольцевой_буфер, базовая версия которого предложена в работе 6 .

 

monitor Кольцевой_буфер;

var BUFFER : array [0..N-1] of Тип_данных;

Tpos : 0..N;{текущая позиция в буфере}

Zpos, Opos : 0..N-1; {соответственно, очередная заполняемая и

очередная освобождаемая позиции в буфере}

BUFNp, BUFNz : condition;{ переменные-условия,

BUFNz- буфер незаполнен, является признаком, которого ждет производитель, если обнаружит, что буфер целиком заполнен, он устанавливается по сигналу потребителя о том, что тот только что освободил позицию;

BUFNp- буфер непуст, является признаком, которого ждет потребитель, если обнаружит, что буфер пуст, этот признак устанавливается по сигналу производителя о том, что он только что поместил данные в некоторую позицию буфера }

Procedure Заполнить_позицию (Данные:Тип данных) ;

if Tpos = N then Wait(BUFNz){ожидание сигнала- буфер незаполнен};

BUFFER[Zpos] := Данные;

Tpos:=Tpos+1;

Zpos:=(Zpos +1) mod N;

Signal(BUFNp){сигнал, оповещающий, о том, что буфер непуст}

end;

 

Procedure Ocвободить_позицию ( var Данные: Тип данных) ;

if Tpos=0 then Wait(BUFNp);{ожидание сигнала- буфер непуст}

Данные := BUFFER[Opos];

Tpos:=Tpos-1;

Opos:= (Opos+1) mod N;

Signal(BUFNz){сигнал, оповещающий о том, что буфер незаполнен}

end;

 

 

Tpos:=0;

Opos:=0;

Zpos:=0

end;

 

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

 

 

В вычислительных системах обычно имеются “процессы-читатели” и “процессы-писатели”(readers and writers) , если первые читают данные из информационной базы, то вторые, записывают данные в информационные базы. Заметим, что процессы-читатели не изменяют содержимого базы и могут обращаться к ней одновременно. А процесс-писатель может изменять данные, поэтому он должен иметь монопольный, исключительный доступ к базе данных.

Эта задача была впервые сформулирована и решена в работе Куртуа, Хейманса и Парнаса7. Решение этой задачи с использованием монитора впервые было предложено в работе Хоара8.

 

monitor Читатели_Писатели;