1

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!

Improve this question
10
  • 1
    Why do you think there is no deadlock? Can you expand on that? What would an example of deadlock be?
    – Gray
    Commented May 1, 2012 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
    Commented May 1, 2012 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
    Commented May 1, 2012 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
    Commented May 1, 2012 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
    Commented May 1, 2012 at 17:33

4 Answers 4

Reset to default
1

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.

Improve this answer
1

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)

Improve this answer
1
  • Neither of those is a deadlock. That is just lock contention.
    – Gray
    Commented May 1, 2012 at 17:23
1

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.

Improve this answer
0

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.

Improve this answer
1
  • 2
    Why is this a deadlock?
    – Steve Townsend
    Commented May 1, 2012 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.