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

Joe Bowbeer joe.bowbeer at gmail.com
Tue Apr 24 17:21:09 EDT 2007


The Mutex example converted to java.util.concurrent follows.

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class List {

    /** Holds one item in singly-linked list. */
    private static class Node {
        /* Each node maintains its own lock. */
        final Lock lock = new ReentrantLock();
        Object item;
        Node next;
        Node(Object item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    /**
     * Points to first node of list.
     * We use synchronized(this) to protect head field.
     */
    private Node head;

    private synchronized Node getHead() {
        return head;
    }

    public synchronized void addFirst(Object x) {
        head = new Node(x, head);
     }

    public boolean contains(Object x) {
        Node p = getHead();
        if (p == null) // empty?
            return false;
        /* Acquire first lock. */
        p.lock.lock();
        try {
            while (true) {
                if (x == p.item || x != null && x.equals(p.item))
                    return true;
                if (p.next == null)
                    return false;
                /* Get next lock before releasing current. */
                p.next.lock.lock();
                /* Advance pointer and release lock on previous node. */
                Node prevp = p;
                p = p.next;
                prevp.lock.unlock();
            }
        } finally {
            /* Release final lock that was held. */
            p.lock.unlock();
        }
    }
}


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