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

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

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

We shall see two single-writer algorithms, byBurns and by Lamport.The rst algorithm, developed by Jim Burns, appears in Figure 11.1. It does not guarantee fairness, but only mutual exclusion and deadlock-freedom. Lamport's algorithm is fairalso, but has the disadvantage of using unbounded variables.Mutual exclusion. The proof that Burns' algorithm guarantees mutual exclusion is sim-ilar to the proof for Dijkstra's algorithm, except that the ag variable is set to 1 where inDijkstra's it is set to 2. For example, consider an operational argument.

If i and j bothreach C , then assume that i set ag to 1 rst. By the code, it keeps it 1 until it leaves C .Also by the code, after j sets its ag to 1, j must check that ag (i) = 0 before it can enterC . The argument is completed by showing that at least one of the processes must noticethat the other has set it ag. Specically, if i < j , then j must return to L, and if i > j ,then i cannot proceed to the critical region.123Shared variables:ag : an array indexed by 1::n] of f0 1g, initially all 0, where ag i] is writtenby pi and read by allCode for piL:ag i] 0for j 2 f1 : : : i ; 1g doif ag j ] = 1 then goto Lend ifend forag i] 1for j 2 f1 : : : i ; 1g doif ag j ] = 1 then goto Lend ifend forM:for j 2 fi + 1 : : : ng doif ag j ] = 1 then goto Mend ifend for**Critical region**ag i] 0**Remainder region**Figure 11.1: Burns' Mutual Exclusion Algorithm124Deadlock-freedom.

This property can be argued by contradiction as follows. As forDijkstra's algorithm, assume that there exists some execution in which all processes are ineither R or T , and their are no further region changes. Partition the processes into thosethat ever reach label M and those that do not call the rst set P and the second set Q.Eventually, in this execution, there must exist a point where all processes in P have alreadyreached M .

Note that they never thereafter drop back to any point prior to label M . Nowwe claim that there is at least one process in P | specically, the one with the lowest indexamong all the contenders | that will reach P . Let i be the largest index of a process inP . We claim that eventually after this point, any process j 2 Q such that j > i has ag (j )set permanently to 0. This is because if its ag is 1, it eventually detects the presence of asmaller index active process and returns to L, where it sets its ag to 0, and from that pointit can never progress far enough to set it back to 1. Finally, we claim that pi will eventuallyreach the critical region, a contradiction.Remark.

Burns' algorithm uses no multi-writer variables, but does use n shared (multireader) variables to guarantee mutual exclusion and deadlock-freedom for n processes. Laterin this lecture we will see that this is optimal in terms of the number of registers, even ifunbounded multi-writer registers are available.11.2 Lamport's Bakery AlgorithmIn this section we discuss Lamport's bakery algorithm.

It is a very basic and interestingmutual exclusion algorithm it is practical, and its ideas reappear in many other places. Inthe presentation here we assume for simplicity that the shared memory consists of (singlewriter) read-write shared variables.6 The algorithm guarantees nice fairness behavior: itfeatures lockout-freedom, a good time bound, and bounded bypass. In fact, it has a strongerproperty: FIFO after a wait-free \doorway" (to be dened below). An unattractive propertyit has, however, is that it uses unbounded size registers. The code is given in Figure 11.2.We remark that the code given here can be simplied in the case of indivisible read-writeregisters.

The given code works also for the safe registers model.In the algorithm, the trying region is broken up into two subregions, which we call thedoorway, and the rest of T . The doorway is the part from when the process enters until itsets choosing i] to 0. In the doorway, the process chooses a number that is greater than thenumbers that it sees that other processes have already chosen. While it does this, it setschoosing i] to 1, to let the other processes know that it is currently choosing a number. NoteThe algorithm works also under a weaker model, called safe registers, in which the registers have muchless predictable behavior in the presence of concurrent accesses. We discuss this model later in the course.6125Shared variables:choosing : an array indexed by 1..n] of integers from f0,1g, initially all 0, wherechoosing i] is written by pi and read by allnumber : an array indexed by 1..n] of integers from f0,1,: : : g, initially all 0, wherenumber i] is written by pi and read by allCode for pi** beginning of doorway **try iL1:choosing i] 1number i] 1 + max fnumber 1] : : : number n]gchoosing i] 0** end of doorway **** beginning of bakery**for j 2 f1 : : : ng doL2:if choosing j ] = 1 then goto L2end ifL3:if number j ] 6= 0 and (number j ] j ) < (number i] i) then goto L3end ifend forcrit i** critical region**** end of bakery **exit inumber i] 0rem i**Remainder region**Figure 11.2: Lamport's bakery mutual exclusion Algorithm126that it is possible for two processes to be in the doorway concurrently, and thus two processesmay obtain the same number.

