У информатици, проблем произвођача и потрошача (познат и као проблем ограниченог бафера) је класичан пример мултипроцесног синхронизационог проблема у конкурентном програмирању. Формулисао га је Едсгер Дајкстра 1972. године.Dijkstra, E. W. "Information streams sharing a finite buffer." Information Processing Letters 1.5 (1972): 179-180. У проблему су описана два процеса, произвођачи и потрошачи, који деле бафер података фиксне величине. Бафер се користи као ред. Задатак произвођача је да генеришу податке и смештају их у бафер. У исто време, потрошач узима један по један податак из бафера. Проблем се састоји у томе да је потребно обезбедити да произвођач не покушава да дода податке у пун бафер, нити да потрошач покушава да узме из празног.
Погрешно решење може довести до мртвог блокирања, у ком процеси бесконачно чекају да буду пробуђени. Проблем се, такође, може генерализовати на више произвођача и потрошача.
Решења
Коришћењем семафора
Пример решења применом семафора у конкурентном Паскалу:
program ProducerConsumer; const BufferSize = 3;
var mutex : semaphore; empty : semaphore; full : semaphore;
procedure Producer(ID : integer); var item : integer; begin while (true) do begin make_new(item); wait(empty); wait(mutex); put_item(item); signal(mutex); signal(full); end; end;
procedure Consumer(ID : integer); var item : integer; begin while (true) do begin wait(full); wait(mutex); remove_item(item); signal(mutex); signal(empty); consume_item(item); end; end;
begin init(mutex,1); init(empty, BufferSize); init(full, 0); cobegin Producer(0); //... Consumer(0); //... coend; end.
Пример решења коришћењем семафора у програмском језику C:
semaphore fillCount = 0; // proizvedeni podaci semaphore emptyCount = BUFFER_SIZE; // preostali prostor
procedure producer() { while (true)
item = produceItem(); down(emptyCount); putItemIntoBuffer(item); up(fillCount);
procedure consumer() { while (true)
down(fillCount); item = removeItemFromBuffer(); up(emptyCount); consumeItem(item);
Коришћењем монитора
Пример решења применом монитора у програмском језику C:
monitor ProducerConsumer { int itemCount = 0; condition full; condition empty;
procedure add(item)
if (itemCount == BUFFER_SIZE)
wait(full);
putItemIntoBuffer(item); itemCount = itemCount + 1;
if (itemCount == 1)
notify(empty);
procedure remove()
if (itemCount == 0)
wait(empty);
item = removeItemFromBuffer(); itemCount = itemCount - 1;
if (itemCount == BUFFER_SIZE - 1)
notify(full);
return item;
procedure producer() { while (true)
item = produceItem(); ProducerConsumer.add(item);
procedure consumer() { while (true)
item = ProducerConsumer.remove(); consumeItem(item);
Види још
Проблем читалаца и писаца Проблем филозофа за ручком Проблем нервозних пушача Паралелно израчунавање
Референце
Литература
Радивојевић, Захарије; Икодиновић, Игор; Јовановић, Зоран (2018). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао, Београд.
Спољашње везе
Проблем произвођача и потрошача на Oracle сајту, Проблем произвођача и потрошача у оперативним системима,
Категорија:Информатика