Implementing a Lock-Free Counter with C11 Atomics

The Race Condition Revisited

You're already familiar with race conditions. When multiple threads try to update a shared variable, operations that seem simple in C, like counter++, are not "atomic" at the machine level. They typically involve three separate steps:

1. Read the current value of counter from memory into a register.
2. Increment the value in the register.
3. Write the new value from the register back to memory.

If Thread A reads the value, and then, before it can write its new value back, Thread B reads the same original value, one of the increments will be lost. This is precisely the problem that mutexes solve by ensuring only one thread can be inside this three-step "critical section" at a time.

The C11 Atomic Solution

Instead of using a mutex, which involves asking the operating system to manage a lock, we can instruct the compiler to use special hardware-level atomic instructions. This is the core idea behind C11's atomic types.

The following video provides a clear demonstration of this concept. It starts with a classic race condition and then fixes it with a single C11 keyword.

As you saw, simply changing the declaration from uint64_t counter; to _Atomic uint64_t counter; was enough to make the program correct.

This works because _Atomic is a type qualifier. When you apply it to a variable, you are telling the compiler that all operations on this variable must be atomic. For simple arithmetic operators like ++, --, +=, -=, etc., the compiler will automatically replace the standard, non-atomic code with a single, atomic hardware instruction.

The Stack Overflow answer by C expert Jens Gustedt provides a very terse summary of this:

Why Atomics are Fast

The reason atomics can be much faster than mutexes is that they avoid the overhead associated with locks.

• Mutexes often require a system call to the OS kernel to acquire or release a lock, which can involve context-switching a thread if the lock is contended. This is a relatively "heavyweight" operation.
• Atomics typically compile down to single machine instructions (like LOCK INC or XADD on x86) that the CPU guarantees will execute indivisibly. This is a "lightweight" hardware-level feature.

The video you watched earlier continues to explain and demonstrate this performance difference.

Implementing a Lock-Free Counter: Two Approaches

You can use C11 atomics in two main ways: using the _Atomic keyword, or using the types and functions from the <stdatomic.h> header.

Approach 1: The _Atomic Keyword

This is the method we've seen so far. It's simple and often sufficient for basic operations.

Here is a complete example. You can compile this with gcc -std=c11 -pthread your_file.c -o your_program.

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h> // Not strictly required for _Atomic, but good practice

// Using the _Atomic keyword to declare an atomic integer.
_Atomic long long counter = 0;

void* worker(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        // The ++ operator on an _Atomic variable is an atomic operation.
        counter++;
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;

    pthread_create(&t1, NULL, worker, NULL);
    pthread_create(&t2, NULL, worker, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Final counter value: %lld\n", counter); // Will correctly print 2000000

    return 0;
}

Approach 2: Using Functions from <stdatomic.h>

The C11 standard also provides a library of functions for working with atomic types. This approach can be more explicit and is necessary for more complex atomic operations that we'll see later.

The most common function for a counter is atomic_fetch_add().

Using this function, our worker code would look like this. Note that we also use atomic_llong from <stdatomic.h> as an alternative way to declare the atomic variable.

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

// Using the atomic type 'atomic_llong' from the header file.
atomic_llong counter = 0;

void* worker(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        // Atomically adds 1 to counter and returns the old value (which we ignore here).
        atomic_fetch_add(&counter, 1);
    }
    return NULL;
}

// ... main function is identical ...

For a simple increment, counter++ and atomic_fetch_add(&counter, 1) achieve the same goal. The function-based approach offers more control and is part of a wider family of atomic functions (e.g., atomic_exchange, atomic_compare_exchange_strong) that enable more complex lock-free algorithms.

Critical Caveats: The Limits of Atomicity

While powerful, atomics are not a magic bullet. Using them correctly requires understanding their limitations. Misunderstanding these can lead to subtle and dangerous bugs.

The video from Jacob Sorber concludes with an excellent discussion of these important caveats.

The key takeaway is that atomicity is guaranteed for single operations (a read, a write) and for specific read-modify-write operators (++, --, +=, &=, etc.). It is not guaranteed for arbitrary expressions that may involve multiple atomic variables or multiple steps.

Conclusion

In this lesson, you've taken your first step into lock-free programming. You've seen that for simple, shared data like counters, C11 atomics provide a high-performance alternative to mutexes by leveraging special hardware instructions.

Key Takeaways:

• C11 provides lock-free synchronization via the _Atomic keyword and the functions in <stdatomic.h>.
• Declaring a variable as _Atomic ensures that simple operations like ++ and += are performed atomically, preventing race conditions.
• Atomic operations are generally faster than mutexes because they avoid the overhead of kernel-level locking and context switches.
• Crucially, atomicity is not automatic for complex expressions. An operation like x = x + 1 on an atomic x is not atomic and can still lead to race conditions.
• You can implement a lock-free counter using either _Atomic int c; c++; or atomic_int c; atomic_fetch_add(&c, 1);.

Preview of the Next Lesson:
Our use of atomics has implicitly relied on the processor to do the "right thing." But what happens when the compiler or CPU reorders instructions to optimize performance? This can break more complex concurrent algorithms in very non-obvious ways. In our next lesson, we will explore this phenomenon by learning to describe how compiler and processor instruction reordering can cause concurrency bugs, which will lead us to the topic of memory barriers (fences).