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.

Here is the question I'm having trouble with:

Give the resource graph and determine whether a deadlock state results. Assume that when a thread requests an available or unallocated resource, the OS immediately allocates that resource to the thread.

  • There are three threads: T1, T2, T3
  • There are three resources: R1, R2, R3

Here is the sequence of events:

  1. T1 requests R1
  2. T1 requests R3
  3. T2 requests R2
  4. T2 requests R3
  5. T3 requests R1"

Now, I have written out the graph for the problem.
Allocation Question

Have I drawn the graph appropriately? Based off of this graph, I assume there is no deadlock because there are no cycles. I am unsure if my solution is correct. Can anyone help clarify this? Thank you!

share|improve this question

migrated from stackoverflow.com May 2 '12 at 20:14

This question came from our site for professional and enthusiast programmers.

1  
Why do you think there is no deadlock? Can you expand on that? What would an example of deadlock be? –  Gray May 1 '12 at 17:17
1  
I think that deadlock occurs only when there is a cycle in the graph. However, I don't see any cycles in it. I know that some threads are waiting for others to free up resources, but that shouldn't create a deadlock--if my assumptions are correct. –  TimeBomb006 May 1 '12 at 17:21
1  
I'm not sure what you mean by cycle but you are correct about waiting for resources versus a deadlock. So what would an example me of a deadlock using the resources? –  Gray May 1 '12 at 17:23
1  
Btw, I assume that the Rs and Ts aren't somehow connected, right? It could be R4, R5, R6 instead of the same numbers as T1-3, right? –  Gray May 1 '12 at 17:28
2  
Yes, you are correct. This is not deadlock because T1 can still operate. When it is done it will unlock R3 and T2 will get it. It will unlock R1 and T3 will get it. –  Gray May 1 '12 at 17:33
show 5 more comments

4 Answers

up vote 1 down vote accepted

I'll summarize our conversation in the comments.

Have I drawn the graph appropriately? Based off of this graph, I assume there is no deadlock because there are no cycles.

You are correct, your question does not show any deadlock conditions.

For me deadlock is not about "cycles" but about multiple locks and different lock order. As you mention in your comments the following is deadlock because they each lock 2 locks in a different order.

T1 requests R1. T2 requests R2. T1 requests R2. T2 requests R1.

Both T1 and T2 are blocking each other forever. That is deadlock.

But in your OP, there is nothing stopping T1 from finishing with the resources and unlocking them. Then T2 and T3 will get their locks and everything will continue. That is just lock contention.

share|improve this answer
add comment

You have two processes accessing the same resource but a deadlock will not occur.

T2 is requesting R3. Since T1 is already using R3 T2 can wait or try again at a later time.

T3 requests R1 but can wait or try again later once T1 has finished. A deadlock would ONLY take place when t3 requests R1 and T1 has not released the lock because it is waiting for a process from T3 (which it wouldnt because it wants access to R1 first)

share|improve this answer
    
Neither of those is a deadlock. That is just lock contention. –  Gray May 1 '12 at 17:23
add comment

http://imageshack.us/photo/my-images/684/ploti.png/

here is how to make the graph, but you have to fix how many cycles the resources will be allocated and could they be allocated for two different threads.

deadlock happens when two threads request same resources and get mutually blocked.

share|improve this answer
add comment

the problem reside in the allocations 4 and 5

4. T2 requests R3
5. T3 requests R1

you have to use a timelined graph (axis1 threads, axis2 cycles) and follow the evolution of the allocations in every cpu cycle.

share|improve this answer
2  
Why is this a deadlock? –  Steve Townsend May 1 '12 at 17:26
add comment

Your Answer

 
discard

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