Skip to content

Volume ITechnology

2.4.1 — Atomic Instructions & Memory Order ​

The photo-upload service counts how many photos it has received. Two threads handle uploads, and each one adds 1 to a shared counter for every photo. Each thread handles a million photos. So at the end, the counter should say two million.

ts
// lost-uploads.ts — two threads count uploads into the same shared memory
import { Worker, isMainThread, workerData } from "node:worker_threads";

const PER_THREAD = 1_000_000;

if (isMainThread) {
  for (const mode of ["plain", "atomic"] as const) {
    const shared = new Int32Array(new SharedArrayBuffer(4));      // (1) one shared 32-bit counter
    await Promise.all([1, 2].map(() => new Promise((done) =>
      new Worker(new URL(import.meta.url), { workerData: { shared, mode } }).on("exit", done))));
    console.log(`${mode}: expected ${2 * PER_THREAD}, got ${shared[0]}`);
  }
} else {
  const { shared, mode } = workerData as { shared: Int32Array; mode: string };
  for (let i = 0; i < PER_THREAD; i++) {
    if (mode === "plain") shared[0] = shared[0] + 1;               // (2) read, add, write
    else Atomics.add(shared, 0, 1);                                // (3) one indivisible step
  }
}

// Three runs printed:
// plain: expected 2000000, got 1227476      plain: … got 1403339      plain: … got 1483865
// atomic: expected 2000000, got 2000000     atomic: … got 2000000     atomic: … got 2000000
  • (1) A SharedArrayBuffer is a block of memory that several threads can see at the same time (2.3.1). We view its 4 bytes as one 32-bit whole number, the counter. Both workers receive the same memory, not a copy.
  • (2) In the first run, each thread adds 1 with an ordinary read and write.
  • (3) In the second run, each thread adds 1 with Atomics.add.

The ordinary version lost between a quarter and almost half of the uploads. Worse, it lost a different number each time. The atomic version was right every time. This page explains exactly why, at the level of single CPU instructions. Then it explains the two hardware facts underneath every lock and every concurrent program: how CPU caches stay in agreement, and why CPUs are allowed to run your memory operations out of order.

The application-level story, such as check-then-act bugs and how to design around them, is in 9.5.1. This page is about the machine underneath it.

1. One line of code is three instructions ​

shared[0] = shared[0] + 1 looks like one action. To the CPU it is three separate instructions (1.5):

  1. Load the counter from memory into a register.
  2. Add 1 to the register.
  3. Store the register back to memory.

Each instruction is fine on its own. The trouble is the gaps between them. Suppose the counter is 41, and both threads run these three steps at almost the same moment on two cores:

thread A (core 0)thread B (core 1)1load counter → 412load counter → 41 (!)3add 1 → 42, store 424add 1 → 42, store 42two uploads counted, counter went 41 → 42: one is lost
Figure 1 — A lost update. ① A reads 41. ② Before A has stored anything, B also reads 41. ③ A stores 42. ④ B stores 42 too, overwriting A's work. Every instruction ran correctly, yet the answer is wrong.

Both threads read 41. Both computed 42. Both stored 42. Two uploads happened, and the counter moved by one. An update was silently lost.

This is a race condition: a bug where the result depends on exactly how the threads' instructions happened to interleave in time. The few instructions that touch the shared data form a critical section. The real problem is that this critical section is not atomic, a word from Greek meaning "uncuttable". Another thread can run in the middle of it and see, or change, a half-finished state.

Three things make races uniquely nasty:

  • They are not repeatable. The result depends on timing down to nanoseconds, so it changes from run to run, as our three different numbers show. A debugger changes the timing, so the bug often vanishes while you watch.
  • They hide in testing. With light load, the bad interleaving might happen once in a million operations. Every test passes, and production fails.
  • They get worse under load. More threads, more cores and more traffic make the rare interleaving common. The bug appears exactly when the system is busiest.

2. Atomic instructions: indivisible in silicon ​

The fix is to make the read, the add and the write happen as one step that nothing can come between. Software cannot do that by itself, for the same reason as in 2.1.1: any software solution would itself be made of several instructions. So CPUs provide special atomic instructions that do a whole read-change-write as one indivisible operation. The hardware guarantees that no other core can read or write that memory in the middle.

