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

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

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

We now consideronly the sux of the fragment, in which pt is in the bakery. Consider the if statements. Theycan be described as \busy waiting" until some predicate holds. We call a test successful ifthe next step is not another execution of the test (specically, if the predicate in L2 and L3128was false). The following lemma bounds the number of successful tests in the fragment weconsider.Lemma 7 The total number of successful tests in the fragment is no more than O(n2).Proof: In all the Trying Region every processor makes O(n) successful tests, and by Lemma5, any processor passes the Trying Region no more than twice.We can now bound the total time of the fragment.Theorem 8 The total time of the execution fragment in question is no more than Td(t) +Tb(t) = O(sn2) + O(cn).Proof: We know that in all states during the execution fragment, some processor can makeprogress (or otherwise the liveness property is contradicted). But this implies that eithersome process is making progress in the doorway, or that some process makes a successfulcomparison, or that some process makes progress in the C .

The total amount of time in thefragment during which some processor in the C is O(cn), since by Lemma 5, any processorenters the C at most once. Also, the total amount of time in the fragment during whichany processor is in the doorway is O(sn2 ), by Lemmas 5 and 6. Taking into account the\successful test" steps from Lemma 7 we can conclude thatTb(t) O(sn2) + O(sn2 ) + O(cn) = O(sn2) + O(cn) :The result is obtained when combining the above bound with Lemma 6.Additional PropertiesThe algorithm has some other desirable properties.

For example, we have FIFO after adoorway. This stronger fairness property says that if i nishes the doorway before j entersT , then i must precede j in entering C . This is an almost-FIFO property: it is not actuallyFIFO based on time of entry to T , or even time of rst non-input step in T (i could set itschoosing variable to 1, then delay while others choose, so all the others could beat it).It isn't very useful to say (as a feature) that an algorithm is FIFO after a doorway,since so far there are no constraints on where the doorway begins. We might even place thedoorway right at the entrance to C ! But the doorway in this algorithm has a nice property:it's wait-free, which means that a process is guaranteed eventually to complete it, if thatprocess continues to take steps, regardless of what the other processes do (continue takingsteps or stop, in any combination, any speed).The bakery algorithm has also some limited amount of fault-tolerance.

Consider faultsin which a user can \abort" an execution at any time when it is not in R, by sending anabort i input to its process. Process i handles this by setting its variables, local and shared,back to initial values. A lag is allowed in resetting the shared variables. We can see that129mutual exclusion is still preserved. Moreover, we still have some kind of deadlock-freedom:suppose that at some point some process is in T and does not fail (abort), and that thereare only nitely many total failures, and that C is empty. Then the algorithm guaranteesthat eventually some process enters C (even if all other processes fail).11.3 The Number of Registers for Mutual ExclusionWe have seen several algorithms using read-write shared memory, for mutual exclusion, withdeadlock-freedom, and also various fairness properties.

The question arises as to whetherthe problem can be solved with fewer than n read-write variables.If the variables are constrained to be single-writer, then the following lemma implies thatat least n variables are needed.Claim 9 Suppose that an algorithm A solves mutual exclusion with deadlock-freedom forn 2 processes, using only read-write shared variables.

Suppose that s is a reachable stateof A in which all processes are in the remainder region. Then any process i can go criticalon its own starting from s, and along the way, i must write some shared variable.Proof: Deadlock-freedom implies that i can go critical on its own from s. Suppose thatit does not write any shared variable. Then consider any other process i0 deadlock-freedomalso implies that i0 can go critical on its own, starting from s. Now consider a third execution,in which process i rst behaves as it does in its solo execution, eventually entering C withoutwriting any shared variable. Since process i does not write any shared variable, the resultingstate s0 \looks like" state s to process i0. (Here, we say that two states look alike to someprocess if the state of that process and the values of all shared variables are the same in thetwo states.) Therefore, i0 is also able to go critical on its own starting from s0.

