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

Joe Bowbeer joe.bowbeer at gmail.com
Tue Apr 24 13:41:06 EDT 2007


I can't locate a good current example either.

There is sample code in the Mutex class of Doug Lea's original
concurrent package:

http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/Mutex.java

To migrate this to java.util.concurrent, translate:

class:
  Mutex => Lock

constructor:
  new Mutex() => new ReentrantLock()

methods:
  lock.acquire => lock.lockInterruptibly
  lock.release => lock.unlock

Note: I recommend using interruptible locks whenever possible, and
especially for operations that might take awhile, such as traversing a
long list.

--Joe

On 4/24/07, Aaron Greenhouse <aarong at cs.cmu.edu> wrote:
> 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