Deadlock (2)OutlineDeadlock - What to do?Deadlock Avoidance – MotivationDeadlock Avoidance AssumptionsSafe Execution SequenceSafe StateRequest Manager - NaïveRequest Manager – AvoidanceExample (from text)P1: 2 4P1: completeP0: 5 10P0: completeSlide 15P2: 2 3?P1: 2 4?P1: complete?Avoidance - Key IdeasAvoidance - Unique Resources“Claim” (Future-Request) EdgesClaim RequestRequest AssignmentSafe: No CycleWhich Requests Are Safe?A Dangerous RequestSee Any Cycles?Are “Pretend” Cycles Fatal?Slide 29Avoidance - Multi-instance ResourcesAvoiding “bank failure”No safe sequence?Banker's AlgorithmSlide 34Slide 35Avoidance - SummarySlide 37Detection & Recovery - ApproachDetection - Key IdeasScanning PolicyDetection - AlgorithmsRecovery - AbortRecovery – Can we do better?Recovery - Resource PreemptionSummary - DeadlockDeadlock - ApproachesSlide 47Summary - Starvation1Deadlock (2)Dave EckhardtBruce Maggs2Outline●Review–Prevention/Avoidance/Detection●Today–Avoidance–Detection/Recovery3Deadlock - What to do?●Prevention–Pass a law against one of four ingredients●Avoidance–Processes pre-declare usage patterns–Request manager avoids “unsafe states”●Detection/Recovery–Clean up only when trouble really happens4Deadlock Avoidance – Motivation●Deadlock prevention passes laws–Unenforceable: shared CD-writers–Annoying: lock order can induce starvation●Lots of starvation opportunities●Do we really need such strict laws?–Couldn't we be more situational?5Deadlock Avoidance Assumptions●Processes pre-declare usage–Request R1, Request R2, Release R1, Request R3, ...–Easier: declare maximal resource usage●I will never need more than 7 tape drives and 1 printer●Processes proceed to completion–Don't hold onto resources forever●Obvious–Complete in reasonable time●Worst-case-ok to stall P2 until P1 finishes6Safe Execution Sequence●P1, P2, P3, ... Pn safe sequence if–Every process Pi can be satisfied using●currently-free resources plus●resources held by P1, P2, ...Pi-1●Bound Pi's waiting–P1 will run to completion, release resources–P2 can complete with now-free + P1's + P2's–P3 can complete with now-free + P1's + P2's + P3's●Pi won't wait forever, no wait cycle, no deadlock7Safe State●System in a safe state if–there exists one safe sequence●Worst-case behavior–Everybody asks for everything at once–Follow the safe sequence●Serial execution is worst-case, not typical–Usually execute in parallel8Request Manager - Naïve●Grant request if–Enough resources are free now●Otherwise, wait–While holding resources●Which are non-preemptible●Easily leads to deadlock9Request Manager – Avoidance●Grant request if–Enough resources are free now–Enough resources would still be free●For somebody to complete●And then somebody else●And then you●Otherwise, wait–While holding resources●Which other processes can complete without10Example (from text)Who Max Has RoomP0 10 5 5P1 4 2 2P2 9 2 7Sys t e m 12 3 -"Is it safe?""Yes, it's safe; it's very safe, so safe youwouldn't believe it."11P1: 2 4 Who Max Has Room P0 10 5 5 P1 4 2 4 2 0 P2 9 2 7 System 12 3 –12P1: complete Who Max Has Room P0 10 5 5 P2 9 2 7 System 12 1 5 -13P0: 5 10Who Max Has RoomP0 10 10 0P2 9 2 7Sys t e m 12 0 -14P0: completeWho Max Has RoomP2 9 2 7Sys t e m 12 10 -Safe sequence is: P1, P0, P2So the current state is safe.15Example (from text)Who Max Has RoomP0 10 5 5P1 4 2 2P2 9 2 7Sys t e m 12 3 -Can P2 ask for more?"Is it safe?""No, it's not safe, it's very dangerous, be careful."16P2: 2 3?Who Max Has RoomP0 10 5 5P1 4 2 2P2 9 3 6Sys t e m 12 2 -Only P1 can be satisfied without waiting17P1: 2 4?Who Max Has RoomP0 10 5 5P1 4 4 0P2 9 3 6Sys t e m 12 0 -18P1: complete?Who Max Has RoomP0 10 5 5P2 9 3 6Sys t e m 12 4 -P0 and P2 can each ask for >4If both do, each will wait for other: deadlock19Avoidance - Key Ideas●Safe state–Some safe sequence exists–Prove it by finding one●Unsafe state: No safe sequence exists●Unsafe may not be fatal–Processes might exit early–Processes might not use max resources today●Rejecting all unsafe states reduces efficiency20Avoidance - Unique Resources●Unique resources instead of multi-instance?–Graph algorithm●Three edge types–Claim (future request)–Request–Assign21“Claim” (Future-Request) EdgesTape 2P1Tape 1P2Tape 3P322Claim RequestTape 2P1Tape 1P2Tape 3P323Request AssignmentTape 2P1Tape 1P2Tape 3P324Safe: No CycleTape 2P1Tape 1P2Tape 3P325Which Requests Are Safe?●Pretend to satisfy request●Look for cycles in resultant graph26A Dangerous RequestTape 2P1Tape 1P2Tape 3P327See Any Cycles?Tape 2P1Tape 1P2Tape 3P328Are “Pretend” Cycles Fatal?●Must we worry about all cycles?–Nobody is waiting on a “pretend” cycle–We don't have a deadlock●“Is it safe?”29Are “Pretend” Cycles Fatal?●No process can, without waiting–Acquire maximum-declared resource set●So no process can acquire, complete, release–(for sure, without maybe waiting)●Any new sleep could form a cycle–“No, it's not safe, it's very dangerous, be careful.”●What to do?–Don't grant the request (put the process to sleep now)30Avoidance - Multi-instance Resources●Example–N interchangeable tape drives–Could represent by N tape-drive nodes–Needless computational expense●Business credit-line model–Bank assigns maximum loan amount (“credit limit”)–Business pays interest on current borrowing amount31Avoiding “bank failure”●Bank is “ok” when there is a safe sequence●One company can–Borrow up to its credit limit–Do well–IPO–Pay back its full loan amount●And then another company, etc.32No safe sequence?●Company tries to borrow up to limit–Bank has no cash–Company C1 must wait for money C2 has–Maybe C2 must wait for money C1 has●In real life–C1 cannot make payroll–C1 goes bankrupt–Loan never paid back in full●Can model as “infinite sleep”33Banker's Algorithmint cash;int limit[N]; /* credit limit */int out[N] /* borrowed */;boolean done[N]; /* global temp! */int future; /* global temp! */int progressor (int cash) { for (i = 0; i < N; ++i) if (!done[i]) if (cash >= limit[i] - out[i]) return (i); return(-1);}34Banker's Algorithmboolean is_safe(void) { future = cash; done[0..N] = false; while (p = progressor(future)) future +=
View Full Document
Unlocking...