Memory: the hierarchy and virtual memory
A value in L1 cache arrives in about a nanosecond; from an SSD, roughly a hundred thousand times slower. Climb the memory hierarchy in 3D, then see how virtual memory gives every process its own private address space.
In this lecture you will
- Describe the levels of the memory hierarchy and their relative speeds and sizes
- Explain why caches work, using the idea of locality
- Explain how virtual addresses are translated to physical addresses with page tables and a TLB
- Describe page faults and what happens when memory runs short
To a programmer, memory looks like one long array of bytes, all equally fast. In reality, a computer’s storage is a stack of very different technologies, and the fastest is thousands of times smaller than the slowest. The operating system and hardware work together to hide this — and understanding how they do it explains a huge range of performance behaviour.
The memory hierarchy
Each level is faster, smaller and more expensive per byte than the one below it. Pick a level to see a request travel from the CPU core down to the data and back. Then switch to the human time scale — if one nanosecond lasted one second — and the gaps become visceral.
Sizes and latencies are typical orders of magnitude for current servers and laptops; exact values vary by hardware.
At human scale, an L1 hit takes a second, a trip to RAM about a minute and a half, an SSD read most of a day and a hard-disk seek around three months. No wonder CPUs spend so much effort avoiding the lower levels.
Why caches work: locality
Caches can be small because programs are predictable in two ways:
- Temporal locality
- Data used recently is likely to be used again soon — a loop counter, a hot function, a popular database row.
- Spatial locality
- Data near recently used data is likely to be used soon — the next element of an array, the next instruction.
- Cache line
- Caches move memory in blocks, typically 64 bytes. Reading one byte brings its neighbours along for free.
This is why data layout matters. Walking through an array touches consecutive bytes and uses every byte of each cache line. Chasing pointers through a linked list or a tree scattered across memory can miss the cache on almost every step — same algorithm on paper, several times slower in practice.
Walk the same matrix two ways through a tiny cache and count the misses:
Rows are stored one after another, so a row is one cache line here. Row by row, each miss brings in seven more numbers for free; column by column, every access needs a different line. Measured on a laptop, summing a 4096 × 4096 matrix of doubles took about 30 ms row by row and about 440 ms column by column — the same arithmetic, over ten times slower.
Virtual memory: a private address space
In lecture 2, every process had its own address space starting at the same addresses. Physical RAM, of course, is shared. Virtual memory bridges the two. Memory is divided into fixed-size pages (typically 4 KB), and the hardware’s memory management unit translates each virtual page to a physical frame using the process’s page table, which the OS maintains.
Step through one translation:
- A virtual addressThe program touches address 0x00403A7C. With 4 KB pages, the low 12 bits (0xA7C) are the offset within the page, and the rest (0x00403) is the virtual page number.
- Check the TLBThe CPU first checks the translation lookaside buffer — a tiny cache of recent translations. This time it misses.
- Walk the page tableThe hardware looks up page 0x00403 in the process’s page table: present, readable and writable, stored in physical frame 0x1F2.
- Build the physical addressThe physical address is the frame number followed by the unchanged offset: 0x001F2A7C. The translation is saved in the TLB.
- TLB hit next timeThe next access to the same page hits the TLB and is translated almost instantly. Thanks to locality, the great majority of accesses hit.
- Page faultPage 0x00500 isn’t in RAM. The CPU traps to the kernel, which finds a free frame, loads the page from disk (or zero-fills a new one), updates the page table and retries the instruction.
What virtual memory makes possible
- Isolation. A process can only reach frames mapped in its own page table. Another process’s memory simply has no address.
- Protection. Page permissions stop code from being overwritten and data from being executed — an important defence against attacks.
- Laziness. Pages are loaded only when first touched, so programs start fast and unused parts never occupy RAM.
- Sharing. Libraries used by many processes can map to the same physical frames, saving memory.
- More than RAM. Rarely used pages can be moved to disk (swap), letting the total memory in use exceed physical RAM — at a cost.
When RAM is full and a new page is needed, the kernel must choose a page to evict. Compare three classic policies on the same sequence of page accesses:
OPT needs to know the future, so no real system can run it; it shows how good a policy could possibly be. LRU comes close by assuming the recent past predicts the near future. Real kernels use cheaper approximations of LRU. In Belady’s example, FIFO gets worse with more memory.
That completes the first module: the kernel, processes, scheduling, concurrency and memory — the machinery underneath every program you write. Module 2 continues with paging policies, file systems, I/O and deadlocks.
Key takeaways
- Storage gets larger, cheaper and slower at every level down from registers to disks — by many orders of magnitude.
- Caches work because programs reuse recent data and access nearby data — temporal and spatial locality.
- Virtual memory maps each process’s pages to physical frames through page tables; the TLB caches recent translations.
- A page fault lets the OS load pages lazily; heavy paging to disk (thrashing) makes a system crawl.
Check your understanding
3 questions · answers explainedQ1Why is iterating over an array element by element usually much faster than following a linked list of the same size?
Q2What does the TLB do?
Q3A server with too little RAM starts spending most of its time moving pages to and from disk. What is this called, and what helps?