Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Recently I've been working on projects that heavily use threading. I think that I'm OK at designing them; use stateless design as much as possible, lock access to all resources that more than one thread needs, etc. My experience in functional programming has helped that immensely.

However, when reading other people's thread code, I get confused. I am debugging a deadlock right now, and since the coding style and design are different from my personal style, I am having a difficult time seeing potential deadlock conditions.

What do you look for when debugging deadlocks?

share|improve this question
    
I'm asking this here instead of SO because I want more general pointers about debugging deadlocks, not a specific answer to my problem. –  Michael K Jan 26 '11 at 14:57

6 Answers 6

up vote 8 down vote accepted

If the situation is a real deadlock (i.e. two threads hold two different locks, but at least one thread wants a lock the other thread holds) then you need to first abandon all pre-conceptions of how the threads order locking. Assume nothing. You may want to remove all comments from the code you're looking at, as those comments may cause you to believe something that doesn't hold true. It's hard to emphasize this enough: assume nothing.

After that, determine what locks get held while a thread attempts to lock something else. If you can, ensure that a thread unlocks in reverse order from locking. Even better, ensure that a thread holds only one lock at a time.

Painstakingly work through a thread's execution, and examine all locking events. At each lock, determine whether a thread holds other locks, and if so, under what circumstances another thread, doing a similar execution path, can get to the locking event under consideration.

It's certainly possible you will not find the problem before you run out of time or money.

share|improve this answer
    
+1 Wow, that's pessimistic...ain't it the truth, though. It's a given that you can't find all bugs. Thanks for the suggestions! –  Michael K Jan 26 '11 at 16:21
  1. As others have said...if you can get useful information for logging then try that first as it is the easiest thing to do.

  2. Identify the locks that are involved. Change all the mutex/semaphores that wait forever to timed waits...something ridiculously long like 5 mins. Log the error when it times out. This will at least point you in the direction of one of the locks that is involved in the issue. Depending the variability of the timing you might get lucky and find both locks after a few runs. Use function failure code's/conditions to log a pseudo stack trace after the timed wait fails to identify how you got there in the first place. This should help you identify the thread that is involved in the issue.

  3. Another thing that you could try is building a wrapper library around your mutex/semaphore services. Track what threads have each mutex and what threads are waiting on the mutex. Build a monitor thread that checks how long threads have been blocking. Trigger on some reasonable duration and dump the state information that you are tracking.

At some point, plain old code inspection is going to be necessary.

share|improve this answer

First step (as Péter says) is logging. Though in my experience this is often problematic. In heavy parallel processing this is often not possible. I had to debug something similar with a neural network once, that processed 100k of nodes per second. The error happened only after several hours and even a single line of output slowed down things so much, that it would have taken days. If logging is possible, concentrate less on the data, but more on the flow of the program, until you know in which part it happens. Just a simple line at the beginning of each function and if you can find the right function, split that in smaller chunks.

Another option is removing parts of the code and data to localise the bug. Maybe even write some small program that takes only some of the classes and runs only the most basic tests (still in several threads of course). Remove everything gui related, for example any output about the actual processing state. (I found the user interface to be the source of the bug often enough)

In your code try to follow the complete logical flow of control between initialising the lock and releasing it. A common error could be to lock at the start of a function, unlock at the end, but have a conditional return statement somewhere in between. Exceptions could prevent releasing too.

share|improve this answer
    
+1 for the applications of "divide and conquer". –  Péter Török Jan 26 '11 at 15:44
    
"Exceptions could prevent releasing" --> I pity languages that do not have scoped variables :/ –  Matthieu M. Jan 26 '11 at 18:04
1  
@Matthieu: Having scoped variables and actually using them properly may be two different things. And he asked for possible problems in general, without mentioning a specific language. So this is one thing, that may influence flow of control. –  thorsten müller Jan 26 '11 at 20:01

My best friends have been print/log statements at interesting places within the code. These usually help me understand better what's really going on inside the app, without disrupting the timing between different threads, which could prevent reproducing the bug.

If that fails, my only remaining method is staring at the code and trying to build up a mental model of the various threads and interactions, and trying to think of possible crazy ways to achieve what apparently has happened :-) But I don't consider myself a very experienced deadlock-slayer. Hopefully others will be able to give better ideas, from which I can learn too :-)

share|improve this answer
    
I debugged a couple of dead locks like this today. The trick was to wrap pthread_mutex_lock() with a macro that prints the function, line number, file name and the mutex variable's name (by tokenizing it) before and after acquiring the lock. Do the same for pthread_mutex_unlock() too. When I saw that my thread's froze, I just had to look at the last two messages, there were two threads trying to lock but never finishing it! Now all that's left is add a mechanism to toggle this at runtime. :-) –  Plumenator May 3 '12 at 12:34

First of all, try to get that code's author. He'll probably have the idea what he had written. even if you two can't pinpoint the problem just by talking, At least you can sit down with him to pinpoint the deadlock portion, which will be much faster than you understanding his/her code without help.

Failing that, like Péter Török said, Logging is probably be the way. As far as I know, Debugger did a bad job on multi-threading environment. try to locate where is the lock is, get a whole what resources are waiting, and in what condition the racing condition occurs.

share|improve this answer
    
no, logging is your enemy here - when you put slow logging in, you change the behaviour of the program to the point where it is easy to get a program that runs perfectly fine with logging enabled, but deadlocks when the logging is turned off. Its the same kind of problem you'd have when running a program on a single rather than a multicore CPU. –  gbjbaanb Oct 22 '12 at 21:41

This question attracts me ;) First of all, consider yourself lucky since you were able to reproduce the issue consistently on every run. If you receive the same exception with the same stacktrace each time then it should be fairly straight-forward. If not, then don't trust the stacktrace that much, instead just monitor the access to the global objects and its state changes during the execution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.