Problem proizvođača i potrošača
U informatici, problem proizvođača i potrošača (poznat i kao problem ograničenog bafera) je klasičan primer multiprocesnog sinhronizacionog problema u konkurentnom programiranju.[1][2] Formulisao ga je Edsger Dajkstra 1972. godine.[3] U problemu su opisana dva procesa, proizvođači i potrošači, koji dele bafer podataka fiksne veličine. Bafer se koristi kao red. Zadatak proizvođača je da generišu podatke i smeštaju ih u bafer. U isto vreme, potrošač uzima jedan po jedan podatak iz bafera. Problem se sastoji u tome da je potrebno obezbediti da proizvođač ne pokušava da doda podatke u pun bafer, niti da potrošač pokušava da uzme iz praznog.
Pogrešno rešenje može dovesti do mrtvog blokiranja, u kom procesi beskonačno čekaju da budu probuđeni. Problem se, takođe, može generalizovati na više proizvođača i potrošača.
Rešenja uredi
Korišćenjem semafora uredi
Primer rešenja primenom semafora u konkurentnom Paskalu:[4]
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.
Primer rešenja korišćenjem semafora u programskom jeziku 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);
}
}
Korišćenjem monitora uredi
Primer rešenja primenom monitora u programskom jeziku 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);
}
}
Vidi još uredi
Reference uredi
- ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Condition Variables] (PDF), Arpaci-Dusseau Books
- ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Semaphores] (PDF), Arpaci-Dusseau Books
- ^ Dijkstra, E. W. "Information streams sharing a finite buffer." Information Processing Letters 1.5 (1972): 179-180.
- ^ „Semafori” (PDF). Elektrotehnički fakultet Univerziteta u Beogradu. Pristupljeno 27. avgust 2020.
Literatura uredi
- Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao, Beograd.
Spoljašnje veze uredi
- Problem proizvođača i potrošača na Oracle sajtu, (jezik: engleski)
- Problem proizvođača i potrošača u operativnim sistemima, (jezik: engleski)