Lecture Operating system concepts (Sixth ed) - Chapter 8: Deadlocks. After studying this chapter you will be able to develop a description of deadlocks, which prevent sets of concurrent processes from completing their tasks; to present a number of different methods for preventing or avoiding deadlocks in a computer system. | Chapter 8: Deadlocks I System Model I Deadlock Characterization I Methods for Handling Deadlocks I Deadlock Prevention I Deadlock Avoidance I Deadlock Detection I Recovery from Deadlock I Combined Approach to Deadlock Handling Operating System Concepts Silberschatz, Galvin and Gagne 2002 The Deadlock Problem I A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. I Example ✦ System has 2 tape drives. ✦ P1 and P2 each hold one tape drive and each needs another one. I Example ✦ semaphores A and B, initialized to 1 P0 P1 wait (A); wait (B); Operating System Concepts wait(B) wait(A) Silberschatz, Galvin and Gagne 2002 Bridge Crossing Example I Traffic only in one direction. I Each section of a bridge can be viewed as a resource. I If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). I Several cars may have to be backed up if a deadlock occurs. I Starvation is possible. Operating System Concepts Silberschatz, Galvin and Gagne 2002 System Model I Resource types R1, R2, . . ., Rm CPU cycles, memory space, I/O devices I Each resource type Ri has Wi instances. I Each process utilizes a resource as follows: ✦ request ✦ use ✦ release Operating System Concepts Silberschatz, Galvin and Gagne 2002 Deadlock Characterization Deadlock can arise if four conditions hold simultaneously. I Mutual exclusion: only one process at a time can use a resource. I Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes. I No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task. I Circular wait: there exists a set {P0, P1, , P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, , Pn–1 is waiting for a resource that is held .
