1 Atomic Operations

Atomic operations are a key concept in lock-free data structures, a family of tools for high-efficiency synchronization in the case when multiple threads contending for a single resource is rare. Atomic operations resemble other assembly instructions, but they have an additional guarantee that all of their work will happen without a separate thread accessing the same resources. Any operation or set of operations that guarantees this kind of exclusive access to its resources during its operation is called atomic. Atomic operations are quite a bit less efficient than their non-atomic counterparts and should be used only when atomicity is required.

Common atomic operations include

• Test-and-set, a single-bit operation that (a) sets a bit in memory to 1 and (b) returns if that bit was changed by this operation (i.e. previously 0) or not.

  This is one of the simplest of the atomic operations to implement in hardware, and many other atomic operations and synchronization primitives are built off of it. I’ve never used it outside of a class that describes how to implement synchronization, but it’s referred to with enough frequency to be worth knowing about.

• Compare-and-set, a multi-bit version of test-and-set which only modifies a value if it had a specific previous value before the modification; in other words, something like

  if (p[0] == oldvalue) { p[0] = newvalue; return 1; }
  else { return 0; }

  Compare and set is widely used to implement lock-free data structures, such as linked lists that can be modified by multiple threads concurrently. The core idea of such approaches is something like

  1. copy the current data into local variables
  2. compute the new values and pointers needed
  3. compare-and-set the new values over the old ones
  4. if the compare-and-set failed, restart the operation

  There are many nuances to this idea, but the core of it (retry on failure) shows why atomic operations are best for situations where threads fighting over a single resource are rare.

• Atomic modification operations, like +=.

  Under the hood, x += 1 involves (a) loading x’s current value from memory, (b) computing the sum of that value and 1, and (c) writing the result back to memory. With a non-atomic version, there is the potential that some other thread will modify x’s memory after step (a), then have its work lost when (c) overwrites that memory. With an atomic version, that kind of race condition is prevented by preventing any other thread from accessing x’s memory between steps (a) and (c).

Atomic operations are available in C using #include <stdatomic.h>, but are not implemented on all platforms, so portable code using them needs fallback non-atomic code to use when they are not available. Because of this, we do not show more about how to program with atomic operations here.

2 Synchronization primitives

All synchronization primitives have the following properties:

• They pair some opaque data (i.e. you never look inside it) and some functions or methods that operate on that data.
• They define rules under which some threads will block when running a function/method, being suspended by the OS until some other function/method on the same data in another thread unblocks it.

There are many synchronization primitives; the following are those I see the most often in code I read and write.

In C, the most common threading library is called pthreads. All pthreads synchronization primitives should be kept at a fixed, never-changing memory address for their entire lifespan and passed to functions by pointer, not by value. Some, but not all, implementations use the address of the primitive as part of the logic it implements. The primitive must be initialized before use (with pthread_type_init) and destroyed after use (with pthread_type_destroy).

pthread_mutex_lock(m);

do things
using only one thread
at a time

pthread_mutex_unlock(m);

synchronized(m) {
    // do things
    // using only one thread
    // at a time
}
// m has been released here, even on exception or return

with m:
    ... # do things
    ... # using only one thread
    ... # at a time
# m has been released here, even on exception or return

pthread_mutex_lock(m);
while (!complicated_condition_is_met()) {
    pthread_cond_wait(cv, m);
}

do things using only one thread at a time
that change the complicated condition for some thread

pthread_cond_broadcast(cv);
pthread_mutex_unlock(m);

while (!complicated_condition_is_met()) {
    pthread_cond_wait(cv, m);
}

lock the mutex
repeat as long as the condition is not met:
    unlock the mutex
    wait for notification that something has changed
    lock the mutex

...

unlock the mutex

pthread_mutex_lock(food_station.mutex);
while (!food_station.has_food()) {
    pthread_cond_wait(food_station.condvar, food_station.mutex);
}
food_station.serve(me);
pthread_mutex_unlock(food_station.mutex);

pthread_mutex_lock(food_station.mutex);
food_station.refill();
pthread_cond_broadcast(food_station.condvar);
pthread_mutex_unlock(food_station.mutex);

pthread_rwlock_rdlock(exhibit);
view_exhibit();
pthread_rwlock_unlock(exhibit);

pthread_rwlock_wrlock(exhibit);
update_exhibit();
pthread_rwlock_unlock(exhibit);