Operating Systems Lecture 6b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously 1 Deadlocks
Deadlock conditions
Methods of handling deadlocks
Today 2 More about deadlocks
More deadlock avoidance
Resource Allocation Graphs
Deadlock detection and recovery
Recap: Prevention of deadlocks
3
Prevention by design
Make sure that at least one of the conditions for a deadlock does not occur:
Mutual exclusion Hold-and-wait
No-preemption Circular wait
P1
R0
R1
P0
R4
P2
R2
P3
R3
P4
Recap: Avoidance of deadlocks 4 Resource Allocation Denial
Request[i] for process Pi
1. If Request[i] <= Need[i], go to step 2.
Otherwise, error (maximum exceeded).
2. If Request[i] < Available, go to step 3.
Otherwise, Pi must wait (resources not available).
3. Pretend to fulfill request:
Available := Available - Request[i] Allocation[i] := Allocation[i] + Request[i] Need[i] := Need[i] - Request[i]
Approve request if resulting state is safe. Otherwise, restore state and set Pi to wait.
Recap: Avoidance of deadlocks 5
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
2
P3
2
1
1
P4
0
0
2
Need
R0
R1
R2
P0
7
4
3
P1
1
2
2
P2
6
0
0
P3
0
1
1
P4
4
3
1
Available
R0
R1
R2
3
3
2
Assume request (1 0 2) by P1
Recap: Avoidance of deadlocks 6
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
2
P3
2
1
1
P4
0
0
2
Need
R0
R1
R2
P0
7
4
3
P1
1
2
2
P2
6
0
0
P3
0
1
1
P4
4
3
1
Available
R0
R1
R2
3
3
2
Assume request (1 0 2) by P1
Request can be served
Allocation
R0
R1
R2
P0
0
1
0
P1
3
0
2
P2
3
0
2
P3
2
1
1
P4
0
0
2
Need
R0
R1
R2
P0
7
4
3
P1
0
2
0
P2
6
0
0
P3
0
1
1
P4
4
3
1
Available
R0
R1
R2
2
3
0
Sufficient resources to continue with P1
Recap: Avoidance of deadlocks 7
Allocation
R0
R1
R2
P0
0
1
0
P1
3
0
2
P2
3
0
2
P3
2
1
1
P4
0
0
2
Available
R0
R1
R2
2
3
0
Need
R0
R1
R2
P0
7
4
3
P1
0
2
0
P2
6
0
0
P3
0
1
1
P4
4
3
1
Assume request (3 3 0) by P4
Request cannot be granted (insufficient resources)
Assume request (0 2 0) by P0
Request cannot be granted (would result in unsafe state with only {2,1,0} available resources)
Avoidance of deadlocks 8 Resource Initiation Denial
Admit process Pn only when its resource requests cannot cause a deadlock 𝑛−1
Need[i][j] + Need[n][j] <= Available[j] 𝑖=0
Assumes that processes know in advance the amount of resources they will need
Assumes worst-case resource allocation
(all processes request their maximum resources at the same time)
Resource allocation graphs 9 Graphical models of resource allocation
Process nodes Pi
Resource nodes Ri
Number of instances of each resource type
Request edge Pi Rj
Assignment edge Rj Pi
What happens if P3 R2 ?
Cycles in the graph indicate a deadlock.
Resource allocation graphs 10 Graphical models of resource allocation
Process nodes Pi
Resource nodes Ri
Number of instances of each resource type
Request edge Pi Rj
Assignment edge Rj Pi
Is there a deadlock in this system? Yes.
Deadlock Detection 11
Always grant resource requests when resources are available
Examine the state of the system to determine whether a deadlock has occurred If so, recover from the deadlock
Drawbacks:
Runtime overhead for deadlock detection Potential losses due to recovery
Deadlock Detection – Single resources 12
Resource allocation graph
Wait graph
Deadlock Detection – Multiple resources 13
There are Available[j] instances of each resource type Rj
Allocation[i][j] is the number of instances of resource type Rj held by process Pi
Request[i][j] is the number of additional instances of resource type Rj requested by process Pi
1.Work := Available
Finish[i] := false if Allocation[i] != 0; otherwise Finish[i] := true
2. Find an index i such that
Finish[i] = false ^ Request[i] <= Work If no such i exists, go to step 4.
3.Work := Work + Allocation[i] Finish[i] := true
Go to step 2.
4. If Finish[i ] == false for some i , then the system is in a deadlocked state. Pi is deadlocked if Finish[i] == false.
Deadlock Detection – Multiple resources 14 Example 1
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
0
P3
1
0
0
P4
0
0
2
Finish
P0
false
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
0
0
Deadlock Detection – Multiple resources 15 Example 1
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
0
P3
1
0
0
P4
0
0
2
Finish
P0
false
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
0
0
Deadlock Detection – Multiple resources 16 Example 1
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
0
P3
1
0
0
P4
0
0
2
Finish
P0
true
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
1
0
Deadlock Detection – Multiple resources 17 Example 1
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
0
P3
1
0
0
P4
0
0
2
Finish
P0
true
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
1
0
Deadlock Detection – Multiple resources 18 Example 1
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
0
0
0
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
0
P3
1
0
0
P4
0
0
2
Finish
P0
true
P1
false
P2
true
P3
false
P4
false
Work
R0
R1
R2
3
1
3
Deadlock Detection – Multiple resources 19 Example 1
Allocation
R0
R1
R2
P0
0
0
0
P1
0
0
0
P2
0
0
0
P3
0
0
0
P4
0
0
0
Request
R0
R1
R2
P0
0
0
0
P1
0
0
0
P2
0
0
0
P3
0
0
0
P4
0
0
0
Finish
P0
true
P1
true
P2
true
P3
true
P4
true
Work
R0
R1
R2
7
2
6
All requests served – no deadlock
Deadlock Detection – Multiple resources 20 Example 2
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
1
P3
1
0
0
P4
0
0
2
Finish
P0
false
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
0
0
Deadlock Detection – Multiple resources 21 Example 2
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
1
P3
1
0
0
P4
0
0
2
Finish
P0
false
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
0
0
Deadlock Detection – Multiple resources 22 Example 2
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
0
P3
1
0
0
P4
0
0
2
Finish
P0
true
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
1
0
Deadlock Detection – Multiple resources 23 Example 2
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
3
P3
2
1
1
P4
0
0
2
Request
R0
R1
R2
P0
0
0
0
P1
2
0
2
P2
0
0
0
P3
1
0
0
P4
0
0
2
Finish
P0
true
P1
false
P2
false
P3
false
P4
false
Work
R0
R1
R2
0
1
0
No further requests can be served - Processes P1, ... , P4 deadlocked
Deadlock Detection 24 When to do deadlock detection?
How often is a deadlock likely to occur?
How many processes will be affected by deadlock when it happens?
Run it
on every resource request? every hour?
based on metrics?
Deadlock Recovery 25
Abort
all processes involved in deadlock
individual processes until there is no deadlock anymore
Rollback
all processes involved in deadlock
individual processes until there is no deadlock anymore
How to choose which processes to kill or preempt? Minimise “loss"
Least CPU time?
Fewest allocated resources?
Deadlock could happen again
Combined Deadlock Handling Strategy 26 For example:
Group resources into resource types: Disks
I/O devices Files
Main memory
Prevent circular wait between these classes
Use appropriate methods within these classes, e.g. Prevent no-preemption on main memory
Avoidance on I/O devices
...
Two-Phase Locking 27 As used in databases
Similar to preventing no-preemption
Summary 28 Deadlocks
Methods for handling deadlocks Deadlock prevention
Deadlock avoidance
Deadlock detection and recovery
Read 29 Tanenbaum & Bos., Modern Operating Systems
Chapter 6
Silberschatz et al., Operating System Concepts Chapter 7
Next Lecture
30
Introduction
Operating System Architectures Processes
Threads - Programming
Process Scheduling - Evaluation Process Synchronisation
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation