Reusable resources EXample Deadlock occurs if each process holds one resource and requests the other EXample If the multiprogramming system interleaves the execution of the two processes as follows po pl q0 q1 p2 92
11 Reusable Resources Example • Deadlock occurs if each process holds one resource and requests the other. • Example: – If the multiprogramming system interleaves the execution of the two processes as follows p0 p1 q0 q1 p2 q2
REusable Resources Example 2 Memory Request Space is available for allocation is 200Kbytes and the following sequence of events occur PI P2 Request 80 Kbytes Request 70 Kbytes Request 60 Kbytes: Request 80 Kbytes; Deadlock occurs if both processes progress to their second request 12
12 Reusable Resources Example 2: Memory Request • Space is available for allocation is 200Kbytes and the following sequence of events occur • Deadlock occurs if both processes progress to their second request P1 . . . . . . Request 80 Kbytes; Request 60 Kbytes; P2 . . . . . . Request 70 Kbytes; Request 80 Kbytes;
Consumable resources EXample Consider a pair of processes, in which each process attempts to receive a message from the other process and then send a message to the other process Deadlock may occur if the receive is blocking P1 P2 Receive(P2) Receive(P1) Send(P2, M1) Send(P1, M2) 13
13 Consumable Resources Example • Consider a pair of processes, in which each process attempts to receive a message from the other process and then send a message to the other process • Deadlock may occur if the Receive is blocking
Resource Allocation Graphs Directed graph that depicts a state of the system of resources and processes Requests Held by PI ●Ra Pl Ra (a)Resouce is requested (b) Resource is held an instance of a resource
14 Resource Allocation Graphs • Directed graph that depicts a state of the system of resources and processes an instance of a resource
Conditions for possible Deadlock Mutual exclusion Only one process may use a resource at a time Hold-and-wait A process may hold allocated resources while awaiting assignment of others No pre-emption No resource can be forcibly removed from a process holding it 15
15 Conditions for possible Deadlock • Mutual exclusion – Only one process may use a resource at a time • Hold-and-wait – A process may hold allocated resources while awaiting assignment of others • No pre-emption – No resource can be forcibly removed from a process holding it