Lock-Free Data Structures in C++ Compare and Swap Routine
- by slf
In this paper: Lock-Free Data Structures (pdf) the following "Compare and Swap" fundamental is shown:
template <class T>
bool CAS(T* addr, T exp, T val)
{
if (*addr == exp)
{
*addr = val;
return true;
}
return false;
}
And then says
The entire procedure is atomic
But how is that so? Is it not possible that some other actor could change the value of addr between the if and the assignment? In which case, assuming all code is using this CAS fundamental, it would be found the next time something "expected" it to be a certain way, and it wasn't. However, that doesn't change the fact that it could happen, in which case, is it still atomic? What about the other actor returning true, even when it's changes were overwritten by this actor? If that can't possibly happen, then why?
I want to believe the author, so what am I missing here? I am thinking it must be obvious. My apologies in advance if this seems trivial.
