🔒 Locked

Detecting deadlocks

Started by technobot Jun 1, 2004 at 3:30 PM 5 replies 950+ views

Original Post

Jun 1, 2004 at 3:30 PM

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]

technobot

Author

technobot

Jun 1, 2004 at 4:10 PM

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!

cmptrgear

Jun 1, 2004 at 4:33 PM

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!

technobot

Author

technobot

Jun 2, 2004 at 4:30 AM

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]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.