Chapter 6 Concurrency: Deadlock and Starvation Principals of Deadlock Deadlock prevention Deadlock avoidance Deadlock detection An Integrated deadlock strategy Dining Philosophers Problem
1 Chapter 6 Concurrency: Deadlock and Starvation • Principals of Deadlock – Deadlock prevention – Deadlock Avoidance – Deadlock detection – An Integrated deadlock strategy • Dining Philosophers Problem
Deadlock A set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the set Typically involves processes competing for the same set of resources The event is typically the freeing up of some requested resources No efficient solution
2 Deadlock • A set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the set – Typically involves processes competing for the same set of resources – The event is typically the freeing up of some requested resources • No efficient solution
Potential deadlock The necessary resources are available for any of the cars to proceed I need need quad C quad B and d and C b I need I need quad A and quad D B and A
3 Potential Deadlock I need quad A and B I need quad B and C I need quad C and D I need quad D and A The necessary resources are available for any of the cars to proceed
Actual deadlock HALT until HALT until D is free C is free HALT until HALT until B is free A is free
4 Actual Deadlock HALT until B is free HALT until C is free HALT until D is free HALT until A is free
TWo Processes P and Q Consider two Process P Process Q processes P and Q Get A Get B · Each needs exc| usIve Get B Get A access to a resourcea Release Release B and b for a period of Release B Release A time
5 Two Processes P and Q • Consider two processes P and Q • Each needs exclusive access to a resource A and B for a period of time
Joint Progress Diagram of Deadlock Q Release Deadlock is only inevitable if the Release Required B joint progress of Get A the two processes B deadlock creates a path that Get B enters the fatal region PI ess Get A Get B Release A Release B =both P and Q want resourceA =both P and Q want resource B Required = deadlock-inevitable region B Required th of P and Q eater-P-iexecuting and Q is waiting Vertical portion of path indicates Q is executing and P is waiting Figure 6.2 Example of Deadlock
6 Joint Progress Diagram of Deadlock Deadlock is only inevitable if the joint progress of the two processes creates a path that enters the fatal region
Alternative logic Whether or not deadlock Process P Process Q occurs depends on both GetA Get B the dynamics of the execution and on the Release A Get A details of the application Get B Release B Suppose that P does not Rel Release a need both resources at the same time
7 Alternative logic • Whether or not deadlock occurs depends on both the dynamics of the execution and on the details of the application • Suppose that P does not need both resources at the same time
Diagram of alternative logic Progress of Q 3 Release A Release Get a Required 5 Get B Deadlock 6 cannot occur Progress Get a Release a get b Release b both P and Q want resource A A Required B Required both P and Q want resource B ion of path indicates Pis executing and Q is waitin portion of path indicates Q is executing and Pis waiting 8 Figure 6.3 Example of No Deadlock [BACO031
8 Diagram of alternative logic Deadlock cannot occur
Resource Categories Two general categories of resources · Reusable can be safely used by only one process at a time and is not depleted by that use examples: processors, IO channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores Consumable can be created (produced) and destroyed (consumed examples: interrupts, signals, messages, and information in l/o buffers
9 Resource Categories Two general categories of resources: • Reusable – can be safely used by only one process at a time and is not depleted by that use. – examples: processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores • Consumable – can be created (produced) and destroyed (consumed) – examples: interrupts, signals, messages, and information in I/O buffers
Reusable resources EXample Consider two processes that compete for exclusive access to a disk file d and a tape drive t Process P Process Q Step Action Step Action Request D) Request (t) ppppppp Lock①D) Lock (T) Request t) Lock(T) qqqq Request (d) Lock①D) Perform function Perform function Unlock(D) Unlock(T) Unlock(T) Unlock D) Figure 6.4 Example of Two Processes Competing for Reusable Resources 10
10 Reusable Resources Example • Consider two processes that compete for exclusive access to a disk file D and a tape drive T
