Search code examples
processoperating-systemsynchronizationcomputer-sciencedeadlock

How to find deadlock exists or not?

Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the resources as follows if executed independently.

Process P1:

t=0: requests 2 units of R2

t=1: requests 1 unit of R3

t=3: requests 2 units of R1

t=5: releases 1 unit of R2 and 1 unit of R1.

t=7: releases 1 unit of R3

t=8: requests 2 units of R4

t=10: Finishes  

Process P2:

t=0: requests 2 units of R3

t=2: requests 1 unit of R4

t=4: requests 1 unit of R1

t=6: releases 1 unit of R3

t=8: Finishes   

Process P3:

t=0: requests 1 unit of R4

t=2: requests 2 units of R1

t=5: releases 2 units of R1

t=7: requests 1 unit of R2

t=8: requests 1 unit of R3

t=9: Finishes

Which one of the following statements is TRUE if all three processes run concurrently starting at time t = 0?

  1. All processes will finish without any deadlock

  2. Only P1 and P2 will be in deadlock

  3. Only P1 and P3 will be in deadlock

  4. All three processes will be in deadlock

Solution

  • I ran through the requests and available resources and all processes finished without deadlock.

    • At t = 3, the process P1 has to wait because it doesn't get required resources but that gets sorted out at t = 5 when P3 releases them. No "circular wait" and "hold and wait" could take place.
    • Next wait for P1 is when at t = 8 it requests 2 of R4 and that is sorted when P3 finishes at t = 9. Same as above, no "circular wait" and "hold and wait" could take place.

    Other than this all requests were granted immediately.