Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 57
Текст из файла (страница 57)
Process pj could onlyhave deferred the OK because it was either in C : but since pj eventually leaves C , it must eventually send the deferred OK. in T : in this case pj deferred the OK because the timestamp of its request was smallerthan pi 's. Since pi's request has the smallest timestamp in T now, pj must havecompleted, thus after exiting C it had to send the deferred OK.279In either case we get a contradiction.Fairness: it can be shown that the algorithm has lockout-freedom.Complexity: it is easy to see that there are 2(n ; 1) messages per request.
The timecomplexity is left as an exercise.22.1.2 Carvalho & Roucairol (1983)This algorithm improves on Ricart-Agrawala by giving a dierent interpretation to the OKmessage. When some process pi sends an OK to some other process pj , not only does itapprove pj 's current request, but it also gives pj pi's permission to re-enter C again andagain until pj sends an OK to pi in response to a try from pi .This algorithm performs well under light load. When a single process is requesting againand again, with no other process interested, it can go critical with no messages sent! Underheavy load, however, it basically reduces to Ricart and Agrawala's algorithm.This algorithm is closely related to (i.e., is generalized by) the Chandy-Misra DiningPhilosophers algorithm.22.2 General Resource AllocationWe now turn to consider more general resource allocation problems in asynchronous networks, as dened earlier.22.2.1 Burns-Lynch AlgorithmThis algorithm solves conjunctive resource problems.
Recall the strategies studied in asynchronous shared memory setting, involving seeking forks in order, and waiting for resourcesone at a time. We can run the same strategies in asynchronous networks. The best way to dothis is not via a general simulation of the shared memory model in the network model: recallthat the algorithms involve busy-waiting on shared variables if simulated, each busy-waitingstep would involve sending messages. Instead, we have each resource represented by its ownprocess (which must be located at some node).
The user process sends a message to theresource process for the rst resource it needs the resource process puts the user index onits queue the user process then waits. When the user index reaches the front of the queue,the resource process sends a message back to that user process, which then goes on to waitfor its next resource, etc. When a process gets all its resources, it tells its external user togo critical when exit occurs, the user process sends messages to all the resource processesto remove its index from the queue.280The analysis is similar to that done in the shared memory case, and depends only onlocal parameters. The general case has exponential dependence on the number of colors.There are some variations in the literature, to improve the running time.
This is still a topicof current research: see, e.g., Styer-Peterson, Awerbuch-Saks, Choy-Singh.22.2.2 Drinking PhilosophersThis is a dynamic variant of the general (conjunctive) static resource allocation problem.In this setting we have the same kind of graph as before, where a process is connected toeveryone with whom it might have a resource conict. But now, when a try request arrivesfrom the outside, it contains an extra parameter: a set B of resources, indicating whichresources the process actually needs this time. This set must be a subset of the static set forthat process | the twist is that now it needn't be the whole set.As before, we want to get exclusion, but this time based on the actual resources beingrequested.
We would like to have also deadlock-freedom and lockout-freedom. The concurrency condition is now modied as follows. Suppose that a request is invoked at node i, andduring the interval of this request, there are no (actual) conicting requests. Suppose theexecution proceeds so that i and all its neighbors in the underlying graph continue to takesteps fairly, and the connecting links continue to operate fairly (note that some processesmight remain in C ). Then eventually i reaches C .Chandy and Misra gave a solution to this, which was based on a particular (inecient)Dining Philosophers algorithm.
Welch and Lynch noticed that the Chandy-Misra algorithmmade almost-modular use of the underlying Dining Philosophers algorithm, and so they redid their result, with the implicit modularity made explicit. Then it was possible to substitutea more ecient Dining Philosophers algorithm for the original Chandy-Misra subroutine.The proposed architecture is sketched in Figure 22.2. The Dining Philosophers subroutineexecutes using its own messages, as usual. In addition, there are new messages for theDrinking Philosophers algorithm.We assume for simplicity here that each resource is shared between only two processes.The heart of the algorithm is the Di automata.
First we describe the algorithm informally,and then present the Di automaton code.When Di enters its trying region needing a certain set of resources, it sends requestsfor those resources that it needs but lacks. A recipient Dj of a request satises the requestunless Dj currently also wants the resource or is already using it. In these two cases, Djdefers the request so that it can satisfy it when it is nished using the resource.In order to prevent drinkers from deadlocking, a Dining Philosophers algorithm is usedas a subroutine.
The \resources" manipulated by the Dining Philosophers subroutine are281User iT CUser jE RT CsendDiDrinkingPhilosophersalgorithm receiveRTC EreceivesendE RDjDrinkingPhilosophersalgorithmT CE RDining Philosophers algorithmFigure 22.2: Architecture for the Drinking Philosophers problem.priorities for the \real resources" (there is one dining resource for each drinking resource).As soon as Di is able to do so in its drinking trying region, it enters its dining trying region,that is, it tries to gain priority for its maximum set of resources. If Di ever enters its diningcritical region while still in its drinking trying region, it sends demands for needed resourcesthat are still missing.
A recipient Dj of a demand must satisfy it even if Dj wants theresource, unless Dj is actually using the resource. In that case, Dj defers the demand andsatises it when Dj is through using the resource.Once Di is in its dining critical region, we can show that it eventually receives all itsneeded resources and never gives them up. Then it may enter its drinking critical region.Once Di enters its drinking critical region, it may relinquish its dining critical region, sincethe benets of having the priorities are no longer needed. Doing so allows some extra concurrency: even if Di stays in its drinking critical region forever, other drinkers can continueto make progress.A couple of points about the code deserve explanation.
We can show that when a requestis received, the resource is always at the recipient thus it is not necessary for the recipientto check that it has the resource before satisfying or deferring the request. On the otherhand, it is possible for a demand for a missing resource to be received, so before satisfyingor deferring a demand, the recipient must check that it has the resource.Another point concerns the questions when the actions of the dining subroutine should beperformed. Note that some drinkers could be locked out if Di never relinquishes the diningcritical region.
The reason for this is that as long as Di is in its critical region, it has priority282for the resources. Thus, if we are not careful, Di could cycle through its drinking criticalregion innitely many times, while other drinkers wait. To avoid this situation, we keeptrack (using variable current ) of whether the dining critical region was entered on behalfof the current drinking trying region (i.e., whether the latest Ci occurred after the latestTi(B )). If it was, then Di may enter its drinking critical region (assuming it has all theneeded resources).
Otherwise, D(i) must wait until the current dining critical region hasbeen relinquished before continuing.The full code is given in Figures 22.3,22.4 and 22.5.Correctness proof. Exclusion is straightforward, based on possession of the resources(since we use explicit tokens). Concurrency is also straightforward. To prove lockout-freedomwe need to rely on the Dining-Philosophers subroutine. The proof is a bit subtle. First,we argue that the environment of the dining philosophers algorithm preserves dining-wellformedness (this is proved by a straightforward explicit check of the code). Therefore, everyexecution of the system is dining-well-formed (since the dining subroutine also preservesdining-well-formedness).
Therefore the dining subroutine provides its guarantees: diningexclusion, and lockout-freedom for the dining subroutine in the context of the drinkingalgorithm.Next, we show the following lemma.Lemma 1 In any fair drinking-well-formed execution, if drinking users always return theresources, then dining users always return the resources.Proof Sketch: Suppose that the dining resources are granted to Di .
Then, Di sendsdemands. Consider any recipient Dj of a demand. If Dj has the resource and is not actuallyusing it, then it gives it to i, because by the exclusion property of the dining subroutine, Djcannot also be in its dining critical region. On the other hand, if Dj is using the resource,then by the assumption that no drinker is stuck in its critical region, Dj eventually nishesand satises the demand. Thus, eventually, Di gets all the needed resources, and enters itsdrinking critical region, after which (by the code) it returns the dining resources.With this we can prove the following property.Lemma 2 In any fair drinking-well-formed execution, if drinking users always return theresources, then every drinking request is granted.Proof Sketch: Once a drinking request occurs, say at node i, then (unless the grant occursimmediately), a subsequent dining request occurs at i.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
