V(свободно);

Остаток цикла I;

goto Li;

end;

Задача “производитель-потребитель”

Общие семафоры

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

ЧПБ – число порций в буфере.

РБ – рабочий буфер.

begin integer ЧПБ;

ЧПБ := 0;

parbegin

производитель: begin

П1: производитель новой порции;

добавление новой порции в буфер;

v(ЧПБ);

goto П1;

end;

parend;

end;

потребитель: begin

П2: p(ЧПБ);

взятие порции из буфера;

обработка взятой порции;

goto П2;

end;

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

begin integer ЧПБ, РБ;

ЧПБ := 0;

parbegin

производитель: begin

П1: производитель новой порции;

p(РБ)

добавление новой порции в буфер;

v(PБ);

v(ЧПБ);

goto П1;

end;

parend;

end;

потребитель: begin

П2: p(ЧПБ);

p(PБ);

взятие порции из буфера;

v(PБ);

обработка взятой порции;

goto П2;

end;

A1 – двоичный семафор. Стремятся использовать только двоичные семафоры. В таком случае программа будет выглядеть так:

begin integer ЧПБ, РБ, ЗП;

ЧПБ := 0;

РБ := 1;

ЗП := 0;

parbegin

производитель: begin

П1: производитель новой порции;

p(РБ)

добавление новой порции в буфер;

ЧПБ := ЧПБ + 1;

If (ЧПБ = 1) then v(ЗП);

v(PБ);

goto П1;

end;

parend;

end;

потребитель: begin integer СЧПБ;

ждать: p(ЗП);

продолжить: p(PБ);

взятие порции из буфера;

ЧПБ := ЧПБ - 1;

СЧПБ := ЧПБ;

v(PБ);

обработка взятой порции;

if (CЧПБ = 0) then goto ждать;

else goto продолжить;

end;

Локальная переменная СЧПБ: значение устанавливается при взятии порции из буфера и фиксирует, не была ли эта порция последней. Здесь двоичный счетчик РБ предназначается по работе с буфером, введен новый двоичный семафор – задержка потребителя (ЗП). Программа представляет интерес в течение времени, когда буфер пуст. В исходном состоянии семафор ЗП установлен в ноль и открывается производителем только в том случае, когда в пустой буфер записывается порция. Установка потребителя на семафор ЗП не блокирует работу с буфером, так как стоит выше операции р(РБ). Смысл ждать есть только в том случае, если буфер пуст.

Задача “производитель-поТребитель”

буфер неограниченного размера

(Программа называется "спящий парикмахер".)

begin

integer ЧПБ, РБ, ЗП;

ЧПБ:=0; РБ:=1; ЗП:=0;

parbegin

производитель: begin

n1: производство новой порции;

P(РБ);

добавление новой порции к буферу;

ЧПБ:=ЧПБ+1;

if ЧПБ=0 then begin V(РБ); V(ЗП); end

else V(РБ);

goto n1;

end;

потребитель: begin

n2: P(РБ);

ЧПБ:=ЧПБ-1;

if ЧПБ=-1 then begin V(РБ); P(ЗП); P(РБ); end;

взятие порции из буфера;

V(РБ);

обработка взятой порции;

goto n2;

end;

parend;

Используется два двоичных семафора: работа с буфером и задержка потребителя.

Особенности:

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

• задача взаимного исключения реализуется через семафоры

• также через семафоры реализуется задержка потребителя, которая действует при попытке потребителя читать данные из пустого буфера

Задача “производитель-потребитель”

буфер ограничен

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

begin

integer ЧПБ, ЧПП, РБ;

ЧПБ:=0;

ЧПП:=N;

РБ:=1;

parbegin

производитель: begin

n1: производство новой порции;

P(ЧПП);

P(РБ);

добавление порции к буферу;

V(РБ);

V(ЧПБ);

goto n1;

end;

потребитель: begin

n1: P(ЧПБ);

P(РБ);

взятие порции из буфера;

V(РБ);

V(ЧПП);

обработка взятой порции;

goto n2;

end;

parend;

end;

И производитель и потребитель решают через РБ задачу взаимного исключения. Проблема производителя: нельзя писать в заполненный буфер. Проблема потребителя: нельзя читать из пустого буфера. Производитель решает свою проблему с использованием общего семафора ЧПП (число пустых порций), а потребитель  через ЧПБ (число порций в буфере).