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