[concurrency-interest] propper way to use CAS ?

Brian Goetz brian at quiotix.com
Mon Oct 10 11:22:45 EDT 2005


> Doesnt this presuppose that you are running on a system the is pre-emptive,
> So if you are running on a non pre-emptive system then the unsuccessful CAS
> retries will just continue wont they?

Until they eventually succeed.  But the point is, under real-world 
conditions, they _will_ eventually succeed.

An uncontended CAS is always successful.  In every contended CAS, one 
thread always succeeds.  Some thread always makes progress.

In order for a thread to continue retrying a CAS forever, it means that 
other threads must be pounding really hard on that same atomic variable, 
and always winning.  But each thread has an unbiased chance of winning 
any given CAS.  On a system with N processors, that chance should be 
close to 1/N.  So the expected number of retrys _in the absolute 
unrealistic worst case, where every processing is doing nothing but 
pounding on one atomic variable_, is N.  A far cry from "retrying 
forever".

But in reality, you will never see contention like that, because 
programs do other work besides pounding on a given memory location with 
CAS.

It's not like locking, where one thread can do this:

   synchronized (globalLock) {
     Thread.sleep(Long.MAX_VALUE);
   }

and deny access to the lock to other threads.  In a CAS, someone always 
makes progress, and in reality, every thread makes progress within a few 
retries.



More information about the Concurrency-interest mailing list