Chapter 9 Modelling III: Asynchronous Shared Memory Model

In this chapter, we give a formal model for asynchronous shared memory systems. This model is presented in terms of the general I/O automaton model for asynchronous systems that we defined in Chapter 8.

A shared memory system consists of a collection of communicating processes, as does a network system. But this time, instead of sending and receiving messages over communication channels, the processes perform instantaneous operations on shared variables.

9.1 Shared Memory Systems

Informally speaking, an asynchronous shared memory system consists of a finite collection of processes interacting with each other by means of a finite collection of shared variables. The variables are used only for communication among the processes in the system. However, so that the rest of the world can interact with the shared memory system, we also assume that each process has a port, on which it can interact with the outside world using input and output actions. The interactions are depicted in Figure 9.1.

We model a shared memory system using I/O automata, in fact, using just a single I/O automaton with its external interface consisting of the input and output actions on all the ports. It might seem more natural to use several automata, one per process and one per shared variable. However, that leads to some complications we would rather avoid in this book. For instance, if each process and each variable were an I/O automaton and we combined them using ordinary I/O automaton composition, then we would get a system in which an operation by a process i on a shared variable x would be modelled by a pair of events—an invocation that is an output of process i and an input of variable x, followed by a response that is an output of variable x and an input of process i. But then the system would also have some executions in which these pairs of events are split. For instance, several operations could be invoked before the first of them returns. This kind of behavior does not occur in the shared memory systems that we are trying to model.

Figure 9.1: An asynchronous shared memory system.

One way out of this difficulty would be to consider a restricted subset of all the possible executions—those in which invocations and corresponding responses occur consecutively. A second way out would be to model only the processes as I/O automata, but to model the shared variables as state machines of a different kind (with invocations and responses combined into single events); in this case, a new composition operation would have to be defined to allow combination of the process and variable automata into one I/O automaton. Since these approaches introduce their own complexities—restricted subsets of the set of executions, pairs of events, a new kind of state machine, or a new operation—we sidestep all these issues by just modelling the entire system as one big I/O automaton A. We capture the process and variable structure within automaton A by means of some locality restrictions on the events.

As in the synchronous network model, we assume that the processes in the system are indexed by 1,…, n. Suppose that each process i has an associated set of states, states_i, among which some are designated as start states, start_i. Also suppose that each shared variable x in the system has an associated set of values, values_x, among which some are designated as the initial values, initial_x. Then each state in states(A) (the set of states of the system automaton A) consists of a state in states_i for each process i, plus a value in values_x for each shared variable x. Each state in start(A) consists of a state in start_i for each process i, plus a value in initial_x for each shared variable x.

We assume that each action in acts(A) is associated with one of the processes. In addition, some of the internal actions in int(A) may be associated with a shared variable. The input actions and output actions associated with process i are used for interaction between process i and the outside world; we say they occur on port i. The internal actions of process i that do not have an associated shared variable are used for local computation, while the internal actions of i that are associated with shared variable x are used for performing operations on x.

The set trans(A) of transitions has some locality restrictions, which model the process and shared variable structure of the system. First, consider an action π that is associated with process i but with no variable; as we noted above, π is used for local computation. Then only the state of i can be involved in any π step. That is, the set of π transitions can be generated from some set of triples of the form (s, π, s′), where s, s′ ∈ states_i, by attaching any combination of states for the other processes and values for the shared variables to both s and s′ (the same combination to both).

On the other hand, consider an action π that is associated with both a process i and a variable x; as we noted above, π is used by i to perform an operation on x. Then only the state of i and the value of x can be involved in any π step. That is, the set of π transitions can be generated from some set of triples of the form ((s, v), π, (s′, υ′)), where s, s′ ∈ states_i and v, υ′ ∈ values_x, by attaching any combination of states for the other processes and values for the other shared variables. There is a technicality: if π is associated with process i and variable x, then whether or not π is enabled should depend only on the state of process i, although the resulting changes may also depend on the value of x. That is, if π is enabled when the state of i is s and the value of x is v, then π is also enabled when the state of i is s and when x has any other value υ′.

