The Deadlock Problem o A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. o Example System has 2 disk drives. P and P2 each hold one disk drive and each needs another one. o Example semaphores A and B,initialized to 1 Po P wait (A); wait(B) wait (B); wait(A)
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 disk drives. P1 and P2 each hold one disk drive and each needs another one. Example semaphores A and B, initialized to 1 P0 P1 wait (A); wait(B) wait (B); wait(A)
Bridge Crossing Example o Traffic only in one direction. o Each section of a bridge can be viewed as a resource. o If a deadlock occurs,it can be resolved if one car backs up(preempt resources and rollback). o Several cars may have to be backed up if a deadlock occurs. o Starvation is possible
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 up if a deadlock occurs. Starvation is possible
System Model oResource types R:R2:...,Fm CPU cycles,memory space,1/O devices o Each resource type Ri has Wi instances. o Each process utilizes a resource as follows: request use release
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
Deadlock Characterization Deadlock can arise if four conditions hold simultaneously. o Mutual exclusion:only one process at a time can use a resource. o Hold and wait:a process holding at least one resource and 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 (Po,P1,...,Po)of waiting processes such that Pois waiting for a resource that is held by P1,P is waiting for a resource that is held by adtn oo
Deadlock Characterization Mutual exclusion: only one process at a time can use a resource. Hold and wait: a process holding at least one resource and 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 . Deadlock can arise if four conditions hold simultaneously
Resource-Allocation Graph A set of vertices V and a set of edges E. o V is partitioned into two types: P=(P1,P2,...P,the set consisting of all the processes in the system. R=(RI,R2,...,R,the set consisting of all resource types in the system. o request edge-directed edge P>R; o assignment edge-directed edge Ri>P
Resource-Allocation Graph V is partitioned into two types: P = {P1 , P2 , …, Pn }, the set consisting of all the processes in the system. R = {R1 , R2 , …, Rm}, the set consisting of all resource types in the system. request edge – directed edge P1 Rj assignment edge – directed edge Rj Pi A set of vertices V and a set of edges E