deadlocks

Information about deadlocks

Published on September 17, 2007

Author: Flemel

Source: authorstream.com

Content

Deadlocks:  Deadlocks Chapter 3 3.1. Resource 3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues Resources:  Resources Examples of computer resources printers tape drives tables Processes need access to resources in reasonable order Suppose a process holds resource A and requests resource B at same time another process holds B and requests A both are blocked and remain so Hardware and software deadlocks Resources:  Resources Deadlocks occur when … processes are granted exclusive access to devices we refer to these devices generally as resources Resources may have multiple copies Preemptable resources can be taken away from a process with no ill effects (for example memory) Nonpreemptable resources will cause the process to fail if taken away (e.g. CDR) Resources:  Resources Sequence of events required to use a resource request the resource use the resource release the resource Must wait if request is denied requesting process may be blocked may fail with error code Nature of requesting a resource is highly system dependent (e.g. request system call) Resource Acquisition:  Resource Acquisition t Introduction to Deadlocks:  Introduction to Deadlocks Formal definition : A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause Usually the event is release of a currently held resource None of the processes can … run release resources be awakened Number of processes and resources is unimportant Introduction to Deadlocks:  Introduction to Deadlocks Different from starvation and livelock Starvation – one process is active, but never gets the resource Livelock – all processes starve Four Conditions for Deadlock:  Four Conditions for Deadlock Mutual exclusion condition Each resource assigned to 1 process or is available Hold and wait condition Process holding resources can request additional No preemption condition Assigned resources cannot be involuntarily claimed Circular wait condition Must be a circular chain of 2 or more processes Each is waiting for resource held by next member of the chain Dealing with Deadlocks:  Dealing with Deadlocks Strategies Just ignore the problem altogether (Ostrich Alg.) Allow deadlock, detect it, break it Prevention Negate one of the four necessary conditions Dynamic avoidance Careful resource allocation – each resource request is analyzed and denied if deadlock might result The Ostrich Algorithm:  The 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 correctness Deadlock Prevention & Avoidance:  Deadlock Prevention andamp; Avoidance Deadlock prevention Define a global ordering of all resources Each process locks resources in order Resource can be unlocked at any time Useful within multi-threaded programs Deadlock avoidance – 'Banker’s Algorithm' Detection: Deadlock Modeling:  Detection: Deadlock Modeling 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 U Deadlock Modeling:  How deadlock occurs A B C Deadlock Modeling Detection with One Resource of Each Type:  Detection with One Resource of Each Type A…G: processes; R…W: resources Note the resource ownership and requests Is this system deadlocked and if yes, which processes are involved? A cycle can be found within the graph, denoting deadlock Detection with One Resource of Each Type:  Detection with One Resource of Each Type We need a formal algorithm for detecting deadlocks A simple one to detect cycles: Use resource graph Perform DFS (depth first search) starting at each node, looking for cycles (recurrence of starting node) If it comes to a node it has encountered in this run, then there exists a cycle. Why use DFS and not BFS? Review DFS vs. BFS. Pseudocode for Deadlock Detection:  Pseudocode for Deadlock Detection For i=1 to N nodes { reset graph to unmarked; L = empty list; traverse_graph (node[i]); } traverse_graph (node) { add node to L; check for cycle in L; if (there exists outgoing unmarked arcs from node) { mark node-andgt;outgoing; traverse_graph (node-andgt;outgoing); } } Detection: Time Complexity:  Detection: Time Complexity N nodes, E arcs Time complexity for DFS is O (N + E) Need to do DFS N times (once for each node) O (N (N + E)) Check for cycles Simple way: can check every node visited to see if it is equal to root – O(1) complexity Better: check for any cycle in branch – worse case O (N ) Total complexity O (N (N + E) + N ) = O (2N + NE) = O (N + NE) N andlt;andlt; E, so N andlt;andlt; N E, total complexity is O (NE) 2 2 2 2 2 Detection: How often to run?:  Detection: How often to run? After every allocation of resource is too expensive Every few minutes When CPU is idle – indication of blocked processes waiting for resources Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Basic idea: Allocate resources to a process that can be run to completion 4 data structures: Vector of resources in existence E = # of resource i in system Vector of available resources, A = # of available resource i Allocation matrix C = # of resource j that are being held by process i Request matrix R = # of resource j that are requested by process i i i ij ij Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Invariant property: Σi=1Cij + Aj = Ej n Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Deadlock detection is based on comparing vectors: Algorithm Look for an unmarked process, Pi for which the i-th row of R is less or equal to A If such a process is found, add the i-th row of C to A, mark the process and go back to step 1 If no such process exists the algorithm terminates Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type Unmark all processes; While (there exists unmarked processes) for i = 1to n processes { can_satisfy = TRUE; for j = 1 to r resources { if (Rij andgt; Aj) { can_satisfy = FALSE; break; } } if (can_satisfy) { for j = 1 to r resources // Release resources since alloted to process i Aj += Cij; // process i can finish and release its resources mark process; } } Detection with Multiple Resources of Each Type:  Detection with Multiple Resources of Each Type An example for the deadlock detection algorithm (3/2/1) Recovery from Deadlock:  Recovery from Deadlock Recovery through preemption Take a resource from some process to allow others to complete Depends on nature of the resource Recovery through rollback Checkpoints are written to a file and include memory image, resource state, and other state variables Lose work that was done after checkpoint since roll back returns machine back to checkpoint state Checkpoints are considered safe states Total rollback means that no safe state existed; restart process Kill process to release resources Need to make sure process can be started again later w/o ill effects Recovery from Deadlock:  Recovery from Deadlock Abort all deadlocked processes Expensive – lose data and results of computation Deadlock may occur again if all processes restarted Abort one process at a time until no deadlock Lots of overhead – after each process is aborted, must do detection again Which process to abort? Abort the one that incurs minimal cost Factors – priority, how long process has run, type of resource process has, requested resources, type of process Deadlock Prevention: Attack 4 Deadlock Conditions:  Deadlock Prevention: Attack 4 Deadlock Conditions Condition Approach Problem Mutual -Spooling – exp. only printer -Not all devices can be spooled Exclusion daemon requests printer Competition for spooler space can become deadlocked Hold andamp; Wait -Require all processes to Condition request all resources before running (then, can use Banker’s) -Allow processes access to only -Not practical for some cases 1 resource at a time. (exp. Copy between 2 disks) No Preemption -Allow preemption -Not viable for some resources (exp. Printers) Circular Wait -Order resources numerically -There may be too many Processes must make requests resources to numerically order in order. (database tables, for exp.) Deadlock PreventionAttacking the Mutual Exclusion Condition:  Deadlock Prevention Attacking the Mutual Exclusion Condition Some devices (such as printer) can be spooled only the printer daemon uses printer resource thus deadlock for printer eliminated Not all devices can be spooled Principle: avoid assigning resource when not absolutely necessary as few processes as possible actually claim the resource Attacking the Hold and Wait Condition:  Attacking the Hold and Wait Condition Goal: Prevent processes that hold resources from waiting for more resources Require processes to request resources before starting a process never has to wait for what it needs Problems may not know required resources at start of run also ties up resources other processes could be using Variation: process must give up temporarily all resources before requesting a new one then request all immediately needed Attacking the No Preemption Condition:  Attacking the No Preemption Condition This is not a viable option Consider a process given the printer halfway through its job now forcibly take away printer !!?? Attacking the Circular Wait Condition:  Attacking the Circular Wait Condition Normally ordered resources A resource graph (a) (b) Attacking the Circular Wait Condition:  Attacking the Circular Wait Condition Rule: All requests of a process must be made in numerical order =andgt; the resource allocation graph can not have cycles Either i andlt; j or i andgt; j =andgt; can’t have deadlocks Same logic with multiple resources: at every instant one assigned resource will be the highest Problem: impossible to find an ordering to satisfy everyone Deadlock Avoidance:  Deadlock Avoidance So far we assumed that all requests take place at the beginning The system must be able to decide whether granting a resource request is safe or not Is there an algorithm that can always avoid deadlocks? Yes, if certain information is known in advance State of Resource Allocation: Safe & Unsafe States:  State of Resource Allocation: Safe andamp; Unsafe States Safe System is not deadlocked and can guarantee that all processes will finish. There is some scheduling order such that all processes finish. Unsafe System may not be deadlocked, but cannot guarantee that all processes can finish No scheduling order that guarantees all processes will finish, but process may be lucky and finish due to some processes releasing resources early Determining Safe/Unsafe Using Banker’s Alg.:  Determining Safe/Unsafe Using Banker’s Alg. Similar to deadlock detection Consider each request as it occurs and see if granting it leads to a safe state If a granting a resource leads to a deadlock cycle, then state is unsafe and do not grant Key assumptions: All processes need to declare their max resources #of processes and resources are fixed. Need to dynamically update resource allocation table for entering/exiting processes to handle dynamic environment Determining Safe & Unsafe States:  Determining Safe andamp; Unsafe States Use resource allocation table Examples for a single resource. Can be scaled to multiple resources Proc. Has Max (Needs) Proc. Has Max (Needs) A 3 9 6 A 4 9 5 B 2 4 2 B 2 4 2 C 2 7 5 C 2 7 5 Free: 3 Free: 2 What is the difference between detection alg. And Banker’s? Other IssuesTwo-Phase Locking:  Other Issues Two-Phase Locking Deadlock avoidance and prevention are difficult to use in practice for large dynamic systems Detection and recovery is more practical Two-phase locking is practical solution often used in databases Phase 1 process tries to lock all records it needs, one at a time if needed record found locked, start over (no real work done in phase one) If phase 1 succeeds, start phase 2 perform updates release locks Note similarity to requesting all resources at once Applicable in small-scale, such as process that updates a few records in a few tables Not useful for processes where release and restart is not possible Non-resource Deadlocks:  Non-resource Deadlocks Possible for two processes to deadlock Each is waiting for the other to do some task Can happen with semaphores Each process required to do a down() on two semaphores (mutex and another) If done in wrong order, deadlock results Solution is more careful programming

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

L14 Deadlock
17. 09. 2007
0 views

L14 Deadlock

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