This chapter examines two problems that plague all efforts to support concurrent processing: deadlock and starvation. We begin with a discussion of the underlying principles of deadlock and the related problem of starvation. Then we examine the three common approaches to dealing with deadlock: prevention, detection, and avoidance. | Chapter 6 Concurrency: Deadlock and Starvation Principals of Deadlock Deadlock Prevention Deadlock Avoidance Deadlock Detection 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 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 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 processes P and Q in a uniprocessor system. Each needs exclusive access to a resource A and B for a period of time. Joint Progress Diagram of Deadlock Deadlock is only inevitable if the joint . | Chapter 6 Concurrency: Deadlock and Starvation Principals of Deadlock Deadlock Prevention Deadlock Avoidance Deadlock Detection 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 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 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 processes P and Q in a uniprocessor system. Each needs exclusive access to a resource A and B for a period of time. 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 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 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, 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. Reusable Resources Example Deadlock occurs if each process holds one resource and requests the other. Example: If the multiprogramming system
