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

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

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

For binary registers, the domain consists of only 0 and 1. Notice thatsince a binary regular register is only required to return a feasible value, it suces to ensure208W'$&%WPRP 1wxr;; rRP nR1RnFigure 17.2: Binary Regular Register from Binary Safe Registerthat all writes done on the low-level register actually change the value | because in thiscase either value is feasible.The basic idea is that the write process, WP, keeps track of the contents of register x.(This is easy because WP is the only writer of x.) WP does a low-level write only when itis performing a WRITE that would actually change the value of the register. If the WRITEis just rewriting the old value, then WP nishes the operation right away without touchingx. Therefore, all low level write s toggle the value of the register.

Specically, the \code" isas follows.write (v ): if v is the last recorded value, then do WRITE-RESPOND else do write (v), andupon receiving write-respond do WRITE-RESPOND.read: do read upon receiving read-respond(x), do READ-RESPOND(x).Now consider what happens when a READ is overlapped by a WRITE. If the corresponding write is not performed (i.e., the value is unchanged), then register x will just return theold value, and this READ will be correct.

If the corresponding write is performed, x mayreturn either 0 or 1. However, both 0 and 1 are in the feasible value set of this READ becausethe overlapping WRITE is toggling the value of the register. Therefore, the READ will becorrect.The implementation relations of Figure 17.1 now reduce to Figure 17.3.209RegularssAtomick-aryXXXXXyXXXXXss ssn-readerk-aryJJJXX^n-reader XXXXJbinary?binary andall safeJJJ^ J1-readerk-ary1-readerbinaryFigure 17.3: Collapsed Implementation Relationships17.1.2 Construction 4: K -ary Regular Register from Binary Regular RegisterWe can implement a k-ary regular register using k binary regular registers arranged as inFigure 17.4.

Here, we assume that the k values of the register are encoded as 0 1 : : : k ; 1.We will use a unary encoding of these values, and the idea (which has appeared in otherpapers, by Lamport and by Peterson) of writing a sequence of bits in one order, and readingthem in the opposite order. We remark that Lamport also gives an improved implementationfor binary representation, thus reducing the space requirement logarithmically.If the initial value of the logical register is v0, then initially xv0 is 1, and the other physicalregisters are all 0 (using unary representation). The code is as follows.WRITE (v): First, write 1 in xv . Then, in order, write 0 in xv;1 : : : x0.READ: Do read x0 x1 : : : xk;1 in order, until xv = 1 is found for some v.

Then RETURNv.Note that RP i is guaranteed to nd a non-zero xv because whenever a physical registeris zeroed out, there is already a 1 written in a higher index register. (Alternatively, we couldinitialize the system so that xk;1 = 1, and then we would have xk;1 always equal to 1.) Wenow prove the correctness of Construction 4 formally.Claim 1 If a READ R sees 1 in xv , then v must have been written by a WRITE that isfeasible for R.210$' & %xk;1 xk;2WR1R2Rnx0WP wwwRP1rrrRP2rrrRPnrrrFigure 17.4: K -ary Regular Registers from Binary Regular RegistersProof: By contradiction. Suppose R sees xv = 1, and neither an overlapping nor animmediately preceding WRITE wrote v to the logical register.

Then v was written eithersometime in the past, say by WRITE W1, or v is the initial value. We analyze below theformer case the initial value case can be treated similarly.So let W1 be the last WRITE completely preceding R that wrote v. Since v is not afeasible value for R, there must be another WRITE W2 after W1 which completely precedesR.

Any such W2 (i.e., a WRITE that follows W1 and completely precedes R) can write onlyvalues strictly smaller than v, because if it wrote a value more than v, it would set xv = 0before R could see xv = 1, and it cannot write v by the choice of W1. Note that if such a W2writes value v0, then the contained write (1) to xv completely precedes the read of xv in R.So, consider the latest write (1) to a register xv such that v0 < v, and such that thewrite (1) follows W1 and completely precedes the read of xv in R. By the above arguments,there is at least one such write.

We now proceed with case analysis.Since R reads the registers in order x0 : : : xk;1, and it returns value v > v0, R must seexv = 0. But we have just identied a place where xv is set to 1. Therefore, there existssome write (0) to xv which follows the write (1) to xv and either precedes or overlaps theread of v0 in R. This can only happen if there is an intervening write (1) to some xv suchthat v00 > v0.

