почему очередь потребителя производителя с одним производителем / потребителем не нуждается в мьютексе?

Question

Код Из википедии для очереди потребителя производителя с одним производителем и одним потребителем:

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

там указано, что

Приведенное выше решение прекрасно работает, когда есть только один производитель и потребитель.

Когда есть больше производителей / потребителей, псевдокод тот же, с мьютексом, защищающим секции 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);
    }
}

Мой вопрос: почему мьютекс не требуется в случае одного потребителя с одним производителем?

учитывает следующее:

1. 5 элементов в очереди, позволяющих 10 элементов.
2. Производитель создает элемент, уменьшает пустой семафор (и успешно), затем начинает помещать элемент в буфер и не завершается
3. Потребитель уменьшает семафор заполнения, затем начинает неожиданно удалять элемент из буфера
4. .Попытка удалить элемент из буфера (3) при помещении элемента в буфер (2)

Почему то, что я описал, не происходит?

Answer 1

Поскольку такая очередь обычно будет реализована в виде циклической очереди.Продюсер будет писать в конец очереди, а потребитель читает из головы.Они никогда не обращаются к одной и той же памяти в одно и то же время.

Идея заключается в том, что и потребитель, и производитель могут отслеживать положение хвоста / головы независимо друг от друга.

Рассмотрим следующий псевдокод:

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 отдельных мьютекса для уменьшения конкуренции.