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

Joe Bowbeer joe.bowbeer at gmail.com
Tue Apr 24 17:46:29 EDT 2007


I just noticed that you were asking about an "addLast" implementation,
so here you go:

    public void addLast(Object x) {
        Node p;
        synchronized(this) {
            if ((p = head) == null) {
                head = new Node(x, null);
                return;
            }
        }
        /* Acquire first lock. */
        p.lock.lock();
        try {
            /* Find tail. */
            while (p.next != null) {
                /* 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();
            }
            /* Attach new node. */
            p.next = new Node(x, null);
        } finally {
            /* Release final lock that was held. */
            p.lock.unlock();
        }
     }

--Joe

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