RE: deadlock detection

["Boehm, Hans" <hans_boehm at hp dot com>]

I think that if you want to detect deadlocks on the fly, you really only have to check as you are about to lock a heavyweight lock.  And then it suffices to do a depth-first search of only the heavyweight locks reachable from the one we're trying to acquire.  My guesses:

1) This is typically very cheap, since you only pay on persistent contention, and there probably aren't very many heavyweight locks.

2) There are probably weird cases for which it's expensive.  It probably shouldn't be the default.

It seems to me that the result is still quite limited though, since it only detects deadlocks involving exclusively locks, as opposed to wait/notify or more obscure dependencies (IO, wait loops on volatiles, etc.)  My guess is that this covers around half the half the Java deadlocks I've seen, though my experience may be atypical.

Hans

> -----Original Message-----
> From: Andrew Haley [mailto:aph@redhat.com]
> Sent: Friday, September 05, 2003 10:28 AM
> To: Jacob Gladish
> Cc: Jeff Sturm; Tom Tromey; GCJ
> Subject: Re: deadlock detection
> 
> 
> Jacob Gladish writes:
>  > I just didn't want to discuss anything that somone might think
>  > inappropriate for this list. But I guess it's fine. I'll check into
>  > these link you provided over the weekend. 
>  > 
>  > If I understand what you're saying here, the graph would have to be
>  > updated as threads enter/exit the monitor calls, and could 
> not be be
>  > generated on demand. I think ideally it would be 
> non-intrusive on normal
>  > operation until the vm was sent a signal which would trigger the
>  > algorithm to get a list of threads and a list of mutexes for each
>  > thread, and then eventually dumping the results somewhere.
> 
> I see your point.
> 
> Well, the first problem would be to find all of the locks in the
> system.  If we're using hash synchronization, I suppose we just need
> to look in the hash table.  That would be non-intrusive.
> 
>  > On the other hand, if the graph was continually updated, 
> the vm could
>  > detect deadlocks before they occurr or simply update the 
> graphs state
>  > waiting for the signal to run the algorithm.
> 
> I like the idea of detecting deadlocks when they occur, but I think
> you have to do a depth-first search of the whole graph.  Still, it
> might work well if you're really stuck, altho' it would slow things
> down a lot.
> 
> Some magic that only triggers when a thread has been blocked for a
> while might work.
> 
>  > Something like this would of course require a method to shut it off
>  > for performance considerations. Possibly a property or static
>  > method on the System class? I'd opt for a property since adding a
>  > method to the system encourages non-portable code.
> 
> OK.
> 
>  > I'm not very familiar with how Sun's vm does this. All I 
> know is that it
>  > is capable of detecing the deadlocks. I guess 
> investigating their docs
>  > might provide some insight.
> 
> As I understand it they have a magic keystroke that stops everything
> and then does deadlock analysis.  I like the idea that we might have
> an option to do continuous checking as well.
> 
> Andrew.
> 
> 
>  > On Fri, 2003-09-05 at 12:43, Andrew Haley wrote:
>  > > Jacob Gladish writes:
>  > >  > 
>  > >  > And I'll second that vouch. We have an application 
> with a large number
>  > >  > of threads, and deadlocking the system is very easy 
> to when a developer
>  > >  > is even slightly careless with synchronized blocks. A 
> simple singal to
>  > >  > report the deadlocked condition would have saved us 
> many hours of
>  > >  > pouring over thread dumps.
>  > >  > 
>  > >  > Maybe this could be something for me to contribute to 
> the 3.3+ line.
>  > > 
>  > > This would be a useful addition to gcj.
>  > > 
>  > >  > Is anyone interested in an offline discussion on this?
>  > > 
>  > > Yes, but I don't think it's necessary to take the 
> discussion offline.
>  > > However, if that's what you want I'll gladly go along with your
>  > > wishes.
>  > > 
>  > > My understanding is that deadlock detection can be done with a
>  > > resource-allocation graph algorithm; you have to look 
> for cycles in
>  > > the graph.  Given that every synchronization calls 
> _Jv_MonitorEnter,
>  > > it should be fairly easy to build such a graph.  There's 
> code to do
>  > > that here:
>  > > 
>  > > http://www.phfactor.net/code/dldet/
>  > > http://www.phfactor.net/code/dldet/deadlock.zip
>  > > 
>  > > On a related matter, there's an interesting paper at
>  > > http://www.acm.org/crossroads/xrds4-2/dynac.html.
>  > > 
>  > > Andrew.
>  > -- 
>  > Jacob Gladish <gladish@spinnakernet.com>
>  > Spinnaker Networks
>  > 
>