enter image description here

Here is a resource allocation graph asked in my Operating Systems Theory midterm. The question is, "Is there a deadlock here? Explain your answer in detail"

Ra and Rb are resource sets and every dot inside of them are resources. Circles are processes. An arrow from process to a resource set means that process is requesting a resource from that set. An arrow from resource set to process means that process owns a resource from that resource set.

I want to have your opinions on this, because the lecturer's answer is conflicting with mine. Lecturer says there is a deadlock here. But my answer was, since Py and Pz are not requesting a resource, they will simply continue their execution and terminate, releasing their resources. Then Px and Pw can obtain their requested resources and keep executing. It is obvious there is a cycle in this graph as Px-Pw but this doesn't conclude us to a deadlock. Thus I can't see a way to make "there is a deadlock here"conclusion.

So is there a deadlock here?

  • 2
    $\begingroup$ As far as I understand RAG then if there is more then one instance for resource then there may or may not be deadlock. But it seems that right here there is no deadlock because resources are rebalenced on Pz and Py. Correct me if i am wrong $\endgroup$ – Bartosz Przybylski Jan 30 '14 at 21:55
  • $\begingroup$ That was my answer Bartek. Because Pz and Py are not requesting any resources, they will terminate after they finish and their resources on Rb and Ra will be released. Then Px and Pw can get their requested resources and finish their execution. But lecturer insists there is a deadlock here. $\endgroup$ – Mert Çelikok Jan 30 '14 at 22:51
  • $\begingroup$ Deadlocks are treated in Tanenbaum, Chapter 6. Here is some material mostly from Brinch Hansen classic OS book and from Maezawa, Oldehoeft, Oldehoeft OS book.May be help you cis.temple.edu/~giorgio/old/cis307f95/readings/deadlock.html $\endgroup$ – Deepak Deepu May 31 '17 at 11:35

I did some thinking and then searching and all RAG conditions of this example leads to conclusion that there is no deadlock (altho there is a cycle here).

Beside after searching I found this where you can find this:

Which clearly stands Graph With A Cycle But No Deadlock

Are you sure that you have your graph correct here?

  • $\begingroup$ These two graphs are identical yes. This was the exact graph asked on exam but I had to draw it myself. $\endgroup$ – Mert Çelikok Jan 31 '14 at 11:32

By all means, your answer is correct: judging by the RAG, Py and Pz have all resources they need to complete; so, once they finish, there will be resources available to Px and Pw finish their own tasks. Therefore, there is no deadlock. Simple like that.

Please, check this answer, provided by Neelesh Shukla.

The only possibility for your answer become wrong: the graph the lecturer referred to is NOT the one depicted here!!


there is no deadlock because there are more than one instance per resource type even though there is cycle in the graph.

  • 1
    $\begingroup$ Could you expand this a little? We're looking for answers with a bit more detail than this. $\endgroup$ – David Richerby Apr 13 '17 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.