To overcome this problem, the comparison is done between(number index ) pairs lexicographically, and thus ties are broken in favor of the process withthe smaller index (this is really an arbitrary rule, but it is commonly used). In the rest ofthe trying region, the process waits for its (number index ) pair to be the lowest, and is alsowaiting for any processes that are choosing.7The algorithm resembles the operation of a bakery: customers enter the doorway, wherethey choose a number, then exit the doorway and wait in the store until their number is thesmallest.11.2.1 AnalysisBasic PropertiesLet D denote the doorway T ; D is then the rest of the trying region. We rst argue thatthe algorithm does not violate the mutual exclusion property.Claim 1 In any reachable state of the algorithm, if pi 2 C and for some j 6= i we havepj 2 (T ; D) C , then (number i] i) < (number j ] j ).We give here an operational proof, since it can be extended more easily to the safe registercase later.Proof: Process i had to read choosing j ] = 0 in L2 before entering C .

Thus, at the time ofthat read, j was not in the \choosing region" (i.e., in the doorway after setting choosing j ]to 1). But since j is in (T ; D) C , j must have gone through the doorway at some point.There are two cases to consider.Case 1: j entered the choosing region after process i read that choosing j ] = 0. Then i'snumber was chosen before j started choosing, ensuring that j saw number i] when it chose.Therefore, when i is in C , we have number j ] > number i], which suces.Case 2: j left the choosing region before i's read.

Then when i reaches L3 and reads j 'snumber, it gets the most recent value number j ]. Since i decided to enter C anyhow, it mustbe that (number i] i) < (number j ] j ).Corollary 2 The bakery algorithm satises mutual exclusion.Proof: Suppose that two processes, i and j , are both in C . Then by Claim 1, we must haveboth (number i] i) < (number j ] j ) and (number j ] j ) < (number i] i), a contradiction.Here, we are using the processes indices in much the same way as we previously used the UID's. Ifthe processes did not know their indices, but had UID's, we could use those here instead. This observationholds also for Dijkstra's algorithm, but not for Peterson's, since there, the indices distinguish the roles theprocesses play.7127Theorem 3 The algorithm satises deadlock-freedom.Proof: Again, we argue by contradiction.

Suppose that deadlock occurs: then eventuallya point is reached, after which a xed set of processes are in T , and no new region changesoccur. Also, by the code, eventually all of the processes in T get out of the doorway andinto T ; D. At this time point, the process with the lowest (number index ) is not blocked.Theorem 4 The algorithm satises lockout-freedom.Proof: Consider a particular process i 2 T . It eventually exits the doorway. Thereafter,any new process that enters the doorway sees i's number, and hence chooses a higher number.Thus, if i doesn't reach C , none of these new processes can reach C either, since they all seethat i has a smaller number, and by the code, they must wait \behind" i.

But by Theorem3, processes in T must continue to go to C , which means that i eventually goes.Time AnalysisIn this section we show that any process enters C at most O(n2) time units after it startsexecuting T . We start by showing that the algorithm has bounded bypass after the doorway.Lemma 5 The total number of times a processor pi enters the bakery while some processorpj is continuously in the bakery is no more than 2.Proof: It suces to show that any processor may exit the bakery at most once while pj isin the bakery. While j is in the bakery, number (j ) is unchanged. Hence, if a process i exitsthe bakery, then when it enters the doorway again, number (i) will be assigned a numberstrictly more than number (i), and pi will not be able to proceed from L2 from some state inthe fragment until pj exits C .We now analyze the the time for an individual process to enter C .

Consider an executionfragment such that in the rst state, some process pt is in L1, and in the last state pt is inC . Our goal is to bound the time of any such execution fragment. Denote by Td(i) the timea processor pi spends in the doorway, and by Tb(i) the time pi spends in the bakery (weconsider only the fragment in question). We shall bound Td(t) + Tb(t). We rst bound thetime spent in the doorway.Lemma 6 For any processor pi, Td(i) = O(sn).Proof: The doorway consists of n reads and 3 writes.By the above lemma, after O(sn) time, the process pt reaches the bakery.

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

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