Concurrency Programming (1): Start with the Hardware — From count++ to Atomicity, Visibility, and Ordering
Starting from the von Neumann architecture and instruction execution, this article follows count++ down to the hardware-level problems of atomicity, visibility, and ordering.
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
- 6. What About the Order of Multiple Memory Operations?
- 7. We Have Actually Encountered Three Problems
- 8. How Does Hardware Address Them?
- 9. Summary
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 execution of one instruction can be simplified as:
┌────────────────────────────────────┐
│ │
PC provides the next instruction address │
↓ │
Fetch: load the instruction from memory │
↓ │
IR: hold the current instruction │
↓ │
Decode: decode the current instruction │
↓ │
Execute: execute the current instruction │
↓ │
PC advances to the next instruction ─────────┘2. What Does count++ Become?
A source-level expression such as count++ must first become machine instructions, and each of those instructions then goes through the execution loop from the previous section.
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 countConnecting this to the instruction cycle from the previous section:
count++
↓ simplified compiled / translated form
LOAD R1, [count]
ADD R1, 1
STORE [count], R1
↓ each machine instruction goes through the previous cycle
PC → address of LOAD
Fetch LOAD
IR ← LOAD R1, [count]
Decode LOAD
Execute LOAD
↓
PC → address of ADD
Fetch ADD
IR ← ADD R1, 1
Decode ADD
Execute ADD
↓
PC → address of STORE
Fetch STORE
IR ← STORE [count], R1
Decode STORE
Execute STOREBoth 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
│
▼
MemoryWhen the CPU accesses count, it normally loads the cache line containing it into a cache. Simplifying again:
CPU
│
▼
Cache: count = 0
│
▼
Memory: count = 0Later 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 memory.
That is fundamentally a performance problem.
Many concurrency issues are related to caches, but we will leave those details aside for now and move directly to the concurrency problems themselves.
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 = 0Then 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 = 1The reason is that:
LOAD
ADD
STOREare 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:
AtomicityWe 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
│ │
└──────────────┬───────────────┘
▼
MemoryThe original count++ race still exists, but multiple cores introduce another issue.
Suppose:
count = 0Both 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 = 0Now Core A changes count:
Core A Cache Core B Cache
count = 1 count = 0The 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:
VisibilityAgain, 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 the same count example:
count = 0
ready = falseThread A Thread B
│ │
├─ count = 1 ├─ read ready
└─ ready = true └─ if true, read countA 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 1We 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 0So 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
readyand a relationship between two writes:
count = 1
ready = trueThis gives us the third problem:
Problem 3: In what order may memory operations become observable to other cores?
That is:
Memory OrderingWhy does hardware make this problem more complicated?
For the same reason as before: modern CPUs introduce various optimizations for performance.
6.1 Store Buffer
Continue with count++. Suppose count = 0 and Core A executes:
LOAD count -> 0
ADD 1 -> 1
STORE [count], 1The STORE of count = 1 may first enter a Store Buffer, as shown below:
CPU (Core)
│
▼
Store Buffer
│
▼
Cache
│
▼
MemoryNote: Store Buffer and Cache are not the same thing. The Store Buffer is a temporary structure on a Core’s write path, while the Cache stores cached data. For simplicity, we will continue with the following abstraction:
CPU (Core A)
executes STORE [count], 1
│
▼
Store Buffer
holds count = 1 temporarily
│
▼
MemoryCore 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.
Continue with the earlier count 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 -> 0In 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? |
Their common effect is that both can influence the order in which memory operations are ultimately observed by other Cores.
7. We Have Actually Encountered Three Problems
The earlier examples can be summarized as three categories:
| Problem | Symptom | What hardware needs to answer |
|---|---|---|
| Atomicity | A and B both execute count++, both may read 0, and both may finally write 1 |
Which operations appear indivisible to other execution units? |
| Visibility | Core A has changed count to 1, while Core B may still read a cached 0 |
After one Core writes data, when can other Cores observe it? |
| Ordering | Core A completes count++ and then writes ready = true; Core B may observe ready = true first and still read count = 0 |
In what order may multiple Memory operations be observed by other Cores? |
Next, let’s look at the basic capabilities provided by hardware:
What mechanisms does modern hardware provide for these three problems?
8. How Does Hardware Address Them?
8.1 Atomicity: Atomic Instruction
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-AddInternally, 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 competitorsReturn 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 = 2It 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 - InvalidReal 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 SharedIf Core A wants to modify it to:
count = 1the hardware must coordinate ownership of that cache line and the state of other copies.
A simplified view is:
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 modificationAfter 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
Suppose count = 1 has not yet been observed by B. On hardware that permits this outcome, we may see:
Thread A / Core A Thread B / Core B
| |
+-- STORE count = 1 |
+-- STORE ready = true |
| +-- LOAD ready -> true
| +-- LOAD count -> 0To 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 -> 1The 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, Compare-And-Swap), making each update appear indivisible to competitors so they cannot observe any intermediate state. |
| Visibility | Cache Coherence: coordinates cached copies of the same Cache Line across Cores, so after one Core completes a write, other Cores do not continue using an invalidated stale value. |
| Ordering | Fence: constrains the order of related Load / Store operations, preventing other Cores from observing those memory operations in an order the program does not allow. |
Next: Thread and runtime scheduling — how threads and goroutines get CPU time.
Discussion
Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub