I understand the concepts of deadlock well enough, but when I’m given a problem like the one below I’m not sure how to go about solving it. I can draw a resource allocation graph, but I’m not sure how to solve it from there.
Is there a better more formal way of solving this?
Consider a system with five processes, P1 through P5, and five
resources, R1 through R5. Resource ownership is as follows.
• P1 holds R1 and wants R3
• P2 holds R2 and wants R1
• P3 holds R3 and wants R5
• P4 holds R5 and wants R2
• P5 holds R4 and wants R2
Is this system deadlocked? Justify your answer. If the system is deadlocked, list
the involved processes.
6
Yes it’s a deadlock, diagram the wait chain of processes (1 -> 2 indicates P1 waiting on P2 to release a resource):
1 -> 3 -> 4 -> 2 -> 1
Ran back into 1 in the wait chain and the cycle is complete; that is 1 is waiting on resources that are waiting on resources that are waiting on 1.
If following 1 like this didn’t run back into itself then it would be accurate to say 1 is not in a deadlock (for instance if it was 1->3->4->2). However if one were not in a deadlock that does not prove or indicate none of the others are in dead locks. To verify none of the resources are in a deadlock you would need to graph the same chain with any nodes that weren’t in the critical path for 1 (if any in the critical path were in a deadlock then 1 would be, so you know all members of it’s dependency chain are not in deadlocks). Since 5 isn’t in the critical path you would have to next follow 5’s path if 1 wasn’t in a deadlock (incidentally 5 is also in a deadlock because it links into the same cycle 1 is in, therefore all listed resources are deadlocked in that cycle)
Another point regarding this particular problem is that all resources available (the set of R1-R5) are already acquired. In such a scenario it is impossible for any process to acquire another resource if no processes are willing to first let go of a resource. A cycle is inevitable in such a scenario. This fact that you should release resources before requesting more is I think supposed to be the lesson of the 73.4 philosophers problem (don’t quote me on that)
5
One of the formal tools aimed at detecting issues in concurrent systems (deadlock, resource starvation…) is Petri nets.
You model your problem with a Petri net, then you can perform mathematical analysis on it and prove some properties of your system, such as unreachable states.
1
In a formal sense, a deadlock will be indicated by one or more cycles in the resource allocation graph. The processes that form the cycle or cycles, or that transitively depend on the cycles are deadlocked.
2
For this problem, I used a Place/Transition (P/T) Net. I used the “standard” graphics for P/T Net with two modifications: changed the token colour from black to “reddish-orange”, added a bounding box with dashed lines to represent a process. I modified the labels you used for processes and resources – instead of starting from 1, I started from 0.
Then I marked the net according to the conditions you specified: P0 holds R0, P1 holds R1, etc.
Next I manually computed the status of each transition in the net (by visually inspecting the marked net). I did not find any enabled transition. So I left each transitions colourless. Since no transition is enabled, the system is deadlocked.
I included the situation where all resources available – in this case, some of the transitions are enabled (and coloured green).
I will include an interactive version in PDF using JavaScript. I’ll post it later.
2