Why is CAS(Compare and Swap) atomic?

Question

I know CAS is a well-known atomic operation. But I struggle to see why it must be atomic. Take the sample code below as an example. After if (*accum == *dest), if another thread jumps in and succeed to modify the *dest first, then switch back to the previous thread and it proceeds to *dest = newval;. Wouldn't that lead to a failure?

Is there something I am missing? Is there some mechanism that would prevent the above scenario from happening?

Any discussions would be greatly appreciated!

bool compare_and_swap(int *accum, int *dest, int newval)
{
  if (*accum == *dest) {
      *dest = newval;
      return true;
  } else {
      *accum = *dest;
      return false;
  }
}

Answer 1

Often people use example code that is not atomic to describe what a CPU does atomically with a single instruction; because it's easier to see how it would work (and because a single cmpxchg instruction doesn't tell you much about how it works).

The code you've shown is like that (not atomic, to help understand how it works).

Answer 2

I had this question,too.This kind of things couldn't happen. The function that you wrote is an abstract operation of CPU, and the impletement is atomatic in real. U can google the key words of "cmpxchg" and will get the answer you find.

Answer 3

As a computer science concept compare and swap HAS to be implemented atomically because of what it is designed to do as a consensus object https://stackoverflow.com/a/56383038/526864

if another thread jumps in and succeed to modify the *dest first

I think that this premise is flawed because dest can not be allowed to change. The pseudocode should look more like

bool compare_and_swap(int *p, int oldval, int newval)
{
  if (*p == oldval) {
      *p = newval;
      return true;
  } else {
      return false;
  }
}

The example that you provided was for a specific implementation that returns the winning processes pid to the losers and only allows the single modification to *dest

an election protocol can be implemented such that every process checks the result of compare_and_swap against its own PID (= newval)

So compare-and-swap is either implemented with an atomic function/library or uses cmpxchg as you surmised

Do you think that these methods are special methods that directly utilize the hardware to perform atomic operations

Answer 4

Yes, this code can lead to pitfalls that you mentioned as it looks from the outside. However, if we look at how it is compiled, it will lead to a cmpxchg command, which will be executed atomically by the compiler.