DOC PREVIEW
UCSD CSE 120 - Deadlocks

This preview shows page 1-2-3-4-5-6 out of 19 pages.

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

Unformatted text preview:

1Lecture 6DeadlocksOctober 14, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 8 (on Deadlock)Midterm is on Tuesday of next week (Oct 21)• Covers all Lectures including this week• Covers Programming Assignment #1• Sample midterm posted on class web page3What is Deadlock?The state of a set of permanently blocked processes• Unblocking of one relies on progress of another• But none can make progress!Example• Processes A and B• Resources X and Y• A holding X, waiting for Y• B holding Y, waiting for X• Each is waiting for the other; will wait foreverAXYBwaitingforwaitingforholdingholding4Traffic Jam as Example of DeadlockAZBDWCY XResource AllocationGraphW XY ZCABDCars deadlockedin an intersection5More Examples of DeadlockMemory (a reusable resource)• total memory = 200KB• P1 requests 80KB• P2 requests 70KB• P1 requests 60KB (wait)• P2 requests 80KB (wait)Messages (a consumable resource)• P1: receive M2 from P2• P2: receive M1 from P1P1P2P1M1M2P26Conditions for DeadlockMutual Exclusion• Only one process may use a resource at a timeHold-and-Wait• Process holds resources while waiting for othersNo Preemption• Can’t take a resource away from a processCircular Wait• The waiting processes form a cycle7How to Attack the Deadlock ProblemDeadlock Prevention• Prevent any possibility of a deadlockDeadlock Avoidance• Avoid situations that lead to deadlockDeadlock Detection• Don’t try to stop deadlocks• Rather, if they happen, detect and resolve8Deadlock PreventionSimply prevent any one of the conditions for deadlock• Mutual exclusion– Relax where sharing is possible• Hold-and-wait– Get all resources simultaneously, wait until all free• No preemption– Allow resources to be taken away• Circular wait– Order all the resources, force ordered acquisition9Preventing a Traffic JamTo apply deadlockprevention to trafficjam problem, just adda traffic light!Which condition is beingprevented?CABD10Deadlock AvoidanceWorks with incremental resource requests• Resources are asked for in increments• Do not grant request that can lead to a deadlockRequires knowledge of maximum resource requirements11Banker’s Algorithm: ConceptsSystem has a fixed number of processes and resources• each process has zero or more resources allocatedSystem state: either safe or unsafe• depends on allocation of resources to processesSafe state• can avoid deadlock by certain order of executionUnsafe state• deadlock is possible (but not necessarily certain)12Safe, Unsafe, and Deadlock StatesUnsafeSafeDeadlockP13Banker’s AlgorithmGiven• a process/resource claim matrix• a process/resource allocation matrix• a resource availability vectorIs there a sequence of process executions such that• a process can run to completion, return resources• resources can then be used by another to complete• eventually, all the processes complete?14Example of a Safe StateCurrent state Claim AllocationP1P2P3P4 P1P2P3P4Avail TotalR13 6 3 4 1 6 2 0 0 9R22 1 1 2 0 1 1 0 1 3R32 3 4 2 0 2 1 2 1 6This is a Safe State• Who can run to completion? P2• After P2 completes, it’s resources are returned• Next select P1, then P3, then P415Example of an Unsafe StateCurrent state Claim AllocationP1P2P3P4 P1P2P3P4Avail TotalR13 6 3 4 1 5 2 0 1 9R22 1 1 2 0 1 1 0 1 3R32 3 4 2 0 1 1 2 2 6So far, this is a safe state, but …• if P2 asks for 1 unit of R1 and 1 unit of R3: safe• if P1 asks for 1 unit of R1 and 1 unit of R3: unsafe• no one may be able to complete: possible deadlock16Avoiding a Traffic JamTo apply deadlockavoidance to trafficjam problem, allow atmost 3 cars to enterintersectionWhat kind of request isbeing denied?CABD17Deadlock Detection and RecoveryDon’t do anything special to prevent or avoid deadlocks• If they happen, they happen• Periodically, try to detect if a deadlock occurred• Do something (or even nothing) about itReasoning• Deadlocks rarely happen• Cost of prevention or avoidance is not worth it• Deal with them in special way (may be very costly)Most systems take this approach!18Detecting DeadlocksConstruct “wait-for” graph• Construct resourceallocation graph• Remove resource nodes• If cycle, deadlockRequires• identifying all resourcesand tracking their use• periodically runningdetection algorithmAZBDWCY XA BD C19Recovery from DeadlockAbort all deadlocked processes• Will remove deadlock, but drastic and costlyAbort deadlocked processes one-at-at-time• Do so until deadlock goes away (need to detect)• What order should processes be aborted?What happens to resources in inconsistent states?• files partially written• interrupted message (e.g., file)


View Full Document

UCSD CSE 120 - Deadlocks

Documents in this Course
Threads

Threads

14 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Processes

Processes

18 pages

Threads

Threads

29 pages

Security

Security

16 pages

Paging

Paging

13 pages

Processes

Processes

32 pages

Lecture 2

Lecture 2

13 pages

Paging

Paging

8 pages

Threads

Threads

14 pages

Paging

Paging

13 pages

Paging

Paging

26 pages

Paging

Paging

13 pages

Lecture

Lecture

13 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Security

Security

17 pages

Threads

Threads

15 pages

Processes

Processes

34 pages

Structure

Structure

10 pages

Lecture 3

Lecture 3

13 pages

Lecture 1

Lecture 1

28 pages

Threads

Threads

15 pages

Paging

Paging

30 pages

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