What is Compare And Swap good for?

Question

I was recently reading about the Compare And Swap atomic action (CMPXCHG, .NET's Interlocked.CompareExchange, whatever).

I understand how it works internally, and how it's used from a client.

What I can't quite figure out is when would someone use CAS?

Wikipedia says:

CAS is used for implementing synchronization primitives like semaphores and mutexes, likewise more sophisticated lock-free and wait-free algorithms.

So, can anyone give me a more generic real-world use case with code and description of CAS usage?

This question is meant to be language-agnostic, so any language will do (C-based or x86 assembly preferred).

Thanks!

Answer 1

This is easy to see by example. Say we want to atomically and concurrently set a bit on a shared variable:

int shared = 0;

void Set(int index) {
 while (true) {
  if (Interlocked.CompareExchange<int>(ref shared, shared | (1 << index), shared) == shared)
   break; //success
 }
}

We detect failure if we see that the "old value" (which is the return value) has changed in the meantime.

If this did not happen we did not have a concurrent modification so our own modification went through successfully.

You can realize pretty complex stuff using this technique. The more complex the more performance loss through spinning, though.

I want to emphasize that a key property of CAS is that it can fail and that failure can be detected reliably.