Re: deadlock detection

[Andrew Haley <aph at redhat dot com>]

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
 >