The task partition tasks(A) must be consistent with the process structure: that is, each equivalence class (task) should include locally controlled actions of only one process. In many cases that we will consider, there will be exactly one task per process—this makes sense, for example, if each process is a sequential program. In this case, the standard definition of fairness for I/O automata, given in Section 8.3, says that each process gets infinitely many chances to take steps. In the more general case, where there can be several tasks per process, the fairness definition says that each task gets infinitely many chances to take steps.

Example 9.1.1 Shared memory system

Let V be a fixed value set. Consider a shared memory system A consisting of n processes, numbered 1,…, n, and a single shared variable x with values in V U {unknown}, initially unknown. The inputs are of the form init(v)_i, where υ ∈ V and i is a process index. The outputs are of the form decide(v)_i. The internal actions are of the form access_i. All the actions with subscript i are associated with process i, and in addition, the access actions are associated with variable x.

After process i receives an init(v)_i input, it accesses x. If it finds x = unknown, then it writes its value V into x and decides v. If it finds x = ω, where ω ∈ V, then it does not write anything into x, but decides w.

Formally, each set states_i consists of local variables.

States of i:

The transitions are

Transitions of i:

There is one task per process, which contains all the access and decide actions for that process.

It is not hard to see that in every fair execution α of A, any process that receives an init input eventually performs a decide output. Moreover, every execution (fair or not, and with any number of init events occurring anywhere) satisfies the “agreement property” that no two processes decide on different values, and the “validity property” that every decision value is the initial value of some process.

We can formulate these correctness claims in terms of trace properties, according to the definition in Section 8.5.2. For example, let P be the trace property such that sig(P) = extsig(A) and traces(P) is the set of sequences β of actions in acts(P) satisfying the following conditions:

1. For any i, if exactly one init_i event appears in β, then exactly one decide_i event appears in β.
2. For any i, if no init_i event appears in β, then no decide_i event appears in β.
3. (Agreement) If decide(v)_i and decide(w)_j both appear in β, then v = w.
4. (Validity) If a decide(v)_i event appears in β, then some init(v)_j event (for the same v) appears in β.

It is then possible to show that fairtraces(A) traces(P). The proof is left for an exercise.

9.2 Environment Model

Sometimes it is useful to model the environment of a system as an automaton also. This provides an easy way to describe assumptions about the environment’s behavior. For instance, in Example 9.1.1, we might like to specify that the environment submits exactly one init_i input for each i, or maybe at least one for each i. For shared memory systems that arise in practice, the environment can often be described as a collection of independent user automata, one per port.

Example 9.2.1 Environment model

We describe an environment for the shared memory system A described in Example 9.1.1. The environment is a single I/O automaton that is composed (using the composition operation for I/O automata defined in Section 8.2.1) of one user automaton, U_i, for each process index i. U_i’s code is as follows.

Thus, U_i initially performs an init_i action, then waits for a decision. If the shared memory system produces a decision without a preceding init_i or produces two decisions, then U_i sets an error flag, which allows it to output any number of inits at any time. (The presence of the dummy_i action allows it also to choose not to perform outputs.) Of course, the given shared memory system is not supposed to cause such errors.

The composition of the shared memory system A with all the U_i, 1 ≤ i ≤ n, is depicted in Figure 9.2. This composition is quite well-behaved: in any fair execution of the composition, there is exactly one init_i event and exactly one decide_i event for each i. Moreover, the decide events satisfy appropriate agreement and validity conditions.

More formally, let Q be the trace property such that sig(Q) consists of outputs init(v)_i and decide(v)_i for all i and v, and such that traces(Q) is the set of sequences β of actions in acts(Q) satisfying the following conditions:

Figure 9.2: Users and shared memory system.

1. For any i, β contains exactly one init_i event followed by exactly one decide_i event.
2. (Agreement) If decide(v)_i and decide(w)_j both appear in β, then v = w.
3. (Validity) If a decide(v)_i event appears in β, then some init(v)_j event (for the same v) appears in β.

