Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 43

Race Conditions and Synchronization

Recommended resources

Welcome to the eighth module of our course. Having spent the last few modules building the intricate single-threaded logic for HNSW graph construction and searching, we are now ready to tackle a new dimension: concurrency. In high-performance systems, harnessing the power of modern multi-core CPUs is not just an optimization—it's a necessity.

In our previous lesson, we finalized the HNSW insertion logic by implementing the robust connection pruning algorithm from the original paper. This completed the core single-threaded implementation of our vector database. Now, we will pivot to making it fast and responsive by allowing multiple operations to happen at the same time.

This lesson begins our journey into concurrent programming by addressing the most fundamental challenge: race conditions. We will explore why simply running tasks on different threads can lead to unpredictable and incorrect results. By the end of this lesson, you will be able to explain what race conditions are, why they occur at a deep hardware and compiler level, and understand the fundamental need for synchronization to write correct concurrent programs.

The Concurrent World: Shared State, Shared Problems

In our project so far, we have been working in a single-threaded environment. One sequence of instructions executes, modifying the state of our graph in a predictable, linear fashion. When we introduce multiple threads, this linearity is lost.

Threads within the same process share most of their resources, which is what makes them powerful for collaborative tasks but also introduces peril.

Race Conditions, Synchronization, Mutexes

These lecture notes from Brown University provide a concise overview of threads and their shared resources.

Please review the table comparing processes and threads under the "Threads" section. Pay close attention to what is shared (Code, Global variables, Heap) and what is not (Stack, Registers). This distinction is the bedrock of concurrent programming challenges.

The shared heap and global variable sections are where our HNSW graph data lives. If we launch multiple threads to insert or search the graph simultaneously, they will all be reading from and writing to this same shared memory. This is where things get complicated.

The Illusion of Atomicity

A common, and dangerous, assumption is that a single line of C code corresponds to a single, indivisible operation. Consider a seemingly innocent operation like incrementing a counter: count++.

At the machine level, this single statement is almost never atomic. It typically decomposes into a sequence of three distinct micro-operations:

  1. Load: Read the current value of count from memory into a CPU register.
  2. Modify: Add 1 to the value in the register.
  3. Store: Write the new value from the register back to memory.

The Weirdest Bug in Programming - Race Conditions

The channel Core Dumped provides an excellent, accessible explanation of why race conditions are so tricky.

First, watch the segment explaining non-atomic operations. This will solidify the concept of a single line of code compiling to multiple CPU instructions. Then, jump to the example of multiple threads incrementing a shared counter. This visualization clearly shows how the load-modify-store sequence can be interleaved between threads, leading to lost updates and an incorrect final result.

When two or more threads execute this sequence concurrently, the operating system's scheduler can interrupt and switch between threads at any point. This interleaving can lead to a "lost update" problem, which is a classic race condition.

Imagine two threads trying to increment a shared counter, which starts at 100.

  1. Thread A loads the value 100.
  2. The OS scheduler preempts Thread A and switches to Thread B.
  3. Thread B loads the value 100, increments it to 101, and stores 101 back to memory.
  4. The OS scheduler switches back to Thread A.
  5. Thread A, which still has the old value 100 in its register, increments it to 101 and stores 101 back to memory, overwriting the result from Thread B.

Even though two increments occurred, the final value is 101, not 102. One update was lost.

This flowchart illustrates a race condition involving a shared bank balance. Process 1 and Process 2 both read the initial balance of 100. Process 2 updates it to 90, but Process 1, operating on its stale copy, updates it to 110, leading to an incorrect final state.

Defining Race Conditions and the Need for Synchronization

This unpredictable outcome leads us to the formal definition:

A race condition is a flaw in a system where the output or result of a process is unexpectedly and critically dependent on the sequence or timing of other uncontrollable events. When applied to software, it occurs when multiple threads access a shared piece of data, and at least one of them is writing to it, without any mechanism to ensure the operations are performed in the correct order.

The following reading provides a clear code example and establishes the fundamental rule of synchronization.

Race Conditions, Synchronization, Mutexes

This reading continues our exploration with a C++ example and formalizes the problem.

Start by reading the section on incr-basic.cc. This demonstrates a real program that produces inconsistent results due to a race condition. Next, study the example interleavings that show a bad outcome and a good outcome. This highlights the non-deterministic nature of the problem. Finally, internalize the basic rule of synchronization. This is the core principle guiding the design of concurrent software.

