DOC PREVIEW
U of I CS 241 - Deadlock Issues

This preview shows page 1-2-19-20 out of 20 pages.

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

Unformatted text preview:

CS241 System Programming Deadlock Issues (2)ContentAdministrative NotesDeadlock Modeling (1)Deadlock Modeling (2)Deadlock Modeling (3)Deadlock Modeling (4)Resource Allocation Graph (multiple resource types)Deadlock ModelStrategiesThe Ostrich AlgorithmAlgorithms to deal with DeadlockDeadlock DetectionDetection with One Resource of Each Type (1)Wait for GraphsRecovery from Deadlock (1)Recovery from Deadlock (2)Deadlock Prevention: Havender's AlgorithmsSummary: Deadlock PreventionReminderCS241 System ProgrammingDeadlock Issues (2)Klara NahrstedtLecture 172/27/200601/14/19 CS 241 - System Programming, Klara Nahrstedt2ContentDeadlock ModelingDeadlock Detection and RecoveryDeadlock Prevention01/14/19 CS 241 - System Programming, Klara Nahrstedt3Administrative NotesMP2 on Monday, February 27Homework 1 – Deadline March 6 – Individual Effort (No Collaboration with your MP partner or other pairs partners)Quiz 5 – March 3, 2006–Covers Signals, Timers and Deadlock Tanenbaum 3.3.1, 3.3.2, 3.3.3, 3.3.4 and 3.3.5R&R: Signals 8.1-8.5, R&R: Signal Handling and Threads 13.5R&R: 9.1, 9.2, 9.3, 9.4, 9.5Lecture Notes: lec13-sched, lec14-sched, lec15-sched, lec16-deadlock, lec17-deadlock01/14/19 CS 241 - System Programming, Klara Nahrstedt4Deadlock Modeling (1) 1972 – Holt showed that the four conditions can be modeled using directed graphs Graph have two kinds of nodes–Processes –Resources Graph’s arcs have two meanings:–Arc from resource node to process node = process holds resource (i.e., resource has been assigned to process and process is holding it)–Arc from process node to resource node = process requests resource (i.e., process is currently blocked waiting for that resource)01/14/19 CS 241 - System Programming, Klara Nahrstedt5Deadlock Modeling (2)Modeled with directed graphs–resource R assigned to process A–process B is requesting/waiting for resource S–process C and D are in deadlock over resources T and U01/14/19 CS 241 - System Programming, Klara Nahrstedt6How deadlock occursA B CDeadlock Modeling (3)01/14/19 CS 241 - System Programming, Klara Nahrstedt7Deadlock Modeling (4)How deadlock can be avoided(o) (p) (q)01/14/19 CS 241 - System Programming, Klara Nahrstedt8Resource Allocation Graph(multiple resource types)01/14/19 CS 241 - System Programming, Klara Nahrstedt9Deadlock Model01/14/19 CS 241 - System Programming, Klara Nahrstedt10StrategiesStrategies for dealing with Deadlocks1. just ignore the problem altogether2. detection and recovery3. dynamic avoidance •careful resource allocation4. prevention •negating one of the four necessary conditions01/14/19 CS 241 - System Programming, Klara Nahrstedt11The Ostrich AlgorithmPretend there is no problemReasonable if –deadlocks occur very rarely –cost of prevention is highUNIX and Windows takes this approachIt is a trade off between –convenience–correctness01/14/19 CS 241 - System Programming, Klara Nahrstedt12Algorithms to deal with DeadlockPrevention–design a system in such a way that deadlocks cannot occur, at least with respect to serially reusable resources. Avoidance– impose less stringent conditions than for prevention, allowing the possibility of deadlock, but sidestepping it as it approaches. Detection– in a system that allows the possibility of deadlock, determine if deadlock has occurred, and which processes and resources are involved. Recovery–after a deadlock has been detected, clear the problem, allowing the deadlocked processes to complete and the resources to be reused. Usually involves destroying the affected processes and starting them over.01/14/19 CS 241 - System Programming, Klara Nahrstedt13Deadlock DetectionCheck to see if a deadlock has occurred!Single resource per type–Can use wait-for graph–Check for cycles–O(n2)01/14/19 CS 241 - System Programming, Klara Nahrstedt14Detection with One Resource of Each Type (1)Note the resource ownership and requestsA cycle can be found within the graph, denoting deadlockTT01/14/19 CS 241 - System Programming, Klara Nahrstedt15Wait for GraphsResource Allocation Graph Corresponding Wait For Graph01/14/19 CS 241 - System Programming, Klara Nahrstedt16Recovery from Deadlock (1)Recovery through preemption–take a resource from some other process–depends on nature of the resourceRecovery through rollback–checkpoint a process periodically–use this saved state –restart the process if it is found deadlocked01/14/19 CS 241 - System Programming, Klara Nahrstedt17Recovery from Deadlock (2)Recovery through killing processes–crudest but simplest way to break a deadlock–kill one of the processes in the deadlock cycle–the other processes get its resources –choose process that can be rerun from the beginning01/14/19 CS 241 - System Programming, Klara Nahrstedt18Deadlock Prevention: Havender's Algorithms Break one of the deadlock conditions. –Mutual exclusionSolution: exclusive use of resources is an important feature, but for some resources (virtual memory, virtual disks, CPU), it is possible.–Hold-and-Wait conditionSolution: Force each process to request all required resources at once. It cannot proceed until all resources have been acquired. –No preemption conditionSolution: 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 them. –Circular wait conditionSolution: All resource types are numbered. Processes must request resources in numerical order01/14/19 CS 241 - System Programming, Klara Nahrstedt19Summary: Deadlock Preventioncondition How to break itMutual Exclusion Spool everythingHold and wait Request all resources initiallyNo preemption Take resources awayCircular wait Order resources numerically01/14/19 CS 241 - System Programming, Klara Nahrstedt20ReminderHomework 1 due 3/6/06Quiz 5 –


View Full Document

U of I CS 241 - Deadlock Issues

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 Issues
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 Issues 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 Issues 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?