On Intel and AMD processors, putting the prefix lock in front of certain instructions makes them atomic. lock xadd adds a number to memory and returns the old value, in one step. That is what Atomics.add turns into on those CPUs. ARM processors, used in phones and Apple's M-series Macs, have their own atomic instructions that do the same job.

How can the hardware promise that? The answer is the cache, which section 4 explains. In short: before the atomic instruction runs, the core takes exclusive ownership of the small block of memory holding the counter. While it owns that block, every other core that wants it has to wait. The core does the read, the add and the write, and only then lets go. To other cores, the counter went from 41 to 42 in a single instant.

Atomics.add in our demo is exactly this. Each call is one indivisible add. So each thread's million adds all land, and the total is always two million.

Not just adding ​

There is an atomic version of each common operation. In JavaScript they are all on the Atomics object, and other languages have the same set under different names.

OperationWhat it does in one step
Atomics.load / storeread or write without tearing
Atomics.add / subadd or subtract, return the old value
Atomics.exchangewrite a new value, return the old one
Atomics.compareExchangewrite only if the value is still what you expect

"Without tearing" in the first row means you never see half of an old value and half of a new one. That can happen on some machines with values wider than the CPU writes in one go.

3. Compare-and-swap: the instruction everything is built on ​

The last row of that table is the most important instruction in all of concurrent programming. It is called compare-and-swap, or CAS. It takes three things: a memory location, the value you expect to find there, and the new value you want. In one indivisible step it does this:

  • If the location still holds the expected value, write the new value, and report success.
  • If it holds anything else, change nothing, and report what it actually holds.

Why is that so useful? Because it lets you do any update safely, not only adding. Read the current value, compute what the new value should be, then use CAS to say "change it, but only if nobody else changed it while I was computing". If someone did, you simply try again.

Here is the upload service keeping track of the largest photo any thread has seen. There is no single "atomic maximum" instruction, but CAS builds one.

ts
// largest-photo.ts — keep the largest upload size seen by any thread, with compare-and-swap
import { Worker, isMainThread, workerData } from "node:worker_threads";

function recordSize(largest: Int32Array, size: number): void {
  while (true) {
    const seen = Atomics.load(largest, 0);                         // (1) read the current value
    if (size <= seen) return;                                      // (2) nothing to do
    if (Atomics.compareExchange(largest, 0, seen, size) === seen)  // (3) swap only if unchanged
      return;                                                      // (4) we won
    // (5) someone changed it between (1) and (3): loop and try again
  }
}

if (isMainThread) {
  const largest = new Int32Array(new SharedArrayBuffer(4));
  await Promise.all([1, 2, 3, 4].map((seed) => new Promise((done) =>
    new Worker(new URL(import.meta.url), { workerData: { largest, seed } }).on("exit", done))));
  console.log("largest photo:", largest[0], "bytes");
} else {
  const { largest, seed } = workerData as { largest: Int32Array; seed: number };
  for (let i = 0; i < 200_000; i++) recordSize(largest, (i * 7919 * seed) % 9_000_000);
  if (seed === 4) recordSize(largest, 9_437_184);                 // one 9 MB photo, from thread 4
}

// Prints:
// largest photo: 9437184 bytes
  • (1) Read the largest size recorded so far.
  • (2) If this photo is not bigger, there is nothing to do.
  • (3) compareExchange returns the value it actually found. If that equals seen, nobody changed the value since line (1), so our new size has been written.
  • (4) Success. We are done.
  • (5) If it returned something else, another thread got in between our read and our swap, perhaps with an even bigger photo. Our swap did nothing, so we loop, read the new value, and decide again.

Four threads hammered the same value 800,000 times, and the 9 MB photo, recorded by thread 4, was kept correctly. No lock was used anywhere. Code that coordinates threads using only atomic instructions like this, without locks, is called lock-free. It never puts a thread to sleep, because a thread that loses a race just tries again.

Lock-free code is fast and hard to get right. One famous trap, the ABA problem, catches people writing lock-free lists. A thread reads value A, gets interrupted, and meanwhile another thread changes A to B and then back to A. The first thread's CAS then succeeds, because it sees A again, even though the world changed underneath it. For a simple counter or a maximum that does not matter. For a linked list, where A is a pointer to a node that has been freed and reused, it can corrupt the list. This is why most programmers use well-tested lock-free building blocks rather than writing their own.

And CAS is how every lock is built. A lock is just a number that says "free" or "taken". Taking the lock means "change it from free to taken, but only if it is free", which is one compare-and-swap. Page 2.4.2 builds one.

