Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 37

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 37)

Since i completes before j begins, the maximum(timestamp index )pair that j sees is at least as great as the maximum one that i sees.First suppose that j does not see its own process with the maximum pair. In this case,j chooses a new timestamp that is strictly larger than the maximum timestamp it sees, sostrictly larger than the maximum timestamp that i sees. Now, i gets ordered right after thewrite whose value it gets, which is by denition the maximum pair write that it sees. Sincethis pair has a smaller timestamp than that of j , it must be that i is ordered before j .On the other hand, suppose that j sees its own process with the maximum pair.

In thiscase, j chooses the same timestamp that it sees. The resulting pair is either greater than orequal to the maximum pair that i sees. If it is greater, then as above, i is ordered before j .If it is equal, then the explicit tie-breaking rule for the same pair implies that write j getsordered by after the write whose value i gets, and hence after the read by i.

This againimplies that i gets ordered before j .Case 4: write i, read j . Since i completes before j begins, j sees a timestamp for i'sprocess that is at least as great as that of operation i, and hence the value that j returnscomes from a write operation that has at least as great a (timestamp index ) pair as does i.So again i is ordered before j .This sort of case analysis is useful for other read-write register algorithms. Before we conclude the discussion on implementing multi-writer registers from single-writer registers, weremark that this problem has a rich history of of complicated/incorrect algorithms, includingpapers by Peterson and Burns, by Schaer, and by Li, Tromp and Vitanyi.15.2 Algorithms in the Read-Modify-Write ModelIn this section we consider shared memory with a dierent memory access primitive, calledread-modify-write.

