Проблем произвођача и потрошача

У информатици, проблем произвођача и потрошача (познат и као проблем ограниченог бафера) је класичан пример мултипроцесног синхронизационог проблема у конкурентном програмирању.^[1]^[2] Формулисао га је Едсгер Дајкстра 1972. године.^[3] У проблему су описана два процеса, произвођачи и потрошачи, који деле бафер података фиксне величине. Бафер се користи као ред. Задатак произвођача је да генеришу податке и смештају их у бафер. У исто време, потрошач узима један по један податак из бафера. Проблем се састоји у томе да је потребно обезбедити да произвођач не покушава да дода податке у пун бафер, нити да потрошач покушава да узме из празног.

Погрешно решење може довести до мртвог блокирања, у ком процеси бесконачно чекају да буду пробуђени. Проблем се, такође, може генерализовати на више произвођача и потрошача.

Решења

Коришћењем семафора

Пример решења применом семафора у конкурентном Паскалу:^[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.

Пример решења коришћењем семафора у програмском језику 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);
    }
}

Види још

Референце

^ 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.
^ „Семафори” (PDF). Електротехнички факултет Универзитета у Београду. Приступљено 27. август 2020.

Литература

Радивојевић, Захарије; Икодиновић, Игор; Јовановић, Зоран (2018). Конкурентно и дистрибуирано програмирање (друго издање). Академска мисао, Београд.