Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 23
Текст из файла (страница 23)
Today we shall consider a new problem in the samemodel. The new problem is the implementation of an interesting programming languageprimitive, a kind of data object called an atomic object. Atomic objects have recently beenproposed as the basis for a general approach to solving problems in the asynchronous sharedmemory model. This approach can be thought of as \object-oriented" style of constructingasynchronous concurrent systems.The system architecture is the same as before (see Figure 10.1).interfacelineprocesssharedmemorycellFigure 10.1: shared memory systemBefore giving a formal denition of atomic objects, we give a simple example.11310.1.1 Example: Read-Write ObjectThe read-write object is somewhat similar to a shared read-write variable, but with separateinvocation and response actions. More specically, it has two types of input actions: read i,where i is a process, and write i (v), where i is a process and v a value to be written.
A read iis supposed to return a value. The \return" event is represented by a separate output actionwhich we call read-respondi(v). For uniformity, also give the write i a corresponding responseaction write-respondi . The write-respondi is merely an ack, whose meaning is that the write iaction is done.The separation of actions (which can be viewed as giving a ner atomicity) makes thiskind of object a little dierent from a shared read-write register. In particular, it permitsconcurrent access to the object from dierent users.The read-write object is one of the simplest useful objects. We can easily dene other,fancier objects for examplequeues (with insert and delete actions),read-modify-write objects (to be discussed later),snapshot objects (to be considered next),and more.
Each object has its own characteristic interface, with inputs being invocations ofoperations and outputs being responses.10.1.2 DenitionIn this section we give an elaborate denition of the requirements from an atomic object.First, recall the cyclic discipline for invocations and responses for the \mutual exclusionobject". Something similar is required from any atomic object: we dene a generalized notionof well-formedness at the interface. Here, this says that for each process i (whose connectionwith the external environment is called line i), the invocations and responses alternate,starting with an invocation. We stress that not everything needs to alternate in this way:only the invocations and responses on any particular line.
There can be concurrency amongthe invocations on dierent lines. We think of the object when it is used in combinationwith user programs that preserve (i.e., are not the rst to violate) this well-formednesscondition, and the rst requirement on an object implementation is that it also preservewell-formedness.Property 1: Preserves well-formedness114Also, as before, we make a restriction on when our processes can take steps. Namely, inwell-formed executions, process i is only permitted to take steps in between an invocationand a response at i (that is, while an invocation is active at i).The next correctness condition involves the correctness of the responses.
This correctnessis dened in terms of a related serial specication. A serial specication describes the correctresponses to a sequence of operation invocations, when they are executed sequentially (i.e,without concurrent invocations). For instance, for a read-write object having initial value 0,the correct sequences include the following (subscripts denote processes/line numbers).read1 read-respond1(0) write2 (8) write-respond2 read 1 read-respond1 (8)Usually, these sequences are specied by a simple state machine in which each operationcauses a change of state and a possible return value.
We remark that this serial specicationis now standard in theory of data types.So let S be a serial specication for a particular set of operation types (e.g., read, write,etc.). An atomic object corresponding to S has the same interface as S . In addition to thewell-formedness condition above, we require something about the contents of the sequences.Property 2: AtomicityWe want to say that any well-formed execution must \look like" a sequence in the serialspecication S . The way of saying this is a little complicated, since we want a conditionthat also makes sense for executions in which some of the operations don't return.
That is,even if for some of the lines i, the nal operation gets invoked and does not return, we wouldlike that the execution obey some rules. Specically, we require, for a (nite or innite)well-formed execution of the object, that it be possible to select the following.1. For each completed operation, a serialization point within the active interval.2. An arbitrary subset T of the incomplete operations (i.e., those having an invocationbut no response), such that for each operation in T we can select a serialization pointsometime after the invocation, and a response action.The points should be selected in a way such that if we move the invocation and responseactions for all the completed operations, and all the operations in T , so that they ank theirrespective serialization points (i.e., if we \shrink" the completed operations and all the operations in T to contain only their respective serialization points), then the resulting sequenceof invocations and responses is in S (i.e., is correct according to the serial specication).So, the atomicity condition essentially stipulates that an execution looks as if the operations that were completed (and some of the incomplete ones) were performed instantaneously115at some time in their intervals.
Figure 10.2 shows a few scenarios involving a two-processread-write object.(c)(a)write(8)process 1process 2write(8)write−respondTimereadreadread−respond(0)read−respond(8)(b)write(8)readwrite(8)write−respondreadread−respond(8)write(8)read(d)read−respond(0) readread−respond(8)(e)read−respond(0) read read−respond(0)Figure 10.2: possible executions of a read-write object with two processes.
The arrows represent serialization points. In the scenario (e), there are innitely many reads that return 0, andconsequently the incomplete write does not get a serialization point.Property 3: LivenessThis property is simple: we require that in every well-formed fair execution, every invocation receives a response. This rules out, for example, the \dead object" that never returnsresponses.Notice that here, we are using the underlying fairness notion for the model | i.e., thatprocesses continue to take steps when those are enabled. In this case, the statement ofProperty 2 could be simplied. The reason we have given the more complicated statementof Property 2 is that in the sequel, we shall consider non-fair executions of atomic objectimplementations.
This will be when we are discussing resiliency, and wait-freedom.5 Notethat Property 3 (so far) only makes sense in the particular model we are using, with processesto which it makes sense to be \fair".Discussion. Intuitively, we can say that an atomic object is a \concurrent version" of acorresponding serial specication. It is appropriate to ask what good is this concept. The5In the literature, wait-freedom is sometimes referred to as \wait-freeness".116important feature we get is that we can use an atomic object in modular construction of systems: suppose that we design a system to use instantaneous objects (e.g., read-write, queues,or something more interesting), but we don't actually have such instantaneous objects.
Ifwe have atomic versions of them, then we can \plug" those implementations in, and, as wewill later see, under certain circumstances, the resulting system \behaves the same", as faras a user can tell. We shall return to this discussion later.10.2 Atomic SnapshotsWe shall now see how can simple atomic objects be used to implement (seemingly) muchmore powerful objects. Specically, we'll see how to implement atomic snapshot object,using atomic registers. We follow the general ideas of Afek Attiya et al]. We start witha description of the the problem, and then give a simple solution that uses registers ofunbounded size. Finally, we rene the construction to work with bounded registers.10.2.1 Problem StatementAtomic snapshot object models an entire memory, divided into n words.
It has n update andn snap lines (see Figure 10.3). The update i(v) writes v into word i, and the snap returns thevector of all the latest values.As usual , the atomic version of this object has the same responses as if shrunk to a pointin the interval.update in linessnap in linesFigure 10.3: schematic interface of an atomic snapshot objectThe model of computation we assume is that of 1-writer n-reader atomic registers.10.2.2 Unbounded AlgorithmSuppose that each update writes into its register in a way such that each value can be veriedto be new. A simple way to do it is to attach a \sequence number" to each value whenever117a newer value is written, it is written with an incremented sequence number.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
