L14 Deadlock

Information about L14 Deadlock

Published on September 17, 2007

Author: Flemel

Source: authorstream.com

Content

Deadlock (2):  Deadlock (2) Dave Eckhardt Bruce Maggs Outline:  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

Related presentations


Other presentations created by Flemel

What is a Play
17. 10. 2007
0 views

What is a Play

Jeopardy HIV STD HPV
06. 08. 2007
0 views

Jeopardy HIV STD HPV

Training School Bus Driver
17. 09. 2007
0 views

Training School Bus Driver

semantics
17. 09. 2007
0 views

semantics

philosophy
27. 09. 2007
0 views

philosophy

como rezar rosario
01. 10. 2007
0 views

como rezar rosario

WorldMuslimCongress Mecca
02. 10. 2007
0 views

WorldMuslimCongress Mecca

sentence
03. 10. 2007
0 views

sentence

DHL presentation
11. 10. 2007
0 views

DHL presentation

VIPAR Presentation
15. 10. 2007
0 views

VIPAR Presentation

annee2005
16. 10. 2007
0 views

annee2005

PrÃsentation JBaer 20avr
17. 10. 2007
0 views

PrÃsentation JBaer 20avr

Panel 17 8 Taking the Pulse
17. 10. 2007
0 views

Panel 17 8 Taking the Pulse

tom eddy
17. 09. 2007
0 views

tom eddy

grass
22. 10. 2007
0 views

grass

CXPBrasil June2005
26. 11. 2007
0 views

CXPBrasil June2005

Theor Astrophysics
29. 11. 2007
0 views

Theor Astrophysics

Carnival Brasil
30. 11. 2007
0 views

Carnival Brasil

boon
26. 10. 2007
0 views

boon

kumar eng
26. 10. 2007
0 views

kumar eng

talking freight
07. 11. 2007
0 views

talking freight

LHC Net meet 101205ppt
28. 09. 2007
0 views

LHC Net meet 101205ppt

cmd04 VW
16. 11. 2007
0 views

cmd04 VW

11 OrgsSimAndReal
22. 11. 2007
0 views

11 OrgsSimAndReal

PolComm1
08. 10. 2007
0 views

PolComm1

CAFTA training
03. 01. 2008
0 views

CAFTA training

2 casting forming
04. 01. 2008
0 views

2 casting forming

Sales Training II Final
11. 08. 2007
0 views

Sales Training II Final

Sonnet
11. 08. 2007
0 views

Sonnet

sommers rev oct 19 ppt
11. 08. 2007
0 views

sommers rev oct 19 ppt

Scherrer
11. 08. 2007
0 views

Scherrer

Topic 12 Genetic Disorders 3
11. 08. 2007
0 views

Topic 12 Genetic Disorders 3

Sonnet MLA
11. 08. 2007
0 views

Sonnet MLA

Autism AHistory
05. 01. 2008
0 views

Autism AHistory

Shortage of Girls in China
11. 08. 2007
0 views

Shortage of Girls in China

3 BasicRepro2
07. 12. 2007
0 views

3 BasicRepro2

How Adults Learn
06. 08. 2007
0 views

How Adults Learn

Introversion Turned Inside Out
06. 08. 2007
0 views

Introversion Turned Inside Out

Jenkins
06. 08. 2007
0 views

Jenkins

HCR 107 Overheads
06. 08. 2007
0 views

HCR 107 Overheads

N REG SANIT INT
22. 10. 2007
0 views

N REG SANIT INT

022 Hexapods for robot soccer
31. 12. 2007
0 views

022 Hexapods for robot soccer

Sung Su Truss Bridge
01. 01. 2008
0 views

Sung Su Truss Bridge

Slides KateSteinbeck
11. 08. 2007
0 views

Slides KateSteinbeck

Senate Hearing 2000
11. 08. 2007
0 views

Senate Hearing 2000

William Graham
23. 11. 2007
0 views

William Graham

truman7
29. 12. 2007
0 views

truman7

231nm02
29. 09. 2007
0 views

231nm02

chpt 1 ppt
24. 02. 2008
0 views

chpt 1 ppt

HIV AIDS in Europe
06. 08. 2007
0 views

HIV AIDS in Europe

Heidtke
29. 02. 2008
0 views

Heidtke

NIBSSep021
28. 12. 2007
0 views

NIBSSep021

07 Uae Profilers in TRMM GV Gage
17. 09. 2007
0 views

07 Uae Profilers in TRMM GV Gage

Protista
26. 03. 2008
0 views

Protista

original
07. 04. 2008
0 views

original

slides prog 71
11. 08. 2007
0 views

slides prog 71

wb english
27. 03. 2008
0 views

wb english

Malaria Blue Sky Final Slideshow
30. 03. 2008
0 views

Malaria Blue Sky Final Slideshow

Session1 Parenteau
10. 04. 2008
0 views

Session1 Parenteau

BS3008w1
13. 04. 2008
0 views

BS3008w1

healthcare
06. 08. 2007
0 views

