Outline for today• Objective: – Background on deadlock– Pulse• Speculative execution• Virtual Machines and Xen• Administrative:– Make teams for programming projectsBackground on DeadlockDealing with DeadlockIt can be prevented by breaking one of the prerequisite conditions (review):– Mutually exclusive use of resources• Example: Allowing shared access to read-only files (readers/writers problem from readers point of view)– circular waiting• Example: Define an ordering on resources and acquire them in order (lower numbered fork first)– hold and wait – no pre-emptionDealing with Deadlock (cont.)Let it happen, then detect it and recover – via externally-imposed preemption of resourcesAvoid dynamically by monitoring resource requests and denying some.– Banker’s Algorithm ...Deadlock TheoryState of resource allocation captured in Resource Graph– Bipartite graph model with a set P of vertices representing processes and a set R for resources.– Directed edges•Ri −> Pj means Ri alloc to Pj•Pj −> Rimeans Pjrequests Ri– Resource vertices contain units of the resourceResourceR0ResourceR1Process P0Process P1RequestArcAlloc ArcReusable ResourcesDeadlock TheoryState transitions by operations:– Granting a request– Making a new request if all outstanding requests satisfiedDeadlock defined on graph:–Piis blocked in state S if there is no operation Pi can perform–Piis deadlocked if it is blocked in all reachable states from S–S is safe if no reachable state is a deadlock state (i.e., having some deadlockedResourceR0ResourceR1Process P0Process P1RequestArcAlloc ArcDeadlock Theory• Cycle in graph is a necessary condition– no cycle −> no deadlock.• No deadlock iff graph is completely reducible– Intuition: Analyze graph, asking if deadlock is inevitable from this state by simulating most favorable state transitions.R0R1P0P1RequestArcAlloc ArcP3Deadlock Detection AlgorithmLet U be the set of processes that have yet to be reduced. Initially U = P. Consider only reusable resources.while (there exist unblocked processes in U){ Remove unblocked Pi from U; Cancel Pi’s outstanding requests;Release Pi’s allocated resources; /* possibly unblocking other Pkin U */}if ( U != λ) signal deadlock;Deadlock Detection ExampleP0R0R2R3R4R1P3P4P2P1Deadlock Detection ExampleP0R0R2R3R4R1P3P4P2P1Deadlock Detection ExampleR0R2R3R4R1P3P4P2P0Deadlock Detection ExampleR0R2R3R4R1P3P4P2P0Deadlock Detection ExampleR0R2R3R4R1P4P2P0Deadlock Detection ExampleP0R0R2R3R4R1P4P2Deadlock Detection ExampleP0R0R2R3R4R1P4Deadlock Detection ExampleP0R0R2R3R4R1P4Deadlock Detection ExampleP0R0R2R3R4R1Deadlock Detection ExampleR0R2R3R4R1Completely ReducibleAnother ExampleR0R1P0P1RequestArcAlloc ArcP2With and without P2Another ExampleR0R1P0P1RequestArcAlloc ArcWith and without P2Is there an unblockedprocess to start with?Another ExampleR0R1P0P1RequestArcAlloc ArcWith and without P2Another ExampleR0R1P0P1RequestArcAlloc ArcWith and without P2Another ExampleR0R1P0P1RequestArcAlloc ArcWith and without P2Another ExampleR0R1P0P1RequestArcAlloc ArcP2With and without P2Is there an unblockedprocess to start with?Consumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ωP0P1P2ProducerArcProducerArcR0R1Consumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ω– Start with P2P0P1P2ProducerArcProducerArcR0R1Consumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ω– Start with P2P0P1P2ProducerArcProducerArcR0R1Not reducibleConsumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ω– Start with P2P0P1P2ProducerArcProducerArcR0R1Consumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ω– Start with P2– Start with P1P0P1P2ProducerArcProducerArcR0R1Consumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ω– Start with P1P0P1P2ProducerArcProducerArcR0R1ωConsumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ω– Start with P1P0P1P2ProducerArcProducerArcR0R1ωωConsumable Resources• Not a fixed number of units, operations of producing and consuming (e.g. messages)• Ordering matters on applying reductions– Reducing by producer makes “enough” units, ω– Start with P1P0P1P2ProducerArcProducerArcR0R1ReducibleDeadlock Detection & Recovery• Continuous monitoring and running this algorithm are expensive.• What to do when a deadlock is detected?– Abort deadlocked processes (will result in restarts).– Preempt resources from selected processes, rolling back the victims to a previous state (undoing effects of work that has been done)– Watch out for starvation.PulseGoal• To increase the kinds of deadlocks that can be detected dynamically• Uses high-level speculative execution to go forward to discover dependenciesOverview of Pulse• Kernel daemon process• Presence of long-sleeping processes trigger detection• Detection mode– Identify processes and events awaited– Fork speculative processes to see what events they generate in the futureCreating General Resource Graph with Consumable ResourcesDetails of Graph Construction• Process and Event nodes– Those processes blocked a long time.– Events – all blocking system calls modified to record the events for which caller waits(resource, condition <op, val>)• Edges– Request edges generated with event nodes.– Producer edges result from speculation• Recorded in event buffer until speculative processes terminate (normally, full buffer, timeout)• Modifying all system calls that unblock the blocking ones•