deadlock detection

Thu Sep 11 17:03:00 GMT 2003

I've implemented a small simulation of a Wait For Graph that I'd like to
fit into the current runtime, but I'm unsure of what data structures to
use. My current implementation uses the stl, since it was easy and quick
to nail the algorithm down. I'm not sure what data structures to use
when putting this into the runtime. Is it ok to use the collections from
java::util? What I currently have planned is to add hooks into the
_Jv_MonitorEnter/_Jv_MonitorExit calls to adjust the graph state, and
the finalize_native to remove any thread entries from the graph. Is it
ok to reference the collections from this level or do new data
structures need to be written from scratch?
On Sat, 2003年09月06日 at 05:40, Andrew Haley wrote:
> Boehm, Hans writes:
>> > 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.
>> Oh, of course! Thanks Hans.
>> That's obvious, but for some reason I didn't think of it -- you only
> have to look at the part of the graph you changed.
>> > 1) This is typically very cheap, since you only pay on persistent
> > 1) contention, and there probably aren't very many heavyweight
> > 1) locks.
> > 
> > 2) There are probably weird cases for which it's expensive. It
> > 2) 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.
>> That's a useful insight.
>> Andrew.
-- 
Jacob Gladish <gladish@spinnakernet.com>
Spinnaker Networks