healthcare

SRM Presentation Jim Hanco
14. 04. 2008
0 views

SRM Presentation Jim Hanco

finnews284 2
16. 04. 2008
0 views

finnews284 2

FX Hedging Strategies1
17. 04. 2008
0 views

FX Hedging Strategies1

ioko times showreel
22. 04. 2008
0 views

ioko times showreel

23 Practice Problems
07. 11. 2007
0 views

23 Practice Problems

PE2 U6 R
14. 02. 2008
0 views

PE2 U6 R

ASUD
18. 06. 2007
0 views

ASUD

armi leggere
18. 06. 2007
0 views

armi leggere

apq
18. 06. 2007
0 views

apq

apicorso
18. 06. 2007
0 views

apicorso

aeipres
18. 06. 2007
0 views

aeipres

901059 Kids Share ppt
18. 06. 2007
0 views

901059 Kids Share ppt

Sporting tips
18. 06. 2007
0 views

Sporting tips

semi2
18. 06. 2007
0 views

semi2

Saker Motorports USALLC
18. 06. 2007
0 views

Saker Motorports USALLC

Running on Fumes
18. 06. 2007
0 views

Running on Fumes

FBranca Luxembourg 3mar
26. 11. 2007
0 views

FBranca Luxembourg 3mar

Sisvalsoc
18. 06. 2007
0 views

Sisvalsoc

Shalom Auschwitz Ginocchio
18. 06. 2007
0 views

Shalom Auschwitz Ginocchio

scrittura
18. 06. 2007
0 views

scrittura

scheda unipol
18. 06. 2007
0 views

scheda unipol

satzherstellung
18. 06. 2007
0 views

satzherstellung

uss presentation
02. 01. 2008
0 views

uss presentation

HandsOnWMS nov
16. 10. 2007
0 views

HandsOnWMS nov

hatikvah E2 short
22. 10. 2007
0 views

hatikvah E2 short

amer deadlocks
17. 09. 2007
0 views

amer deadlocks

deadlocks
17. 09. 2007
0 views

deadlocks

Chapter 03
17. 09. 2007
0 views

Chapter 03

Slides Egidi
18. 06. 2007
0 views

Slides Egidi

Ballanti Diagramaps 070704
18. 06. 2007
0 views

Ballanti Diagramaps 070704

1111 123080220071234
24. 10. 2007
0 views

1111 123080220071234

Dr Tom Sparrow
17. 09. 2007
0 views

Dr Tom Sparrow

amiland gesetze
18. 06. 2007
0 views

amiland gesetze

Gen Micro130 ch1
16. 10. 2007
0 views

Gen Micro130 ch1

bus safety
15. 06. 2007
0 views

bus safety

xo Overheads 2
15. 06. 2007
0 views

xo Overheads 2

Wandering
15. 06. 2007
0 views

Wandering

walker ssm
15. 06. 2007
0 views

walker ssm

spelling
15. 06. 2007
0 views

spelling

spanish american humor
15. 06. 2007
0 views

spanish american humor

research paper checklist
15. 06. 2007
0 views

research paper checklist

Phil Logic 2000 1
15. 06. 2007
0 views

Phil Logic 2000 1

merchant
15. 06. 2007
0 views

merchant

Love 3
15. 06. 2007
0 views

Love 3

jewish humor
15. 06. 2007
0 views

jewish humor

oef 9 opl
15. 06. 2007
0 views

oef 9 opl

oef 2 opl
15. 06. 2007
0 views

oef 2 opl

obscenity andc ensorship
15. 06. 2007
0 views

obscenity andc ensorship

intro to personality psych
06. 08. 2007
0 views

intro to personality psych

Neorev
24. 02. 2008
0 views

Neorev

session 3b cogdell
18. 06. 2007
0 views

session 3b cogdell

jurors
06. 08. 2007
0 views

jurors

Hyde
06. 08. 2007
0 views

Hyde

Reunion Burgos
18. 06. 2007
0 views

Reunion Burgos

JSOBasic
06. 08. 2007
0 views

JSOBasic

sipf050405ih
23. 10. 2007
0 views

sipf050405ih

419 banks 051
10. 03. 2008
0 views

419 banks 051

pries vortraege
14. 11. 2007
0 views

pries vortraege

scar slides
17. 11. 2007
0 views

scar slides

Item 2 Mercury in Terns
06. 08. 2007
0 views

Item 2 Mercury in Terns

The new obesity guidance
11. 08. 2007
0 views

The new obesity guidance

Socrates IIa
11. 08. 2007
0 views

Socrates IIa

ID3 MedhaPradhan
26. 10. 2007
0 views

ID3 MedhaPradhan

AeroSpace Workshop JK mods
22. 10. 2007
0 views

AeroSpace Workshop JK mods

tritroph
30. 12. 2007
0 views

tritroph

Trick or Treaters
18. 06. 2007
0 views

Trick or Treaters

Saviez vous que
11. 08. 2007
0 views

Saviez vous que