Then it is possible to show that fairtraces(A Π_1≤i≤n U_i) traces(Q). The proof is left for an exercise.

9.3 Indistinguishable States

We define a notion of indistinguishability that will be useful in some impossibility proofs in Chapter 10.

Consider an n-process shared memory system A and a collection of users U_i, 1 ≤ i ≤ n. Let s and s′ be two states of the composed system A Π_1≤i≤n U_i. Then we say that s and s′ are indistinguishable to process i if the state of process i, the state of U_i, and the values of all the shared variables are the same in s and s′. We write s ~i s′ to indicate that s and s′ are indistinguishable to i.

9.4 Shared Variable Types

In the general definition we have given for shared memory systems, we have not restricted the types of operations a process may perform on a shared variable when it accesses the variable. That is, when a process i accesses a variable x, we have allowed arbitrary changes to the state of i and the value of x to occur, depending in arbitrary ways on the previous state of i and value of x. But in practice, shared variables normally support only a fixed set of operations, such as read and write operations, or a combined read-modify-write operation. In this subsection, we define the notion of a variable type, and say what it means for a shared memory system to observe type restrictions.¹

A variable type consists of

• a set V of values
• an initial value v₀ ∈ V
• a set of invocations
• a set of responses
• a function f: invocations V → responses V

The function f says what happens when a given invocation arrives at the variable and the variable has a given value; f describes the new value the variable takes on and the response that is returned. Note that a variable type is not an I/O automaton, even though some of its components look similar to I/O automaton components. Most importantly, in a variable type, the invocations and responses are thought of as occurring together as part of one function application, whereasin the I/O automaton model, inputs and outputs are separate actions (and other actions may occur between them).

Suppose we have a shared memory system A. What does it mean to say that shared variable x in system A is of a given variable type? It means, first, that the set values_x must be equal to the set V of values of the type, and that the set initial_x of initial values for x consists of just one element, v₀. Moreover, all the transitions involving x must be describable in terms of the invocations and responses allowed by the type. Namely, each action involving x must be associated with some invocation a of the variable type. Moreover, for each process i and each invocation a, the set of transitions involving i and a must be describable in the following form, where p is some predicate on states_i and g is some relation, g states_i responses x states_i. (In the code, we use the notation state_i to denote the state of process i.)

This code means that the determination that variable x is to be accessed by process i using invocation a is made according to predicate p (which just involves the state of i). If this access is to be performed, then the function f for the variable type is applied to the invocation a and the value of variable x to determine a response b and a new value for x. The response b is then used by process i to update its state, in some way allowed by relation g.

In the descriptions of shared memory algorithms in this book, transitions involving accesses to shared variables of particular types will not be written explicitly in terms of predicates p and relations g as above. However, theoretically, they could all be expressed in this style.

Example 9.4.1 Read/write shared variables (registers)

The most frequently used variable type in multiprocessors is one supporting only read and write operations. A variable of this type is known as a read/write variable, or a read/write register, or just a register.

A read/write register comes equipped with an arbitrary set V of values and an arbitrary initial value v₀ ∈ V. Its invocations are readand write(v), υ ∈ V. Its responses are υ ∈ V and ack.² Its function f is defined by: f(read, v) = (v, v) and f(write(v), ω) = (ack, v).

Note that variable x in the system of Example 9.1.1 cannot be described as a read/write register, because there is no way that the given accesses could be rewritten in the form given above. It is possible to rewrite the algorithm so that x is a register, for example, by separating each access into a read and a write step. The resulting process code might look as follows. The status value access is replaced by two new status values, read and write.

The task partition again groups together all locally controlled actions of process i. Although this code is not explicitly written in terms of a predicate p and a relation g, note that it could easily be rewritten in this way. For instance, for the read_i action, the predicate p is simply “status = read,” and the relation g is just the set of triples (s, b, s′) ∈ states_i x (VU {unknown}) x states_i such that s′ is obtained from s by the code:

