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

studdugie studdugie at gmail.com
Fri Mar 31 07:19:04 EST 2006

Crystal clear, thanx to you.  I love that psychological "click" that
happens when something you've been stuck on finally make sense.

Thanx a million.


On 3/31/06, David Holmes <dcholmes at optusnet.com.au> wrote:
> > 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)?
> To a certain extent yes. volatile reads and writes, together with use of
> Atomics, plus locks, all establish "happens-before" relationships. Within a
> single thread each action that comes before another action in program-order,
> happens-before that second action. If a write of a variable happens-before a
> subsequent read of that variable then the read is guaranteed to see the
> value that was written. When considering actions across threads then there
> are basically no guarantees about what values will be read by thread A after
> a write by thread B unless the read and write are ordered by a
> happens-before relationship.
> The happens-before relationship is transitive: if a happens-before b, and b
> happens-before c, then a happens-before c.
> So in your example every CAS that manages to set locked to true has to
> happen-before a preceding set of locked=false in another thread.
> Consequently any write to  backoff that happens-before locked=false, also
> happens-before the other thread sets locked=true. As the write of backoff
> and the read of backoff are ordered by a happens-before relationship, then
> the read is guaranteed to see the value that was previously written by the
> other thread.
> In the old memory model volatiles only had memory synchronization effects
> with respect to other volatiles - which meant for most intents and purposes
> if a volatile flag protected some data then the data also had to be
> volatile. The new memory model defines the happens-before relationship which
> is more general, and so non-volatile variables can acquire visibility
> guarantees by "piggybacking" on the memory synchronization effects of
> volatiles and Atomics. This is the same "piggybacking" that has always been
> true for use of synchronized - you didn't have to make the data protected by
> a monitor, volatile, as use of the monitor ensures the visibility of the
> data.
> Hope that clarifies things.
> Cheers,
> David Holmes

More information about the Concurrency-interest mailing list