Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

technobot

Detecting deadlocks

This topic is 5284 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. We are currently working on the multithreading infrastructure of our game engine, and we have come accross the issue of dealing with deadlocks. As long as we can detect them, we can deal with them, but how can we detect them efficiently? The solution we found so far is this: 1. Maintain a wait-dependancy graph, which stores which threads are waiting for which other threads. 2. Derive our own syncronization objects. 3. Override the lock method in each of those objects to do: . a. Check which threads have a lock on the given synchronization object, with a lock type that is mutually exclusive to the requested lock type. This thread will have to wait for these threads to finish with their lock. . b. Trace the wait-dependancy data for those threads. If the current thread id is encountered, then we have a deadlock situation, and must terminate. . c. If we survived step b, initiate the lock and add the current thread to the wait-dependancy graph. 4. Override the unlock method in the sync objects to remove the corresponding thread from the wait-dependancy graph. Unforetunately, this requires a potentially expensive graph traversal each time a lock is initiated. In particular, if multiple-read-exclusive-write synchronizers are involved, this can get rather nasty, since each write lock request may be waiting for multiple read locks to be removed. Further, this method does not allow the detection of a deadlock stemming from two event objects (more widely known as semaphores, I think) waiting for each other. Then again, I'm not sure any method can detect that kind of deadlock, since it is technically not really a deadlock... Is there a better way to detect/handle deadlocks, or is this as good as it gets? Michael K., Co-designer and Graphics Programmer of "The Keepers"
We come in peace... surrender or die! [edited by - technobot on June 1, 2004 4:37:10 PM]

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
> As long as we can detect them, we can deal with them

Do I get you right here? Are you trying to detect deadlocks programatically and if you do, try to resolve it in runtime??? Basically trying to fix bug while running the program?

If I got you right, I''d *strongly* advise you to not do this. The way to avoid deadlocks is to be clear about all locks needed and in what order they are taken. I cannot see why you would like to do this during runtime.

Go for a good design, draw lock object dependencies so you can make sure to always acquire locks in the same order etc.

Share this post


Link to post
Share on other sites
Not really resolve.. not sure if it''s even possible. Log the deadlock and terminate the program is our current intention. This is for debugging purposes.

Even if the design is such that there should theoretically be no deadlocks, deadlocks can still occur in practice due to errors in the implementation, or even in the design itself. If we cannot detect the deadlocks, we cannot fix them.

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

Share this post


Link to post
Share on other sites
The simplest way I can think of is to have a central lock manager and all threads contact the manager in order to receive/release a lock. The lock manager can ensure that locks arent given out in an order that would cause deadlock. There are other ways to do it but most of them assume that threads can still do other things while waiting for a lock. I dont know if that is true in your case or not.

"Give a man a fish and he will eat for a day, drown a man in the water and the fish will eat for a week!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Do a decent design, make sure to always take locks in the same order. I.e. if thread A and thread B both needs to aquire lock L1 and L2, make sure that both threads always first aquire L1 and then L2.

Deadlocks are mostly very visible, so you will notice when they occur. If/when you see them, attach a debugger and work to find the problem. Windbg is a free debugger from Microsoft great for this kind of debugging.

I don''t think you need to start with detecting deadlocks programatically. Actually I think you would spend a whole lot of time on something that still doesn''t give you a bullet-proof solution. What you could do is to have some sort of tracing system, so that you later on could see what happened before the deadlock in a logfile or so.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Also, keep the locks as local as possible (low lock granularity). Don''t have a super-mega-global critical section for everything, but rather a few well chosen ones, that you aquire within a well defined code block.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Do a decent design, make sure to always take locks in the same order.[...]

yes, I agree that a solid design is the first and most crucial step, but as I said - bugs happen.
quote:
Deadlocks are mostly very visible, so you will notice when they occur. If/when you see them, attach a debugger and work to find the problem. Windbg is a free debugger from Microsoft great for this kind of debugging.

I'm not so sure how visible they are.. Assumming there is a bug that causes two threads to deadlock, unless one or both of them have major affect on the other threads, the deadlock can easily be unnoticed. Even if the deadlock causes enough problems to be noticed, identifying the source of the problems as a deadlock is not always easy.

On the other hand, if we detect the deadlock as it first occurs, we will immediately see from the log that we have a deadlock, and will also know where it occured and which locks were called where, and in what order. This would significantly shorten the debugging process, which is why we prefer to detect all errors (deadlocks included) as they first occur and log any useful debugging info at that time, rather than rely on a third party debugger to figure out what's going on in retrospect.
quote:
I don't think you need to start with detecting deadlocks programatically. Actually I think you would spend a whole lot of time on something that still doesn't give you a bullet-proof solution. What you could do is to have some sort of tracing system, so that you later on could see what happened before the deadlock in a logfile or so.

The reliability of the detection mechanism and the time spent on its programing depends on its design, and the restrictions placed on the locks. This is why I posted my original question - to find alternative approaches, which may work better than what I've come up with. I can then use that knowledge to design a system that is also as easy as possible to write.

Note that the number of possible lock types is finite and small, therefore the number of possible deadlock types is (I think) also finite and (relatively) small. So it should be possible to prepare for all the deadlock types.. I'll post a deatailed list of the types of possible locks and deadlocks in our system later.


cmptrgear : the central lock manager suggestion sounds interesting.. but how would you implement the lock order check? Would you not also need some sort of graph, only a lock sequence graph instead of a wait dependancy graph? Granted, such a graph would be able to detect the possibility of a semaphore to semaphore deadlock, which is something the wait dependancy graph cannot do..

What other methods are there?

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

[edited by - technobot on June 2, 2004 5:39:10 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!