Буфер ограниченного размера
Производитель и потребитель связаны через буфер ограниченной емкости в 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 i:=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, то он должен присоединиться к процессам, которые ожидают размещения порции в буфер.