Up till this point in the book, we've avoided dipping into the formal terms for specifying concurrent systems, because while they are very useful for discussing ideas and reasoning, they can be difficult to learn absent some context. Now that we have context, it's time.
How do we decide whether a concurrent algorithm is correct? How, if we're game for the algorithm, do we analyze an implementation and reason about it's correctness? To this point, we've used techniques to demonstrate fitness-for-purpose of an implementation through randomized and repeat testing as well as simulation, in the case of helgrind. We will continue to do so. In fact, if that's all we did, demonstrating fitness-for-purpose of implementations, then we'd be in pretty good condition. The working programmer will find themselves inventing more often than not, taking an algorithm and adapting it—as was seen in the previous chapter's discussion of hopper—to fit some novel domain. It's easy enough to do this and not notice.
What we're searching for, when we sit down to reason about the systems we're constructing, is a unifying concept that'll separate the workable ideas from the goofs. That concept for us, here, in the design and construction of concurrent data structures, is linearizability. What we're looking to build are objects that, paraphrasing Nancy Lynch, make it seem like operations on them occur one at a time, in some sequential order, consistent with the order of operations and responses. Lynch's Distributed Algorithms is concerned with the behavior of distributed systems, but I've always thought that her explanation of what she refers to as atomic objects is brilliantly concise.
The notion of linearizability was introduced in Axioms for Concurrent Objects by Herlihy and Wing in 1986. Their definition is a bit more involved, done up in terms of histories—a finite sequence of operation invocation and response events—and specifications, which are, to be quick about it, a set of axiomatic pre and post conditions that hold on, the object in terms of the operations defined on it.
Let the result of an operation be called res(op) and the application or invocation of an operation be called inv(op), and distinguish operations by some extra identifier. op_1 is distinct from op_2 but the identifier has no bearing on their ordering; it's just a name. A history H is a partial order over operations so that op_0 < op_1 if res(op_0) happens before inv(op_1) in H. Operations that have no ordering according to < are concurrent in the history. A history H is sequential if all of its operations are ordered with regard to <. Now, the history H is linearizable if it can be adjusted by adding zero or more operations into the history to make some other history H' so that:
- H' is composed only of invocations and responses and are equivalent to some legal, sequential history S
- The ordering operation of H' is an inclusive subset of the ordering of S.
Phew! An object is linearizable if you can record the order of the operations done to it, fiddle with them some, and find an equivalent sequential application of operations on the same object. We've actually done linearizabilty analysis in previous chapters, I just didn't call it out as such. Let's keep on with Herlihy and Wing and take a look at their examples of linearizable vs. unlinearizable histories. Here's a history on a familiar queue:
A: Enq(x) 0 B: Enq(y) 1 B: Ok(()) 2 A: Ok(()) 3 B: Deq() 4 B: Ok(x) 5 A: Deq() 6 A: Ok(y) 7 A: Enq(z) 8
We have two threads, A and B, performing the operations enq(val: T) -> Result((), Error) and deq() -> Result(T, Error), in pseudo-Rust types. This history is in fact linearizable and is equivalent to:
A: Enq(x) 0 A: Ok(()) 3 B: Enq(y) 1 B: Ok(()) 2 B: Deq() 4 B: Ok(x) 5 A: Deq() 6 A: Ok(y) 7 A: Enq(z) 8 A: Ok(())
Notice that the last operation does not exist in the original history. It's possible for a history to be linearizable, as Herlihy and Wing note it, even if an operation takes effect before its response. For example:
A: Enq(x) 0 B: Deq() 1 C: Ok(x) 2
This is equivalent to the sequential history:
A: Enq(x) 0 A: Ok(()) B: Deq() 1 B: Ok(x) 2
This history is not linearizable:
A: Enq(x) 0 A: Ok(()) 1 B: Enq(y) 2 B: Ok(()) 3 A: Deq() 4 A: Ok(y) 5
The culprit in this case is the violation of the queue's ordering. In sequential history, the dequeue would receive x and not y.
That's it. When we talk about a structure being linearizable, what we're really asking is, can any list of valid operations against the structure be shuffled around or added to in such a way that the list is indistinguishable from a sequential history? Each of the synchronization tools we looked at in the last chapter were used to force linearizability by carefully sequencing the ordering of operations across threads. At a different level, these tools also manipulated the ordering of memory loads and stores. Controlling this ordering directly, while also controlling the order of operations on structures, will consume the remainder of this chapter.