Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Shadowgandor]

Hey all, I'm currently studying for a test on application infrastructure and I was wondering if someone could answer my question.
There are three processes running and four resources available. P means it's getting claimed while V means it's getting released.


Can this program cause a deadlock to happen and why? My guts says that it can but I can't find any proof for it. It would be great of someone could help me with this!

[Drakale]

If the P functions are atomic, I don't see how it can lock in this specific case, unless one of the critical process hangs of course. Due to process 3 never holding R3 and R2 at the same time, there is not interlock possible.

Not 100% sure, but thats my opinion.

Also, it's pretty weird that process 1 and 2 release function they never locked. It's harmless now since those function are only used by process 3 and releasing them early will not cause a lock, but if the resources are used in process 1 or 2 there will be problems down the road. If you where to add a lock on process 1 and 2 to fix that, then you have to be really careful about interlocks.

[Vector]

Yeah.  Everything that Drakale said.

[Shadowgandor]

Thanks for the replies!
I was actually wondering...What is Process1 takes R1 and R4. Next, process3 takes R3 and process1 runs again, releasing R3. Now when process3 tries to release R3, would it go like "Hey! I want to release this resource but I currently don't have it. I will wait for it.." and pause. Process1 releases R1 and R4 and process 2 claims R1 and R4. Process 2 now waits for a chance to release R2, but seeing how process3 is still sleeping, the program will deadlock.

I'm just not sure if the program would continue if it tries to release a resource that already was released. That image plus my question was exactly what one of the example questions from a test looked like. Ah well, if this question gets into the real test as well, I guess I need to defend my answer in order to get my points ^^

[Drakale]

Typically, you won't get a hang if you try to release a lock that is already released. It is however a sign that something is sloppy in your thread management. I'd be more worried about the consequences of having a locked resource randomly freed mid-critical instruction as nothing prevent another thread to lock it and play around with it.

[gimlet]

You could, ya know, ask the professor....   Either pop in during office hours, or see if he has a minute after class.   Getting clarification on these weird cases can save you some grief, either a wake up call that you're not grasping something fundamental or conversely agonizing over a typo or a bad example.   (First make REALLY SURE the answer isn't somewhere in your text though).

And you can follow up with your question on when a program might WANT to have processes  release locks that they did not claim - it helps to understand the motivation behind some of the problems (or, as I suspect, he'll agree w/Drakale and say something like  "yeah that's unusual, confusing and full of potential problems if you're not really really careful")

[Shadowgandor]

Yea thanks for the advise, although I already had the exam this morning. Procrastination ftw! This question returned in a somewhat different form, but it was pretty tame compared to some other questions in terms of vagueness.

[Shakerag]

Generally speaking, you only want to release a lock you obtained.  As far as I know, you will get an ABEND if you try that nonsense in assembler.  Maybe those frilly higher-level languages let you get away with murder anymore >_>

[Stargrasper]

Generally speaking, you only want to release a lock you obtained.  As far as I know, you will get an ABEND if you try that nonsense in assembler.  Maybe those frilly higher-level languages let you get away with murder anymore >_>

Somehow, I'm guessing the higher level languages would be more likely to prevent that by virtue of their tendency to enforce more rules.  I'm willing to bet C/C++ will let you do it; just because they let you do virtually anything, tell you you're an idiot for doing it, and then (usually) blow up when you try anyway.  I haven't tried that recently, but  I'm assuming all it would do is be a fine demonstration in poor design.

You're definitely right, you need a very good reason to allow a process to release a lock it doesn't currently own.  If that reason isn't deadlock resolution, after detection, you're probably doing it wrong.

On that note, it might be worth mentioning that programs typically do one of three things to handle deadlocks:

• Nothing - Not attempting to do anything is the fastest and computationally easiest by virtue of non-existent overhead; but if deadlock occurs, you're screwed.  This will be used if deadlocks are assumed to be impossible or extremely unlikely.
• Deadlock Prevention - If well designed, prevention can ensure that deadlock cannot occur; but this involves a great deal of overhead and if you missed something, you're still screwed.  This would be used if it is assumed deadlocks will be relatively common.
• Deadlock Detection and Resolution - Every N cycles, the system will scan for deadlocks.  If detected, certain processes will be killed and their resources freed.  A well designed resolution system will ensure that no single process is likely to be starved.  This would probably be used if deadlocks are assumed to be rare, but it is assumed that they will occur.  This involves at lot of overhead a certain times, but no overhead most of the time.

Also worth noting is that systems typically will either prevent or detect.  Not both.

[MorleyDev]

Some semaphore implementations may allow it, but since C++11's mutex locking is supposed to be used via scoped_lock, which is RAII so it should never be a problem.

Since pthread's serves the basis for C++11 mutex's design, and that doesn't allow this behaviour...I'd imagine it'd just blow up (it's technically "undefined behaviour" in pthread, so it could work, or it could cause your computer to start singing daisy daisy).

[Aptus]

My gut instinct is to say that no, that setup can't deadlock. (I am curious why T1 releases a lock it does not take, I know there is a weird kind of synchronization hack that can be done by use of assymetric mutex but as far as I know it is not good programming to do it that way.)

The conditions for deadlock:

• Mutual Exclusion
• No Preemption
• Hold and Wait
• Circular Wait

T1 and T2 share resources but the way it is set up they can not deadlock with eachother. Now if one of them had switched it around a bit we would have a classic example of deadlock. (T1 takes R1 and then R4 while T2 takes R4 then R1. Then T1 would be waiting for R4 while T2 would be waiting for R1.)
T3 is clear to just run, assuming these are the only threads using these mutexes and it is the only thread claiming them, it can't lock. It is terribly set up though since T1 and T2 can release the locks held by T3 while it is still in it's critical sections.

Basically the relation between T1 and T2 do not have the "Circular Wait" condition met so they can't deadlock and T3 has no other threads that it shares mutex with.

So from the information given in that picture, no that system can not deadlock, but it is still horribly designed.

[Sigulbard]

I thought this thread was going to be about dreadlocks.