Atomic operations

Oliver the squirrel had a simple system for winter preparation: collect acorns, check them for quality, then store them in his hollow.

One autumn day, Oliver gathered a pile of acorns at the base of an oak tree. Halfway through inspecting them, he had to rush off to help his cousin escape from a cat.

When he returned an hour later, his pile was ruined. Other animals had taken the best acorns, birds had damaged several more, and rain had caused the rest to begin sprouting. This happened over and over again.

As winter approached and his hollow remained empty, Oliver learned the hard way that his gathering process couldn’t handle interruptions. The entire sequence—from collection to storage—needed to happen as one complete operation, or external factors would inevitably compromise the result.

The need for atomic operations #

Oliver’s problem is actually similar to what we encounter in the software world. We do a lot of concurrent computing where many actors will operate on shared data, oftentimes critical data.

It’s important to do those operations in a way that maintains data consistency, keeps systems predictable to follow, and ensures efficient performance.

The fundamental unit of achieving that is executing a series of instructions as a single, indivisible unit–an atomic operation.

What are the major atomic operations? #

There are a slew of these but let’s focus on a few of the most popular:

• test-and-set
• compare-and-swap
• fetch-and-add

It’s worth noting that due to how useful and critical these operations are, they’re often explicitly supported by the CPU instruction set!

That said, to better illustrate how these work, we’ll walk through how they look in software land.

Test-and-set #

Test-and-set is a relatively simple operation that aims to write a value to a memory location. It will record the current value, write the new value, and then return the original value.

Here’s a frequent variant where the value to “set” is 1 (this could also be a boolean value of True).

Note that as written, this is not atomic, just illustrative.

int testAndSet(int* pointer) {
    int originalValue = *pointer;
    *pointer = 1;
    
    return originalValue;
}

The test-and-set operation is often used to implement a spinlock–a synchronization mechanism that checks until a condition becomes true.

// Wait for lock to become available
while (testAndSet(&lock)) {
    // Do critical work
    // ...
    // At the end, unset the lock.
    *lock = 0;
}

As mentioned earlier, test-and-set has the distinct advantage that it’s near universally implemented at the hardware-level. So it can be a helpful tool for concurrent systems.

Compare-and-swap #

This operation is also for writing a value to a location in memory. It compares a reference value with the current value in memory, and only if those two match, it will write the new value.

bool compareAndSwap(int *pointer, int referenceValue, int newValue) {
    if (*pointer != referenceValue) {
        return false;
    }
    
    *pointer = newValue;
    return true;
}

Here’s one example of building a simple incrementor:

int increment(int* pointer, int amount) {
    bool done = false;
    while (!done) {
        int originalValue = *pointer;
        done = compareAndSwap(pointer, originalValue, originalValue + amount);
    }

    return originalValue + amount;
}

Compare-and-swap is especially useful for synchronizing processes without the need for locks. It can also be used to implement concurrency primitives itself, like mutexes and semaphores.

Fetch-and-add #

This operation basically increments a value in a location in memory by a given amount, and returns the original value.

int fetchAndAdd(int *pointer, int incrementAmount) {
    int oldValue = *pointer;
    *pointer = oldValue + incrementAmount;
    
    return oldValue;
}

Also, like the other atomic instructions, fetch-and-add is also helpful for building synchronization primitives (e.g. mutexes etc.).

It is best suited for incrementing without requiring a comparison.

Here’s an example of how we can use it to build a ticket lock (basically a “wait for a numbered turn” lock).

Keep in mind #

Note that the examples above are just illustrative – these operations can be implemented in different ways. Because they’re often done at the hardware level and they’re often building blocks for higher-level concurrency mechanisms, it’s rare to directly see them when writing software.

Also, they are not the only atomic operations, just some well-known ones.

Even if we don’t see them in daily use, they’ve helped us bring more complex, parallel systems into the world!