Re: Deadlock-avoiding with .equals() (was: Re: Vector (was Re: Change
character in string))
On Sun, 15 Mar 2009, Andreas Leitgeb wrote:
Tom Anderson <twic@urchin.earth.li> wrote:
On Sat, 14 Mar 2009, Andreas Leitgeb wrote:
For the philosophers that would mean, that before even taking their
first fork, they'd first have to grab the one napkin in the center of
the table (ugh :-)
Btw., this also extends to that the rivalling school of misosophists at
next table can have their own table's central napkin, and do not need to
go over to their arch-foes' table to take theirs. The misosophists, of
course, also won't borrow any of the philosophers' forks.
That reminds me: there is yet another solution. You have a global map
(probably a WeakHashMap) from Pair<List> to Object, which is lazily filled
with pairs of any interesting lists, mapped to Objects to which there are
no heap references outside the map; pairs (a, b) and (b, a) always map to
the same Object. Pair's equals and hashCode methods have to be based on
the identity of the lists rather than their contents. Then, to do an
equals, you use Pair(this, that) as a key into the map, and use the
resulting object as a mutex.
Actually, there's another way: if there's a total order on the forks, then
the philosophers just have to agree to always pick them up in that order.
That thought also occurred to me. If java maintains internally some object
identity, that won't change during the whole lifetime of the object,
especially not during any GC'ing.
That's exactly what an identity hash code is. See System.identityHashCode,
and the thread we had here several months ago where someone dug out the
actual implementation(s).
(I don't know if "the internal address of the object" as mentioned in
the javadoc for java.lang.Object really has that property. It should,
but it's not guaranteed to exist) With that, Java could add a
multisync(obj1,obj2,...) feature, that would first make a consistent
re-arrangement of the given objects based on that identity, and then
lock them all in the "same" order.
The problem is that the identity hash is no more than 32 bits in size, and
a JVM can have more than 2**32 objects, at least on 64-bit machines. That,
and the fact that the definition does not promise that objects will have
unique identity hashes, and the implementation that's used doesn't make
any particular effort to achieve it (we think it's a per-thread
pseudorandom number generator).
As a small inconvenience it would be necessary to throw some Exception,
if the current Thread already had any of these objects locks. (Strictly
it could even allow certain held locks (namely if it's the first few
according to the internal arrangement, but that would make it rather
unpredictable for the programmer who doesn't know the internal ordering,
but may vaguely know about this Thread's already held locks. The trivial
cases could even be caught by the compiler.)
Eh, it's threading, unpredictable is par for the course.
I do not propose this feature - just brainstorm what could be possible.
// assume non-identity, non-nullity and listness are known by this point
public boolean equals(List<?> that) {
List<?> first;
List<?> second;
if (order(this, that)) {
first = this;
second = that;
}
else {
first = that;
second = this;
}
synchronized (first) {
synchronized (second) {
return list.equals(that);
}
}
}
That's about what multisync would do just without exposing the order and
with any (>=2) number of objects. And you must be sure that the calling
thread doesn't yet have any of the locks, or you still may run into
deadlocks (namely if you happens to have the second one).
Yes, i hadn't thought of that when i wrote my code, but it's quite true.
However, given the limitations of the existing identity hashes, i don't
think it's possible.
If the VM used a GC which, although it moved objects around, never changed
their order (which is not entirely unreasonable - generational GC looks a
lot like that anyway), then it could implement multi-locking using the
order of objects in memory. In fact, it wouldn't have to keep them in
order as long as it could reconstruct the allocation order; if it kept
objects allocation-ordered within particular regions, and knew which order
those regions were allocated in, that would also do it. That would fit
with a generational collector with a pair of semi-spaces for young
objects, which is what i believe the current standard collector is. I
don't know if it preserves object order, though - from what i know of
classical moving collectors, they don't, since they move objects in the
order of a breadth-first traversal of the object graph.
tom
--
There is no violence or enmity in the LEGO universe until you, the
builder, decide what to build with the pieces. -- Pyrogenic