4. Every core has its own cache, and they must agree ​

Section 2 said a core takes "exclusive ownership" of memory before an atomic operation. To see what that means, recall 1.6: every core has its own small, fast cache, because main memory is far too slow to reach on every instruction. Caches do not hold single bytes. They hold cache lines, blocks of usually 64 bytes.

Now there is a problem. If core 0 and core 1 both have a copy of the counter's cache line, and core 0 changes its copy, core 1's copy is now wrong. The cores must keep their caches in agreement. That job is called cache coherence, and the hardware does it automatically, all the time.

Most CPUs use a rule set whose classic form is called MESI, after the four states each cache line can be in:

StateMeaning
Modifiedonly this core has it, and has changed it
Exclusiveonly this core has it, unchanged
Sharedseveral cores have identical copies
Invalidthis copy is out of date; do not use it

The rule that matters is this: to write to a cache line, a core must first make every other core's copy Invalid. It sends a message across the chip saying "I am writing this line; throw your copies away". Only then may it write. The next time another core reads that line, its copy is Invalid, so it has to fetch the fresh version from the core that changed it.

That is how an atomic instruction stays atomic. The core takes the line into the Modified state, holds it there for the whole read-add-write, and only then answers other cores' requests for it.

The cost: a cache line bouncing between cores ​

In our counter demo, both threads write the same line, millions of times. So the line keeps moving: core 0 takes it, core 1 takes it back, core 0 takes it again. Every move is a trip across the chip that costs tens of nanoseconds, far more than the add itself. An atomic counter that many threads update is correct, but slow, because the cores spend their time passing one cache line back and forth.

False sharing: slow without even sharing ​

Here is a trap that catches experienced engineers. Give each of two threads its own counter, so they never touch the same variable. Surely there is no contention now? It depends on where the two counters sit in memory.

ts
// false-sharing.ts — two threads, two separate counters, near each other or far apart
import { Worker, isMainThread, workerData } from "node:worker_threads";

const N = 20_000_000;

if (isMainThread) {
  for (const gap of [1, 16]) {                                    // (1) 1 slot = 4 bytes; 16 slots = 64 bytes
    const counters = new Int32Array(new SharedArrayBuffer(4 * 64));
    const start = performance.now();
    await Promise.all([0, gap].map((slot) => new Promise((done) =>
      new Worker(new URL(import.meta.url), { workerData: { counters, slot } }).on("exit", done))));
    console.log(`counters ${gap * 4} bytes apart: ${(performance.now() - start).toFixed(0)} ms`);
  }
} else {
  const { counters, slot } = workerData as { counters: Int32Array; slot: number };
  for (let i = 0; i < N; i++) Atomics.add(counters, slot, 1);     // (2) each thread touches only its own slot
}

// Printed on an 8-core laptop (three runs gave 975/345, 1089/318 and 978/327 ms):
// counters 4 bytes apart: 975 ms
// counters 64 bytes apart: 345 ms
  • (1) The first run puts the two counters right next to each other, 4 bytes apart. The second puts them 64 bytes apart.
  • (2) Each thread only ever touches its own counter. The threads share no variable at all.

Yet the first run was about three times slower. The reason is the 64-byte cache line. Two counters 4 bytes apart sit in the same line. The cores do not track individual variables. They track lines. So every write by thread 0 invalidates thread 1's copy of the line, and the other way round, exactly as if they shared a variable. This is false sharing: the threads share nothing in the code, but share a cache line in the hardware.

The fix is to keep data that different threads write often at least one cache line apart, by adding unused padding between them. Even better, let each thread count privately in its own local variable, and add the totals together once at the end.

5. Your memory operations can run out of order ​

There is one more hardware fact, and it is the strangest. Both the compiler and the CPU are allowed to reorder your memory operations, as long as a single thread cannot tell the difference.

The compiler does it to make code faster, for example by moving a read out of a loop. The CPU does it too. A store, a write to memory, is slow. So each core puts its stores in a small queue called a store buffer, and carries on with the next instructions while the store drains to the cache in the background. A load that comes after the store in the program may therefore reach memory before the store does.

For one thread on its own, this is invisible. The core checks its own store buffer, so it always sees its own writes. But another thread on another core can see the effects in a different order. Here is the classic example. Two flags, x and y, start at 0.

