DOC PREVIEW
U of I CS 241 - Deadlock Handling

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 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 26 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 26 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 26 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 26 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 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Deadlock HandlingCS241 AdministrativeReview: Deadlock ModelingDeadlock ModelingResource Allocation Graph (multiple resource types)StrategiesDeadlock PreventionDeadlock Prevention: Havender's AlgorithmsMutual ExclusionWait-for ConditionSlide 11No Preemption ConditionSlide 13Circular Wait ConditionSlide 15Deadlock AvoidanceSlide 17Safe State and Unsafe StateExample (Safe Sequence)Example (Unsafe State) – let’s assume Max/Need changes for the processesDeadlock DetectionWait for GraphsDeadlock RecoveryRecovery From DeadlockThe Ostrich AlgorithmSummaryCS 241 Spring 2007System Programming 1Deadlock Handling Lecture 22Klara Nahrstedt2CS241 AdministrativeRead Stallings Chapter 6 about Deadlock HandlingRegular Quiz 7 this week on Queuing and Deadlock HandlingDiscussion Sessions this week (on Queuing and File Systems – needed for LMP1)LMP1 (Long Machine Problem) starts today LMP1 is part of three major assignments (LMP1, LMP2, LMP3 which together will build distributed file system services) LMP1 will be split into two parts, PART I and overall LMP1 delivery. You will need to deliver PART I by Wednesday, March 28 and the final overall LMP1 will be due by April 2. For each delivery you will receive points. LMP1 quiz will be on April 2. The graders will provide some feedback on the Part I that should assist you in the overall LMP1 delivery.3Review: Deadlock Modeling Modeled with directed graphsresource R assigned to process Aprocess B is requesting/waiting for resource Sprocess C and D are in deadlock over resources T and Uassignrequest4How deadlock occursA B CDeadlock Modeling5Resource Allocation Graph(multiple resource types)6StrategiesStrategies for dealing with Deadlocksprevention negating one of the four necessary conditionsdynamic avoidance careful resource allocationdetection and recovery7Deadlock PreventionPrevention: design a system in such a way that deadlocks cannot occur, at least with respect to serially reusable resourcesHaving rules so that a deadlock can NEVER happen8Deadlock Prevention: Havender's AlgorithmsIf any one of the conditions for deadlock (with reusable resources) is denied, deadlock is impossible9Mutual ExclusionWe don't want to deny this; exclusive use of resources is an important feature. However, sometimes its possible---Virtual memoryVirtual network connectionsVirtual diskCachesCPU preemption10Wait-for ConditionForce each process to request all required resources at once. It cannot proceed until all resources have been acquired11While did not get all resources{ P(mutex) Try to pick up all resources if did not get all resources put resources back V(mutex) wait a while and try again}Use resourcesP(mutex)Release all resourcesV(mutex12No Preemption Condition If a process holding some reusable resources makes a further request which is denied, and it wishes to wait for the new resources to become available, it must release all resources currently held and, if necessary, request them again along with the new resources. Thus, resources are removed from a process holding them13while need a resource { P(mutex) Test to see if resource is free if free, grab resource else release all resources V(mutex) Wait a while and try again }14Circular Wait ConditionAll resource types are numberedProcesses must request resources in numerical orderif a resource of order N is held, the only resources which can be requested must be of order > N15P(s1)P(s2)WorkV(s2)V(s1)P(s2)P(s3)WorkV(s3)V(s2)P(s1) P(s3)WorkV(s3)V(s1)Process 1 Process 2 Process 316Deadlock Avoidance Avoidance: impose less stringent conditions than for prevention, allowing the possibility of deadlock, but sidestepping it as it approachesBanker algorithmEach process provides the maximum number of resources for each typeFor each request, the system checks if granting this request may lead to a deadlock in the worse caseIf yes, not granting the requestIf no, granting the request17Deadlock AvoidanceThe system needs to know the resource ahead of timeBanker Algorithm (Dijkstra, 1965) Each customer tells banker the maximum number of resources it needs Customer borrows resources from banker Customer returns resources to banker Customer eventually pays back loan Banker only lends resources if the system will be in a safe state after the loan Safe state - there is a lending sequence such that all customers can take out a loan Unsafe state - there is a possibility of deadlock18Safe State and Unsafe StateSafe Statethere is some scheduling order in which every process can run to completion even if all of them suddenly request their maximum number of resources immediatelyFrom safe state, the system can guarantee that all processes will finishUnsafe state: no such guaranteeNot deadlocked stateSome process may be able to complete19Example (Safe Sequence) Res. Alloc Max Need Available (Banker) Processes | A B | A B | A B | A B ---------------------------------------------------------------------------------------------------------------------P1 3 0 5 3 2 3 6 5P2 2 2 6 5 4 3P3 1 3 9 8 8 5P4 0 5 8 5 8 0Sequence: P1 can go (borrows from Banker A(2) and B(3), since Need.A(2) is less than Available A(6) and Need.B(3) < Available.B(5). After lending, Available will be A(4), B(2)). After P1 finishes it releases Allocated Resources A(3) and B(0) to the banker, and so the banker will have A(8) = A(6) + A(3) and B(5)=B(5)+B(0) availableP2 can go (borrows from Banker A(4) and B(3)). After P2 finishes it releases the allocated resource A(1) and B(3) to the banker and available will be A(11), B(7)P3 can go (borrows from Banker A(8) and B(5), since Need.A(8) < Available.A(11) and Need.B(5) < Available.B(7)). After P3 finishes, it releases the allocated resources to the banker and Available resources will be A(12) = A(11) + A(1) and B(10)=B(7+B(3)P4 can go because P4 can borrow from Banker Need.A(8) < Available.A(12) and Need.B(0)<Available.B(10). After P4 finishes, the resources are released, and Banker will have available A(12) and B(15)Hence, there exists a safe sequence with this snapshot of resources and processes. The safe sequence is P1, P2, P3, P420Example (Unsafe State) – let’s assume Max/Need


View Full Document

U of I CS 241 - Deadlock Handling

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Deadlock Handling
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 Deadlock Handling 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 Deadlock Handling 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?