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. Formulisao ga je Edsger Dajkstra 1972. godine. 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

Korišćenjem semafora

Primer rešenja primenom semafora u konkurentnom Paskalu:

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

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š

• Problem čitalaca i pisaca
• Problem filozofa za ručkom
• Problem nervoznih pušača
• Paralelno izračunavanje

Literatura

• Radivojević, Zaharije; Ikodinović, Igor; Jovanović, Zoran (2018). Konkurentno i distribuirano programiranje (drugo izdanje). Akademska misao, Beograd.

Spoljašnje veze

• 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)