Thread AThread B
x = 1y = 1
read yread x

Can both threads read 0? By the program order it seems impossible: whichever thread goes second must see the other's 1. But on an ordinary Intel or AMD processor, both can read 0. Each core's write sits in its own store buffer while its read races ahead to the cache and finds the other flag still at 0. ARM processors allow even more kinds of reordering than that.

Why should you care? Because this is exactly the pattern of the simplest hand-made "lock": "set my flag, then check whether the other thread's flag is set". With reordering, both threads can believe they got in first.

Barriers put the order back ​

CPUs provide memory barriers, also called fences: instructions that say "all memory operations before this point must be visible before any after it". Atomic instructions act as barriers too. Languages build on these with two common ideas:

  • A release write makes everything this thread wrote before it visible to any thread that later sees that write.
  • An acquire read guarantees that this thread sees everything that was written before the release it read.

Together they are the contract every lock gives you. Taking a lock is an acquire. Releasing it is a release. So everything one thread did inside the lock is visible to the next thread that takes it. That is why, as long as you use locks correctly, you never have to think about reordering yourself.

In JavaScript, every Atomics operation is the strongest kind, called sequentially consistent: all threads see all atomic operations in one single order, as if there were no reordering at all. Ordinary reads and writes to a SharedArrayBuffer, like line (2) of the first demo, have no such guarantee. That is the rule to take away: memory that several threads write must only be touched with atomic operations or inside a lock.

A common misunderstanding is worth naming. In C and C++, marking a variable volatile does not make it safe to share between threads. It only stops the compiler from removing or caching reads of it. It does nothing about the CPU's store buffer, and it does not make count++ atomic. Java's volatile is different and does give ordering guarantees, which is one source of the confusion.

What the interviewer will push on ​

"Why is count++ not thread-safe?" They are checking that you know it is three instructions: load, add, store. Two threads can both load the old value, and one update is lost. The strong answer names the critical section and says the fix is to make it atomic, either with an atomic instruction or a lock.

"How does an atomic increment actually work in hardware?" The tell is cache coherence. The core takes exclusive ownership of the cache line, does the read, the add and the write while holding it, and other cores wait. On x86 that is a lock-prefixed instruction.

"What is compare-and-swap, and what is it used for?" "Write the new value only if the old value is still what I expect, in one step." It builds lock-free updates, such as a maximum, by retrying in a loop, and it builds every lock. Bonus points for the ABA problem.

"What is false sharing?" Two threads writing different variables that happen to sit in the same 64-byte cache line, so the line bounces between cores. The fix is padding, or per-thread counters summed at the end. Quoting a measured slowdown, such as this page's three times, shows you have seen it.

"Can a CPU reorder memory operations? Does volatile fix it?" Yes, through store buffers and compiler optimisation; barriers, atomics and locks restore the order. In C and C++, volatile does not.

Something to volunteer that nobody asks for: an atomic counter is correct but does not scale, because every update moves one cache line between cores. High-traffic counters in real systems are kept per thread or per core and added up when someone reads them.

Recall

  • count++ is three instructions, load, add and store. Two threads can interleave inside that critical section and lose an update. That is a race condition: not repeatable, hidden in testing, worse under load.
  • Atomic instructions (x86 lock prefix, Atomics.add in JavaScript) do a whole read-change-write as one step no other core can interrupt.
  • Compare-and-swap writes a new value only if the old one is still as expected. It builds lock-free updates by retrying, and it is the instruction every lock is built on.
  • Cache coherence (MESI) keeps each core's cache in agreement by invalidating other copies before a write. Hot shared data bounces between cores; false sharing does the same to unrelated variables in one 64-byte cache line.
  • Compilers and CPUs reorder memory operations; memory barriers, acquire and release, atomics and locks restore order. Shared memory must be touched only with atomics or inside a lock; C's volatile is not enough.

Self-test: Walk through how two threads turn 41 into 42 instead of 43. What does the CPU do so that Atomics.add cannot lose an update? Write the steps of a CAS retry loop. Why were two separate counters three times slower when 4 bytes apart? How can two threads that each set a flag and then read the other's flag both read 0?

Quiz Bank ​

FoundationalWhat is a race condition? Give the classic example.

