The thread-safe stack

One of the simplest data structures from the point of view of concurrency is the stack. All operations on the stack deal with the top element, so there is (conceptually, at least) a single location that needs to be guarded against races.

The C++ standard library offers us the std::stack container, so it makes a good starting point. All C++ containers, including the stack, offer the weak thread-safety guarantee: a read-only container can be safely accessed by many threads. In other words, any number of threads can call any const methods at the same time as long as no thread calls any non-const methods. While this sounds easy, almost simplistic, there is a subtle point here: there must be some kind of synchronization event accompanied by a memory barrier between the last modification of the object and the portion of the program where it is considered read-only. In other words, write access is not really done until all threads execute a memory barrier: the writer...