DOC PREVIEW
CORNELL CS 414 - Deadlocks

This preview shows page 1-2-3-4-26-27-28-54-55-56-57 out of 57 pages.

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

Unformatted text preview:

DeadlocksSystem ModelFor example: SemaphoresSlide 4Four Conditions for DeadlockReal World Deadlocks?Slide 7Avoiding deadlockTesting for deadlockSlide 10Graph reduction exampleSlide 12What about “resource” waits?Resource-wait graphsA tricky choice…Slide 16Reduction rules?This graph is reducible: The system is not deadlockedThis graph is not reducible: The system is deadlockedCommentsSome questions you might askSlide 22Slide 23Dealing with DeadlocksSlide 25Deadlock PreventionSlide 27Slide 28Slide 29Deadlock AvoidanceSlide 31Safe StateSafe State ExampleRes. Alloc. Graph AlgorithmRes. Alloc. Graph issues:Banker’s AlgorithmSlide 37Slide 38Slide 39Basic AlgorithmSafety CheckBanker’s Algorithm: ExampleSlide 43Slide 44PowerPoint PresentationDeadlock Detection & RecoveryUsing the RAG Algorithm to detect deadlocks2nd Detection AlgorithmSlide 49ExampleSlide 51Slide 52Slide 53When to run Detection Algorithm?Deadlock RecoveryFYI: Java 1.5 Concurrency ToolsWhat you should know from this week..DeadlocksSystem Model•There are non-shared computer resources–Maybe more than one instance–Printers, Semaphores, Tape drives, CPU•Processes need access to these resources–Acquire resource•If resource is available, access is granted•If not available, the process is blocked–Use resource–Release resource•Undesirable scenario:–Process A acquires resource 1, and is waiting for resource 2–Process B acquires resource 2, and is waiting for resource 1 Deadlock!For example: Semaphoressemaphore: mutex1 = 1 /* protects resource 1 */ mutex2 = 1 /* protects resource 2 */Process A code: { /* initial compute */ P(mutex1) P(mutex2) /* use both resources */ V(mutex2) V(mutex1)} Process B code: { /* initial compute */ P(mutex2) P(mutex1) /* use both resources */ V(mutex2) V(mutex1)}DeadlocksDefinition: Deadlock exists among a set of processes if –Every process is waiting for an event –This event can be caused only by another process in the set•Event is the acquire of release of another resource•Kansas 20th century law: “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone”Four Conditions for Deadlock•Coffman et. al. 1971•Necessary conditions for deadlock to exist:–Mutual Exclusion•At least one resource must be held is in non-sharable mode–Hold and wait•There exists a process holding a resource, and waiting for another–No preemption•Resources cannot be preempted–Circular wait•There exists a set of processes {P1, P2, … PN}, such that–P1 is waiting for P2, P2 for P3, …. and PN for P1All four conditions must hold for deadlock to occurReal World Deadlocks?•Truck A has to waitfor truck B tomove•NotdeadlockedReal World Deadlocks?•GridlockAvoiding deadlock•How do cars do it?–Never block an intersection–Must back up if you find yourself doing so•Why does this work?–“Breaks” a wait-for relationship–Illustrates a sense in which intransigent waiting (refusing to release a resource) is one key element of true deadlock!Testing for deadlock•Steps–Collect “process state” and use it to build a graph•Ask each process “are you waiting for anything”?•Put an edge in the graph if so–We need to do this in a single instant of time, not while things might be changing•Now need a way to test for cycles in our graphTesting for deadlock•One way to find cycles–Look for a node with no outgoing edges–Erase this node, and also erase any edges coming into it•Idea: This was a process people might have been waiting for, but it wasn’t waiting for anything else–If (and only if) the graph has no cycles, we’ll eventually be able to erase the whole graph!•This is called a graph reduction algorithmGraph reduction example8104117125610239This graph can be “fully reduced”, hence there was no deadlock at the time the graph was drawn.Obviously, things could change later!Graph reduction example•This is an example of an “irreducible” graph•It contains a cycle and represents a deadlock, although only some processes are in the cycleWhat about “resource” waits?•Processes usually don’t wait for each other.•Instead, they wait for resources used by other processes.– Process A needs access to the critical section of memory process B is using•Can we extend our graphs to represent resource wait?Resource-wait graphs•We’ll use two kinds of nodes•A process: P3 will be represented as:•A resource: R7 will be represented as:–A resource often has multiple identicalunits, such as “blocks of memory”–Represent these as circles in the box•Arrow from a process to a resource: “I want k units of this resource.” Arrow to a process:this process holds k units of the resource–P3 wants 2 units of R737 2A tricky choice…•When should resources be treated as “different classes”?–To be in the same class, resources do need to be equivalent•“memory pages” are different from “printers”–But for some purposes, we might want to split memory pages into two groups•Fast memory. Slow memory–Proves useful in doing “ordered resource allocation”Resource-wait graphs11 422 2314115Reduction rules?•Find a process that can have all its current requests satisfied (e.g. the “available amount” of any resource it wants is at least enough to satisfy the request)•Erase that process (in effect: grant the request, let it run, and eventually it will release the resource)•Continue until we either erase the graph or have an irreducible component. In the latter case we’ve identified a deadlockThis graph is reducible: The system is not deadlocked11 422 2314111This graph is not reducible: The system is deadlocked11 422 2314115Comments•It isn’t common for systems to actually implement this kind of test •However, we’ll use a version of the resource reduction graph as part of an algorithm called the “Banker’s Algorithm”.•Idea is to schedule the granting of resources so as to avoid potentially deadlock statesSome questions you might ask•Does the order in which we do the reduction matter?–Answer: No. The reason is that if a node is a candidate for reduction at step i, and we don’t pick it, it remains a candidate for reduction at step i+1–Thus eventually, no matter what order we do it in, we’ll reduce by every node where reduction is


View Full Document

CORNELL CS 414 - Deadlocks

Documents in this Course
Security

Security

49 pages

Processes

Processes

24 pages

Threads

Threads

5 pages

Threads

Threads

29 pages

Deadlocks

Deadlocks

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