This violatesthe mutual exclusion requirement.Claim 9 directly implies that if only single-writer registers are available, then the algorithm must use at least n of them. But note that we have not even beaten this bound whenwe used multi-writer variables. In this section we prove that this is not an accident. In fact,we have the following lower bound.Theorem 10 If algorithm A solves mutual exclusion with deadlock-freedom for n 2 processes, using only read-write variables, then A must use at least n shared variables.Note that this result holds regardless of the size of the shared variables: they can be assmall as a single bit, or even unbounded in size.

Also note that no fairness assumption isneeded deadlock-freedom is sucient to get the impossibility result.To get some intuition, we start with two simple cases. We rst consider the case of onevariable and two processes then we consider the case for two variables and three processes,130and nally we shall extend the ideas to the general case.We shall use the following denition extensively.Denition 1 Suppose that at some global state s, the action enabled in some process p iswriting to a variable v (that is, the next time p takes a step, it writes to v ). In this case wesay that p covers v .11.3.1 Two Processes and One VariableSuppose that the system consists of two processes p1 and p2, and only 1 variable. Weconstruct a run that violates mutual exclusion for this system. Claim 9 implies that thereis a solo run of p1 that causes it to enter C , and to write the single shared variable v beforedoing so.

So now run p1 just until the rst time it is about to write to v, i.e., until the rsttime it covers v. We then run p2 until it goes to C (since p1 hasn't written anything yet,for p2 the situation is indistinguishable from the state in which p1 is in R, and hence p2 willbehave as it does running solo). Then let p1 continue running. Now, the rst thing p1 doesis to write v, thereby overwriting anything that p2 wrote and so eliminating all traces of p2'sexecution.

Thus, p1 will run as if alone, and also go to C , contradicting the mutual exclusionrequirement.11.3.2 Three processes and Two VariablesNow suppose that we have three processes p1 p2 p3 and two variables v1 v2. Again, we shallconstruct a run that violates mutual exclusion, using the following strategy. Starting froman initial state, we will maneuver p1 and p2 alone so that each is covering a dierent variablemoreover, the resulting state, s, is indistinguishable to p3 from another reachable state, s0,in which all three processes are in R. Then we run p3 from s, and it must eventually goto C , since it can't tell that anyone else is there.

Then we let p1 and p2 each take a step.Since they are covering the two variables, the rst thing they do is to overwrite all traces ofp3's execution, and so they will run as if they are alone, and by deadlock-freedom, one willeventually go to C , yielding the desired violation of mutual exclusion.It remains to show how we maneuver p1 and p2 to cover the two shared variables.

We dothis as follows (see Figure 11.3).First, we run p1 alone until it covers a shared variable for the rst time. Call this pointt1. Then, we run p1 alone until it enters C , then continues to E , R, back to T , and againcovers some variable for the rst time. Call this point t2. We repeat this procedure to obtaina third point t3. Notice that two of the three points t1, t2 an t3 must involve covering the131Critical RegionRemainder Regiont1t2t3Figure 11.3: solo run of p1.

It covers a variable at each of t1, t2, and t3, and hence it covers thesame variable twice.same variable (see Figure 11.3). Without loss of generality, suppose that in t1 and t3 p1covers v1 (the same argument holds for all the other cases).Now consider the following execution. Run p1 until point t1. Then let p2 enter and runalone. We claim that eventually p2 enters C , since the state looks to p2 as if it is in the soloexecution. Moreover, we claim that along the way p2 must write the other variable, call itv2. For otherwise, p2 could go to C , then p1 could immediately write v1 and thus overwriteall traces of p2 , then go on and violate mutual exclusion.Remainder Regionp1p1 covers v1p1p2p2 covers v2p1 overwritesv1p1 covers v1Figure 11.4: Execution for 2 variables. By the end of this fragment, p1 and p2 cover both sharedvariables, and the state is indistinguishable from the state in whichremainder state.p1andp2are in their lastSo now we construct the required execution as follows (see Figure 11.4.) Run p1 untilpoint t1, when it covers v1.

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

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