Previous | Next --- Slide 20 of 29
Back to Lecture Thumbnails

Load value from memory, increment it locally, use compare and swap on (address, old value, incremented value), compare to original value, and if they're the same then we're good.

If someone else accessed after we loaded the value before, then the values won't be the same so we won't swap (increment).

atomicIncrement(int* x) {
  while(true) {
    int n = *x;
    if(CAS(x, n, n+1) == n) break;

Atomic addition is so common that many architectures provide specialized instructions for it. For example, x86 provides xadd, which when combined with the lock prefix, performs addition atomically.

int atomicIncrement (int* addr) {
  int old = *addr;
  int assumed;
  do {
    assumed = old;
    old = atomicCAS(addr, assumed, assumed+1);
  } while (old != assumed)
  return old;