Foundations of shared memory

This chapter begins our study of the foundations of concurrent computation by examining its most basic primitive, the read–write register. A register is a single location of shared memory. We characterize a register by the values it can store, the number of threads that can access it and what operations they can do, and the properties it guarantees. Starting from a one-bit register that supports only a single reader and a single writer, and guarantees the values read only if the read does not overlap a write, we present a series of constructions of increasingly powerful registers, culminating in an arbitrary-sized atomic multi-reader, multi-writer register. We also show how to use atomic registers to implement an atomic snapshot object, which can read multiple registers atomically. Although most of the algorithms presented in this chapter are impractical for real systems, they illustrate useful techniques for designing and reasoning about concurrent systems.