Our model is the instantaneous shared memory model, only now thevariables are accessible by a more powerful operation. Intuitively, the idea is that a processshould be able, in one instantaneous step, to access a shared variable, to use the variable'svalue and the process' state to determine the new value for the variable, and the new processstate. We can formulate this in the invocation-response style by using apply (f ) to describethe information needed to update the variable, and the old value v comes back as a response(cf.

Homework 5). The response value can be used to an update the state, since input tothe process can trigger an arbitrary state change.182In its full generality, this is a very powerful type of shared memory, since it allowsarbitrary computation based on the state and shared memory values. It is not exactly clearhow this would be implemented { remember that the basic model implies fair turns to allthe processes, which means fair access to the shared memory. So it seems that in this modelwe are implicitly assuming some low-level arbitration mechanism to manage access to thesevariables. Still, we might be able to implement the fair access with high probability | ifaccesses are fast, for example, then interference is unlikely, and by repeated retry, maybewith some backo mechanism, we would eventually gain access to the variable.In what follows, we shall consider various problems in this model, including consensus,mutual exclusion, and other resource allocation problems.15.2.1 ConsensusIt is very easy to implement wait-free consensus using a single read-modify-write sharedvariable as follows.

The variable starts out with the value \undened". All processes accessthe variable if a process sees \undened", it changes the value to its own initial value, anddecides on this value. If a process sees 0 or 1, it does not change the value written there,but instead accepts the written value as the decision value. It is easy to verify correctnessand wait-freedom for this scheme.Let us formulate the idea using the apply (f ) style. Each process uses f0 or f1, dependingon its initial value, where8<fb(x) = : b if x = undenedx otherwiseAn input (i.e., return value) of \undened" causes decision to be set to the initial value, andan input of b causes it to be set to b.Another style for writing this algorithm is describing ow of control, with explicit bracketsindicating the beginning and ending of steps (involving the shared memory and the localstate).

Since arbitrarily complicated computations can be done in one step, there can bemany steps of code within one pair of brackets. There shouldn't be nonterminating loops,however, since a step must always end. The code is given in this style in Figure 15.1, and inthe precondition-eect style in Figure 15.2.In a result by Herlihy, it is proven that it is impossible to obtain a wait-free implementation of atomic read-modify-write objects in the instantaneous shared memory model, wherethe memory is read-write. This can now be seen easily as follows. If we could solve wait-freeconsensus in this model, then by using transitivity, applied to the simple solution above forthe read-modify-write model and the claimed implementation of read-modify-write objects,183init i (b)value blockif x = undened thenxbdecision belse decision xunlockdecide i(d)Figure 15.1: Consensus in the lock-unlock memory stylewe could solve wait-free consensus in the instantaneous read-write model, which we have already shown to be impossible.

Also, a similar argument implies that we can't get a wait-freeimplementation of atomic read-modify-write objects in the atomic read-write object model.15.2.2 Mutual ExclusionConsider the mutual exclusion problem with the more powerful read-modify-write memory.In some sense, this seems almost paradoxical: it sounds as if we're assuming a solution toa very similar problem { fair exclusive access to a shared variable { in order to get fairexclusive access to the critical region. This seems likely to make the problem trivial. Andindeed, it does simplify things considerably, but not completely.

In particular, we shall seesome nontrivial lower bounds.Deadlock-FreedomRecall that for read-write registers, we needed n variables to guarantee only the weak properties of mutual exclusion and deadlock-freedom. To see how dierent read-modify-write modelis from read-write, consider the trivial 1-variable algorithm in Figure 15.3. It is straightforward to see that the algorithm guarantees both mutual exclusion and deadlock-freedom.184State:pc , with values finit access decide donegvaluedecisionActions:init i (b)Eect: value bpc accessaccess iPrecondition: pc = accessEect: if x = undened thenx valuedecision valueelse decision xpc decidedecide i(d)Precondition: pc = decide , and decision = dEect: pc doneFigure 15.2: Consensus algorithm in the precondition-eect language185Shared variables: shared variable v, values f0 1g, initially 0Local variables: (for process i) pc, values in fR T 1 T 2 C E 1 E 2g, initially RCode for process i:try iEect: pc T 1test iPrecondition: pc = T 1Eect: if v = 0 thenv1pc T 2crit iPrecondition: pc = T 2Eect: pc Cexit iEect: pc E 1return iPrecondition: pc = E 1Eect: v 0pc E 2rem iPrecondition: pc = E 2Eect: pc RFigure 15.3: Mutual exclusion algorithm for the read-modify-write model186Bounded BypassThe simple algorithm of Figure 15.3 does not guarantee any fairness.

But we could evenget FIFO order (based on the rst locally controlled step of a process in the trying region),e.g., by maintaining a queue of process indices in the shared variable. An entering processadds itself to the end of the queue when a process is at the beginning of the queue, it cango critical, and when it exits, it deletes itself from the queue. This is simple, fast, and onlyuses one variable, but it is space-consuming: there are more than n! dierent queues of atmost n indices, and so the variable would need to be able to assume more than n! dierentvalues, i.e., !(n log n) bits. One might try to cut down the size of the shared variable. Theinteresting question is how many states we need in order to guarantee fairness.

Can we doit in constant number of values? Linear?We can achieve fairness with n2 values (2 log n bits) by keeping only two numbers inthe (single) shared variable: the next \ticket" to be given out, and the number of the\ticket" that has permission to enter the critical region. (This can be viewed as a distributedimplementation of the queue from the previous algorithm.) Initially, the value of the sharedvariable is (1 1). When a process enters, it \takes a ticket" (i.e., copies and increments therst component). If a process' ticket is equal to the second component, it goes to criticalregion. When a process exits, it increments the second component.

This algorithm is alsoFIFO (based on the rst non-input step in trying region). We can allow the tickets to beincremented mod n, with a total of n2 values.The obvious question now is whether we can do better. The following theorem givesthe answer for the case of bounded bypass (which is a stronger requirement than lockoutfreedom).Theorem 2 Let A be an n-process mutual exclusion algorithm with deadlock-freedom andbounded bypass, using a single read-modify-write shared variable.

Then the number of distinctvalues the variable can take on is at least n.Proof: By contradiction: we shall construct an execution in which some process will bebypassed arbitrarily (but nitely) many times. We start by dening a sequence of niteexecutions, where each execution is an extension of the previous one, as follows. The rstexecution 1 is obtained by letting process p1 run alone from the start state until it enters C .In the second execution 2, after 1 we let p2 enter the trying region and take one non-inputstep. (Obviously, p2 remains in the trying region.) And i, for 3 i n, is dened bystarting after the end of i;1, then letting pi enter the trying region and take one non-inputstep.Dene vi to be the value of the shared variable just after i, 1 i n.

We rst claimthat vi 6= vj for i 6= j . For assume the contrary, i.e., that vi = vj , and without loss of187generality, assume i < j . Then the state after i looks like the state after j to p1 p2 : : : pi,since the value of the shared variable and all these processes' states are the same in both.Now, there is a fair continuation of i involving p1 : : : pi only, that causes some process toenter C innitely many times. This follows from the deadlock-freedom assumption (whichonly applies in fair executions).The same continuation can be applied after j , with the same eect. But note that nowthe continuation is not fair: pi+1 : : : pj are not taking any steps, although they are in T .However, running a suciently large (but nite) portion of this extension after j is enoughto violate the bounded bypass assumption | pj will get bypassed arbitrarily many times bysome process.Is this lower bound tight, or can it be raised, say to !(n2)? Another result in BFJLP]shows that it can't.

Характеристики

Список файлов книги