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

Joe Bowbeer joe.bowbeer at gmail.com
Tue Apr 24 19:28:36 EDT 2007


For completeness, here's the original example with the improved
try-finally nesting:

/*
 * Adapted from com.oreilly.tiger.ch10.LinkedList
 * http://examples.oreilly.com/javaadn/
 */

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

public class LinkedList<E> {

    /** The value of this node. */
    private E value;

    /** The rest of the list. */
    private LinkedList<E> rest;

    /** A lock for this node. */
    private final Lock lock = new ReentrantLock();

    public LinkedList(E value) {
        this.value = value;
    }

    public void append(E value) {
        // Start the pointer at this node
        LinkedList<E> node = this;
        // Lock this node
        node.lock.lock();
        try {
            // Traverse the links, using hand-over-hand locking
            while (node.rest != null) {
                // Lock the next node
                node.rest.lock.lock();
                // Advance our pointer
                LinkedList<E> prev = node;
                node = node.rest;
                // Unlock the previous node
                prev.lock.unlock();
            }
            // We're at the final node, so append
            node.rest = new LinkedList<E>(value);
            // node.linkChanged.signalAll();
        } finally {
            // Release final lock
            node.lock.unlock();
        }
    }

    // ...


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