[concurrency-interest] thoughts on ordered, concurrent locking

Marcelo Fukushima takeshi10 at gmail.com
Sat Mar 7 13:23:32 EST 2009


hi,
lemme try to help you
comments inlined

On Sat, Mar 7, 2009 at 2:55 PM, Taylor Gautier
<tgautier at terracottatech.com> wrote:
> Suppose I have a Person object, which has a list of friends, like so:
> Person:
>   String name;
>   List<Person> friends = new ArrayList<Person>();
> My question is, let's assume that a business rule requires that
> relationships are commutative, i.e if Bob is friend of Alice, then Alice is
> also a friend of Bob.
> This means that if we want to establish that relationship, we need to update
> both records atomically.   So let's try that (naively):
> public static void makeFriends(Person p1, person p2)
> {
>     synchronized (p1) {
>         p1.friends.add(p2);
>     }
>     synchronized (p2) {
>         p2.friends.add(p1);
>     }
> }
> Uh oh.  This looks like a disaster waiting to happen - the operation is not
> atomic.  Let's fix that:
> public static void makeFriends(Person p1, person p2)
> {
>     synchronized (p1) {
>         synchronized (p2) {
>             p1.friends.add(p2);
>             p2.friends.add(p1);
>         }
>     }
> }
> Ok better, but there is still a possibility of deadlocking this, consider
> two threads:
> Thread 1: makeFriends(bob, alice);
> Thread 2: makeFriends(alice, bob);
> We have two choices now,
> 1) We can find a higher order lock
> 2) Order the locks
> Approach #1 - Find a higher order lock
> If we try to do 1, then later, we cannot do fine-grained locking on Person
> to read what friends they have without acquiring the higher order lock.  We
> also start getting into trouble, what if we decide we want to update the
> person's name, now what lock do we use, and so on.  While it seems like a
> good goal -- in practice it may not be achievable given the application.
> Approach #2 - Order the locks
> I like this approach better.  It lets me do whatever other fine-grained
> locking on the Person object I would like to do, so it is compatible with a
> fine-grained approach.  But now we get to the crux of the problem - how do
> we order the locks?
> I am imagining a helper class here:
> public static void makeFriends(final Person p1, final Person p2)
> {
>     orderedSynchronizeOn(new Runnable() {
>         public void run() {
>             p1.friends.add(p2);
>             p2.friends.add(p1);
>         }
>     }, p1, p2);
> }
> Does anyone know of an implementation of orderedSynchronizeOn?  I can
> imagine writing something (pseudo-code) like:
> public void orderedSynchronizeOn(Runnable cmd, Object... objects)
> {
>     List sortedList = sort objects;
>     for (Object o: sortedList) {
>         lock (o);
>     }
>     cmd.run();
>     for (Object o: sortedList) {
>         unlock (o);
>     }
> }

you probably want to use a recursive function to synchronize on all
objects if you can / want to use simple synchronized blocks, which
might look something like this (assuming objects are already sorted)

private void runLocked(Runnable run, int index, Object[] locks) {
  if(index == locks.length) { run.run(); }
  else {
    synchronized(locks[index]) {
      runLocked(run, index+1, locks);
    }
  }
}

its kind of like what ConcurrentHashMap does (take a look at the
source code for that and more)

> Of course my pseudo-code is insufficient and has several problems that will
> arise which are:
> 1) how to sort the objects.  Presumably hashcode would be good - but could
> be unpredictable if the hashcode is not stable

you might consider using System.identityHashcode( object ) for sorting
maybe breaking ties with the class hashcode, but im not sure how safe
is that (and most likely not 100% safe)

> 2) I cannot think of any way to programmatically acquire the monitor for an
> object that corresponds to synchronized (o);

like i said before, try a recursive version of the method

> 3) Of course exceptions have to be handled, and the proper unlocks have to
> be executed in a finally block, which is rather tricky in the generic case

if you use plain synchronized blocks, exception are taken care of automatically

i hope that helps

> So, I can't see how to solve 2 and 3 using programmatic constructs
> (iterative approach to locking all passed in objects).  I can see how to
> implement say:
> orderedSynchronizeOn1,
> orderedSynchronizeOn2,
> orderedSynchronizeOn3,
> orderedSynchronizeOn4,
> orderedSynchronizeOn5,
> and so on by unrolling the loop and writing the appropriate try/finally with
> synchronized.
> And then implementing:
> public void orderedSynchronizeOn(Runnable cmd, Object... objects)
> {
>    switch (objects.length) {
>         case 1:  orderedSynchronized1(cmd, objects[0]); break;
>         case 2:  orderedSynchronized1(cmd, objects[0], objects 1); break;
>         ...
>   }
> }
>
>  That seems pretty ugly, but solves the problem assuming we can presume
> stable hash codes.
> Any other thoughts?
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>



-- 
[]'s
Marcelo Takeshi Fukushima



More information about the Concurrency-interest mailing list