1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Deadlock Prevention

  1. Aug 6, 2014 #1
    1. The problem statement, all variables and given/known data

    Here is the relevant info from the assignment handout:

    http://pastebin.com/nfXcF88u [Broken]

    3. The attempt at a solution

    I have written the code, however i do not see how deadlocks can even be possible with this assignment. Since there is a monitor thread which automatically frees resources after their usage time is ended, there is no way a deadlock could occur. I thought one of the conditions of deadlock was that a thread would not give up the resource it has until it is able to access the resource it wants. In this assignment, the monitor will force threads to release resources so even if there exists a cycle, it will be broken by the monitor thread very quickly.

    It seems like the Banker's Algorithm would be overkill for this assignment. Can someone explain how exactly a deadlock would be possible?

    Would it not be the most efficient to just let threads access the resources they need (unless of course there are no instances of a needed resource) until they are all done?
    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Aug 6, 2014 #2
    Unfortunately, I cannot access pastebin.com.

    If there are two threads and each can claim the same two resources and they might claim them in reverse order, then you have the potential for a deadlock.

    When you say "access the resource they need", I hope you mean once they have successfully claimed the resource. Deadlocks aside, two threads should not attempt to access the same resource at the same time.
  4. Aug 6, 2014 #3
    In this assignment, threads 'claim' resources. A resource cannot be accessed by more than 1 thread at a time.

    The issue is, even if a deadlock were to occur, the monitor would free a resource and break the loop.

    We have learnt in class that there are 4 conditions that must hold in order for deadlocks to actually "happen". One of those conditions is "hold and wait", ie. a process holding at least one resource is waiting to acquire additional resources held by other processes. Since the monitor makes it impossible for threads to hold a resource indefinitely, there technically can't be deadlocks, right?
  5. Aug 6, 2014 #4
    I'm not sure what you mean by "breaking the loop". Do you mean that the threads sit in a wait loop for resources?

    How does the monitor keep a thread from holding a resource too long? Does it simply kill that thread?
  6. Aug 6, 2014 #5
    When i say loop i mean a deadlock cycle, ie.


    This deadlock cycle can occur with the code i have, however since there is a monitor thread which frees resources from processes, the deadlock will be undone.

    If the monitor did not exist, then the deadlocks would be permanent.
  7. Aug 6, 2014 #6
    A monitoring function that simply frees the resources after a time limit is a pretty useless monitor. What happens to the thread that is still using that resource? Let's say it's a block of memory. What happens when the thread tries to write to that block? Does it succeed - which means that it could interfere with other threads? Or does if fail, perhaps generating an exception, which that thread would have to deal with?

    More importantly, how does that thread know that it has lost its first resource if it isn't accessing it any more because it is trying to get a second resource?

    Is there some other way I could see this assignment? Pastebin.com is blocked from where I am now.
  8. Aug 6, 2014 #7
    Here it is

    Currently my code works but i have a feeling i'm not actually doing deadlock prevention the way they want us to. I don't even have any deadlock prevention in my code since it never gets stuck.
    Last edited: Aug 6, 2014
  9. Aug 6, 2014 #8
    You need a new instructor.
    Not only is that assignment broken, the notes that say "rejected, deadlock prevented" are misplaced and make me wonder if your prof understands the subject matter. What they should say is simply "rejected, resource unavailable" - which is almost the opposite.

    What I would do is change the OS so that time elapses against a resource only when the thread is not waiting.
  10. Aug 6, 2014 #9
    I'd like to make a lot of changes to the assignment however i doubt they would take kindly to that.

    Given the description of the assignment, my best assumption of what they mean by "deadlock prevented" is that there were no resources available to the thread when it tries to acquire one, so it instead waits and tries again to acquire the resource once the monitor has freed one.

    But the solution to this seemingly goes against the concept of deadlocks. There can't be a deadlock if there's an external monitor thread with the ability to free resources from all of the threads.
    Last edited: Aug 6, 2014
  11. Aug 6, 2014 #10
    I can't find a way to interpret this assignment in a useful way. There is one term: "cooperating". In what way are these threads supposed to be cooperating? Perhaps that is the key.

    In the example, it certainly looks as though they are granting the requests whenever the resource is available.

    A null test case is one that you try for the purpose of demonstrating a failure - in this case a deadlock. As you have noted, in this assignment there is no null test case - you can't loose.

    What you can do is demonstrate an algorithm for yourself using a model that does not advance the time - and therefore can be broken. Then submit that with the broken model (as assigned) - perhaps with a note indicating that it had been tested under conditions where the null test case failed.

    I would also report two types of resource request rejection - one for the resource being unavailable, the other for the purpose of avoiding a deadlock.

    --- edit ---

    What level course is this? Is it a pretty difficult engineering college?
  12. Aug 7, 2014 #11
    This is a computer science course about operating systems, synchronization, parallelism, CPUs etc.

    Since there can be pseudo-deadlocks, should i attempt to trace a circle from one thread back to itself when it tries to acquire a resource?


    Thread1 has already acquired Resource1.
    Thread2 has already acquired Resource2.
    T1 acquires R2.
    T2 tries to acquire R1 but since R1 -> T1 -> R2 -> T2 -> R1, it is disallowed, using the logic from that diagram i posted.
  13. Aug 7, 2014 #12
    When you say you want to "prevent deadlocks", you mean one of two things:
    1) When a deadlock occurs, you don't want the system to hang - but it's okay if the application crashes.
    2) You want to avoid a possible deadlock before it happens - by declining a claim.

    The first case is pretty simple. All you have to do is detect a deadly embrace (each thread requesting the resource the other has), kill one of those two threads, and take its resources.

    To do the second, you need to order the resources so that whenever a thread claims one resource, it also ties up all other resources that precede it in the order. If you know ahead of time which thread may need which resources, you can be loose with resources that are not potentially claimed by more than one thread.

    For example:

    Thread 1 will need A, C, E, and G
    Thread 2 will need B, E, F, and G

    Resources are ordered E, G.
    Resources A, B, C, D, and F are unordered because they are uncontested.

    Thread 1 claims A
    Thread 2 claims F
    Thread 2 claims G - this ties up E which precedes G in the order
    Thread 1 attempts to claim E - but must wait.

    The potential deadlock is thus avoided. Thread 2 is unencumbered and thread 1 has nothing that thread 2 might want. So eventually thread 2 will complete or reach another state that will allow E to be claimed by thread 1.

    You can implement this, but the model provided in the exercise will not allow you to test it. To test it, you will need to change the model. After it is tested, you can change the model back - and, of course, it will still work, and it will meet the requirements of your assignment.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted