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

Joe Bowbeer joe.bowbeer at gmail.com
Tue Apr 24 14:18:09 EDT 2007


Btw, the problem with unchecked exceptions that you point out is real,
and also exists in the Mutex sample.  You don't need to use a flag in
this case, though.  I'll post a robust sample soon.

On 4/24/07, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
> 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