Change character in string

[Andreas Leitgeb]

So you meant to have it deterministically check for a cycle *every* time
a lock acquisition was attempted?

Not every time, but only if the thread would actually go into blocking
state *and* already holds a lock. My reasons for favoring my approach to
a watchdog (that's how I understood yours) is, that here we have a trigger
(namely a thread with a lock in its hand trying to grab another one and
not immediately getting that other one) that immediately points us to a
candidate, whereas the watchdog would have to be actively checking through
all existing threads for one being deadlocked, each period.

I believe it is not a significantly expensive pre-check and for those
threads that meet this condition, it is worth the trouble to follow
the chain in search of a loop.

Those cases of high throughput are those where the lock is immediately
available, and I don't yet see anything changing about that.

One thing, that makes my idea a bit hard to understand, is that I'm
talking of a thread doing something (namely searching through the
lock-chain for a loop), while actually in blocked state. That sure
requires some new pitch black jvm magic, but I don't consider it
unthinkable.

 

[Andreas Leitgeb]

This discussion is heading in towards one of the interesting research
areas, transactional memory.

I didn't see it heading this direction. but nevertheless it's surely
an interesting area.

Drepper, U. 2009. Parallel programming with transactional memory.
Commun. ACM 52, 2 (Feb. 2009), 38-43. DOI=
http://doi.acm.org/10.1145/1461928.1461943

I first got a bit stuck with thinking whether the bug they mention with
the locking approach is about locking timestamp1 but using timestamp2,
or whether there was a more subtle bug that I fail to spot. I do not see
how that simple example there could even be susceptible to a deadlock.

Finally, I do not follow the argument about how the "collide, step back-
and retry later" is already supposed to work fine in IP-networks, of which
probably only a very small number still runs over those 10MBit Coax-cables,
where one could have more senders to the same wire. Today's IP-networks are
working with hubs, switches and routers, but afaict no longer with a single
(coax) cable passing by all the machines in the room. I'm even surprised
to read that this collision handling is supposed to be part of IP, rather
than of the ethernet layer.

I for myself do not yet buy in to this idea of TM. (While still using
transactions with databases, of course.)

 

[Andreas Leitgeb]

whereas the watchdog would have to be actively checking through
all existing threads for one being deadlocked, each period.

Even worse (for the watchdog):
- threads t1 and t2 might lock each other.
- thread t3 has an unrelated object's lock, and waits for a
lock held by either t1 or t2.

If the watchdog happens to visit t3 first, it's lock chain
never comes back to t3, but doesn't terminate, either, as
it is caught in the loop spanning t1 and t2.

 

[Larry K. Wollensham]

Not every time, but only if the thread would actually go into blocking
state *and* already holds a lock.

This makes sense.

One thing, that makes my idea a bit hard to understand, is that I'm
talking of a thread doing something (namely searching through the
lock-chain for a loop), while actually in blocked state. That sure
requires some new pitch black jvm magic, but I don't consider it
unthinkable.

Ah. It also removes some efficiency worries, if the thread itself does
the cycle-check and while it would otherwise have been idle anyway.

 

[Larry K. Wollensham]

Even worse (for the watchdog):
- threads t1 and t2 might lock each other.
- thread t3 has an unrelated object's lock, and waits for a
lock held by either t1 or t2.

If the watchdog happens to visit t3 first, it's lock chain
never comes back to t3, but doesn't terminate, either, as
it is caught in the loop spanning t1 and t2.

Such a watchdog would have to mark each thread it visited and see if it
reached an already-marked thread, rather than just remembering its
starting point. After you clarified it, I think your idea may be better,
cycle-detection during lock acquisition when already holding at least
one lock and the target lock is contended.

 

[Andreas Leitgeb]

This makes sense.

Isn't it boring, once a factual consensus has been reached? ;-)