Memory Hierarchy Lab — Storage → RAM → Cache → CPU

Step 1 · demand paging

Open an app

Pick up to 4 apps. If the next one does not fit, the OS reclaims page frames from a resident process and hands them to the new allocation. Simulation model: these MB values are a simplified working-set footprint, not the real memory usage of these applications. Install size ≠ virtual size ≠ resident set ≠ working set.

0 of 4 selected · 0 MB

Physical memory · LRU ordered

What's resident in RAM

Oldest → newest. The first card is the next eviction victim.

Next step

What would you like to do?

Step 3 · execution

Which app should the CPU execute?

A thread only makes progress while the pages it touches are resident — the core executes through the memory subsystem, not by reading the drive as if it were memory. Pick a process and one of its threads is scheduled onto core 2.

Concept · diagrams · examples

How memory really works

The one-line idea

Fast memory is expensive and small. Big memory is cheap and slow. So a computer does not pick one — it stacks them, keeps the data you are using now at the top, and pushes what you have stopped using downward.

Everyday version. Your hands hold 2 things (registers). Your desk holds 20 (cache). Your bookshelf holds 500 (RAM). The library across town holds a million (SSD). You do not read in the library — you fetch a book home first. That fetch is exactly what loading an app into RAM is.

Diagram 1 — the ladder, drawn to scale

Bar length is latency. Each rung down is roughly 3–4× slower, except the last one, which is a cliff: going to the SSD costs about a thousand DRAM accesses.

Diagram 2 — cache-line granularity: why one miss buys many cheap hits

This is why looping over an array in order is fast and hopping around it is slow, even though both run the same number of instructions.

Diagram 2b — the request goes outward, the fill comes back inward

Most accesses never leave L1. The DRAM → L3 → L2 → L1 movement animated in this lab is the fill path taken after a miss, not the route every instruction travels.

L1, L2 and L3 in depth

Three levels exist because one level cannot be big and fast and affordable. SRAM is roughly six transistors per bit and needs no refresh, so it is fast but expensive per byte and hungry for area. DRAM is one transistor and one capacitor, so it is cheap and dense but must be refreshed and takes far longer to reach. The hierarchy buys you the speed of the small one and the capacity of the big one, provided your program has locality.

	L1d	L2	L3
Typical size	32–48 KB per core	1–2 MB per core	2–4 MB per core, shared
Latency	~4 cycles	~14 cycles	~40–60 cycles
Associativity	8–12 way	8–16 way	12–16 way
Shared with	nobody	nobody	every core
Indexed by	often virtual index, physical tag	physical	physical, address-hashed across slices
Main job	keep the pipeline fed	catch L1's misses cheaply	catch L2's misses, and be the coherence point

Why L1 is split into L1I and L1D

Every cycle a core may fetch instructions and perform loads or stores. One shared cache would need enough ports to serve both and would let a streaming data loop evict the loop's own instructions. Splitting them gives each its own ports and its own footprint. From L2 outward they merge — by then the traffic is rare enough that one unified array is cheaper than two.

How a lookup actually works

Nothing is ever "searched". The index is wired directly to one set; only the tags inside that set are compared, and they are compared simultaneously. This is why cache lookup costs a handful of cycles rather than a scan.

Worked example — the same loop, two orders

A 2048 × 2048 matrix of 4-byte ints is 16 MB, so it fits in L3 but nowhere smaller. Sum it two ways:

Row-major for i: for j: sum += a[i][j]
Consecutive j are adjacent in memory. One miss pulls a 64 B line holding 16 ints, so 15 of every 16 accesses are L1 hits.
→ about 4.2 M misses over 4.2 M lines · roughly 1.6 accesses' worth of stall per 16 elements.

Column-major for j: for i: sum += a[i][j]
Consecutive i are 8 KB apart. Every access lands on a new line, and by the time the loop wraps back that line is long gone.
→ about 4.2 M misses over every single access · typically 8–20× slower for identical arithmetic.

Same instruction count, same result, same compiler. The only difference is whether the access pattern matches the way memory is delivered.

The hardware always fetches 64 bytes. The only question is whether your loop uses the other 60.

L3 also keeps the cores honest

Beyond catching L2 misses, the shared L3 is where cache coherence is arbitrated. Each line carries a state — typically some variant of Modified, Exclusive, Shared, Invalid — and the interconnect uses it to guarantee that two cores never disagree about the same address. Two practical consequences:

Sharing is cheap when read-only. Many cores can hold the same line in Shared state at once.
False sharing is expensive. Two threads writing to different variables that happen to sit in the same 64 B line will bounce that line between cores on every write. The fix is padding, not locking — the data was never actually shared, only the line was.

Rules of thumb this buys you

Walk memory in the order it is laid out. Sequential beats clever almost every time.
Prefer arrays of values over arrays of pointers — pointer chasing defeats the prefetcher.
Shrink hot structures so more of them fit per line; move cold fields out.
Tile or block big loops so a working chunk stays in L1/L2 across its reuse.
Pad per-thread counters to a full line to avoid false sharing.
Measure with hardware counters — perf stat -e cache-misses,L1-dcache-load-misses — rather than guessing.

Diagram 3 — reclamation, step by step

