Ao Li

Can a Data Race Happen on a Single-Core Machine?

1. The Question

I woke up wondering: Can a data race happen on a single-core machine?.

A data race occurs when a program contains two conflicting accesses (write/write or read/write) that are not ordered by a happens-before relationship. This is the definition from Java Language Specification.

My first instinct was to ask Claude. The answer I received confidently showed a counter++ example and called it a “data race.”

1// Thread 1
2counter++;  // Read counter, increment, write back
3
4// Thread 2  
5counter++;  // If OS switches here mid-operation, data race occurs

and they explained:

If Thread 1 is interrupted between reading counter and writing the incremented value back, Thread 2 might read the old value, leading to lost updates.

In fact, in this example, the bug is caused by race condition (atomicity violation more specifically) instead of data race. In this example, the error occurs because the increment operation (counter++) is not atomic. It consists of three steps: read the value of counter, increment it, and write the new value back. If a context switch happens between these steps, another thread could read the old value of counter, leading to lost updates. Removing data-race does not solve this problem—if we make the counter variable atomic, and write the following program:

1AtomicInteger counter = new AtomicInteger(0);
2// Thread 1
3counter.set(counter.get() + 1);  
4
5// Thread 2
6counter.set(counter.get() + 1);  

This program does not have any data race because all accesses to counter are atomic. However, it still has race condition because the increment operation is still not atomic. The correct way to increment an AtomicInteger is to use the incrementAndGet() or getAndIncrement() methods, which are atomic operations.

I went back to Google but unfortunately, I could not find any relevant discussion on this topic except this StackOverflow question. Interestingly, both the original question and the top-rated answer focus on race conditions rather than data races specifically.

2. Definitions

Race condition (broad concept). Program correctness depends on the relative timing or ordering of operations. Many kinds of bugs fall under this umbrella: atomicity violations, order violations.

Data race (formal notion, e.g., Java / C / C++ memory models). Two conflicting memory accesses (same location, at least one write) performed by different threads that are not ordered by a happens-before relation and are not synchronization operations. When a data race occurs, the language usually declares the program to have undefined behavior (C/C++) or allows otherwise surprising outcomes.

Key points often missed (this part is added by LLM but I found them useful so I keep them):

John Regehr’s post on Race Condition vs. Data Race provides nice examples about data race and race conditions. (I’m unsure about transfer4. If you do not try to observe them are they still considered data races?)

3. Hardware Memory Model and Why Data Race Happens

CPUs are implemented with various optimizations, such as store buffers, caches, out-of-order execution, etc. These optimizations may change the order of memory operations. Russ Cox’s post on hardware memory models provides a good overview of how hardware memory models work. And the following diagram shows how x86-TSO (Total Store Order) model works:

x86 TSO conceptual diagram

Data race can happen in x86-TSO model because of the store buffer. For example, consider the following code:

1// Thread 1           // Thread 2
2x = 1                 y = 1
3r1 = y                r2 = x

It is possible for both r1 and r2 to be 0 at the end of execution. Here is how it can happen:

  1. Thread 1 executes x = 1 and puts the store into its store buffer.
  2. Thread 2 executes y = 1 and puts the store into its store buffer.
  3. Thread 1 executes r1 = y and reads the value of y from memory, which is still 0 because Thread 2’s store is in its store buffer and has not been flushed to memory yet.
  4. Thread 2 executes r2 = x and reads the value of x from memory, which is still 0 because Thread 1’s store is in its store buffer and has not been flushed to memory yet.

4. Back to the Single Core Question

Why does single core matters? Because, one problem caused by data race is that one thread may not observe the memory operations from other threads if they are not synchronized. However, if we run all threads on a single core, then all memory operations are observed by all threads in the same order. A single hardware thread never observes its own operations out of program order (“program-order illusion”). So, it seems that data race cannot happen in a single core machine. While searching for references, I found Jeff Preshing’s post on memory reordering also confirmed my thinking:

a single processor never sees its own operations out of order, even when threads are pre-empted and rescheduled at arbitrary times.

5. Programming Language Memory Model

But if you read Jeff’s post carefully, you will find this interesting sentence:

Don’t be spooked by the presence of the asm volatile line in the above code listing. This is just a directive telling the GCC compiler not to rearrange the store and the load when generating machine code, just in case it starts to get any funny ideas during optimization.

Ah, so compiler optimization can also cause reordering! This means that even on a single core machine, if the compiler is allowed to reorder instructions, we may still observe outcomes that are not explainable by simple interleaving of operations. This is also mentioned by Java Language Specification (§17.4): The semantics of the Java programming language allow compilers and microprocessors to perform optimizations that can interact with incorrectly synchronized code in ways that can produce behaviors that seem paradoxical. Here are some examples of how incorrectly synchronized programs may exhibit surprising behaviors.

Unfortunately, triggering a compiler optimization that causes reordering is not easy. I wrote the following program and run it on my desktop but never observed the reordering effect. If you know a better way to observe data race caused by compiler optimization, please let me know!

 1public class ReorderTest {
 2    static int A, B;
 3    static int r1, r2;
 4
 5    public static void main(String[] args) throws Exception {
 6        for (long iter = 1; ; iter++) {
 7            A = B = 0; r1 = r2 = -1;
 8            Thread t1 = new Thread(() -> { r2 = A; B = 1; });
 9            Thread t2 = new Thread(() -> { r1 = B; A = 2; });
10            t1.start(); t2.start();
11            t1.join(); t2.join();
12            if (r1 == 0 && r2 == 0) {
13                System.out.println("Reordering observed after " + iter + " iterations");
14                break;
15            }
16        }
17    }
18}

6. Conclusion

Can data races occur on single-core machines? The answer is both yes and no, depending on several factors. Data races can still happen due to compiler optimizations and language memory model specifications that may reorder operations or cache values in unexpected ways. However, if you’re working at the assembly level with direct hardware control, a single-core machine can help you avoid certain types of data races since there’s no true concurrent execution of instructions.

Am I missing something? Please let me know if you have other opinions.

Disclaimer

I wrote the initial draft of this post and used LLMs to polish the language.

#Data Race #Race Condition #Concurrency