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

We know that it must fail becauseotherwise it would go to C , which we have assumed doesn't happen this quickly.Second, we claim that the additional time elapsed until turn equals a contender index isat most O(s). To see this, we need a small case analysis. If when pi tests turn , turn holds acontender index, we're done, so suppose that this is not the case specically, suppose thatturn = j , where j is not a contender. Then within time O(s) after this test, pi will testag (j ). If pi nds ag (j ) = 0, then pi sets turn , to i, which is the index of a contender,and we are again done. On the other hand, if it nds ag (j ) 6= 0, then it must be that inbetween the test of turn by pi and the test of ag (j ), process j entered the trying region andbecame a contender.

If turn has not changed in the interim, then turn is equal to the indexof a contender (j ) and we are done. On the other hand, if turn has changed in the interim,then it must have been set to the index of a contender. So again, we are done.Then after an additional time O(s), no process can ever reset turn (or enter the secondstage). Then time O(sn) later, all others in the second stage will have left, since they don'tsucceed because it's too soon. Then within an additional time O(sn), i must succeed inentering C .1049.2 Improved Mutual Exclusion AlgorithmsWhile Dijkstra's algorithm guarantees mutual exclusion and deadlock-freedom, there areother desirable properties that it does not have. Most importantly, it does not guaranteeany sort of fairness to individual processes that is, it is possible that one process willcontinuously be granted access to its critical region, while other processes trying to gainaccess are prevented from doing so.

This situation is sometimes called process starvation.Note that this is a dierent kind of fairness from that discussed earlier: this is fairness tothe invoked operations, rather than fairness of process steps.Another unattractive property of Dijkstra's algorithm is that it uses a multi-reader/multiwriter variable (for turn ). This may be dicult or expensive to implement in certain kindsof systems. Several algorithms that improve upon Dijkstra's have been designed.

We shalllook at some algorithm developed by Peterson, and by Peterson and Fischer.9.2.1 No-Starvation RequirementsBefore we look at alternative mutual exclusion algorithms, we consider what it means for analgorithm to guarantee fairness. Depending upon the context in which the algorithm is used,dierent notions of fairness may be desirable. Specically, we shall consider the followingthree ideas that have been used to rene the requirements for mutual exclusion algorithms.Lockout-freedom: In a fair execution (with respect to processes' steps) of the algorithmwhere the users always return the resource, any process in T eventually enters C . (Also,in any fair execution, any process in E eventually enters R.)Time bound b: If the users always return the resource within time c of when it is granted,and processes always take steps in T E within time s, then any process in T enters Cwithin time b.

(Note: b will typically be some function of s and c.) (Also, if processesalways take steps in T E within time s, then any process in E enters R within timeb.)Number of bypasses b: Consider an interval of an execution throughout which some pro-cess pi is in T (more specically, has performed the rst non-input step in T ). Duringthis interval, any other process pj , j 6= i, can only enter C at most b times.

(Also, thesame for bypass in E .)In each case above, we have stated fairness conditions for the exit region that are similarto those for the trying region. However, all the exit regions we will consider are actuallytrivial, and satisfy stronger properties (e.g., are \wait-free").105Some implications. There are some simple relations among the dierent requirementsfrom mutual exclusion protocols.Theorem 6 If an algorithm is lockout-free then it is deadlock-free.Proof: Consider a point in a fair execution such that i is in T , no one is in C , and supposethat no one ever enters C .

Then this is a fair execution in which the user always returns theresource. So the lockout-freedom condition implies that i eventually enters C , as needed fordeadlock-freedom.Likewise, consider a point in a fair execution such that i is in E . By lockout-freedom, ieventually enters R, as needed for deadlock-freedom.Theorem 7 If an algorithm is deadlock-free and has a bypass bound, then the algorithm islockout-free.Proof: Consider a point in a fair execution.

Suppose that the users always return theresource, and i is in T . Deadlock-freedom and the user returning all resources imply thatthe system keeps making progress as long as anyone is in T . Hence, the only way to avoidbreaking the bypass bound, is that eventually i must reach C .The argument for the exit region is similar.Theorem 8 If an algorithm has any time bound then it is lockout-free.Proof: Consider a point in a fair execution.

Suppose the users always return the resource,and i is in T . Associate times with the events in the execution in a monotone nondecreasing,unbounded way, so that the times for steps of each process are at most s and the times forall the critical regions are all at most c. By the assumption, i enters C in at most the timebound, so in particular, i eventually enters C , as needed for lockout-freedom.The argument for the exit region is similar.In the following, we shall see some protocols that satisfy some of these more sophisticatedrequirements.9.2.2 Peterson's Two-Process AlgorithmWe begin with an algorithm that gives lockout-freedom, and a good time bound (with aninteresting analysis). We start with a 2-process solution, for processes p0 and p1.

We write%{ for 1 ; i, i.e., the index of the other process. The code is given in Figure 9.2.We now argue that the algorithm is correct.Theorem 9 Peterson's two-process algorithm satises mutual exclusion.Proof Sketch: It is easy to show by induction thatlevel (i) = 0 =) i 2= (at-wait before-C in-C) :106(9.1)Shared variables:level : a Boolean array, indexed by 0 1], initially 0turn : a Boolean variable, initial state arbitraryCode for pi :** Remainder Region **try ilevel (i) := 1turn := iwait for level (%{) = 0 or turn 6= icrit i** Critical Region **exit ilevel (i) := 0rem iFigure 9.2: Peterson's algorithm for two processesUsing (9.1), we can show by induction thati 2 (before-C in-C) =) (%{ 2= (at-wait before-C in-C)) _ (turn 6= i) :(9.2)There are three key steps to check: First, when i passes the wait test, then we have one ofthe following.

Either turn 6= i and we are done, or else level (%{) = 0, in which case we aredone by (9.1).Second, when %{ reaches at-wait, then it explicitly sets turn 6= i. Third, when turn getsset to i, then this must be a step of process pi , performed when it is not in the indicatedregion.Theorem 10 Peterson's two-process algorithm satises deadlock-freedom.Proof Sketch: We prove deadlock-freedom by contradiction. That is, assume that at somepoint, i 2 T , there is no process in C , and no one ever enters C later. We consider two cases.If %{ eventually enters T , then both processes must get stuck at the wait statement since theydon't enter C . But this cannot happen, since the value of turn must be favorable to one ofthem.107On the other hand, suppose that %{ never reaches T .

In this case, we can show by inductionthat level (%{) eventually becomes and stays 0, contradicting the assumption that i is stuck inits wait statement.Theorem 11 Peterson's two-process algorithm satises lockout-freedom.Proof Sketch: We show the stronger property of 2-bounded bypass. Suppose the contrary,i.e., that i is in T after setting level (i) = 1, and %{ enters C three times. By the code, inthe second and third time, %{ sets turn := %{ and then must afterwards see turn = i. Thismeans that there are two occasions upon which i must set turn := i (since only i can setturn := i).