Search code examples
graphresourcesoperating-systemdeadlockcycle

Determining which request can be granted as edge of hold,wait and illegal

Consider the resource allocation graph :-

enter image description here

Assume the sequence of requests is given as:
P4 → R3
P1 → R4
P3 → R1
P2 → R3
P4 → R2
P5 → R4

Which requests can be granted such that there should be no deadlock?

I tried solving it but just need a heads-up as I got confused browsing different graphs with different results.

This is my answer -
P4 → R3 - hold
P1 → R4 - wait
P3 → R1 - wait
P2 → R3 - wait
P4 → R2 - illegal
P5 → R4 - wait

Solution

  • The answer I derived is the same as what you mentioned,CONGRATS for solving it on your own. I am just briefing it out for future visitors :-

    P4 -> R3 ------ will hold as one instance of R3 is available.
P1 -> R4 ------ will wait as the only instance of R4 is occupied by P4.
P3 -> R1 ------ will wait as the only instance of R1 is occupied by P1.
P2 -> R3 ------ will wait as both instances of R3 are occupied by P3 and P4.
P4 -> R2 ------ will be illegal due to satisfying circular wait condition.

    Explanation of above ---> P4 needs R2, which is occupied by P2 and P5. P2 needs R3 which is occupied by P4 itself. So, here's a cycle which is an unsafe state. Hence, this will result in deadlock due to circular wait.

    P5 -> R4 ------ will wait in queue after P1, as P1 has requested for R4
                before than P5.

    NOTE :- We won't consider the 5th case as it will result in deadlock and hence will not be considered in evaluation of the future requests of resources by the processes.