For the write(v)_i action, the predicate p is simply “status = write and v = input,” and the relation g is just the set of triples (s, b, s′) ∈ states_i x (V U {unknown}) x states_i such that s′ is obtained from s by the code:

So x is a read/write shared variable.

Notice that when we rewrite the algorithm in this way, the agreement condition mentioned in Example 9.1.1 is no longer guaranteed.

Example 9.4.2 Read-modify-write shared variables

Another important variable type allows the powerful read-modify-write operation. In one instantaneous read-modify-write operation on a shared variable x, a process i can do all of the following:

1. Read x.
2. Carry out some computation, possibly using the value of x, that modifies the state of i and determines a new value for x.
3. Write the new value to x.

It is not easy to implement a general read-modify-write operation using the usual primitives provided by multiprocessors. The shared memory model requires not only that each access to the variable be indivisible, but also that all the processes should get fair turns to perform such accesses. Implementing this fairness requires some sort of low-level arbitration mechanism.

As we have described it, it is not obvious that read-modify-write variables can be modelled in terms of variable types: the read-modify-write operation appears to involve two accesses to the variable rather than just one as required. One way to do this is to have a process that wishes to access the variable determine, based on its state, a function h to use as an invocation of the variable. The function h provides the information from the process′s state that is needed to determine the transition, expressed in the form of a function to apply to the variable. The effect of the function h on the variable when it has value v is to change the variable’s value to h(v) and return the previous value v to the process. The process can then change its state, based on its old state and v.

Formally, a read-modify-write variable can have any set V of values and any v₀ → V as an initial value. Its invocations are all the functions h, where h: V → V. Its responses are υ ∈ V. Its function f is defined by f(h, v) = (v, h(v)). That is, it responds with the prior value and updates its value based on the submitted function.

For instance, in Example 9.1.1, the function submitted by a process to the variable is of the form h_v, where

The particular h_v submitted by a process uses the process′s input as the value of v. A return value of unknown causes output to be set to the value of input, while a return value of υ ∈ V causes output to be set to v. In either case, status is appropriately modified.

Example 9.4.3 Other variable types

Many of the variable types used in shared memory multiprocessors include restricted forms of read-modify-write, plus basic operations such as read and write. Some popular restricted form of read-modify-write include compare-and-swap, swap, test-and-set, and fetch-and-add operations. These operations are defined as follows. Fix a set V and initial value v₀.

The invocations for compare-and-swap operations are of the form compare-and-swap(u, v), u, υ ∈ V, and the responses are elements of V. The function f is defined for compare-and-swap invocations by

That is, if the variable’s value is equal to the first argument, u, then the operation resets it to the second argument, v; otherwise, the operation does not change the value of the variable. In either case, the original value of the variable is returned.

The invocations for swap operations are of the form swap(u), u ∈ V, and the responses are elements of V. The function f is defined for swap invocations by

That is, the operation writes the input value u into the variable and returns the original variable value v.

The invocations for test-and-set operations are of the form test-and-set, and the responses are elements of V. The function f is defined for test-and-set by

That is, the operation writes 1 into the variable and returns the original variable value v. (We assume that 1 ∈ V.)

Finally, the invocations for fetch-and-add operations are of the form fetch-and-add(u), u ∈ V, and the responses are elements of V. The function f is defined for fetch-and-add by

That is, the operation adds the input value u to the variable value v and returns the original value v. (This operation requires that the set V support a notion of addition.)

We can define the executions of a variable type in a natural way, as finite sequences v₀, a₁, b₁, v₁, a₂, b₂, v₂,…, v_r or infinite sequences v₀, a₁, b₁, v₁, a₂, b₂, v₂,…. Here, the υ′s are values in V, v₀ is the initial value of the variable type, the a’s are invocations, the b’s are responses, and the quadruples v_k, a_k+1, b_k+1, v_k+1 satisfy the function of the type. (That is, (b_k+1, v_k+1) = f(a_k+1, v_k).) Also, the traces of a type are the sequences of a’s and b’s that are derived from executions of the type.