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

David Holmes dcholmes at optusnet.com.au
Fri Mar 31 04:23:00 EST 2006


> 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