A race condition is a bug whose result depends on the exact timing of how concurrent threads' instructions interleave. The classic example is two threads each adding 1 to a shared counter a million times. count = count + 1 is three instructions: load, add, store. If one thread loads the old value, and the other loads the same value before the first stores, both store the same new value and one increment is lost. The final total is unpredictably less than two million. The few instructions that touch the shared value are the critical section, and the root cause is that it is not atomic.

FoundationalWhat is an atomic instruction?

An atomic instruction is a CPU instruction that performs a whole read-change-write on memory as one indivisible step, so no other core can read or write that memory in the middle. Examples are atomic add, exchange, and compare-and-swap. On x86 they are written with a lock prefix; in JavaScript they are the Atomics methods. Software cannot create this guarantee from ordinary instructions, so the hardware provides it, and every lock is built on top of it.

AppliedExplain compare-and-swap and show how it can implement an update that has no dedicated atomic instruction.

Compare-and-swap takes a location, an expected value and a new value. In one step, if the location still holds the expected value it writes the new value and reports success; otherwise it changes nothing and reports the value it found.

To update a shared maximum: read the current value; if the new candidate is not larger, stop; otherwise CAS from the value you read to the candidate. If the CAS reports that the value changed in the meantime, another thread got in first, so read again and retry. This loop is lock-free: no thread ever sleeps, and a thread that loses a race just tries again.

InterviewWhat is false sharing, and how do you fix it?

CPU caches track memory in cache lines, usually 64 bytes. When two threads write two different variables that happen to be in the same cache line, cache coherence treats it as sharing: each write by one core invalidates the other core's copy, and the line bounces back and forth. The code shares nothing, but runs as if it did. In a measured example, two counters 4 bytes apart were about three times slower than the same counters 64 bytes apart.

Fix it by keeping frequently written per-thread data at least a cache line apart, with padding, or by letting each thread count in a private local variable and combining the results at the end.

InterviewCan the CPU reorder memory operations? How do programs stay correct?

Yes. Compilers reorder operations to optimise code, and CPUs let a later load complete before an earlier store has left the core's store buffer. A single thread cannot tell, but another thread can observe writes in a different order. In the classic two-flag example, each thread sets its own flag and then reads the other's, and on ordinary x86 hardware both can read 0.

Programs stay correct by using memory barriers and the atomic operations and locks built on them. Taking a lock acts as an acquire and releasing it as a release, so everything written inside the lock by one thread is visible to the next thread that takes it. JavaScript's Atomics operations are sequentially consistent. In C and C++, volatile does not provide these guarantees.

StaffA metrics library keeps one global atomic counter per metric, and under high load on a 64-core machine the service spends a large share of CPU time inside the counter increments. Explain and propose a design.

Every increment is correct, but each one needs exclusive ownership of the counter's cache line. With 64 cores incrementing the same counter, that line moves between cores on nearly every operation, each move costing tens of nanoseconds of cross-chip traffic, so the increments serialise and dominate the profile. Counters packed next to each other also cause false sharing between different metrics.

The standard design is to shard. Keep one counter per core or per thread, each padded onto its own cache line. Each thread increments its local counter, with no contention. Sum the shards only when someone reads the metric, which is rare by comparison. Reads become slightly more expensive and slightly less instantaneous, which is fine for metrics. This is the same idea behind per-CPU counters inside the Linux kernel.

Scenario Drill ​

DrillThe photo-upload service keeps two shared values in a SharedArrayBuffer: the number of uploads and the total bytes uploaded. A colleague updates each with Atomics.add and says the pair is now safe. A dashboard reading both sometimes shows an average photo size that is impossible. Explain.

Each Atomics.add is atomic on its own, so neither value loses updates. But the pair is updated in two separate steps: first the count, then the bytes. A reader can run between those two steps, and see a count that already includes a new photo and a byte total that does not yet. Dividing the two gives an average that matches no real moment in time.

Atomic operations protect one memory location at a time. When two values must change together, the whole update is the critical section, and it needs a lock around both the writes and the reads. Page 2.4.2 builds exactly that lock. Alternatives are to pack both values into one 64-bit atomic value, or to have the reader retry until it gets a consistent pair, but a lock is the simplest correct answer.

Next: an atomic instruction protects one memory location for one instruction. Real critical sections are longer: update the count and the bytes, or add a photo to a list. For those you need a lock. Page 2.4.2 builds one from compare-and-swap, shows why spinning wastes the CPU, and explains how the kernel puts a waiting thread to sleep.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet