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

David Holmes dcholmes at optusnet.com.au
Fri Apr 27 12:55:31 EDT 2007


Let me clarify that "all the exceptions" means:
- any exception from Lock.lock()  (OutOfMemoryError most likely one to
encounter)
- any exception from equals()
- OutOfMemoryError from "new Node"

Any other exception, such as NullPointerException would be considered an
inherent programming error and not something the code tries to cope with.
Naturally asynchronous exceptions aren't handled either.

Cheers,
David Holmes

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Joe
> Bowbeer
> Sent: Friday, 27 April 2007 3:51 PM
> To: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] Canonical example of how to
> dohand-over-hand locking?
>
>
> 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?
> >
>
> In case you're still interested, here's one more example.  (I really
> like this question:)
>
> The methods are in order of increasing complexity.  The 'remove'
> method is the most complex, needing nested try-finally's to handle all
> the possible exceptions.
>
> public class List {
>
>     /**
>      * Holds one item in a singly-linked list.
>      * It's convenient here to subclass ReentrantLock
>      * rather than add one as a field.
>      */
>     private static class Node extends ReentrantLock {
>         Object item;
>         Node next;
>         Node(Object item, Node next) {
>             this.item = item;
>             this.next = next;
>         }
>     }
>
>     /**
>      * Sentinel node. This node's next field points to
>      * the first node in the list. Its item field is ignored.
>      */
>     private final Node sentinel = new Node(null, null);
>
>     public void addFirst(Object x) {
>         Node p = sentinel;
>         p.lock();
>         try {
>             p.next = new Node(x, p.next);
>         } finally {
>             p.unlock();
>         }
>      }
>
>     public void addLast(Object x) {
>         Node p = sentinel;
>         /* Acquire first lock. */
>         p.lock();
>         try {
>             /* Find tail, using hand-over-hand locking. */
>             while (p.next != null) {
>                 Node prevp = p;
>                 p.next.lock();
>                 p = p.next;
>                 prevp.unlock();
>             }
>             /* Attach new node. */
>             p.next = new Node(x, null);
>         } finally {
>             /* Release final lock that was held. */
>             p.unlock();
>         }
>      }
>
>     public boolean contains(Object x) {
>         Node p = sentinel;
>         /* Acquire first lock. */
>         p.lock();
>         try {
>             while (p.next != null) {
>                 /*
>                  * Get next lock and release current.
>                  * Sentinel is skipped on first iteration.
>                  */
>                 Node prevp = p;
>                 p.next.lock();
>                 p = p.next;
>                 prevp.unlock();
>                 /* Found? */
>                 if (x == p.item || x != null && x.equals(p.item))
>                     return true;
>             }
>             return false;
>         } finally {
>             /* Release final lock that was held. */
>             p.unlock();
>         }
>     }
>
>     public boolean remove(Object x) {
>         Node p = sentinel;
>         /* Acquire first lock. */
>         p.lock();
>         try {
>             while (p.next != null) {
>                 /*
>                  * Get next lock and release current.
>                  * Sentinel is skipped on first iteration.
>                  */
>                 Node prevp = p;
>                 p.next.lock();
>                 p = p.next;
>                 try {
>                     /* Found? */
>                     if (x == p.item || x != null && x.equals(p.item)) {
>                         /* Remove node p. */
>                         prevp.next = p.next;
>                         return true;
>                     }
>                 } finally {
>                     prevp.unlock();
>                 }
>             }
>             return false;
>         } finally {
>             /* Release final lock that was held. */
>             p.unlock();
>         }
>     }
> }
>
> --
> Joe Bowbeer
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest



More information about the Concurrency-interest mailing list