CompareAndSet Operations overriding of values

Question

While going through the Blocking/Non Blocking Algorithms section at the link

and the below code to explain the Atomic compareAndSet operation

boolean updated = false;
while(!updated){
long prevCount = this.count.get();
updated = this.count.compareAndSet(prevCount, prevCount + 1);
}

It states that

Therefore no synchronization is necessary, and no thread suspension is necessary. This saves the thread suspension overhead.

Does it mean that if there are 2 threads that call compareAndSet() at the same time in the above code, both of them will execute concurrently or parallelly which is in contrast to the synchronized block where one thread gets blocked if both access simultaneously? If that's the case wouldn't the values get overwritten in the above case? Which is same case when there is no synchronization?

Unrelated but in that link it states "Java volatile variables are variables that are always read directly from main memory. When a new value is assigned to a volatile variable the value is always written immediately to main memory. " which is not accurate, just to let you know — dreamcrash, Jan 01 '21 at 15:51
Btw does this help you https://stackoverflow.com/questions/32634280/how-does-compare-and-set-in-atomicinteger-works ? — dreamcrash, Jan 01 '21 at 15:53
What do you mean by "overriden"? In a sense that this is not thread-safe? Or in a sense that thread A first does an update and then thread B does an update, .. which is .. the point of a counter? — akuzminykh, Jan 01 '21 at 16:26
@akuzminykh, basically my question is if 2 threads try to execute the compareAndSet() at the same time, will both of them execute parallely or will either of them get suspended? If they get blocked than what's the advantage does it offer against the existing synchronised block or method mechanism? — ghostrider, Jan 01 '21 at 16:36
They will both run in parallel one, will have the most updated value while the other will try again — dreamcrash, Jan 01 '21 at 16:37
If they both run parallelly, than both will execute the compareAndSet with the same expected value right? So how will one get failed and other succeed if both of them have the same expected value? — ghostrider, Jan 01 '21 at 16:42
@dreamcrash, Thanks for the link. That explains my doubt. But it says "Now because of atomics - only one thread will succeed, the other will recieve false from the compareAndSet and go around again". "Atomics" means that the other thread cannot come in between one thread is executing. Does this not mean the thread is blocked? — ghostrider, Jan 01 '21 at 16:53
The operation will be done atomically by the hardware, and only one of the threads will perform first the operation otherwise you would have a race condition. Atomic implies synchronization but in a much much more finer grain at the instruction level and with the help of the hardware — dreamcrash, Jan 01 '21 at 16:56
Thanks. You are saying "only one of the threads will perform first the operation otherwise you would have a race conditions" Doesn't this mean one thread is blocked/suspended? — ghostrider, Jan 01 '21 at 16:59
Ok thanks. Which resource do you suggest to get a firm grasp on this subject? — ghostrider, Jan 01 '21 at 17:07
@ghostrider For instance the book https://www.goodreads.com/book/show/127932.Java_Concurrency_in_Practice — dreamcrash, Jan 01 '21 at 17:08
@ghostrider As you've asked again and again and .. if a thread is blocked: no. You need to understand that CAS is an *atomic* machine instruction, like assigning a reference. Two instructions, one by A and one by B, can run either A then B or B then A. There is no A_1 then B then A_2, if you know what I mean. With CAS if A then B, B returns `false` as A came first. But this is why you put these calls in a loop: Both will execute non-blocking. — akuzminykh, Jan 01 '21 at 17:49
The _definition_ of compareAndSet is that only one thread can *succeed* (get returned true) at a time, but other threads aren't blocked, they just get returned false. — Louis Wasserman, Jan 01 '21 at 22:41

pveentjer · Accepted Answer · 2021-01-02T05:07:28.800

The value of the AtomicLong is on a cacheline. On the X86 there is a feature called cacheline locking which is used for locked instructions. So when a cas is done, the cacheline is first acquired in modified/exclusive state and then locked.

If a different CPU wants to access the same cacheline, its cache coherence requests including the request-for-ownership will be ignored till the cacheline is unlocked.

So it is a very lightweight form of synchronization. If you are lucky, the other CPU has some out of order instructions it can execute while it waits for the cacheline.

This approach is called non blocking even though it could lead to other threads 'blocking' since they need to wait. The primary difference with a blocking algorithm is that it can't happen that the CPU (thread) owning the locked cacheline gets suspended while it has locked that cacheline. This is taken care of at the hardware level (so the CPU can't be interrupted between cacheline lock acquire and release). So the blocking is guaranteed to be very short instead of unbounded like with a blocking algorithm.

According to @BeeOnRope there might be some optimistic behavior as well involved but this goes beyond my knowledge level.

CompareAndSet Operations overriding of values

1 Answers1