L14 Deadlock

Category: Entertainment

Presentation Description

No description available.


By: pratik030492 (122 month(s) ago)

how can i download dis ppt????????

Presentation Transcript

Deadlock (2): 

Deadlock (2) Dave Eckhardt Bruce Maggs


Outline Review Prevention/Avoidance/Detection Today Avoidance Detection/Recovery

Deadlock - What to do?: 

Deadlock - 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 happens

Deadlock Avoidance – Motivation: 

Deadlock Avoidance – Motivation Deadlock prevention passes laws Unenforceable: shared CD-writers Annoying: lock order can induce starvation Lots of starvation opportunities Do we really need such strict laws? Couldn't we be more situational?

Deadlock Avoidance Assumptions: 

Deadlock Avoidance Assumptions Processes pre-declare usage Request R1, Request R2, Release R1, Request R3, ... Easier: declare maximal resource usage I will never need more than 7 tape drives and 1 printer Processes proceed to completion Don't hold onto resources forever Obvious Complete in reasonable time Worst-case-ok to stall P2 until P1 finishes

Safe Execution Sequence: 

Safe Execution Sequence P1, P2, P3, ... Pn safe sequence if Every process Pi can be satisfied using currently-free resources plus resources held by P1, P2, ...Pi-1 Bound Pi's waiting P1 will run to completion, release resources P2 can complete with now-free + P1's + P2's P3 can complete with now-free + P1's + P2's + P3's Pi won't wait forever, no wait cycle, no deadlock

Safe State: 

Safe State System in a safe state if there exists one safe sequence Worst-case behavior Everybody asks for everything at once Follow the safe sequence Serial execution is worst-case, not typical Usually execute in parallel

Request Manager - Naïve: 

Request Manager - Naïve Grant request if Enough resources are free now Otherwise, wait While holding resources Which are non-preemptible Easily leads to deadlock

Request Manager – Avoidance: 

Request Manager – Avoidance Grant request if Enough resources are free now Enough resources would still be free For somebody to complete And then somebody else And then you Otherwise, wait While holding resources Which other processes can complete without

Example (from text): 

Example (from text)

P1: 2  4: 

P1: 2  4

P1: complete: 

P1: complete

P0: 5  10: 

P0: 5  10

P0: complete: 

P0: complete

Example (from text): 

Example (from text)

P2: 2  3?: 

P2: 2  3?

P1: 2  4?: 

P1: 2  4?

P1: complete?: 

P1: complete?

Avoidance - Key Ideas: 

Avoidance - 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 efficiency

Avoidance - Unique Resources: 

Avoidance - Unique Resources Unique resources instead of multi-instance? Graph algorithm Three edge types Claim (future request) Request Assign

“Claim” (Future-Request) Edges: 

'Claim' (Future-Request) Edges

Claim  Request: 

Claim  Request

Request  Assignment: 

Request  Assignment

Safe: No Cycle: 

Safe: No Cycle

Which Requests Are Safe?: 

Which Requests Are Safe? Pretend to satisfy request Look for cycles in resultant graph

A Dangerous Request: 

A Dangerous Request

See Any Cycles?: 

See Any Cycles?

Are “Pretend” Cycles Fatal?: 

Are '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?'

Are “Pretend” Cycles Fatal?: 

Are '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)

Avoidance - Multi-instance Resources: 

Avoidance - 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 amount

Avoiding “bank failure”: 

Avoiding '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.

No safe sequence?: 

No 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'

Banker's Algorithm: 

Banker's Algorithm int cash; int limit[N]; /* credit limit */ int out[N] /* borrowed */; boolean done[N]; /* global temp! */ int future; /* global temp! */ int progressor (int cash) { for (i = 0; i andlt; N; ++i) if (!done[i]) if (cash andgt;= limit[i] - out[i]) return (i); return(-1); }

Banker's Algorithm: 

Banker's Algorithm boolean is_safe(void) { future = cash; done[0..N] = false; while (p = progressor(future)) future += borrowed[p]; done[p] = true; return (done[0..N] == true) }

Banker's Algorithm: 

Banker's Algorithm Can we loan more money to a company? Pretend we did update cash and out[i] Is it safe? Yes: lend more money No: un-do to pre-pretending state, sleep Multi-resource Version Generalizes easily to N independent resource types See text

Avoidance - Summary: 

Avoidance - Summary Good news - No deadlock No static 'laws' about resource requests Allocations flexible according to system state Bad news Processes must pre-declare maximum usage Avoidance is conservative Many 'unsafe' states are almost safe System throughput reduced – extra sleeping 3 processes, can allocate only 2 tape drives!?!?

Deadlock - What to do?: 

Deadlock - 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 happens

Detection & Recovery - Approach: 

Detection andamp; Recovery - Approach Don't be paranoid Don't refuse requests that might lead to trouble (someday) Most things work out ok in the end Even paranoids have enemies Sometimes a deadlock will happen Need a plan for noticing Need a policy for reacting Somebody must be told 'try again later'

Detection - Key Ideas: 

Detection - Key Ideas 'Occasionally' scan for wait cycles Expensive Must lock out all request/allocate/deallocate activity Global mutex is the 'global variable' of concurrency Detecting cycles is an N-squared kind of thing

Scanning Policy: 

Scanning Policy Throughput balance Too often - system becomes (very) slow Before every sleep? Only in small systems Too rarely - system becomes (extremely) slow Policy candidates Scan every andlt;intervalandgt; Scan when CPU is 'too idle'

Detection - Algorithms: 

Detection - Algorithms Detection: Unique Resources Search for cycles in resource graph (see above) Detection: Multi-instance Resources Slight variation on Banker's Algorithm (see text) Now what? Abort Preempt

Recovery - Abort: 

Recovery - Abort Evict processes from the system All processes in the cycle? Simple andamp; blame-free policy Lots of re-execution work later Just one process in the cycle? Often immediately creates a smaller cycle – re-scan? Which one? Priority? Work remaining? Clean-up work?

Recovery – Can we do better?: 

Recovery – Can we do better? Motivation Re-running processes is expensive Long-running tasks may never complete Starvation

Recovery - Resource Preemption: 

Recovery - Resource Preemption Tell some process(es) lock(R347) ' 'Deadlock!' Policy question: which one? Lowest-numbered?  starvation! What does 'Deadlock!' mean? Can't just retry the request!! Must release other resources, try later Forced release may require 'rollback' (yuck)

Summary - Deadlock: 

Summary - Deadlock Deadlock is... Set of processes Each one waiting for something held by another Four 'ingredients' Three approaches (aside from 'Hmmm...andlt;rebootandgt;')

Deadlock - Approaches: 

Deadlock - Approaches Prevention - Pass a law against one of: Mutual exclusion (right!) Hold andamp; wait (maybe...) No preemption (maybe?) Circular wait (sometimes)

Deadlock - Approaches: 

Deadlock - Approaches Avoidance - 'Stay out of danger' Not all 'danger' turns into trouble Detection andamp; Recovery Frequency: delicate balance Preemption is hard Rebooting Was it really hung?

Summary - Starvation: 

Summary - Starvation Starvation is a ubiquitous danger Prevention is one extreme Need something 'illegal'? 'Illegal' = Eternal starvation! Detection andamp; Recovery Less structural starvation Still must make good choices

authorStream Live Help