Thread-Safe Producer-Consumer Queue: Mutex, Then Spin Lock, Then Lock-Free

Implement a thread-safe queue through which producer threads hand work items to consumer threads, then make it progressively faster:

1. a version protected by a mutex;
2. the same queue with the mutex replaced by a spin lock;
3. a lock-free version built on atomics, with an explicit memory order on every atomic operation.

The discussion is in C++. Expect questions on memory ordering, on the standard containers you use (such as std::queue and std::list), on how those containers are implemented internally, and on where memory is allocated.

Clarifying Questions

• How many producers and how many consumers are there: exactly one of each, or several of each?
• Is the queue bounded? If so, what should a producer do when it is full: block, fail, or overwrite?
• Should pop block until an item arrives, or return immediately when the queue is empty?
• What is the item type, and is it cheap to move?
• How should the queue shut down, so that blocked threads wake up and exit?

Part 1 — Mutex-based queue

Implement push and pop protected by a std::mutex. A consumer that finds the queue empty must wait without burning CPU, and no item may ever be lost.

What This Part Should Cover

• A correct critical section: every read and write of shared state happens under the lock.
• Waiting and waking: no lost wake-ups, and correct handling of spurious wake-ups.
• Capacity and shutdown behavior that matches the clarified requirements.

Part 2 — Replace the mutex with a spin lock

Implement a spin lock on top of std::atomic and use it instead of the mutex. Explain when this is faster than the mutex version and when it is slower.

What This Part Should Cover

• A spin lock whose acquire and release carry the right memory ordering.
• Reducing contention and wasted work while spinning.
• The conditions under which spinning beats sleeping, the failure mode when the lock holder is descheduled, and what happens to a blocking pop once there is no mutex to pair a sleep with.

Part 3 — Lock-free queue and memory ordering

Remove the lock entirely. Implement a lock-free queue for the producer and consumer topology you clarified, and justify the memory order of every atomic load and store.

What This Part Should Cover

• A correct publish and consume protocol: a consumer never reads an item before the producer has finished writing it, and a producer never overwrites a slot the consumer is still reading.
• A justified choice between acquire/release, relaxed and sequentially consistent operations.
• Hardware effects such as false sharing, and the extra problems (ABA, memory reclamation) that appear with several producers or consumers.