What Every Systems Programmer Should Know About Concurrency

Concurrency is a fundamental aspect of modern computing, enabling efficient utilization of resources and improving performance. However, it introduces complexities that can lead to subtle and hard-to-debug issues. This article provides an overview of the key concepts and tools that systems programmers need to understand to effectively manage concurrency.

Background

In today’s computing environment, threads run concurrently, whether on a single-core or multi-core processor. These threads interact by sharing state, and ensuring the correct ordering of memory operations is crucial for correctness. Consider a simple example where one thread writes a value and sets a flag, while another thread waits for the flag before reading the value. Ensuring that the flag is set after the value is written requires careful handling of memory operations.

int v; bool v_ready = false;

void threadA() 
    v = 42;
    v_ready = true;


void threadB() 
    while (!v_ready)  /* wait */ 
    const int my_v = v;
    // Do something with my_v...

Enforcing Law and Order

To prevent data races and ensure correctness, programming languages like C and C++ provide atomic types and operations. These tools help manage the ordering of memory operations across threads.

std::atomic_int v(0);
std::atomic_bool v_ready(false);

void threadA() 
    v = 42;
    v_ready = true;


void threadB() 
    while (!v_ready.load())  /* wait */ 
    const int my_v = v.load();
    // Do something with my_v...

Atomicity

Atomic operations ensure that reads and writes to shared variables are indivisible. This prevents torn reads and writes, which can occur when a variable is larger than the machine’s word size.

std::atomic<int64_t> counter;

void increment() 
    counter.fetch_add(1, std::memory_order_relaxed);

Read-Modify-Write Operations

Read-modify-write (RMW) operations are essential for implementing synchronization primitives. Common RMW operations include exchange, compare-and-swap (CAS), and fetch-and-add.

std::atomic<int> value;

int old_value = value.exchange(42);
if (value.compare_exchange_weak(expected, desired)) 
    // CAS succeeded

Memory Orderings

Memory orderings define the constraints on how operations can be reordered by the compiler and hardware. Sequentially consistent operations provide the strongest ordering guarantees, ensuring a single total order of all operations.

std::atomic<int> x(0), y(0);

void thread1() 
    x.store(1, std::memory_order_seq_cst);
    int val = y.load(std::memory_order_seq_cst);


void thread2() 
    y.store(1, std::memory_order_seq_cst);
    int val = x.load(std::memory_order_seq_cst);

Acquire and Release

Acquire and release orderings provide one-way memory barriers, ensuring that operations within a critical section are not reordered across the barrier.

std::atomic<bool> flag(false);
int data;

void producer() 
    data = 42;
    flag.store(true, std::memory_order_release);


void consumer() 
    while (!flag.load(std::memory_order_acquire))  /* spin */ 
    // data is now visible

Relaxed Operations

Relaxed operations offer the weakest ordering guarantees and are useful when no specific ordering is required.

std::atomic<int> counter(0);

void increment() 
    counter.fetch_add(1, std::memory_order_relaxed);

False Sharing and Cache Effects

Cache coherence protocols can introduce performance bottlenecks due to false sharing, where unrelated variables share the same cache line.

struct RMLock 
    int readers;
    bool writer_flag;
    char padding[CACHE_LINE_SIZE - sizeof(int) - sizeof(bool)];
;

Volatile and Atomic Fusion

The volatile keyword is not a suitable tool for concurrency. It does not provide the necessary ordering and atomicity guarantees.

volatile int shared_var; // Incorrect for concurrency

Conclusion

Concurrency is a complex topic, but understanding the fundamental concepts of atomicity, ordering, and synchronization can help systems programmers write correct and efficient concurrent code. By using the right tools and techniques, programmers can avoid common pitfalls and build robust concurrent systems.

Additional Resources

Sign In