The core issue is a lack of defined order. To fix this, we need to introduce synchronization—mechanisms that allow us to enforce a specific order on operations across different threads, ensuring that critical sections of code are executed with mutual exclusion.

A critical section is a piece of code that accesses a shared resource and must not be concurrently executed by more than one thread. The simplest way to enforce this is with a mutex (mutual exclusion lock).

A mutex has two primary operations:

  • lock(): A thread calls lock() to request exclusive access. If the mutex is already locked by another thread, the calling thread will block (wait) until it becomes available. Once available, the thread locks it and proceeds.
  • unlock(): After the thread has finished its work in the critical section, it calls unlock(), releasing the lock and allowing another waiting thread to acquire it.

Thread synchronization with mutexes in C

This Engineer Man video provides a very practical demonstration of fixing a race condition with a C program using POSIX threads and mutexes.

Watch the initial explanation of what a mutex is. See the demonstration of the program with the race condition, which fails to count correctly. Observe how pthread_mutex_lock and pthread_mutex_unlock are used to protect the critical section. Finally, note the correct and consistent output after the fix.

The Deep Roots: Compiler and CPU Reordering

The problem of interleaving is actually deeper than just OS scheduling. Modern compilers and CPUs are aggressive optimizers. To maximize single-threaded performance, they are permitted to reorder instructions, as long as the observable behavior of a single thread remains the same.

For example, if you write:

x = 1;
y = 2;

The compiler or CPU might decide it's more efficient to execute y = 2 first. In a single thread, you'd never notice. But in a multi-threaded program where another thread relies on x being set before y, this reordering can break your logic in subtle and catastrophic ways. CPUs also use techniques like store buffering, where a write operation is temporarily held in a buffer and not immediately made visible to other CPU cores.

This is a critical topic in low-level systems and high-frequency trading, where understanding memory visibility guarantees is paramount.

HFT 03 - How you could invent the C++ Memory model

This article from brocbyte provides a fantastic deep dive into the underlying reasons for concurrency issues, framing it in the context of high-performance computing.

In "Part 1: Tricksters", read about the two sources of reordering: The Compiler and The CPU (specifically about store buffers). Read the section titled "The conflict", which summarizes the tension between programmer assumptions and hardware reality. Next, we need a formal way to reason about order. Read the definition of a data race and the "deal" that the SC-DRF (Sequential Consistency for Data-Race-Free) model provides. Finally, and most importantly, read the section on "Happens-before". This relation is the cornerstone of modern memory models. It formally defines causality: if operation A happens-before operation B, the effects of A are guaranteed to be visible to B. Synchronization primitives like mutexes create these happens-before relationships.

This "happens-before" relationship is what we are truly trying to establish with our synchronization. When thread A unlocks a mutex and thread B subsequently locks it, a synchronizes-with relationship is created, which in turn establishes a happens-before edge between the operations in thread A before the unlock and the operations in thread B after the lock. This guarantees memory visibility and prevents the chaos of reordering.

Conclusion

In this lesson, we have laid the crucial groundwork for our venture into concurrent programming. We've moved from a simple world of linear execution to the complex, non-deterministic world of multiple threads.

Key Takeaways:

  • Race Conditions: Occur when multiple threads access shared data without synchronization, and at least one access is a write. The program's outcome becomes dependent on unpredictable thread scheduling.
  • Non-Atomicity: Seemingly simple operations like x++ are not atomic; they are sequences of load, modify, and store instructions that can be interleaved.
  • The Need for Synchronization: We must use synchronization primitives like mutexes to protect critical sections and enforce mutual exclusion, ensuring only one thread can access a shared resource at a time.
  • Deeper Causes: Race conditions aren't just about OS scheduling. Aggressive optimizations by compilers and CPUs (like instruction reordering and store buffering) break naive assumptions about program order.
  • The Happens-Before Relationship: This is the formal model for reasoning about causality and memory visibility between threads. Synchronization mechanisms create "happens-before" edges, guaranteeing that memory effects from one thread are visible to another.

Now that you understand the fundamental problem, we are ready to build the solution. In the next lesson, you will apply this knowledge to a practical task: implementing a thread-safe task queue using POSIX mutexes and condition variables. This queue will become the core of a thread pool that we'll use to parallelize our HNSW graph construction.