[concurrency-interest] Canonical example of how to do hand-over-hand locking?

Aaron Greenhouse aarong at cs.cmu.edu
Tue Apr 24 09:21:07 EDT 2007


The javadoc for the java.util.concurrent.locks package explicitly 
mentions that the locks can be used for hand-over-hand locking.  But it 
doesn't give an example.  How does this interact with the recommendation 
that unlocks occur in finally clauses so as to insure that all locks are 
always unlocked?

The only example I have been able to find (in my 10 minutes of 
searching) is this one that says it is from

   Java 1.5 'Tiger': A Developer's Notebook (O'Reilly)
   by Brett McLaughlin and David Flanagan.


I am not convinced, however, that it is correct (or at least it is 
potentially misleading).  Here is the example; the hand-over-hand 
locking is in the append() method:

/*
License for Java 1.5 'Tiger': A Developer's Notebook
      (O'Reilly) example package

Java 1.5 'Tiger': A Developer's Notebook (O'Reilly)
by Brett McLaughlin and David Flanagan.
ISBN: 0-596-00738-8

You can use the examples and the source code any way you want, but
please include a reference to where it comes from if you use it in
your own products or services. Also note that this software is
provided by the author "as is", with no expressed or implied warranties.
In no event shall the author be liable for any direct or indirect
damages arising in any way out of the use of this software.
*/
public class LinkList<E>

   // The value of this node
   E value;

   // The rest of the list
   LinkList<E> rest;

   // A lock for this node
   Lock lock;

   // ... methods elided ....

   public void append(E value) {
     // Start the pointer at this node
     LinkList<E> node = this;
     node.lock.lock();

     while (node.rest != null) {
       LinkList<E> next = node.rest;

       // Here's the hand-over-hand locking
       try {
         // Lock the next node
         next.lock.lock();
       } finally {
         // unlock the current node
         node.lock.unlock();
       }

       // Traverse
       node = next;
     }

     // We're at the final node, so append and then unlock
     try {
       node.rest = new LinkList<E>(value);

       // Let any waiting threads know that this node's link has changed
       node.linkChanged.signalAll();
     } finally {
       node.lock.unlock();
     }
   }
}

The book doesn't give a great deal of discussion to the example.  The 
problem I see is if code were inserted between the close of the 
while-loop and the start of the subsequent try-finally block.  In that 
case if there were an exception, the lock of the last node would not be 
released.  This potential future accident could be averted by moving the 
while-loop into the try-block.

But I was trying to figure out how, if at all, you would correctly write 
the following:

lock1.lock();
// If an exception occurs here, only release lock1
lock2.lock();
// If an exception occurs here, release lock2 and lock1
lock1.unlock();
// If an exception occurs here, release lock2
lock2.unlock();

I think it would have to something like this, where we need to use a flag:

boolean doUnlock1 = false;
lock1.lock();
try {
     // If an exception occurs after here, only release lock1
     doUnlock1 = true;

     // do stuff

     lock2.lock();
     try {
         // If an exception occurs after here, release lock2 and lock1

         // do stuff

         lock1.unlock();
         // If an exception occurs after here, release lock2
         doUnlock1 = false;

         // do stuff
     } finally {
         lock2.unlock();
     }
} finally {
     if (doUnlock1) lock1.unlock();
}

This suffers from the same problem as above, where the placement of the 
assignments to doUnlock1 are very important.


I don't have any example of what I am trying to, other than to figure 
out how to do it.  This is coming up in the context of writing test 
cases for an analysis.

--Aaron




More information about the Concurrency-interest mailing list