[concurrency-interest] thoughts on ordered, concurrent locking

Taylor Gautier tgautier at terracottatech.com
Sat Mar 7 14:35:20 EST 2009


Thanks that should do!  I guess my aversion to recursion blinded me  
here ;)



On Mar 7, 2009, at 10:23 AM, Marcelo Fukushima <takeshi10 at gmail.com>  
wrote:

> 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