Previous | Next --- Slide 16 of 31
Back to Lecture Thumbnails

Question: Why is there NO need for atomic head/tail pointer update in this example? See the lines:

q->tail = MOD_N(q->tail+1);
q->head = MOD_N(q->head+1);

I CANNOT see why a lack of atomicity will cause serious problem here. Because producer's updating tail will at most cause returning false in consumer, and consumer's updating head will at most cause returning false in producer, in which cases there won't be fatal error.


There is no need for atomicity here because before any modification to the data structure takes place, there is always a check that head does not equal tail. Since push only updates tail and pop only updates head, the two threads will never attempt to update the same index in the array.

One might ask: say we have a thread T0 that's trying to pop, it checks that head != tail, but before it gets to pop it gets switched out of its execution context and another thread T1 comes in and pops the very element that T0 was about to pop?

This will never happen in our case because it's a single reader and single writer situation. Therefore, we can be sure that after a thread checks head != tail, this condition will always remain true until the very same thread updates the head itself. No other thread will update head but the reader and similarly, other thread will update tail but the writer.


"single reader"-> at most one thread in pop -> No need to atomically update the q->head value.

"single writer"-> at most one thread in push -> No need to atomically update the q->tail value.


Because it is not possible that "tail" or "head" will be modified by concurrent two or more thread. "tail" is modified in "push", which only one thread call "push" function. Same reason for "head"