Deadlock: Conditions, Detection, and Avoidance
Lecture 19: Deadlock:
Conditions, Detection and
Avoidance
1
2
Review: strategies for dealing
with deadlocks
•
just ignore the problem altogether
•
detection and recovery
•
dynamic avoidance
•
prevention
3
Deadlock Avoidance
•
Be very conservative when granting
resources
•
Don’t grant a resource if it could lead to a
potential deadlock
•
Not very practical, since this is too much
overhead for granting resources
4
Deadlock Avoidance
Figure 6-8. Two process resource trajectories.
5
Safe and Unsafe States (1)
Demonstration that the state in (a) is safe
(a) (b) (c) (d) (e)
6
Safe and Unsafe States (2)
Demonstration that the state in b is not safe
(a) (b) (c) (d)
7
The Banker's Algorithm for a Single Resource
•
Three resource allocation states
–
safe
–
safe
–
unsafe
(a) (b) (c)
8
Banker's Algorithm for Multiple Resources
Example of banker's algorithm with multiple resources
9
Review: Four Conditions for
Deadlock
1.
Mutual exclusion condition
•
each resource assigned to 1 process or is available
2.
Hold and wait condition
•
process holding resources can request additional
3.
No preemption condition
•
previously granted resources cannot forcibly taken away
4.
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
10
Deadlock Prevention
•
Attacking the mutual exclusion condition
•
Attacking the hold and wait condition
•
Attacking the no preemption condition
•
Attacking the circular wait condition
11
Attacking the Hold and Wait Condition
•
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 all resources
–
then request all immediately needed
12
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
–
!!??
13
Attacking the Circular Wait Condition
•
Normally ordered resources
•
A resource graph
(a) (b)
14
Summary of deadlock prevention
Summary of approaches to deadlock prevention
15
Other Issues
•
Two-phase locking
•
Communication deadlocks
•
Livelock
•
Starvation
Explore strategies for dealing with deadlocks, from detection and recovery to dynamic avoidance. Learn about deadlock avoidance methods like being conservative in resource granting and dive into safe and unsafe states, the Banker's algorithm, and the four conditions for deadlock. Discover how to prevent deadlocks by attacking the root causes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 19: Deadlock: Conditions, Detection and Avoidance 1
Review: strategies for dealing with deadlocks just ignore the problem altogether detection and recovery dynamic avoidance prevention 2
Deadlock Avoidance Be very conservative when granting resources Don t grant a resource if it could lead to a potential deadlock Not very practical, since this is too much overhead for granting resources 3
Deadlock Avoidance Figure 6-8. Two process resource trajectories. 4
Safe and Unsafe States (1) (a) (b) (c) (d) (e) Demonstration that the state in (a) is safe 5
Safe and Unsafe States (2) (a) (b) (c) (d) Demonstration that the state in b is not safe 6
The Banker's Algorithm for a Single Resource (a) (b) (c) Three resource allocation states safe safe unsafe 7
Banker's Algorithm for Multiple Resources Example of banker's algorithm with multiple resources 8
Review: 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 previously granted resources cannot forcibly taken away 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 1. 2. 3. 4. 9
Deadlock Prevention Attacking the mutual exclusion condition Attacking the hold and wait condition Attacking the no preemption condition Attacking the circular wait condition 10
Attacking the Hold and Wait Condition 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 all resources then request all immediately needed 11
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 !!?? 12
Attacking the Circular Wait Condition (a) (b) Normally ordered resources A resource graph 13
Summary of deadlock prevention Summary of approaches to deadlock prevention 14
Other Issues Two-phase locking Communication deadlocks Livelock Starvation 15
