Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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. 
share|improve this question
5  
This is why the real world is easier than these made up scenarios: In industry if this situation arose, people wouldn't try identifying if it was a deadlock scenario, they would all recognize it was a terrible mess waiting to become a problem if it wasn't already, and would come up with a solution for whichever problem this situation was trying to solve that didn't involve such a horribly risky resource dependency scenario –  Jimmy Hoffa Jun 26 '13 at 5:05
1  
@Jimmy Hoffa: such scenarios arise all the time in a DBMS that has row-level locking, and the industry solution is to have an automatic deadlock detector that rolls back transactions involved in any deadlocks it finds. –  Michael Borgwardt Jun 26 '13 at 6:34
    
@MichaelBorgwardt True, and everytime I've worked on a system where a deadlock victim was chosen by the DBMS in a scenario, there was a fair amount of engineering effort expended afterwards to find where so that whatever caused it could be restructured to have a less risky resource utilization approach. There is of course a minority of software in the world where this level of complexity is just a fact (like the DBMS itself; there's no getting around writing a DBMS means committing to accept and manage a high level of complexity), but that's a small minority. –  Jimmy Hoffa Jun 26 '13 at 6:48
    
@MichaelBorgwardt: No, such scenario's only arise if you don't follow the "always acquire locks in the same order". That rule was invented long before I even started in IT (and that was a long time ago in itself). –  Marjan Venema Jun 26 '13 at 7:46
1  
@Marjan Venema: The problem is: if you have row-level locking in a DBMS, locks are often acquired implicitly, and specifying their order can be difficult or impossible –  Michael Borgwardt Jun 26 '13 at 8:15
show 1 more comment

3 Answers

up vote 4 down vote accepted

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)

share|improve this answer
    
is there a typo? P1 -> P3(R3) -> P4(R5) -> P2(R2) -> P1(R1) –  rwong Jun 26 '13 at 5:10
    
@rwong oh I didn't look close enough to see P4/P5 have there ersources swapped. That's a silly trick just trying to make people miss a detail, thanks for the correction! –  Jimmy Hoffa Jun 26 '13 at 5:14
    
Thanks, this is by far the easiest method I've seen. –  Dawson Jun 26 '13 at 5:17
    
Is there a way with this method to ID the processes that are in deadlock or it just indicates a deadlock exists? –  Dawson Jun 26 '13 at 5:18
    
@Dawson if a linked list has a cycle (loop) inside of it, every member of that linked list is a member of an unending list. Deadlocks occur when a dependency chain is unending, thus all members of a dependency chain in deadlock are deadlocked, any members not in the deadlocked dependency chain however might not be deadlocked, you would have to check them to find out. For instance if the dependencys were 1->2->3->2 and 4->5, 1,2,3 are in deadlock but 4,5 are not. –  Jimmy Hoffa Jun 26 '13 at 5:22
show 2 more comments

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.

share|improve this answer
    
+1: would be even better if you mentioned an algorithm for cycle detection. –  Michael Borgwardt Jun 26 '13 at 7:43
    
He wants to do it manually and he says he has already drawn the graph. He is asking for "a way to solve this", not an algorithm. –  Stephen C Jun 26 '13 at 16:58
add comment

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.

share|improve this answer
    
+1 for listing a formal tool which is well studied and the comprehension/use of which yields benefits in having a great deal of known details and calculations that past researchers have come up with so you don't have to reinvent any of them. –  Jimmy Hoffa Jun 26 '13 at 6:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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