If you stick with the following constraints:
- Only one thread is allowed to modify the head pointer at any time
- Only one thread is allowed to modify the tail pointer at any time
- Dequeue-on-empty gives a return value indicating nothing was done
- Enqueue-on-full gives a return value indicating nothing was done
- You don't keep any count of how many values are stored in the queue.
- You 'waste' one index in the array that will never be used, so that you can tell when the array is full or empty without having to keep count.
It is possible to implement a circular array/queue.
The enqueuing thread owns the tail pointer. The dequeueing thread owns the head pointer. Except for one condition, these two threads don't share any state so far, and so there are no problems.
That condition is testing for emptyness or fullness.
Consider empty to mean that head == tail; Consider full to mean tail == head - 1 modulo array size. Enqueue has to check to see if the queue is full, dequeue has to check to see if the queue is empty. You need to waste one index in the array to detect the difference between full and empty - if you enqueued into that last bucket, then full would be head == tail
and empty would be head == tail
and now you deadlock - you think you're empty and full at the same time, so no work would get done.
In performing these checks, its possible that one value could be updated while being compared. However since these two values are monotonically increasing, there is no correctness problem:
- If, in the dequeue method, the head == tail computes to be true during the comparison, but tail moves forward just afterward, no problem - you thought the array was empty when it actually wasn't, but no big deal, you'll just return false from the dequeue method and try again.
- If, in the enqueue method, the tail == head - 1 computes to be true, but just after so the head increments, then you'll think the array was full when it really wasn't, but again, no big deal, you'll just return false from enqueue and try again.
This is the design used behind the implementation I found in Dr. Dobb's years ago, and it has served me well:
http://www.drdobbs.com/parallel/lock-free-queues/208801974