Re: Locking objects in an array
Philipp wrote:
Hello,
I've come accross a threading problem for which I can't find a nice
solution. (SSCCP at end of post)
I have a bidimensional array of objects (view it as a 2D lattice). I
want to make atomic operations on random square 2x2 regions of the
lattice. Thus I want to lock the 4 objects of the region, then perform
the change, then unlock those objects. Several threads should be
allowed to work on the array at the same time, if each thread is
accessing a 2x2 region which does not overlap with that of another,
they should be capable of doing the work in a parallel way.
How should I design the code to achieve this?
My solution (which may be misguided) so far is that, each object of
the lattice contains a Lock and has a lock() and unlock() method which
delegate to the lock.
So the approach is basically:
1. call lock() on each of the 4 objects (always in the same order)
2. make change
3. call unlock() on each of the 4 objects
What I don't like about this, is that
a) lock and unlock really have nothing to do in the API of the objects
in the lattice. Would it be possible to achieve the same result
without using an explicit Lock (thus no lock() method), but using the
Java synchronized() mechanism?
There is a relevant inconsistency between the problem statement and the
sample code. The code appears to be designed to allow for a block size
other than 2x2 through a simple change in a constant.
If you can bind it to 2x2, you can do a 4-deep nested synchronization:
synchronized(lattice[x][y]){
synchronized(lattice[x][y+1]){
synchronized(lattice[x+1][y]){
synchronized(lattice([x+1][y+1]){
// do the work
}
}
}
}
Synchronization with varying block sizes would be more complicated.
b) if an exception is thrown anywhere, eg. where only a part of the
lattice region has been locked, the cleanup is ugly because you can't
test if a lock is presently locked. You have to rely on unlock() to
throw.
Or keep a variable that tracks which locks you have obtained.
c) An exception may leave the lattice in an inconsistent state.
This seems to be orthogonal to the synchronization issue. I assume the
counter increment task is just a placeholder for possibly more
complicated work.
If you need maintain consistency even in the presence of exceptions part
way though the work, you need to do one of two things:
1. Note the old state at the start of a transaction, and rollback to it
in a finally block unless a flag indicates the whole transaction was
successful.
2. Not make any changes to the actual lattice until after the last
possible non-fatal exception. You could, for example, calculate new
values into a 2x2 array, and only copy its values into the lattice on
success.
Either approach would work if you can make the lattice objects
immutable, so that the operation creates new pointers for the four
cells, rather than changing the state of the objects they reference.
However, the first approach could be done even with mutable objects if
they are made transaction aware with commit and rollback. At the start
of the synchronized block you would inform each of the four objects of
the transaction start. In a finally block you would tell each to commit
if a flag indicated success, or rollback to their state at the start of
the transaction if there were a failure.
Patricia