Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


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




 

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





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 469 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ћогика может привести ¬ас от пункта ј к пункту Ѕ, а воображение Ч куда угодно © јльберт Ёйнштейн
==> читать все изречени€...

1387 - | 1351 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.013 с.