I got this question in a 2017 Wells white-board coding interview, and discussed with my friend Shanyou. We hoped to avoid locks and also avoid other synchronization devices such as volatile, atomic variables..
Q1: only a single producer thread and a single consumer thread and no other threads.
I put together a java implementation that can enqueue without synchronization, most of the time, until See https://github.com/tiger40490/repo1/blob/jProj/java/com/wells/UnboundedQFor1Producer1Consumer.java
Q1b: Is it possible to avoid synchronization completely, i.e. single-threaded mode?
A: No. Consumer thread would have absolutely NO idea whatsoever how close it is to the producer end. No. We need a memory barrier at the very least.
Q2: what if there are multiple producer/consumer threads?
I believe we can use 2 separate locks for the two ends, rather than a global lock. This is more efficient but invites the tricky question “how to detect when the two ends meet“. I am not sure. I just hope the locks enforce a memory barrier.
Alternatively, we could use CAS on both ends.