Table of Contents
- 1. Start with the von Neumann Architecture
- 2. What Does
count++Become? - 3. Why Do We Need Caches?
- 4. Concurrency on One Core: Why Can
count++Lose an Update? - 5. From One Core to Multiple Cores: Visibility
This article continues to use count, but focuses only on the hardware layer:
What concurrency problems do the CPU and memory system introduce, and what capabilities does the hardware provide to address them?
1. Start with the von Neumann Architecture
The von Neumann model treats programs as data: instructions and data are stored in the same general way. At a high level, a computer can be divided into a control unit, arithmetic unit, memory, input devices, and output devices.
The arithmetic and control units form the CPU, which also contains registers. The Program Counter (PC) stores the address of the next instruction; the Instruction Register (IR) stores the instruction currently being processed; general-purpose registers such as R1 hold data and intermediate results.
┌──────────────────┐ ┌──────────────────┐
│ Input Device │ │ Output Device │
└─────────┬────────┘ └─────────▲────────┘
│ │
└───────────────────┬───────────────────┘
│
System Bus
│
┌────────────────┴─────────────────┐
│ │
▼ ▼
┌────────────────────────┐ ┌────────────────────────┐
│ CPU │ │ Memory │
│ │ │ │
│ Control Unit │ │ Instructions + Data │
│ Arithmetic Unit │ │ │
│ Registers │ │ │
│ PC / IR / R1 │ │ │
└────────────────────────┘ └────────────────────────┘
The CPU execution loop can be simplified to:
PC provides instruction address
↓
Fetch → Decode → Execute
↓
PC advances to the next instruction and repeats
The CPU repeatedly performs Fetch → Decode → Execute. A source-level expression such as count++ must eventually be converted into machine instructions that follow this process.
2. What Does count++ Become?
For discussion, we can simplify count++ into three machine-level operations:
LOAD R1, [count] // load count into R1
ADD R1, 1 // increment R1 inside the CPU
STORE [count], R1 // write the result back to count
Both LOAD and STORE access data. That leads naturally to the next question:
What would happen if every LOAD and STORE had to wait directly for main memory?
3. Why Do We Need Caches?
A CPU executes far faster than main memory can be accessed. If every LOAD had to wait for main memory to return data and every STORE had to wait until memory completed the write, the CPU would spend a large amount of time idle.
Modern processors therefore place smaller, faster cache levels between a CPU core and main memory. A simplified hierarchy looks like this; exact levels and which caches are shared depend on the processor design:
CPU
│
▼
L1 Cache
│
▼
L2 Cache
│
▼
L3 Cache
│
▼
Memory
When the CPU accesses count, it normally loads the cache line containing it into a cache. Simplifying again:
CPU
│
▼
Cache: count = 0
│
▼
Memory: count = 0
Later accesses to count may hit in the cache instead of going to main memory every time.
So:
Caches address the speed gap between the CPU and main memory.
That is a performance optimization. It does not make:
count++
a safe concurrent operation automatically.
Start with a single core.
4. Concurrency on One Core: Why Can count++ Lose an Update?
Suppose the machine has only one CPU core:
Thread A ──┐
│
├──> Core 0 ──> Cache ──> Memory
│
Thread B ──┘
The two threads cannot literally execute at the same instant on that core, but the scheduler can interleave them.
Start with:
count = 0
Then the following schedule is possible:
Thread A Thread B
│ │
├─ LOAD count -> 0 │
│ │
├─────── context switch ────────────>│
│ ├─ LOAD count -> 0
│ ├─ ADD 1
│ ├─ STORE count -> 1
│ │
│<────── context switch ─────────────┤
├─ ADD 1 │
├─ STORE count -> 1 │
During a context switch, the operating system preserves Thread A's execution context, including intermediate state. When A resumes, it can continue computing from the 0 it read earlier.
The final result is:
count = 1
The reason is that:
LOAD
ADD
STORE
are not one indivisible operation.
If another execution unit can run between those steps, a lost update becomes possible.
This gives us the first problem:
Problem 1: How can a compound operation execute indivisibly?
That is the problem of:
Atomicity
We will not answer it yet. First, move from one core to multiple cores.
5. From One Core to Multiple Cores: Visibility
With multiple CPU cores, two threads may truly execute in parallel:
Thread A Thread B
│ │
▼ ▼
Core A Core B
│ │
▼ ▼
Cache A Cache B
│ │
└──────────────┬───────────────┘
▼
Memory
The original count++ race still exists, but multiple cores introduce another issue.
Suppose:
count = 0
Both Core A and Core B have read count. The same data may now exist in separate caches:
Core A Cache Core B Cache
count = 0 count = 0
Memory
count = 0
Now Core A changes count:
Core A Cache Core B Cache
count = 1 count = 0
The question becomes:
May Core B keep using its old copy?
Or more generally:
Problem 2: After one core writes data, when can other cores observe the new value?
That is:
Visibility
Again, hold the answer for a moment and move to the third class of problem.
6. What About the Order of Multiple Memory Operations?
Continue with a publication-style example:
count = 0
ready = false
Thread A Thread B
│ │
├─ count = 1 ├─ read ready
└─ ready = true └─ if true, read count
A programmer naturally wants the following guarantee:
If Thread B has already observed
ready = true, it should also observe the earlier writecount = 1.
Ideally, B should only see one of these outcomes:
Outcome 1:
Thread A Thread B
read ready -> false
do not enter if
Outcome 2:
Thread A Thread B
count = 1
ready = true read ready -> true
enter if
read count -> 1
print 1
We do not want:
Thread A Thread B
count = 1
(write not yet observed by B)
ready = true read ready -> true
enter if
read count -> 0
print 0
So the question is:
Once B has read
ready = true, how do we prevent it from still reading the oldcount = 0?
This is no longer merely a question about multiple cached copies of the same location. We now have two different memory locations:
count
ready
and a relationship between two writes:
count = 1
ready = true
This gives us the third problem:
Problem 3: In what order may memory operations become observable to other cores?
That is:
Memory Ordering
Why does hardware make this complicated? Primarily because modern CPUs introduce aggressive performance optimizations.
6.1 Store Buffer
Continue with count++. Suppose count = 0 and Core A executes:
LOAD count -> 0
ADD 1 -> 1
STORE [count], 1
The STORE of count = 1 may first enter a store buffer.
First, place the Store Buffer back into a slightly more complete conceptual write path:
CPU (Core)
│
▼
Store Buffer
│
▼
Cache
│
▼
Memory
Note: the Store Buffer and Cache are not the same thing. The Store Buffer is a temporary structure on a core's write path; the Cache stores cached data. Real processors have more complicated write paths, cache hierarchies, and coherence protocols. This diagram is only meant to distinguish the two layers.
To highlight the point that “the write has already been executed by the current Core, but another Core has not observed it yet,” the following diagram omits Cache / Coherence details and continues with a simplified view:
CPU (Core A)
executes STORE [count], 1
│
▼
Store Buffer
holds count = 1 temporarily
│
▼
Memory
Core A can continue executing before the buffered write becomes visible to other cores:
initial: count = 0
Core A Core B
│ │
├─ LOAD count -> 0 │
├─ ADD 1 -> 1 │
├─ STORE count -> 1 │
│ enters Store Buffer │
├─ continue with later instructions │
│ ├─ LOAD count -> 0
│ │ still sees old value
└─ count = 1 becomes visible │
6.2 Out-of-Order Execution
Modern CPUs also rearrange internal execution, where dependencies allow it, to keep execution units busy.
As long as this does not change the result observed by the current thread, such optimization is valid from that thread's perspective. The difficulty appears when multiple cores interact.
Return to the publication example:
Thread A / Core A Thread B / Core B
count = 1 if ready {
ready = true print(count)
}
The source code writes count before ready. But without additional ordering constraints, on hardware whose memory model permits it, another core may observe:
initial: count = 0, ready = false
Thread A / Core A Thread B / Core B
│ │
├─ STORE count = 1 │
│ not yet observed by Core B │
├─ STORE ready = true │
│ ├─ LOAD ready -> true
│ └─ LOAD count -> 0
In other words, A issued the count write first in source order, yet B observed ready = true first and then still read the old count = 0.
The underlying question is:
In what order is another core allowed to observe these memory operations?
6.3 Store Buffer vs Out-of-Order Execution
These two mechanisms are easy to confuse, so compare the questions they answer directly:
| Concept | What question does it answer? |
|---|---|
| Store Buffer | After a STORE has already been executed by the current Core, why might another Core still not see it yet? |
| Out-of-Order Execution | Why might an independent instruction that appears later in source code execute earlier inside the Core? |
Therefore, Store Buffer and Out-of-Order Execution are not the same mechanism: the former concerns write propagation and visibility timing, while the latter concerns instruction scheduling inside the Core. Both can affect the memory order eventually observed by other Cores.
7. We Have Actually Encountered Three Problems
The earlier examples can be summarized as three categories:
| Problem | Symptom | What hardware must define |
|---|---|---|
| Atomicity | A and B both execute count++, both can read 0, and both finally write 1
|
Which operations are atomic? |
| Visibility | Core A has changed count to 1, while Core B may still read a cached 0
|
When does a write by one core become observable to another? |
| Ordering | Core A writes count = 1 and then ready = true, while Core B may observe ready = true and still read count = 0
|
Which ordering relationships are guaranteed between memory operations? |
The first problem can occur both with single-core context switches and with true multicore parallelism. The key issue is not the number of CPU cores, but whether the steps of a Read-Modify-Write sequence can be interleaved with another execution unit.
Now we can ask what primitives the hardware provides:
What mechanisms does modern hardware provide for these three problems?
8. How Does Hardware Address Them?
8.1 Atomicity: Atomic Instructions
A normal LOAD + ADD + STORE consists of several operations. To make a Read-Modify-Write operation appear indivisible to other execution units, hardware provides atomic operations such as:
Compare-And-Swap
Exchange
Fetch-And-Add
Internally, these operations are not necessarily a single microscopic step. “Atomic” describes what competing execution units are allowed to observe:
┌──────────────────┐
│ read old value │
│ │ │
│ ▼ │
│ modify │
│ │ │
│ ▼ │
│ write new value │
└────────┬─────────┘
│
└── appears as one indivisible atomic operation to competitors
Return to count++. If a language implements the increment with a hardware-supported atomic Read-Modify-Write, we can reason about the result as:
initial: count = 0
Thread A Thread B
atomically change count 0 -> 1
atomically change count 1 -> 2
final: count = 2
It does not matter whether A or B wins first. Each atomic update must operate on a definite previous value, so both threads cannot independently read 0 and then both write 1.
8.2 Visibility: Cache Coherence
Multicore processors use cache-coherence protocols to coordinate cached copies of the same memory location across cores.
MESI is one of the classic coherence protocols:
M - Modified
E - Exclusive
S - Shared
I - Invalid
Real processors may use MESI or extensions and variants such as:
MESI
MOESI
MESIF
...
We do not need every state transition here; focus on the problem coherence solves.
Suppose both cores cache the line containing count:
Core A Cache Core B Cache
count = 0 count = 0
Shared Shared
If Core A wants to modify it to:
count = 1
the hardware must coordinate ownership of that cache line and the state of other copies.
At a very high level:
Core A wants to modify count
│
▼
obtain write permission for the cache line
│
▼
invalidate copies that may no longer be used
│
▼
Core A performs the modification
After Core A obtains write permission, Core B's old count = 0 copy is invalidated. The next time B reads count, it cannot continue using that stale copy.
8.3 Memory Ordering: Fence
Consider again:
count = 1
ready = true
Modern CPUs use store buffers, out-of-order execution, and other mechanisms to improve performance. A hardware memory model must define:
Which memory-operation orderings are guaranteed?
Which reorderings are permitted?
Which outcomes may different cores observe?
That is memory ordering.
Return to the publication example. If count = 1 has not yet become observable to B, hardware that permits the outcome might allow:
Thread A / Core A Thread B / Core B
| |
+-- STORE count = 1 |
+-- STORE ready = true |
| +-- LOAD ready -> true
| +-- LOAD count -> 0
To forbid that result, fences can constrain the order of memory operations on each side:
Thread A / Core A Thread B / Core B
| |
+-- STORE count = 1 |
+-- FENCE |
+-- STORE ready = true |
| +-- LOAD ready -> true
| +-- FENCE
| +-- LOAD count -> 1
The writer-side fence prevents count = 1 from being ordered after ready = true. The reader-side fence prevents the read of count from being ordered before the read of ready.
A fence does not guarantee that B will read ready = true. But once B has observed ready = true under the required synchronization pattern, the later read of count cannot still return the stale 0.
9. Summary
Hardware provides different foundations for the three concurrency problems:
| Problem | Hardware capability |
|---|---|
| Atomicity | Atomic Instruction: provides an atomic Read-Modify-Write operation (for example, Fetch-And-Add), so one update appears indivisible to competitors and they cannot observe an intermediate state. |
| Visibility | Cache Coherence: coordinates the state of copies of the same cache line across cores, so writes propagate according to the coherence protocol and other cores cannot continue using an invalidated stale copy. |
| Ordering | Fence: constrains related Loads / Stores from being observably reordered across the barrier, establishing the memory-operation ordering relationships required across cores. |
The next article returns to the language layer and looks at how Java, Go, and CPython turn these hardware capabilities into rules that programmers can rely on.
This article was first published on ThinkerQAQ's personal blog and syndicated here by the author. The original article may be revised over time; please refer to the personal blog for the latest version.