As above, in this case we must have v00 < v. (If not, then before doing thewrite (0) to xv , the enclosing WRITE would overwrite the 1 in xv , and so R could not get00000000000211it.) But then this is a contradiction to the choice of the write of v0 as the latest. (Note thewrite (1) to xv completely precedes the read of xv in R, because the write (0) to xv eitherprecedes or overlaps the read of xv in R, and v00 > v0.)000000ss sssThe implementation relationships now collapse as shown in Figure 17.5.n-readerk-ary atomicn-readerbinary atomic JJJJ^ 1-readerJJJ^ Jk-ary atomic1-readerbinary atomic?regularand safeFigure 17.5: Collapsed Implementation Relationships17.1.3 Construction 5: 1-Reader K -ary Atomic Register from Regular RegisterWe now show how to construct a 1-writer, 1-reader k-ary atomic register from two 1-writer,1-reader k-ary regular registers arranged as in Figure 17.6.

The code is given in Figure 17.7.The cases in the code are designed to decide whether to return the new or the old valueread. Intuitively, if x0:num = 3, it means that there has been much progress in the write (orit may be nished), so it is reasonable to return the new value. At the same time, it is usefulto remember that the new value has already been returned, in the new-returned variable.This is because a later read of x that overlaps a write could get an earlier version of thevariable, with num = 2 (because x is a regular register, and not an atomic register). Noticethat it couldn't get num = 1.

The second case covers the situation in which the previousread could have already returned the value of a write that overlaps both. The conditions looka little ad hoc. Unfortunately, we can't give a correctness proof in class. For the correctnessproof, we refer the reader to Lamport86]. This is not the sort of proof that can be done inany obvious way using invariants, because the underlying registers are not atomic. Instead,212WR'$&%WP wrxRP wy@;;r @Figure 17.6: 1-Reader Atomic Register from Regular RegistersLamport developed an alternative theory of concurrency, based on actions with duration,overlapping or totally preceding each other.

Another approach to prove the correctness isto use the Lemma presented in Lecture 15.The implementation relations now collapse as in Figure 17.8. This concludes Lamport'sconstructions.17.1.4 Multi-Reader Atomic RegistersNotice that the constructions thus far still leave a gap between the n-reader, 1-writer atomicregisters and the 1-reader, 1-writer atomic registers. This gap has been closed in a couple ofother papers: SinghAG87], NewmanW87,].

We remark that these algorithms are somewhatcomplicated. It is also not clear if they are practical, since their time complexity is high.Singh-Anderson-Gouda have a reasonable construction, related to Lamport's Construction5.17.2 Lamport's Bakery RevisitedWe now show that the original Lamport bakery algorithm presented in class still works ifthe underlying registers are only safe. The explanation is as follows.

A read of the choosing variable while it is being written will be guaranteed to geteither 0 or 1, since these are the only possible values. But those correspond to eitherthe point before or after the write step. If a number is read by a chooser while it is being written, the chooser can get anarbitrary value. When the chooser takes the maximum of this arbitrary value with213Shared Variables: (regular registers) x: stores tuples of (old new num color ), where old new are from the value domain of the atomic register, and num 2 f1 2 3g.

Initially x = (v0 v0 3 red ). y: stores values from fred blue g. Initially y = blue .Code for write (v):newcolor :yoldvalue x:new(record value of x locally: no need to read it)for i 2 f1 2 3g dox (oldvalue v i newcolor )Code for read :(remember last two reads in x0 and x00)x00 x0x0 xy x0:color .casex0:num = 3:new-returned truereturn x0:newx0:num < 3 and x0:num (x00:num ; 1) and new-returned and x0:color = x00:color :return x0:newotherwise:new-returned falsereturn x0:oldend caseFigure 17.7: Code for constructing single-read k-ary atomic register from regular registers214sssn-readerk-ary atomicn-readerbinary atomic JJJ ?^Jregular and safe1-reader atomicFigure 17.8: Collapsed Implementation Relationshipsthe others, the result is that the chooser is guaranteed to choose something biggerthan all the values it sees without overlap, but there is no guarantee it will choosesomething bigger than a concurrent writer.

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

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