程序代写代做代考 database file system Object-Oriented Programming

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