tailieunhanh - Lecture Operating system concepts (Fifth edition): Module 7 - Avi Silberschatz, Peter Galvin

Module 7 - 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. | Lecture Operating system concepts Fifth edition Module 7 - Avi Silberschatz Peter Galvin Module 7 Deadlocks System Model Deadlock Characterization Methods for Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection Recovery from Deadlock Combined Approach to Deadlock Handling Silberschatz and Galvin 1999 The Deadlock Problem A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. Example System has 2 tape drives. P1 and P2 each hold one tape drive and each needs another one. Example semaphores A and B initialized to 1 P0 P1 wait A wait B wait B wait A Silberschatz and Galvin 1999 Bridge Crossing Example Traffic only in one direction. Each section of a bridge can be viewed as a resource. If a deadlock occurs it can be resolved if one car backs up preempt resources and rollback . Several cars may have to be backed upif a deadlock occurs. Starvation is possible. Silberschatz and Galvin 1999 System Model Resource types R1 R2 . . . Rm CPU cycles memory space I O devices Each resource type Ri has Wi instances. Each process utilizes a resource as follows request use release Silberschatz and Galvin 1999 Deadlock Characterization Deadlock can arise if four conditions hold simultaneously. Mutual exclusion only one process at a time can use a resource. Hold and wait a process holding at least one resource is waiting to acquire additional resources held by other processes. No preemption a resource can be released only voluntarily by the process holding it after that process has completed its task. 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 by Pn and P0 is waiting for a resource that is held by P0. Silberschatz and Galvin 1999 Resource-Allocation Graph A set of vertices V and a set of edges E. V is .