代写 operating system database graph security Go Operating Systems Lecture 6b

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