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. ```hint Sleep on a condition A thread that cannot proceed should sleep until another thread changes the state it is waiting on. Decide what it waits on, and what it must re-check after it wakes. ``` #### 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. ```hint Watch the lock's cache line Think about what every waiting thread does to the cache line that holds the lock flag, and how to wait while generating less traffic on it. ``` #### 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. ```hint Count the writers For each shared variable, ask which threads write it. The fewer writers a variable has, the weaker the atomic operation it needs. ``` #### 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. ### What a Strong Answer Covers - Correctness first, then optimization, with a clear statement of what each step gains and what it gives up. - A precise explanation of the C++ memory model as it applies to this code, not only which keywords to use. - Where each version allocates memory, and why allocation inside a critical section or on the hot path matters. - How the three versions would be benchmarked and compared, including with more threads than cores. ### Follow-up Questions - What container does `std::queue` use underneath by default, and what allocations happen on `push` compared with a `std::list`-backed queue? - How would you extend the lock-free design to several producers and several consumers, and what is the ABA problem? - What happens to the spin-lock version if the thread holding the lock is preempted, and how can that be mitigated? - How would a consumer of the lock-free queue wait efficiently when the queue is empty?