Nothing here evicts "an application". Two of YouTube's frames were selected, one written to swap and one dropped, and those two frames became Firefox's. YouTube stays runnable and faults C and D back in only if it touches those addresses again.

Diagram 4 — address translation: TLB, page table, frames and faults

Every process sees a private address space. The page table holds virtual→physical mappings plus status and protection bits (present, dirty, accessed, read/write, user/supervisor); the MMU consults it during translation, and the TLB caches the results so most translations never touch it.

Not every page fault touches storage

The lab's Page fault · disk button shows the disk-backed case, but a fault simply means "this mapping was not usable right now". Common causes:

Kind	What the OS does	Storage I/O?
Demand-zero	first touch of new anonymous memory — hand over a zeroed frame	no
Copy-on-write	write to a shared frame after fork — copy it, remap	no
Minor / soft	page is already in RAM (page cache, standby list) — just fix the mapping	no
File-backed (major)	read the page from an executable, library or mapped file	yes
Reclaimed / swapped	read the frame's contents back from the swap area	yes
Protection fault	write to a read-only page — signal, or an OS-managed remap	no

Only the storage-backed faults in this model cost the ~80 µs this lab animates: file-backed major faults and reclaimed / swapped pages. Minor, demand-zero, copy-on-write and protection faults need no storage read at all — they are thousands of times cheaper, and on a healthy system they vastly outnumber the major ones.

Numbers worth memorising

Level	Typical size	Latency	Unit of transfer
Registers	~1–2 KB / core	0 cycles	4–8 bytes
L1d cache	48 KB / core	4 cyc · 1 ns	64 B line
L2 cache	2 MB / core	14 cyc · 4 ns	64 B line
L3 shared	32 MB	~50 cyc · 14 ns	64 B line
DRAM	8–64 GB	~300 cyc · 85 ns	64 B burst / 4 KB page
NVMe SSD	0.5–4 TB	~80 µs	4 KB page

If one CPU cycle were one second, an L1 hit would take 4 seconds, a DRAM read about 5 minutes, and an SSD read about 3 days.

Reclamation happens per frame, not per application

It is tempting to picture the OS "swapping out Firefox". It does not work that way — the unit of reclamation is the page frame:

This lab reclaims frames from one victim process at a time so the movement stays legible, and it shows the victim shrinking rather than vanishing. The LRU / FIFO switch is a classroom model of page replacement, not a description of any shipping kernel.

Things people usually get wrong

“Cache is a chip on the motherboard.” No — L1, L2 and L3 are all on the CPU die. Lift the heat spreader in the lab and look.
“More RAM makes the CPU faster.” It does not raise the clock. It removes swapping, which is why a RAM-starved machine feels slow while the CPU sits mostly idle.
“The CPU reads files from the SSD.” The core does not execute instructions out of NVMe as if it were main memory — code and data must be mapped and resident first. The CPU can reach devices, through memory-mapped I/O registers and driver code, but that is the OS and driver path that sets up a DMA transfer, not ordinary instruction fetch.
“Every access walks RAM → L3 → L2 → L1.” A request starts at L1 and only moves outward on a miss. The inward L3 → L2 → L1 movement here is the return path of a miss — and even that depends on the fill policy, since inclusive, exclusive and non-inclusive hierarchies all ship.
“An application gets swapped out.” The OS reclaims individual frames; a process normally stays runnable with a smaller resident set.
“An app uses as much RAM as its install size.” Demand paging means only the pages actually touched are resident — usually a fraction of the file on disk.
“Closing a tab frees RAM instantly.” The OS often keeps the pages around on a standby list in case you come back, and reclaims them only under pressure.

Where this simulation simplifies reality

All deliberate teaching simplifications — worth knowing before quoting any of it in an exam answer.

App sizes are a simplified working-set footprint, not measured usage of YouTube, Netflix or anything else. Install size ≠ virtual size ≠ resident set ≠ working set.
Latency figures are illustrative values for a representative desktop CPU at ~3.5 GHz. The ratios are the lesson; real parts vary.
Replacement policy is exact LRU or FIFO, chosen for clarity. Production kernels only approximate LRU.
Reclamation is animated one victim process at a time so it stays readable; real reclaim scans frames system-wide.
Dirty vs clean is randomised per reclamation here, purely so both outcomes are visible. A real system keeps a dirty bit per page in the page-table entry, set by hardware on the first write.
File-backed vs anonymous matters for the cost: an unmodified file-backed page can be dropped because the file still holds it, but an anonymous page (heap, stack, COW copies) has no file behind it and must be written to swap once it has been touched.
Cache fill is drawn as L3 → L2 → L1 on every miss return; actual placement depends on the inclusion policy.
The die floorplan is representative, not a photograph of a shipping processor.
TLB and page-table walks are described but not animated block by block; multi-level tables and page-walk caches are omitted.
NUMA, prefetchers, store buffers, memory ordering and huge pages are out of scope.

Try this in the lab

Set RAM to 1 GB, select 4 apps, and load them. Count how many swap events you trigger.
Set RAM to 8 GB and load the same 4. No swapping — that single change is what "buy more RAM" actually buys you.
Press L1 hit then DRAM fetch back to back and watch the total stall counter. That gap is the entire reason cache exists.
Load an app, swap it out, then open it again and watch every page come back from the SSD.