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

studdugie studdugie at gmail.com
Thu Mar 30 22:21:16 EST 2006


Now it could be that I'm just slow in the head so bear with me because
I'm still stuck on the caching issue. Here is what I'm stuck on.

Lets continue with your example and restrict ourselves to the
assumption that there are only 2 threads that will ever set locked to
true, A and B.  So what happens on the third go round after A and B
have updated backoff and A is back at it again? My understanding of
the visibility rules say that if backoff is not volatile then A can
cache the value it computed in the first go round and reuse it as the
basis for computation in the third. In other words, A never has to
re-read backoff, thus it may never see B's update.

Now if I'm wrong about this it means that my understanding of the
visibility rules is flawed and the rules have changed. So let me ask
you this. Are you saying the mixing of volatile and non-volatile
fields causes the non-volatile fields to behave like volatiles (no
caching)?

Sincerely,

Dane

On 3/30/06, David Holmes <dcholmes at optusnet.com.au> wrote:
> 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