Hands-On Concurrency with Rust

An incorrect atomic queue

Before we build anything else, we're going to need a key data structure—a unbounded queue. In Chapter 5, Locks – Mutex, Condvar, Barriers, and RWLock, we discussed a bounded deque protected at either end by mutexes. We're in the business, now, of building synchronization and can't make use of the mutex approach. Our ambition is going to be to produce an unbounded first-in-first-out data structure that has no locks, never leaves an enqueuer or dequeuer deadlocked, and is linearizable to a sequential queue. It turns out there's a pretty straightforward data structure that achieves this aim; the Michael and Scott Queue, introduced in their 1995 paper Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue ...