Is it strictly necessary to use mutex locks while accessing the buffers in producer-consumer problem?

Question

Below are the pseudo-code of the producer-consumer problem as given Operating System Concepts by Galvin, et. al.

We assume that the pool consists of n buffers, each capable of holding one item. The mutex binary semaphore provides mutual exclusion for accesses to the buffer pool and is initialized to the value 1.

 //initialization
 int n; 
 semaphore mutex = 1; 
 semaphore empty = n; 
 semaphore full = 0;

Below is the pseudo-code for the structure of the producer:

 while (true) 
{ 
   . . . 
  /* produce an item in next_produced */ 
  . . . 
  wait(empty); 
  wait(mutex); 
  . . . 
  /* add next produced to the buffer */ 
  . . . 
  signal(mutex); 
  signal(full); 
}

Below is the pseudo-code for the structure of the consumer:

 while (true) 
 { 
   wait(full); 
   wait(mutex); 
   . . . 
   /* remove an item from buffer to next_consumed */ 
   . . . 
   signal(mutex); 
   signal(empty); 
   . . . 
   /* consume the item in next consumed */ 
   . . . 
}

The above is as far as the text is concerned. Let me go a bit further and include the working of the buffer as well. Let char buffer[n] be a shared array between the two processes acting as the buffer. So we have:

/*Structure of the producer- elaborated by me*/
int i=0;
while (true) 
{ 
   . . . 
  /* produce an item in next_produced */ 
  . . . 
  wait(empty); 
  //wait(mutex); 
  . . . 
  buffer[i]=next_produced; 
  /* add next produced to the buffer */
  i=(i+1)%n; 
  . . . 
  //signal(mutex); 
  signal(full); 
}

/*Structure of the consumer elaborated by me*/
int i=0;
while (true) 
 { 
   wait(full); 
   //wait(mutex); 
   . . . 
   next_consumer=buffer[i]; 
   /* remove an item from buffer to next_consumed */ 
   i=(i+1)%n;
   . . . 
   //signal(mutex); 
   signal(empty); 
   . . . 
   /* consume the item in next_consumed */ 
   . . . 
}

Though the text uses mutex locks before accessing the buffers, (as per their logic, since the buffer is a shared item, it should be accessed in a mutually exclusive manner), I do not think that is strictly necessary to use mutex while accessing the buffer elements, because, the producer and the consumer though can access the buffer simultaneously, but I guess they can never access the same the location of the buffer array simultaneously. Since they cannot access the same location simultaneously, there is no possibility of race condition...

This is what I feel. Please correct me if I am wrong. Also please point me to the portion where I made the mistake. Thank you.

Answer 1

After digging the web for days, I think I've finally found the answer!

It has to do with "memory consistency", and as @jom-rogers noted, multiple readers/writers.

The solution was first offered by Dijkstra [1], who first introduces the solution without the mutex. Then he says:

Particularly in the case of buffer implementation by means of chaining it is not unusual that the operations "add portion to buffer" and "take portion from buffer" -operating as they are on the same clerical status information of the buffer- could interfere with each other in a most undesirable fashion.

Honestly, I don't understand the problem. However, to solve the problem, he adds the mutex to the solution. Then, he goes on to say (emphasis mine):

Remark. The presence of the binary semaphore "buffer manipulation" has another consequence. We have given the program for one producer and one consumer, but now the extension to more producers and/or more consumers is straightforward: the same semaphore sees to it that two or more additions of new portions will never get mixed up and the same applies to two or more takings of a portion by different consumers.

So, one aspect of the solution is to handle multiple producers and consumers.

But I also found the following excerpt in a thesis [2] (emphasis mine):

One optimization of the previous solution was found by Lamport in [6], which proves that if the underlying Reads and Writes to the head and the tail satisfy a sequentially consistent memory model, then the prior algorithm in Listing 2.1 can remove the mutex.lock() and mutex.unlock() statements while maintaining a correct algorithm. Most all systems satisfy a sequentially consistent memory model, and that means that the mutual exclusion in the prior section which prevented simultaneous pushes and pops to occur is actually often unnecessary. This change will allow the queue to make progress on multiple cores at the same time which in theory should improve performance. [...] but there are some competing effects which complicate this analysis. In order to maximize system performance, modern AMD and Intel CPUs may reorder read and write operations on different cores.

So, as he says, if some memory consistency assumptions are correct, the mutex can be removed. I checked the original paper by Lamport [3] that he cites, but the notation was too difficult for me to understand.

[1] Dijkstra, Edsger W. "Cooperating sequential processes." The origin of concurrent programming. Springer, New York, NY, 1968. 65-138.

[2] Frank, Reginald Austin. Designing a High Throughput Bounded Multi-Producer, Multi-Consumer Queue. Diss. 2021.

[3]Lamport, Leslie. "Specifying concurrent program modules." ACM Transactions on Programming Languages and Systems (TOPLAS) 5.2 (1983): 190-222.