Can CompareExchange be implemented with CompareAndSwap?

Question

Assuming that CompareAndSwap (or CAS) never fails spuriously, can CompareExchange be implemented with CAS?

CompareExchange both take a pointer, an expected value, and a new value and atomically set the memory referenced by the pointer to the new value if it matches the expected value. The difference between the two is that CompareExchange returns the previous value of the memory area and CompareAndSwap returns a bool indicating success or failure.

It's trivial to implement CAS with CompareExchange:

int CompareExchange (int* p, int expected, int newvalue);

bool CAS (int* p, int expected, int newvalue)
{
   return CompareExchange (p, expected, newvalue) != expected;
}

... but is it possible to implement CompareExchange with CAS? All the attempts I've seen either have race conditions or don't guarantee lockless properties. I don't believe it's possible.

Answer 1

I don't see how it's possible. For the case where CAS fails, you'll need a separate operation to get the previous value. This separate operation will not be atomic relative to the CAS.

You can get part way there:

int CompareExchnage(int *p, int expected, int newvalue)
{
    if (CAS(p, expected, newvalue))
        return expected;
    else
        ???;
}

It's the case where CAS fails where you have the problems. Getting *p to find what the previous value is will not be atomic relative to CAS so you either have a race condition or you would have to lock around the CAS and the *p dereference.