为什么单 producer/consumer 的生产者消费者队列不需要互斥体？

Question

具有单个生产者和单个消费者的生产者消费者队列的代码From wikipedia是：

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);
    }
}

那里说

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

当有更多的producers/consumers时，伪代码是相同的，用一个互斥锁来保护putItemIntoBuffer(item);和removeItemFromBuffer();部分：

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);
    }
}

我的问题是，为什么在单一生产者单一消费者案例中不需要互斥量？

考虑以下因素：

队列中有 5 个项目，允许 10 个项目。
生产者产生一个项目，递减空信号量（并成功），然后开始将项目放入缓冲区，并且没有完成
消费者递减填充信号量，然后开始从缓冲区中删除项目
出乎意料。尝试从缓冲区 (3) 中删除项，同时将项放入缓冲区 (2)

为什么我描述的情况没有发生？

Answer 1

因为这样的队列通常会被实现为循环队列。生产者将写入队列的尾部，而消费者从头部读取。他们永远不会同时访问相同的内存。

这里的想法是消费者和生产者都可以独立地跟踪 tail/head 的位置。

考虑以下伪代码：

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;
}

consumerPtr 和 producerPtr 只有当队列为满或为空时才可以相等，在这种情况下，不会调用这些函数，因为执行进程将在信号量上保持阻塞。

你可以说信号量被用作消息传递机制，允许另一方增加它的指针，同步它。

现在，如果一侧有多个进程，则该侧将需要以原子方式执行增量和数据复制，因此需要互斥锁，但仅适用于具有多个进程的一侧，例如对于多生产者和多消费者队列，您可以使用 2 个独立的互斥体来减少争用。

为什么单 producer/consumer 的生产者消费者队列不需要互斥体？

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

parallel-processing

synchronization

mutex

semaphore

producer-consumer