DOC PREVIEW
CMU CS 15410 - Lecture

This preview shows page 1-2-3-23-24-25-26-47-48-49 out of 49 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 49 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 491Deadlock (2)Dave EckhardtBruce Maggs1Outline●Review–Prevention/Avoidance/Detection●Today–Avoidance–Detection/Recovery1Deadlock - 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 happens1Deadlock Avoidance – Motivation●Deadlock prevention passes laws–Unenforceable: shared CD-writers???–Annoying●Mandatory lock-acquisition order may induce starvation–Locked 23, 24, 25, ... 88, 89, now must lock 0...●Lots of starvation opportunities●Do we really need such strict laws?–Couldn't we be more situational?1Deadlock Avoidance Assumptions1. Processes pre-declare usage patterns–Could enumerate all paths through allocation space●Request R1, Request R2, Release R1, Request R3, ...●Request R1, Request R3, Release R3, Request R1, ...–Easier: declare maximal resource usage●I will never need more than 7 tape drives and 1 printer1Deadlock Avoidance Assumptions2. Processes proceed to completion–Don't hold onto resources forever●Obvious–Complete in “reasonable” time●So it is ok, if necessary, to stall P2 until P1 completes●We will try to avoid this1Safe Execution Sequence●(P1, P2, P3, ... Pn) is a safe sequence if–Every process Pi can be satisfied using●currently-free resources F plus●resources currently held by P1, P2, ...Pi-1●Pi's waiting is bounded by this sequence–P1 will run to completion, release resources–P2 can complete with F + P1's + P2's–P3 can complete with F + P1's + P2's + P3's–Pi won't wait forever, no wait cycle, no deadlock1Safe State●System in a safe state if–there exists at least one safe sequence●Worst-case situation–Every process asks for every resource at once–Follow the safe sequence (run processes serially)●Slow, but not as slow as a deadlock!●Serial execution is worst-case, not typical–Usually execute in parallel1Request Manager - Naïve●Grant request if–Enough resources are free now●Otherwise, tell requesting process to wait–While holding resources●Which are non-preemptible, ...●Easily leads to deadlock1Request Manager – Avoidance●Grant request if–Enough resources are free now, and–Enough resources would still be free●For some process to complete and release resources●And then another one●And then you●Otherwise, wait–While holding resources...●...which we already prooved other processes can complete without1Example (from text)Who Max Has RoomP0 10 5 5P1 4 2 2P2 9 2 7System 12 3 -" Is it safe?"" Yes, it's safe; it's very safe, so safe you wouldn'tbelieve it."Max declaredHas allocatedRoom (Max-Has)1P1: 2  4Who Max Has Room Who Max Has RoomP010 5 5 P0 10 5 5P14 2 2P1 4 4 0P29 2 7 P2 9 2 7System12 3-System 121-1P1: CompleteWho Max Has Room Who Max Has RoomP010 5 5 P0 10 55P14 4 0P29 2 7 P2 9 2 7System12 1-System 125-1P0: 5  10Who Max Has Room Who Max Has RoomP010 5 5P0 10 10 0P29 2 7 P2 9 2 7System12 5-System 120-1P0: CompleteWho Max Has Room Who Max Has RoomP010 10 0P29 2 7 P2 9 2 7System12 0-System 1210-P1, P0, P2 is a safe sequence.So the system was in a safe state.1Example (from text)Who Max Has RoomP0 10 5 5P1 4 2 2P2 9 2 7Sys t em 12 3 -"Can P2 ask for more?" Is it safe?"" No, it's not safe, it's very dangerous, be careful."1P2: 2  3?Who Max Has Room Who Max Has RoomP010 5 5 P0 10 5 5P14 2 2 P1 4 2 2P29 2 7P2 9 3 6System12 3-System 122-Only P1 can be satisfied without waiting.1P1: 2  4?Who Max Has Room Who Max Has RoomP010 5 5 P0 10 5 5P14 2 2 P1 4 4 0P29 3 6P2 9 3 6System12 2-System 120-1P1: Complete?Who Max Has Room Who Max Has RoomP010 5 5 P0 10 5 5P14 4 0P29 3 6 P2 9 3 6System12 0-System 124-Problem: P0 and P2 are allowed to ask for >4.If both do, deadlock.1Avoidance - 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 efficiency1Avoidance - Unique Resources●Unique resources instead of multi-instance?–Graph algorithm●Three edge types–Claim (future request)–Request–Assign1“Claim” (Future-Request) EdgesTape 2P1Tape 1P2Tape 3P31Claim  RequestTape 2P1Tape 1P2Tape 3P31Request  AssignmentTape 2P1Tape 1P2Tape 3P31Safe: No CycleTape 2P1Tape 1P2Tape 3P31Which Requests Are Safe?●Pretend to satisfy request●Look for cycles in resultant graph1A Dangerous RequestTape 2P1Tape 1P2Tape 3P31See Any Cycles?Tape 2P1Tape 1P2Tape 3P31Are “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?”1Are “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)1Avoidance - 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 amount1Avoiding “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.1No 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”1Banker's Algorithmint cash;int limit[N]; /* credit limit */int out[N] /* borrowed */;boolean done[N]; /* global temp! */int future; /*


View Full Document

CMU CS 15410 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?