CS514: Intermediate Course in Operating SystemsRecall our discussion of timeToday: “Simultaneous” actionsTemporal distortionsSlide 5Slide 6Slide 7Slide 8Slide 9Consistent cuts and snapshotsSlide 11Slide 12Who cares?Deadlock detection “algorithm”Suppose we detect this statePhantom deadlocks!Slide 17Chandy/Lamport AlgorithmUsing logical clocks to make cutsSlide 20Turn idea into an algorithmChandy/LamportSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36What’s in the “state”?Other algorithms?CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TARecall our discussion of timeLogical clocks: represent part of relation, small overheadVector clocks: accurately represent but more costlyWall clocks: tradeoff between precision and accuracy.Rarely precise enough for use in protocolsHence often view time as an “add on”Today: “Simultaneous” actionsThere are many situations in which we want to talk about some form of simultaneous eventOur missile interceptor is one caseBut think about updating replicated dataPerhaps we have multiple conflicting updatesThe need is to ensure that they will happen in the same order at all copiesThis “looks” like a kind of simultaneous actionTemporal distortionsThings can be complicated because we can’t predictMessage delays (they vary constantly)Execution speeds (often a process shares a machine with many other tasks)Timing of external eventsLamport looked at this question tooTemporal distortionsWhat does “now” mean? p0 a f e p3 b p2 p1 c dTemporal distortionsWhat does “now” mean? p0 a f e p3 b p2 p1 c dTemporal distortionsTimelines can “stretch”…… caused by scheduling effects, message delays, message loss… p0 a f e p3 b p2 p1 c dTemporal distortionsTimelines can “shrink”E.g. something lets a machine speed up p0 a f e p3 b p2 p1 c dTemporal distortionsCuts represent instants of time. But not every “cut” makes senseBlack cuts could occur but not gray ones. p0 a f e p3 b p2 p1 c dConsistent cuts and snapshotsIdea is to identify system states that “might” have occurred in real-lifeNeed to avoid capturing states in which a message is received but nobody is shown as having sent itThis the problem with the gray cutsTemporal distortionsRed messages cross gray cuts “backwards” p0 a f e p3 b p2 p1 c dTemporal distortionsRed messages cross gray cuts “backwards”In a nutshell: the cut includes a message that “was never sent” p0 a e p3 b p2 p1 cWho cares?Suppose, for example, that we want to do distributed deadlock detectionSystem lets processes “wait” for actions by other processesA process can only do one thing at a timeA deadlock occurs if there is a circular waitDeadlock detection “algorithm”p worries: perhaps we have a deadlockp is waiting for q, so sends “what’s your state?”q, on receipt, is waiting for r, so sends the same question… and r for s…. And s is waiting on p.Suppose we detect this stateWe see a cycle…… but is it a deadlock?p qsrWaiting forWaiting forWaiting forWaiting forPhantom deadlocks!Suppose system has a very high rate of locking.Then perhaps a lock release message “passed” a query messagei.e. we see “q waiting for r” and “r waiting for s” but in fact, by the time we checked r, q was no longer waiting!In effect: we checked for deadlock on a gray cut – an inconsistent cut.Consistent cuts and snapshotsGoal is to draw a line across the system state such thatEvery message “received” by a process is shown as having been sent by some other processSome pending messages might still be in communication channelsA “cut” is the frontier of a “snapshot”Chandy/Lamport AlgorithmAssume that if pi can talk to pj they do so using a lossless, FIFO connectionNow think about logical clocksSuppose someone sets his clock way ahead and triggers a “flood” of messagesAs these reach each process, it advances its own time… eventually all do so.The point where time jumps forward is a consistent cut across the systemUsing logical clocks to make cuts p0 a f e p3 b p2 p1 c d Message sets the time forward by a “lot”Algorithm requires FIFO channels: must delay e until b has been delivered!Using logical clocks to make cuts p0 a f e p3 b p2 p1 c d “Cut” occurs at point where time advancedTurn idea into an algorithmTo start a new snapshot, pi …Builds a message: “Pi is initiating snapshot k”. The tuple (pi, k) uniquely identifies the snapshotIn general, on first learning about snapshot (pi, k), pxWrites down its state: px’s contribution to the snapshotStarts “tape recorders” for all communication channelsForwards the message on all outgoing channelsStops “tape recorder” for a channel when a snapshot message for (pi, k) is received on itSnapshot consists of all the local state contributions and all the tape-recordings for the channelsChandy/LamportThis algorithm, but implemented with an outgoing flood, followed by an incoming wave of snapshot contributionsSnapshot ends up accumulating at the initiator, piAlgorithm doesn’t tolerate process failures or message failures.Chandy/LamportpqrstuvwxyzA networkChandy/LamportpqrstuvwxyzA networkI want to start a snapshotChandy/LamportpqrstuvwxyzA networkp records local stateChandy/LamportpqrstuvwxyzA networkp starts monitoring incoming channelsChandy/LamportpqrstuvwxyzA network“contents of channel p-y”Chandy/LamportpqrstuvwxyzA networkp floods message on outgoing channels…Chandy/LamportpqrstuvwxyzA networkChandy/LamportpqrstuvwxyzA networkq is doneChandy/LamportpqrstuvwxyzA networkqChandy/LamportpqrstuvwxyzA networkqChandy/LamportpqrstuvwxyzA networkqzsChandy/LamportpqrstuvwxyzA networkqvzxusChandy/LamportpqrstuvwxyzA networkqvwzxusyrChandy/LamportpqrstuvwxyzA snapshot of a networkqxusvrtwpyzDone!What’s in the “state”?In practice we only record things important to the application running the algorithm, not the “whole” stateE.g. “locks currently held”, “lock release messages”Idea is that the snapshot will beEasy to analyze, letting us build a picture of the system stateAnd will have everything that matters for our real purpose, like deadlock detectionOther
View Full Document
Unlocking...