[concurrency-interest] A little lock free algorithm [the code]

David Holmes dcholmes at optusnet.com.au
Thu Mar 30 21:45:48 EST 2006


The use of backoff only occurs after a successful setting of the
AtomicBoolean. The memory semantics for Atomics are like volatiles. This is
what I meant by "piggybacking".

If thread A sets locked to true, updates backoff and sets locked to false
then:

  locked=true happens-before backoff=x
  backoff=x happens-before locked=false

If thread B successfully sets locked to true then:

  ThreadA:locked=false happens-before ThreadB:locked=true

and by transitivity the setting of backoff in Thread A happens-before its
use in Thread B.

Hence no need for backoff to be volatile *iff* only read/written while
locked==true.

Consider if you had use a synchronized block instead (or an explicit lock),
you would not make backoff volatile if it is only accessed while the lock is
held.

Cheers,
David Holmes
> -----Original Message-----
> From: studdugie [mailto:studdugie at gmail.com]
> Sent: Friday, 31 March 2006 12:31 PM
> To: dholmes at ieee.org
> Cc: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] A little lock free algorithm [the
> code]
>
>
> But what about it (backoff) getting cached?
>
> On 3/30/06, David Holmes <dcholmes at optusnet.com.au> wrote:
> > Okay this is basically a tryLock style of approach: if you can't get the
> > lock you know someone else is doing the increment. You've built your own
> > tryLock out of an AtomicBoolean.
> >
> > If backoff is only read and written when you've set the atomic
> boolean then
> > you can drop the volatile for it as it "piggybacks" on the AtomicBoolean
> > memory semantics.
> >
> > Cheers,
> > David Holmes
> >
> > > -----Original Message-----
> > > From: concurrency-interest-bounces at cs.oswego.edu
> > > [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of
> > > studdugie
> > > Sent: Friday, 31 March 2006 12:13 PM
> > > To: concurrency-interest at cs.oswego.edu
> > > Subject: [concurrency-interest] A little lock free algorithm
> [the code]
> > >
> > >
> > > public class TFailure
> > > {
> > >     volatile boolean dead;
> > >     volatile long expiration =
> > >         System.currentTimeMillis() + BACKOFF_INCREMENT;
> > >     private static final long BACKOFF_MAX = ...;
> > >     private static final long BACKOFF_INCREMENT = ...;
> > >     private volatile long backoff = BACKOFF_INCREMENT;
> > >     private final AtomicBoolean locked = new AtomicBoolean();
> > >
> > >     /**
> > >      * Increases the expiration timeout for the host if and only if
> > >      * it's not already dead and the current expiration time has
> > >       * elapsed.
> > >      */
> > >     void increment()
> > >     {
> > >         long millis;
> > >         if( dead || (millis = System.currentTimeMillis()) <
> expiration )
> > >             return;
> > >
> > >         if( locked.compareAndSet( false, true ) )
> > >         {
> > >             backoff += BACKOFF_INCREMENT;
> > >             if( backoff > BACKOFF_MAX )
> > >                 dead = true;
> > >             else
> > >                 expiration = millis + backoff;
> > >             locked.set( false );
> > >         }
> > >     }
> > > }
> > >
> > > _______________________________________________
> > > 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