V(свободно);
Остаток цикла I;
goto Li;
end;
Задача “производитель-потребитель” применение ОбщиХ семафорОв
Рассматриваются два процесса, которые называются производитель и потребитель.
Производитель – циклический процесс, который при каждом циклическом повторении участка программы производит отдельную порцию информации, которая должна быть обработана потребителем.
Потребитель – также циклический процесс, который при каждом повторении обрабатывает следующую порцию информации, выработанной производителем.
Отношения производитель-потребитель подразумевают наличие одностороннего канала связи, по которому могут передаваться порции информации. Предполагается, что процессы связаны через буфер неограниченной емкости, то есть произведенные порции не обязательно должны немедленно потребляться, а могут организовывать в буфере очередь. Буфер должен обеспечить размещение последовательности порций информации и должен располагаться в подходящей запоминающей среде, доступной обоим процессам. Буфер также должен отражать линейную упорядоченность порций информации. Буфер работает по принципу FIFO.
Упрощенный вариант решения задачи «производитель-потребитель» (здесь используется общий семафор ЧПБ (число порций в буфере)):
begin integer ЧПБ;
ЧПБ := 0;
parbegin
производитель:
begin
П1: производство новой порции;
добавление новой порции в буфер;
v(ЧПБ);
goto П1;
end;
потребитель:
begin
П2: p(ЧПБ);
взятие порции из буфера;
обработка взятой порции;
goto П2;
end;
parend;
end;
Операции добавления порции к буферу производителем и взятия порции из буфера потребителем могут помешать друг другу, если по отношению к этим действиям не решить задачу взаимного исключения. Для этой цели можно применить двоичный семафор РБ (работа с буфером):
begin integer ЧПБ, РБ;
ЧПБ := 0;РБ := 1;
parbegin
производитель:
begin
П1: производство новой порции;
p(РБ);
добавление новой порции в буфер;
v(PБ);
v(ЧПБ);
goto П1;
end;
потребитель:
begin
П2: p(ЧПБ);
p(PБ);
взятие порции из буфера;
v(PБ);
обработка взятой порции;
goto П2;
end;
рarend;
end;
Необходимо обратить внимание на два момента:
- последовательность v-операций у производителя не имеет значения;
- для потребителя последовательность р-операций существенна, так как если их поменять местами, то может возникнуть ситуация блокировки буфера и потребитель не сможет работать.
Так как обработка общих семафоров более трудоёмка, чем обработка двоичных семафоров, то эту задачу можно решить, используя только двоичные семафоры РБ (работа с буфером) и ЗП (задержка потребителя):
begin integer ЧПБ, РБ, ЗП;
ЧПБ := 0; РБ := 1; ЗП := 0;
parbegin
производитель:
begin
П1: производство новой порции;
p(РБ);
добавление новой порции в буфер;
ЧПБ := ЧПБ + 1;
If (ЧПБ = 1) then v(ЗП);
v(PБ);
goto П1;
end;
потребитель: begin integer СЧПБ;
ждать: p(ЗП);
продолжать: p(PБ);
взятие порции из буфера;
ЧПБ := ЧПБ - 1;
СЧПБ := ЧПБ;
v(PБ);
обработка взятой порции;
if (CЧПБ = 0) then goto ждать;
else goto продолжать;
end;
parend;
end;
В динамическом поведении программы интересны моменты, когда буфер пуст. Каждый такой промежуток времени, связанный с пустым буфером, сопровождается р- и v-операциями над семафором ЗП.
Локальная переменная СЧПБ, значение которой устанавливается и изменяется после взятия порции из буфера, позволяет определить, была ли эта порция последней. Если это так, то потребитель ждёт, пока будет занесена порция в буфер производителем.
Есть ещё одно решение этой задачи, которое называется "спящий парикмахер":
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;
end;
Пустота буфера имеет значение только тогда, когда потребитель хотел бы взять новую порцию, а буфер ещё пустой.
Семафорные операции над ЗП не выполняются, если буфер пустовал короткое время, но снова заполнился.