Object-Oriented Programming
Operating Systems
Lecture 6b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Deadlocks
Deadlock conditions
Methods of handling deadlocks
1
Today
More about deadlocks
More deadlock avoidance
Resource Allocation Graphs
Deadlock detection and recovery
2
Recap: Prevention of deadlocks
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
3
P1
P0
P2
P3
P4
R0
R1
R2 R3
R4
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 Assume request (1 0 2) by P1 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 Recap: Avoidance of deadlocks 6 Assume request (1 0 2) by P1 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 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 Request can be served Available R0 R1 R2 2 3 0 Available R0 R1 R2 3 3 2 Sufficient resources to continue with P1 Recap: Avoidance of deadlocks 7 Assume request (3 3 0) by P4 Assume request (0 2 0) by P0 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 Request cannot be granted (insufficient resources) 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 𝑖=0 𝑛−1 Need[i][j] + Need[n][j] <= Available[j] 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 Work R0 R1 R2 0 0 0 Finish P0 false P1 false P2 false P3 false P4 false 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 Work R0 R1 R2 0 0 0 Finish P0 false P1 false P2 false P3 false P4 false 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 Work R0 R1 R2 0 1 0 Finish P0 true P1 false P2 false P3 false P4 false 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 Work R0 R1 R2 0 1 0 Finish P0 true P1 false P2 false P3 false P4 false 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 Work R0 R1 R2 3 1 3 Finish P0 true P1 false P2 true P3 false P4 false 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 Work R0 R1 R2 7 2 6 Finish P0 true P1 true P2 true P3 true P4 true 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 Work R0 R1 R2 0 0 0 Finish P0 false P1 false P2 false P3 false P4 false 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 Work R0 R1 R2 0 0 0 Finish P0 false P1 false P2 false P3 false P4 false 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 Work R0 R1 R2 0 1 0 Finish P0 true P1 false P2 false P3 false P4 false 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 Work R0 R1 R2 0 1 0 Finish P0 true P1 false P2 false P3 false P4 false No further requests can be served - Processes P1, … , P4 deadlocked Deadlock Detection 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? 24 Deadlock Recovery 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 25 Combined Deadlock Handling Strategy 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 . . . 26 Two-Phase Locking As used in databases Similar to preventing no-preemption 27 Summary Deadlocks Methods for handling deadlocks Deadlock prevention Deadlock avoidance Deadlock detection and recovery 28 Read Tanenbaum & Bos., Modern Operating Systems Chapter 6 Silberschatz et al., Operating System Concepts Chapter 7 29 Next Lecture Introduction Operating System Architectures Processes Threads - Programming Process Scheduling - Evaluation Process Synchronisation 30 Deadlocks Memory Management File Systems Input / Output Security and Virtualisation