[concurrency-interest] thoughts on ordered, concurrent locking

Taylor Gautier tgautier at terracottatech.com
Sat Mar 7 12:55:00 EST 2009


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); 
} 
} 


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 
2) I cannot think of any way to programmatically acquire the monitor for an object that corresponds to synchronized (o); 
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 


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? 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090307/c6191219/attachment.html>


More information about the Concurrency-interest mailing list