Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 38
Текст из файла (страница 38)
This is demonstrated by a counterexample algorithm that needs onlyn + c values for bounded-bypass (where the bound is around 2) mutual exclusion withdeadlock-freedom.The main idea of the algorithm is as follows. The processes in the trying region aredivided into two sets, called buer and main.
When processes enter the trying region, theygo into buer , where they lose their relative order. At some time, when main is empty, allprocesses in buer go to main , thereby emptying buer . Then processes are chosen one ata time, in an arbitrary order, to go to the critical region.The implementation of this idea needs some communication mechanisms, to tell processeswhen to change regions. We'll sketch the ideas here, and leave the details to the reader.Assume, for a start, that we have a supervisor process that is always enabled (regardless ofuser inputs), and that can tell processes when to change regions and go critical.
Clearly, thesupervisor does not t within the rules of our models we'll see how to get rid of it later.With such a supervisor, we have the following strategy. First, let the variable have 2components, one for a count 0 : : : n and one to hold any of a nite set of messages. This iscn values, but we can optimize to n + c by employing a priority scheme to allow preemptionof the variable for dierent purposes.
The supervisor keeps counts of number of processesit knows about in the buer and main regions. When a process enters, it increments thecount in the shared variable to inform the supervisor that someone new has entered, andthen waits in buer . The supervisor, whenever it sees a count in the variable, absorbs itin its local buer-count and resets the variable count to 0. Thus, the supervisor can gureout when to move processes to main . This is done (sequentially) by putting messages in themessage component of the shared variable.
We have the following messages:ENTER-MAIN: the rst process in buer that sees this message can \pick it up", andbe thereby told to go to main .188ACK: process response.ENTER-CRIT: can be picked up by anyone in main . The process that picks it up cango to the critical region.ACK: process response.BYE: the process in the critical region says it's done and leaves.Let's see briey how can we reuse the variable. We need the variable for two purposes:counting, and message delivery. Note that message communication proceeds more or lesssequentially (see Figure 15.4 for example).supervisorprocessenter−mainackn−maienter−mainkc−anmaienter−critackn−maiFigure 15.4: A typical communication fragment through the shared variable.We have an implicit \control thread" here.
If this thread is ever \broken" by overwritinga message with a count increase, the rest of the system will eventually quiesce: the supervisorwill eventually absorb all counts, and count will become 0. At that point, the over-writtenmessage could be replaced (count = 0 will be default if message is there). More specically,the following occurs. When a process that enters the system sees a message in the variable,it picks it up and puts down a count of 1 to announce its presence.
This process holds themessage until count is 0 again, and then replaces the message it is holding in the sharedvariable.Now we turn back to our model, in which there is no supervisor. The idea is to have a\virtual supervisor" simulated by the processes. E.g., at any time, the process that controls Cwill be the \designated supervisor", and it must pass responsibility on when it leaves C . Thisinvolves passing on its state information, and we need to use the variable to communicate this189too. This can be done by using the variable as a message channel, where we again optimizemultiple uses of message channel as before.
Note that if ever there's no other process topass it to, it means that no one is waiting. But then there's no interesting information inthe state anyway, so there is no problem in \abandoning responsibility", when the processleaves and puts an indicator in the variable.Lockout-FreedomThe lower bound of Theorem 2 can be beefed up to get a similar lower bound for lockoutfreedom BFJLP].
This is harder, because lockout freedom, unlike bounded bypass, is aproperty of (possibly innite) fair executions, and not only nite executions. The bad executions that are constructed must be fair.We can get a lower bound of n=2, by a complicated construction with an extra assumption,that processes don't remember anything when they return to their remainder regions. Sometries were made to raise the bound to n, since it seems as if an algorithm has to havesuciently many dierent values of the variable to record any number of entering processes.But the search for a lower bound was halted by another clever counterexample algorithm,giving lockout-freedom using only n=2 + c values.The idea that algorithm is as follows.
Similarly to the n + c value algorithm, the algorithmhas incoming processes increment a count, which now only takes on values 0 : : : n=2, andthen wraps around back to 0. The count is absorbed by a (conceptual) supervisor, as before.If it wraps around to 0, it seems like a group of n=2 processes is hidden. But this is not quitethe case: there's someone who knows about them | called the \executive" | the one thatdid the transition from n=2 to 0. The executive can send SLEEP messages to (an arbitraryset of) n=2 processes in buer , to put them to sleep. It doesn't matter which processesin buer go to sleep. Then, having removed n=2 from the fray, the executive reenters thesystem. Now the algorithm runs exactly as the bounded bypass algorithm, since it can'toverow (but it only gets up to count n=2).
When the executive reaches C , it can take careof the sleepers by sending them messages to awaken, and telling the supervisor about them.Again, we must share the variable, now with a more complicated priority scheme.Note: we can't have 2 executives overlapping and confusing their sleepers, because it'snot possible for that many to enter while the others are asleep.1906.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchNovember 5, 1992Lecture 1616.1 Read-Modify-Write Algorithms (cont.)16.1.1 Mutual Exclusion (cont.)Last time, we described read-modify-write algorithms for mutual exclusion with boundedbypass, and mutual exclusion with lockout-freedom. We showed that we can get algorithmsthat use a linear number of values for either.
Today, we conclude this topic with one morelower bound result.Though we will not give here the full n=2 lower bound for lockout-freedom, (too complicated!), we will show the kinds of ideas that are needed for such a proof. We shall only sketchpa weaker lower bound for lockout-freedom, of approximately n. Specically, we prove thefollowing theorem.Theorem 1 Any system of n k22;k ; 1 or more processes satisfying mutual exclusion andlockout-freedom requires at least k values of the shared variable.Proof: By induction on k. The base case k = 2 is trivial. 2 Assume now that theoremholds for k we show that it holds for k + 1.
Suppose n (k+1) 2;(k+1) ; 1, and suppose forcontradiction that number of shared values is no more than k. From the inductive hypothesis,it follows that the number of values is exactly k. We now construct a bad execution to derivea contradiction.Dene an execution 1 by running p1 alone until it enters C . Dene further an execution2 by running p2 after 1, until p2 reaches a state with shared variable value v2, such thatp2 can run on its own, causing v2 to recur innitely many times. Such a state must existsince x can assume only nitely many values. Likewise, get i, for 3 i n, by runningpi after i;1 until it reaches a point where it could, on its own, cause the current value ofthe shared variable x to recur innitely many times. Let vi be the value corresponding toi.
Since there are only k values for x, by the pigeonhole principle, there must exist i andj , where n ; k i < j n, such that vi = vj .Now, processes p1 : : : pi comprise a system with at least k22;k ; 1 processes, solvingmutual exclusion with lockout-freedom. Thus, by induction, they must use all k values of191shared memory. More specically, for every global state s that is i-reachable from the stateqi just after i, and every value v of x, there is a global state reachable from s in whichthe value of x is v. (If not, then we could run the system to global state s, then startingfrom there we have a reduced system with fewer than k values, contradicting the inductionhypothesis.) This implies that there exists a fair of execution of processes p1 : : : pi thatstarts from qi, such that all k values of shared memory recur innitely many times.Now we can construct the bad execution as follows.
First run p1 : : : pj through j , tostate qj , which looks like qi to p1 : : : pi. Then run p1 : : : pi as above, now from qj insteadof qi, in the execution in which each shared value recurs innitely often. Now recall that inqj , each process pi+1 : : : pj is able to cause the value it sees to recur innitely many times.So intersperse steps of the main run of p1 : : : pi with steps of pi+1 : : : pj as follows: eachtime the shared variable is set to some vl, i +1 l j , run pl for enough steps (at least one)to let it return the value to vl.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
