why does producer consumer queue with single producer/consumer doesn't need mutex?

Question

The code From wikipedia for producer consumer queue with a single producer and a single consumer is:

semaphore fillCount = 0; // items produced
semaphore emptyCount = BUFFER_SIZE; // remaining space

procedure producer() 
{
    while (true) 
    {
        item = produceItem();
        down(emptyCount);
        putItemIntoBuffer(item);
        up(fillCount);
    }
}

procedure consumer() 
{
    while (true) 
    {
        down(fillCount);
        item = removeItemFromBuffer();
        up(emptyCount);
        consumeItem(item);
    }
}

it is stated there that

The solution above works fine when there is only one producer and consumer.

When there are more producers/consumers, the pseudocode is the same, with a mutex guarding the putItemIntoBuffer(item); and removeItemFromBuffer(); sections:

mutex buffer_mutex; // similar to "semaphore buffer_mutex = 1", but different (see notes below)
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;

procedure producer() 
{
    while (true) 
    {
        item = produceItem();
        down(emptyCount);
        down(buffer_mutex);
        putItemIntoBuffer(item);
        up(buffer_mutex);
        up(fillCount);
    }
}

procedure consumer() 
{
    while (true) 
    {
        down(fillCount);
        down(buffer_mutex);
        item = removeItemFromBuffer();
        up(buffer_mutex);
        up(emptyCount);
        consumeItem(item);
    }
}

My question is, why isn't the mutex required in the single producer single consumer case?

consider the following:

5 items in a queue allowing 10 items.
Producer produces an item , decrements the empty semaphore (and succeeds), then starts putting the item into the buffer, and is not finished
Consumer decrements the fill semaphore, then starts to remove item from buffer
unexpected. Trying to remove item from buffer (3) while putting item to buffer (2)

Why does what i described not happen?

StaceyGirl StaceyGirl · Accepted Answer · 2018-12-19T15:36:25

Because such queue will usually be implemented as a circular queue. Producer will be writing to the tail of the queue, while consumer reads from the head. They never access the same memory at the same time.

The idea here is that both consumer and producer can track the position of the tail/head independently.

Consider the following pseudo-code:

T data[BUFFER_SIZE];
int producerPtr = 0, consumerPtr = 0;

void putItemIntoBuffer(Item item)
{
     data[producerPtr] = item;
     producerPtr = (producerPtr  + 1) % BUFFER_SIZE;
}

Item removeItemFromBuffer(void)
{
     Item item = data[consumerPtr ];
     consumerPtr = (consumerPtr + 1) % BUFFER_SIZE;
     return item;
}

Both consumerPtr and producerPtr can be equal only when the queue is either full or empty in which case those functions will not be called as executing process will remain blocked on a semaphore.

You can say that semaphores are used as a message passing mechanism, allowing the other side to increment its pointer, synchronizing this.

Now if you have multiple processes on one side, that side will need to perform increment and data copying atomically, therefor mutex is needed, but only for the side that has multiple processes e.g. for multiple-producer and multiple-consumer queue you can use 2 separate mutexes to decrease contention.

why does producer consumer queue with single producer/consumer doesn't need mutex?

1 Answers