Задача “производитель-потребитель”, буфер неограниченного размера(Спящий парикмахер)

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

n2: P(ЧПБ);

P(РБ);

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

V(РБ);

V(ЧПП);

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

goto n2;

end;

parend;

end;

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

Пример применения приоритетного правила

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

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

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

Дано: N  производителей; M  потребителей; RB  размер буфера.

begin

integer array желание[1:N], СП[1:N];

integer ЧПБ, ББ, РБ, ЧСЕБ, i;

for цикл:=1 step 1 until N do begin

желание[i]:=0;

СП[i]:=0;

end;

ЧПБ:=0; ЧСЕБ:=RB;

ББ:=0; РБ:=1;

parbegin

производитель 1: begin ... end;

. . . . . . . . . . . . . . . .

производитель n: begin integer РП;

цикл n: производство новой порции и установка размера порции (РП);

P(РБ);

if ( (ББ=0) and (ЧСЕБ>=РП) ) then

ЧСЕБ:=ЧСЕБ-РП

else

begin

ББ:=ББ+1;

желание[n]:=РП;

V(РБ);

P(СП[n]);

P(РБ);

end;

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

V(РБ);

V(ЧПБ);

goto цикл n;

end;

... ... ...

производитель N: begin ... end;

потребитель 1: begin ... end;

... ... ...

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

integer РП, i, max, nmax;

цикл m: P(ЧПБ);

P(РБ);

взятие порции из буфера и установка РП;

ЧСЕБ:=ЧСЕБ+РП;

проверка: if (ББ>0) then

begin

max:=0;

for i:=1 step 1 until N do

begin

if(max<желание[i]) then

begin

max:=желание[i];

nmax:=i;

end

end;

if (max=<ЧСЕБ) then

begin

ЧСЕБ:=ЧСЕБ-max;

желание[nmax]:=0;

ББ:=ББ-1;

V(СП[nmax]);

goto проверка;

end;

end;

V(РБ);

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

goto цикл m;

end;

Для решения задачи вводится переменная состояния для каждого производителя - “желание”, обозначающая число единиц информации в буфере, необходимых для размещения порции, которая в текущий момент не может быть добавлена к буферу. Если для процесса-производителя эта переменная равна нулю, то процесс-производитель не имеет неудовлетворённых требований на добавление пор­ций.

Для каждого производителя вводится двоичный семафор СП (семафор производителя).

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

Как только в буфер добавляется новая порция, она может быть обработана. Так как безразлично, кто из потребителей её возьмёт, то для определения этого может быть использован общий семафор ЧПБ (число порций в буфере). О свободных областях в буфере производителям сообщается через цело­численную переменную состояния ЧСЕБ (число свободных единиц в буфере). Введена целочисленная переменная ББ (блокировка буфера), значение которой определяет, сколько процессов-производителей имеют желание добавить порцию в буфер, но не смогли разместить свои порции в буфере и она уве­домляет производителя в том, что уже есть процессы, которые обнаружили, что ББ>0, то он должен присоединиться к процессам, которые ожидают размещения порции в буфер.