COMP 3150Operating Systems

Module 3 · Unit 8 · Lesson 1 of 6

The Memory Hierarchy

Memory is not one thing. It is a stack of storage levels — registers, cache, main memory, and disk — ranging from tiny, fast, and expensive at the top to huge, slow, and cheap at the bottom. Every level caches the level below it, and the whole structure works because programs exhibit locality of reference. This lesson establishes the physical reality that the operating system's memory management policies exist to exploit.

01 Introduction

Module 2 was about processes and concurrency. The central resource was the CPU — how it is shared among processes, how threads within a process cooperate, and how they can deadlock. This unit turns to a different resource: memory. Memory is the storage that holds a program's code and data while it runs, and its management is the second of the classical concerns of operating-system design, alongside process management.

Before we can discuss how the operating system allocates and protects memory, we need to understand the hardware it is managing. That is the subject of this lesson. Memory is not a single homogeneous resource; it is a hierarchy of storage levels, each with a different capacity, latency, and cost. At the top are the registers, holding a few hundred bytes and accessible in a fraction of a nanosecond. At the bottom are magnetic disks and tapes, holding terabytes and accessible in milliseconds — a difference of seven orders of magnitude in time and ten orders of magnitude in capacity.

The hierarchy exists because no single memory technology can be fast and large and cheap. Fast memory — the kind implemented with the same semiconductor processes as the CPU — is expensive per byte and cannot be made large without dominating the cost of the machine. Large memory — the kind implemented with magnetic or flash storage — is cheap per byte but slow. The hierarchy resolves the tension by using a small amount of fast memory to cache the working set of a much larger, slower memory. If the caching works — if the fast memory usually contains what the CPU wants next — then the system behaves as though it had memory as fast as the top of the hierarchy and as large as the bottom.

The mechanism that makes the hierarchy work is locality of reference: the empirical observation that programs tend to access a small subset of their memory repeatedly, and to access memory locations near ones they have recently accessed. Locality is not a law of nature; it is a property of the programs people write, and it is the property that the entire memory system — from the CPU's cache to the operating system's page replacement — is designed to exploit.

This lesson has three purposes. First, it presents the levels of the hierarchy and the trade-offs between them, so that the rest of the unit has a concrete physical basis. Second, it introduces locality of reference and shows how it makes the hierarchy effective. Third, it defines the operating system's role in memory management — what the OS is responsible for, and what is handled by the hardware — as a framework for the five lessons that follow.

Prerequisites

This lesson opens Module 3, so it has no prerequisites within the memory unit itself. It builds on the computer-organization material from the course's prerequisite (address spaces, the fetch–decode–execute cycle, the role of the program counter and registers) and on the process model from Unit 3 (a process has code, data, heap, and stack segments in its address space). Familiarity with the process address space from Lesson 3.1 is particularly helpful, since the memory unit will explain how that address space is realised in hardware.

02 Learning objectives

By the end of this lesson you will be able to

  • Describe the levels of the memory hierarchy and the trade-offs between capacity, latency, and cost at each level.
  • Explain locality of reference and distinguish its temporal and spatial forms.
  • Explain why the memory hierarchy works and what would happen without locality.
  • Describe the memory wall and its consequences for system design.
  • Identify the operating system's responsibilities in memory management and distinguish them from the hardware's responsibilities.

This lesson contributes to U8.1, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

  • Operating System Concepts — Chapter 9, Section 9.1, Background. The textbook's introduction to memory management, including the distinction between the memory the CPU can address directly and the storage the operating system manages, and the notions of base and limit registers that begin the discussion of protection.
  • Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.1, No Memory Abstraction, and Section 3.2, A Memory Abstraction: Address Spaces. A complementary treatment that develops the motivation for memory management from first principles.
  • OSTEP — Chapter 13, Address Spaces, and Chapter 14, Interlude: Memory API. OSTEP's treatment connects the address-space abstraction to the C programmer's view of memory, which is the level at which most of this unit's material will be applied.
  • Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, Chapter 6, The Memory Hierarchy. The definitive treatment of the memory hierarchy from the programmer's perspective. Read sections 6.1 and 6.2 for the storage technologies, and section 6.3 for locality.
  • Hennessy, J. L., & Patterson, D. A. — Computer Architecture: A Quantitative Approach, Chapter 2, Memory Hierarchy Design. The architectural view: how caches are designed and why. Read the introduction and the section on cache performance for the quantitative framework used in this lesson.
  • Linux man pages: man 1 lscpu, man 1 lstopo, man 1 perf-stat, man 3 getpagesize, man 2 mmap, man 5 proc (the /proc/meminfo interface).

Reading strategy

Read the Bryant & O'Hallaron chapter first. It is the clearest available treatment of the memory hierarchy from the perspective of someone who wants to write fast programs, and its explanation of locality and the cache-oriented programming model is exactly what this lesson needs. Then read the Silberschatz background section for the operating-system perspective — which is a different perspective, concerned with allocation and protection rather than with performance. The two views are complementary: the hardware's job is to make memory access fast, and the operating system's job is to make it correct and safe.

04 Core content

4.1 Memory as a resource

In Unit 3, a process was defined as a program in execution, with an address space containing the program's code, its global and static data, its heap, and its stack. That address space is a software abstraction: the operating system and the hardware cooperate to present it to the process, and the process treats it as a private, contiguous region of memory. But the underlying physical reality is very different. The address space is backed by a combination of storage devices with wildly different characteristics, and the operating system's job is to make the abstraction work.

The first thing to understand is that memory is not one thing. A modern computer contains several distinct kinds of storage, organised in a hierarchy, and each kind exists because it makes a different trade-off between three competing objectives:

  • Capacity. How much data can be stored? A program's working set — the data it is currently using — must fit in the fastest level that is large enough to hold it.
  • Latency. How long does it take to retrieve a piece of data? Latency is measured in nanoseconds for the top of the hierarchy and in milliseconds for the bottom.
  • Cost. How much does a byte of storage cost? Cost per byte spans an enormous range, from dollars per byte for registers to fractions of a cent per byte for disk.

The three objectives conflict. Fast memory is expensive: the semiconductor processes that make memory fast (large transistor budgets, complex sense amplifiers, wide buses) also make it costly per byte. Large memory is slow: the technologies that store data densely (magnetic media, flash cells with multiple bits per cell) have long access times. Cheap memory is both slow and limited in a different sense: it can store a lot, but it cannot deliver data quickly.

There is no memory technology that is simultaneously fast, large, and cheap. The hierarchy is the standard resolution of the conflict: instead of trying to build one memory that is all three, the system is built from several memories, each of which is good at one or two of the three, and the system moves data between them as needed.

4.2 The levels of the hierarchy

A modern system has five or six levels of memory, from the registers inside the CPU to the magnetic disks and tapes at the bottom. The following figure presents them with approximate figures for a typical 2025-era machine.

The memory hierarchy A diagram of the memory hierarchy as a series of stacked levels, from the top with tiny fast registers to the bottom with large slow tape storage. Each level shows the technology, the typical capacity, the typical access time, and what manages that level. The top levels are smaller and faster and more expensive; the bottom levels are larger and slower and cheaper. Arrows on the right show the direction of increasing capacity and latency, and arrows on the left show the direction of increasing cost per bit. THE MEMORY HIERARCHY faster · smaller · costlier slower · larger · cheaper LEVEL TYPICAL CAPACITY TYPICAL LATENCY MANAGED BY Registers CPU internal ~1 KB 0.2 – 0.5 ns Compiler L1 cache per core, on-chip 32 – 64 KB ~1 ns (4 cycles) Hardware L2 cache per core, on-chip 256 KB – 1 MB ~4 ns (15 cycles) Hardware L3 cache shared across cores 8 – 64 MB ~15 ns (50 cycles) Hardware Main memory DRAM, off-chip 8 – 512 GB ~80 ns (250 cycles) OS + hardware SSD / flash NVMe, non-volatile 256 GB – 8 TB ~100 µs (10⁵ cycles) OS (file system) Magnetic disk spinning platters 1 – 20 TB ~10 ms (10⁷ cycles) OS (file system) The gap across the hierarchy From a register access (~0.3 ns) to a disk seek (~10 ms) is a factor of about 30 million. Each level caches the level below it. The top three levels (cache) are transparent to software — managed entirely by the hardware. Main memory and below are managed by the operating system, which is where the policies of this unit apply.
Figure 8.1 — The memory hierarchy. Each level is smaller, faster, and more expensive per byte than the level below it. The top three levels — registers and the caches — are managed entirely by the hardware and are transparent to software. The bottom four levels are managed by the operating system, and the policies that govern them are the subject of this unit. The latency figures are for a typical 2025-era x86-64 machine.

Each level in the hierarchy has the same structure. It is a small, fast memory that holds a copy of the most recently or most frequently used data from the level below. When the CPU (or the operating system) wants a piece of data, it looks first in the fastest level, then the next, and so on down the hierarchy until the data is found. If the data is found in a level — a hit — the request is served from that level. If it is not found — a miss — the request is passed to the level below, and when the data is eventually retrieved, it is copied into the levels above so that subsequent accesses will hit.

The hit rate — the fraction of accesses that are served by a given level — is the single most important quantity in the performance of the hierarchy. A level with a 95% hit rate and 1 ns latency, backed by a level with 100 ns latency, has an average access time of 0.95 × 1 + 0.05 × 100 = 5.95 ns — dramatically better than the 100 ns of the lower level alone. This is why the hierarchy works: a small amount of fast memory, used well, can serve the vast majority of requests, and the slow level below is accessed only occasionally.

4.3 Locality of reference

The hierarchy works only if the fast levels usually contain what the CPU wants next. That this is true is not a coincidence; it is a consequence of a property of programs called locality of reference.

Locality of reference is the empirical observation that a program's memory accesses tend to cluster: at any moment, the program is actively using a small fraction of its address space, and the accesses it makes tend to be near each other in space and time. Locality comes in two forms.

Temporal locality
If a program accesses a memory location, it is likely to access that same location again soon. The classic example is a loop: the loop counter, the loop bound, and the loop body are all accessed repeatedly for the duration of the loop. A variable that is incremented in a loop is accessed on every iteration, so after the first access, it stays in the fastest memory level for the whole loop.
Spatial locality
If a program accesses a memory location, it is likely to access nearby locations soon. The classic example is array traversal: accessing a[0] is usually followed by accessing a[1], a[2], and so on. Because memory is organised in blocks and caches fetch whole blocks rather than individual bytes, an access to one element of an array brings the neighbouring elements into the cache as well, so the subsequent accesses hit.

Locality is what makes both caching and paging effective. A cache line of 64 bytes, loaded into L1 on a miss, contains not only the requested byte but the next 63 bytes; if the program's accesses are spatially local, those bytes will be requested soon, and each will be a hit. Similarly, a page of four kilobytes, loaded into memory on a page fault, contains the entire region the program is working in; if the program is temporally local, the page will be accessed repeatedly before it is evicted, and the cost of the fault will be amortised over many accesses.

Programs that violate locality perform poorly on every level of the hierarchy. A program that accesses memory randomly across a large region will miss in every cache level and fault on every page. This is why the performance of a program is often dominated not by its instruction count but by its memory access pattern — a phenomenon that every programmer discovers when a change of loop order, with no change to the algorithm, produces a tenfold speedup. The worked example in this lesson will demonstrate this concretely.

4.4 The memory wall

For most of computing history, CPU speed and memory speed improved together. From the 1970s through the early 1990s, processor clock rates and memory access times both improved by roughly 40 to 60 percent per year, and the ratio between them stayed roughly constant. Around 1995, the two curves diverged: processor performance continued to improve at its historical rate, driven by deeper pipelines and higher clock frequencies, while memory latency improved much more slowly, because it is bounded by physical limits (the speed of light, the time to charge a DRAM cell's capacitance) that do not scale with process technology the way transistor switching does.

The result is a growing gap between the time a CPU takes to execute an instruction and the time it takes to fetch a datum from main memory. The gap is called the memory wall or the von Neumann bottleneck. In 1980, a memory access might cost a few CPU cycles; in 2025, it costs two hundred to three hundred cycles. If the CPU had to wait for every memory access, it would spend the overwhelming majority of its time idle.

The caches exist to hide this latency. A program that fits in L1 runs at the CPU's full speed; a program that fits in L2 runs at a modest slowdown; a program that fits in L3 is noticeably slower; a program whose working set exceeds main memory and spills to disk runs orders of magnitude slower. This is why the memory hierarchy is not merely an implementation detail: it is the central determinant of performance on modern hardware, and it is the reason the operating system's memory management policies matter so much.

The memory wall: the growing gap between processor and memory performance A graph showing the growth of processor performance and memory latency from 1980 to 2025 on a logarithmic scale. Processor performance grows steeply throughout the period, from 1 in 1980 to about 10000 by 2025. Memory latency grows much more slowly, from 1 in 1980 to about 30 by 2025. The widening gap between the two curves is the memory wall. After 2005, the processor curve flattens as clock-frequency scaling ends, but the gap remains wide. THE MEMORY WALL year performance ratio (log scale, 1980 = 1) 1980 1988 1996 2004 2012 2020 2025 1 10 100 1,000 10,000 Processor performance (~10,000× since 1980) Memory latency (relative) (~30× since 1980) The memory wall: a memory access costs hundreds of CPU cycles After 2005, clock-frequency scaling slows and processors gain performance through parallelism instead — but the latency gap remains.
Figure 8.1b — The memory wall. Processor performance has grown by about four orders of magnitude since 1980, while memory latency has grown by only about one and a half. The widening gap is the memory wall: a main-memory access that cost a few CPU cycles in 1980 now costs a few hundred. The caches exist to hide this latency, which is why their effectiveness — and therefore the program's locality — is the dominant factor in performance on modern hardware.

4.5 What is cached, and by whom

The hierarchy is built on the principle that each level caches the level below it. But the levels differ in what they cache, how the caching is managed, and who is responsible for the policy.

What each level caches and who manages it
Level Caches Unit of transfer Managed by Transparent to software?
Registers Recently used values from L1 Word Compiler No — the compiler decides what lives in registers
L1 / L2 / L3 cache Recently used blocks of main memory Cache line (64 bytes) Hardware (cache controller) Yes — software is unaware of the cache
Main memory Recently used pages of the address space Page (4 KB typical) Operating system No — the OS controls what is resident
SSD / disk All files and the swap area Block (4 KB typical) Operating system (file system + VM) No — the OS controls file and swap layout

The division of responsibility is what makes the hierarchy interesting from the operating-system perspective. The cache levels are managed entirely by the hardware: the cache controller decides what to keep, what to evict, and when to fetch, and the software is (with a few exceptions, such as cache-prefetch instructions) unaware that the cache exists. The lower levels are managed by the operating system: the kernel decides which pages are resident in main memory, which are written to swap, and where in the disk a file's blocks are placed.

This is the origin of the two central problems of this unit. The allocation problem — how should the operating system divide main memory among the processes that need it? — is the subject of Lessons 8.2 through 8.6. The residency problem — which pages should be in memory at any given moment, and which should be on disk? — is the subject of Unit 9. Both are applications of the same principle: use a small, fast resource to cache a large, slow one, and exploit locality to make the cache effective.

4.6 The operating system's role

The operating system has three responsibilities in memory management. They are worth stating explicitly, because they frame the rest of the unit.

Allocation
The operating system decides which processes get which parts of memory, and how much memory each process gets. When a process is created, the operating system must arrange for its code, data, heap, and stack to have space in the address space; when the process requests more memory (via malloc or brk or mmap), the operating system must find space for it. Allocation is the classical concern of memory management, and Lessons 8.4 and 8.5 are about the algorithms that implement it.
Protection
The operating system must ensure that one process cannot read or write another process's memory. In a multi-programmed system, several processes share the physical memory, and a bug or a malicious program in one process must not be able to corrupt another. The protection mechanisms — base and limit registers, segmentation, paging, and the memory-management unit — are the subject of the rest of this unit and of Unit 9.
Transparency
The operating system must present the physical memory as the clean abstraction that the programmer expects. A process should see a private, contiguous address space with a stack that grows down, a heap that grows up, and no visible interference from other processes. The mechanisms that realise this abstraction — address translation, virtual memory, demand paging — are what allow a program written for one machine to run unchanged on another with a different physical memory layout, and what allow a system to run a program larger than its physical memory.

These three responsibilities are the backbone of the memory-management unit. Allocation is about dividing the resource; protection is about keeping the divisions meaningful; transparency is about making the divisions invisible to the code being run. Every mechanism in the next five lessons — address binding, dynamic loading, contiguous allocation, fragmentation, segmentation, and paging — is an instance of one or more of these.

4.7 Why the operating system manages memory at all

It is worth pausing to ask why the operating system is involved in memory at all. In a single-tasking system with no protection requirements, a program could be given the whole machine: it would load at a fixed address, use memory freely, and there would be no need for an operating system to intervene. The involvement of the operating system arises from three requirements that such a system cannot satisfy.

  • Multiprogramming. Several processes must share the physical memory at the same time, because the CPU would otherwise be idle whenever one process blocks on I/O. Sharing requires allocation — deciding how much memory each process gets — and protection — ensuring that they do not interfere.
  • Isolation. A process must not be able to read or write another process's memory, whether by accident or by intent. Isolation requires the hardware to check every memory access against a description of the address space, and it requires the operating system to establish and maintain that description.
  • Overcommitment. The total memory demanded by the processes in the system is often larger than the physical memory available. The operating system must be able to run more processes than fit, by keeping some of their pages on disk and bringing them in on demand. This is virtual memory, and it is the subject of Unit 9.

The combination of these requirements is what makes memory management the deep problem it is. A system that could satisfy only one of them would be much simpler — a system with no multiprogramming needs no sharing policy, a system with no isolation needs no protection, a system with no overcommitment needs no demand paging. It is the combination that produces the base-and-limit registers, the segment tables, the page tables, and the translation lookaside buffers, all of which exist to satisfy all three requirements at once.

4.8 Common misconceptions

"Memory is one thing."

Memory is a hierarchy of five or six distinct storage technologies, spanning seven orders of magnitude in latency and ten in capacity. Treating it as one thing is a useful abstraction, but it is not the physical reality that the operating system manages.

"Caches are managed by the operating system."

The L1, L2, and L3 caches are managed entirely by the hardware. The operating system is unaware of them and cannot control their policy. The OS manages main memory and below.

"Locality is guaranteed by the hardware."

Locality is a property of programs, not of hardware. The hardware and the operating system are built to exploit locality, but a program that does not have locality performs poorly on every level of the hierarchy.

"A bigger cache is always better."

A larger cache has longer access times and higher cost. The hierarchy is a balancing act: the right size for a cache depends on the workload and on the cost budget. Multiple levels exist precisely because no single size is right for all cases.

"The memory wall is a solved problem."

The caches hide the latency for programs with locality, but for programs without locality the wall remains. The gap between CPU speed and memory latency has driven decades of architectural innovation and is still a central constraint.

"Virtual memory is the same as physical memory."

Virtual memory is an abstraction: the address space that a process sees is not the physical memory of the machine. The mapping between them is what allows protection, sharing, and overcommitment, and it is the central mechanism of Unit 9.

"The operating system decides what is in the cache."

The operating system decides what is in main memory (which pages are resident). The cache controller decides what is in the cache. The two decisions are made independently, at different levels of the hierarchy.

"Memory performance is a hardware problem."

Memory performance is a joint problem. The hardware provides the hierarchy and the translation mechanisms; the operating system provides the allocation and residency policies; the programmer provides the access pattern. All three matter.

05 Worked example

The following example computes the effective access time of a two-level hierarchy for several hit rates, and then demonstrates the effect of locality on a concrete program.

Effective access time of a two-level hierarchy

Suppose a system has a fast memory with latency t_fast = 1 ns and a slow memory with latency t_slow = 100 ns. The fast memory has a hit rate h. When a request misses in the fast memory, the data must be fetched from the slow memory, and the cost of the miss includes both the slow access and the subsequent placement of the data into the fast memory.

The effective access time (EAT) is: 

EAT = h × t_fast + (1 − h) × (t_fast + t_slow)

The first term is the case where the data is found in the fast memory: the cost is one fast access. The second term is the case where the data is not found: the cost is one fast access (which missed) plus one slow access (which fetched the data), and — in the simplest model — the data is placed in the fast memory so that a subsequent access will hit.

The table below computes the EAT for a range of hit rates.

Hit rate h EAT (ns) Speedup vs. slow memory alone Slow accesses per 1000 requests
0.00101.00.99×1000
0.5051.01.96×500
0.8021.04.76×200
0.9011.09.09×100
0.956.016.7×50
0.992.050.0×10
1.001.0100×0

The pattern is instructive. At a 90 percent hit rate, the hierarchy is nine times faster than the slow memory alone. At 99 percent, it is fifty times faster. The difference between 90 percent and 99 percent is a factor of more than five in performance, even though both hit rates are "high". This is why a cache that is slightly too small for the working set can be catastrophically slower than one that is just large enough: the hit rate drops from 99 percent to 90 percent, and the performance drops by a factor of five.

Extending to three levels. A real system has more than two levels. With L1 (1 ns, hit rate h₁), L2 (5 ns, hit rate h₂ conditional on an L1 miss), and main memory (100 ns), the effective access time is: 

EAT = t_L1
    + (1 − h₁) × t_L2
    + (1 − h₁) × (1 − h₂) × t_mem

For h₁ = 0.95 and h₂ = 0.90: 

EAT = 1 + 0.05 × 5 + 0.05 × 0.10 × 100
    = 1 + 0.25 + 0.5
    = 1.75 ns

The result is 1.75 ns, close to the L1 latency of 1 ns, even though the main memory latency is 100 ns. The multi-level hierarchy does its job: the vast majority of accesses are served by the fast levels, and the slow levels are touched only occasionally.

Locality in a concrete program

Consider two versions of a program that sums a 2048 × 2048 matrix of int values. Version A traverses the matrix row by row; version B traverses it column by column. 

/* Version A: row-major traversal */
long sum = 0;
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

/* Version B: column-major traversal */
long sum = 0;
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

Both versions perform the same number of additions — 4,194,304 — and both produce the same sum. But their performance differs dramatically, because C stores two-dimensional arrays in row-major order: the elements of a row are adjacent in memory, and the elements of a column are 8,192 bytes apart (2048 ints × 4 bytes each).

Version A accesses memory sequentially: a[0][0], a[0][1], a[0][2], and so on. Each cache line of 64 bytes contains 16 ints, so one cache miss brings in the next 15 elements, which the loop will use immediately. The result is one miss every 16 accesses — a 93.75 percent hit rate.

Version B accesses memory with a stride of 8,192 bytes: a[0][0], a[1][0], a[2][0], and so on. Each access is in a different cache line, and because the working set (the entire matrix, 16 MB) far exceeds the cache, each access evicts a line that will not be used again until the next column iteration. The result is a miss on essentially every access — a hit rate near zero.

Version Access pattern Cache hit rate (L1) Relative time
Row-major (A)Sequential~94%1.0×
Column-major (B)Stride 8 KB~3%8–15×

The numbers vary with the machine and the compiler, but the direction is universal: the version with good spatial locality is dramatically faster. The lesson is that algorithm analysis in terms of operation counts is incomplete. Both versions perform 4 million additions, but one takes eight to fifteen times as long. The difference is entirely in the memory access pattern, and it is a consequence of the memory hierarchy.

This is why the memory hierarchy matters for the operating system as well as for the programmer. The operating system's memory management policies determine how much of a process's working set fits in memory, how often the process faults, and how much of the memory hierarchy is available to it. A policy that fragments memory or evicts pages poorly is a policy that pushes the program's working set down the hierarchy, where every access costs orders of magnitude more.

06 Interactive activity

Activity · measure the memory hierarchy on your machine

The goal of this activity is to observe the memory hierarchy directly — its shape, its latencies, and the effect of locality on performance. Work through the steps in your course VM.

  1. Inspect the hierarchy. Use lscpu to see the cache sizes on your machine, and getconf to see the page size and the cache-line size. 
    lscpu | grep -i cache
getconf LEVEL1_DCACHE_SIZE
getconf LEVEL1_DCACHE_LINESIZE
getconf PAGE_SIZE
getconf LEVEL3_CACHE_SIZE
    Write down the L1, L2, and L3 sizes and the page size. These are the parameters that determine the behaviour of every program you run.
  2. Visualise the topology. If lstopo is available (from the hwloc package), use it to see the topology of the machine — which caches are per-core and which are shared, and how the cores are grouped. 
    lstopo --of console
# or, if installed, the graphical version:
lstopo
    Note which caches are private and which are shared. The sharing structure determines whether two threads on different cores contend for cache space.
  3. Measure cache latency. Write a small C program that measures the time to traverse a buffer of increasing size, and observe the points at which the latency jumps as the buffer outgrows each cache level. 
    #include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE (64 * 1024 * 1024)
#define STRIDE   64

int main(void) {
    char *buf = malloc(MAX_SIZE);
    if (!buf) return 1;

    for (size_t size = 4096; size <= MAX_SIZE; size *= 2) {
        /* touch every cache line to warm the cache */
        for (size_t i = 0; i < size; i += STRIDE)
            buf[i] = 1;

        struct timespec t0, t1;
        clock_gettime(CLOCK_MONOTONIC, &t0);
        volatile long sum = 0;
        for (int rep = 0; rep < 100; rep++)
            for (size_t i = 0; i < size; i += STRIDE)
                sum += buf[i];
        clock_gettime(CLOCK_MONOTONIC, &t1);

        double elapsed = (t1.tv_sec - t0.tv_sec)
                       + (t1.tv_nsec - t0.tv_nsec) / 1e9;
        double ns_per_access = elapsed * 1e9 / (100.0 * size / STRIDE);
        printf("size = %8zu bytes   %6.2f ns per access\n",
               size, ns_per_access);
    }
    free(buf);
    return 0;
}
    Compile with gcc -O2 -o latency latency.c and run. Plot or tabulate the results. You should see the latency stay low while the buffer fits in L1, jump when it moves into L2, jump again in L3, and rise sharply when it exceeds main memory.
  4. Demonstrate locality. Write the row-major and column-major matrix sum from the worked example. Compile both with -O2 and time them. 
    #include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 2048

static int a[N][N];

int main(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            a[i][j] = i + j;

    struct timespec t0, t1;
    long sum = 0;

    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            sum += a[i][j];
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double row = (t1.tv_sec - t0.tv_sec)
               + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("row-major:    %.3f s  (sum = %ld)\n", row, sum);

    sum = 0;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            sum += a[i][j];
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double col = (t1.tv_sec - t0.tv_sec)
               + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("column-major: %.3f s  (sum = %ld)\n", col, sum);

    printf("ratio: %.1fx\n", col / row);
    return 0;
}
    Compile with gcc -O2 -o mat mat.c and run. Note the ratio. Try compiling with -O0 and with -O3 and observe how the ratio changes.
  5. Count cache misses with perf. Use perf stat to count the cache references and misses for the two versions of the matrix program. 
    perf stat -e L1-dcache-loads,L1-dcache-load-misses \
          ./mat
    Run the program with each traversal order in turn — or split the program into two binaries and run perf stat on each — and compare the miss rates. The column-major version should show a dramatically higher miss rate.
  6. Observe the memory wall with a pointer chase. Write a program that follows a linked list whose nodes are spread across a large array, so that each access is a cache miss. Measure the time per node traversal. Compare it to a program that traverses an array sequentially. The difference is the memory wall in action. 
    /* Build a linked list in a large array, then traverse it.
   Each traversal step is a pointer dereference to an
   unpredictable location, so the cache cannot help. */
  7. Inspect the system's memory. Use /proc/meminfo to see the state of the system's memory and the page size, and /proc/self/maps to see the layout of a process's address space. The address space of a process is the abstraction the operating system builds on top of the physical hierarchy. 
    head -10 /proc/meminfo
cat /proc/self/maps | head -20
    Note that /proc/meminfo reports memory in kilobytes and that /proc/self/maps shows the segments of the address space — code, data, heap, stack, and the shared libraries — each with its own permissions.
  8. Read man 1 lscpu. Read the man page and identify all the cache-related options. Then answer: what is the difference between the L1 data cache and the L1 instruction cache? Why are they separate? What is the associativity of each cache on your machine, and what does the associativity mean?

Reflect: the memory hierarchy is invisible to the program in the sense that the program does not have to know about it to be correct — but it is highly visible in performance. A program that ignores the hierarchy and a program that respects it can differ by an order of magnitude in running time, with no difference in the algorithm. What does this imply for the way we should write and evaluate software? Should the operating system or the language runtime try to optimise memory layout automatically, or is it the programmer's responsibility? What would the trade-offs of automatic optimisation be?

07 Knowledge check

Check your understanding

Question 1

Describe the levels of the memory hierarchy. For each level, give its typical capacity and latency, and explain the trade-off it makes between the three objectives of capacity, latency, and cost.

Show answer
The memory hierarchy has five or six levels, from the fastest and smallest to the slowest and largest. Registers are inside the CPU, with a capacity of about 1 KB and a latency of 0.2–0.5 ns. They are the fastest possible storage, but there are so few of them that only the compiler's most critical variables live in registers. L1 cache is per-core and on-chip, with 32–64 KB and a latency of about 1 ns (4 cycles). It is the first level that is transparent to software. L2 cache is also per-core, with 256 KB to 1 MB and about 4 ns (15 cycles). L3 cache is shared across the cores of a socket, with 8–64 MB and about 15 ns (50 cycles). Main memory is off-chip DRAM, with 8–512 GB and about 80 ns (250 cycles). It is the first level managed by the operating system. SSD or flash storage holds 256 GB to 8 TB at about 100 µs — a factor of a thousand slower than DRAM. Magnetic disk holds 1–20 TB at about 10 ms — another factor of a hundred slower. Each level trades off against the others: the fast levels are small because fast memory is expensive per byte, and the large levels are slow because dense storage technologies have long access times. The hierarchy exists because no single technology can be simultaneously fast, large, and cheap, so the system uses a combination of technologies, each of which is good at one or two of the three.

Question 2

Define locality of reference and distinguish its temporal and spatial forms. Why is locality necessary for the memory hierarchy to be effective? What would happen to the performance of a program that had no locality at all?

Show answer
Locality of reference is the empirical observation that a program's memory accesses tend to cluster: at any moment the program is actively using a small fraction of its address space, and the accesses it makes tend to be near each other in space and time. Locality has two forms. Temporal locality is the tendency to access the same location again soon — the loop counter accessed on every iteration, the function called repeatedly, the variable read and written in a tight loop. Spatial locality is the tendency to access nearby locations soon — the array traversed in order, the structure whose fields are read together, the code executed sequentially. Locality is necessary for the hierarchy to be effective because the hierarchy works by caching: a small fast memory holds a copy of the most recently or most frequently used data from a larger slow memory, and a request that hits in the cache is served quickly. For the cache to have a high hit rate, the data it holds must be the data the program will request next. Locality is the property that makes this true: because programs re-use recently accessed data (temporal) and nearby data (spatial), the cache's policy of keeping recent data gives it the right data most of the time. A program with no locality at all — one that accessed memory uniformly at random across a large region — would miss in every cache level on essentially every access, and would run at the speed of main memory, hundreds of times slower than the CPU could otherwise execute. It would also fault on every page if it exceeded the physical memory, running at the speed of disk. In practice, no real program has zero locality, but programs with poor locality run dramatically slower than programs with good locality, as the worked example's matrix traversal demonstrates.

Question 3

What is the memory wall? Why did it arise, and what are its consequences for system design? What mechanisms exist to mitigate it?

Show answer
The memory wall, also called the von Neumann bottleneck, is the growing gap between the speed at which a CPU can execute instructions and the time it takes to fetch a datum from main memory. It arose because processor performance and memory latency improved at different rates. From the 1970s through the early 1990s, both improved by roughly 40 to 60 percent per year, and the ratio between them stayed roughly constant. Around 1995 the two diverged: processor performance continued its historical improvement, driven by deeper pipelines and higher clock frequencies, while memory latency improved much more slowly because it is bounded by physical limits — the speed of light and the time required to charge a DRAM cell's capacitance — that do not scale with process technology the way transistor switching does. By 2025, processor performance had increased by about four orders of magnitude since 1980, while memory latency had increased by only about one and a half. A memory access that cost a few CPU cycles in 1980 costs a few hundred today. The consequence for system design is that the CPU cannot be kept busy by a program that accesses memory naively: if every access had to go to main memory, the CPU would be idle for more than 99 percent of the time. The primary mitigation is the cache hierarchy: small fast memories close to the CPU that hold recently used data, reducing the fraction of accesses that reach main memory. The caches work because of locality of reference. Secondary mitigations include hardware prefetching (the cache controller guesses which data will be needed next and fetches it in advance), out-of-order execution (the CPU continues executing independent instructions while a memory access is outstanding), simultaneous multithreading (the CPU interleaves instructions from two threads to hide the latency of one with the work of the other), and software techniques such as cache blocking (the programmer reorganises the computation so that the working set fits in cache). All of these depend on the program's access pattern being predictable and local; for a program with poor locality, no amount of hardware cleverness can close the gap.

Question 4

Which levels of the memory hierarchy are managed by the operating system, and which are managed by the hardware? What are the operating system's three responsibilities in memory management, and why does the involvement of the operating system arise?

Show answer
The levels of the memory hierarchy are divided between hardware and software. The registers are allocated by the compiler, which decides which variables live in them. The L1, L2, and L3 caches are managed entirely by the hardware — the cache controller decides what to keep, what to evict, and when to fetch, and the software is unaware that they exist. The main memory, SSD, and disk are managed by the operating system: the kernel decides which pages are resident in main memory, which are written to swap, and where files are placed on disk. The operating system has three responsibilities in memory management. Allocation: deciding which processes get which parts of memory and how much memory each process gets, including the space for a process's code, data, heap, and stack, and the additional memory a process requests at runtime. Protection: ensuring that one process cannot read or write another process's memory, whether by accident or by intent. This requires hardware support (base and limit registers, segmentation, paging) and operating-system policy (setting up the translation tables for each process). Transparency: presenting physical memory as the clean abstraction the programmer expects — a private, contiguous address space, with no visible interference from other processes, and with the ability to run a program larger than physical memory. The operating system's involvement arises from three requirements that a simple system cannot satisfy. Multiprogramming: several processes must share physical memory so that the CPU is not idle when one blocks on I/O. Isolation: a process must not be able to affect another, which requires the hardware to check every access against a description of the address space. Overcommitment: the total memory demanded by the processes often exceeds the physical memory, so the system must be able to keep some pages on disk and bring them in on demand. Each of these requirements alone would be manageable; it is their combination that produces the full complexity of modern memory management.

Question 5

Two versions of a program traverse a large matrix — one row by row, the other column by column. Both perform the same number of operations and produce the same result, but one runs several times faster. Explain why, in terms of the memory hierarchy and locality, and describe what the difference implies for the operating system's memory management policies.

Show answer
The difference is entirely in the memory access pattern. In C, a two-dimensional array is stored in row-major order: the elements of a row are adjacent in memory, and the elements of a column are one row-length apart (for a 2048 × 2048 int array, 8,192 bytes apart). The row-major traversal accesses memory sequentially: a[0][0], a[0][1], a[0][2], and so on. Because the cache fetches a whole line of 64 bytes on a miss, one miss brings in 16 consecutive ints, all of which the loop will use immediately. The result is one miss every 16 accesses — a hit rate of about 94 percent. The column-major traversal accesses memory with a stride of 8,192 bytes: a[0][0], a[1][0], a[2][0], and so on. Each access is in a different cache line, and because the working set (the whole matrix, 16 MB) far exceeds the cache (typically 32 KB of L1), each access evicts a line that will not be used again until the next column iteration — by which time it has been evicted. The result is a miss on essentially every access, and each miss costs the full main-memory latency. The performance difference is a direct consequence of the memory hierarchy: the row-major version has good spatial locality and stays in cache, while the column-major version has no spatial locality and reaches main memory on every access. For the operating system, the implication is that the memory management policies matter enormously. A policy that fragments memory, that evicts pages poorly, or that gives a process less resident memory than its working set needs will push the working set down the hierarchy, where every access costs orders of magnitude more. The same principle that makes cache-friendly code fast — keeping the working set in the fastest level that can hold it — is the principle behind the operating system's page-replacement policies in Unit 9.

08 Unit discussion

Discussion prompt

The memory hierarchy exists to resolve a conflict that cannot be resolved by technology alone: no memory can be simultaneously fast, large, and cheap. The solution is to combine memories that are good at different things, and to move data between them. The movement is driven by locality of reference, a property of programs that the hardware and the operating system are designed to exploit.

This has an interesting consequence. The hierarchy is invisible to the programmer in the sense that a correct program does not need to know it exists — the hardware and the operating system handle the movement of data transparently. But the hierarchy is highly visible in performance: a program that respects it and a program that ignores it can differ by an order of magnitude in running time, with no difference in the algorithm and no difference in the result. The abstraction of a flat, uniform memory is a lie, and the lie leaks.

Should the abstraction be maintained, or should programmers be taught about the hierarchy explicitly? Some argue that the abstraction is valuable: it lets programmers reason about correctness without being distracted by the hardware, and it lets the hardware evolve without requiring every program to be rewritten. Others argue that the abstraction is harmful: it leads programmers to write code that performs poorly, and the performance problem is invisible until the program is measured. Languages such as C and C++ expose the hierarchy through the memory model and through explicit cache hints; languages such as Java and Python hide it behind the runtime.

What do you think? Should the memory hierarchy be taught as a central topic in a first programming course, or reserved for systems courses? Should language runtimes do more to optimise memory layout automatically, at the cost of taking control away from the programmer? Is there a design that gives the programmer the ability to control the layout when it matters and to ignore it when it does not?

Post your response to the Unit 8 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 8.2. Aim to spend 60–90 minutes on it.

  1. Tabulate the hierarchy. On your own machine, use lscpu and getconf to find the actual capacity and cache-line size of each cache level. Build a table with columns for level, capacity, latency (estimated from published figures or from your own measurement), cost per byte (estimated), and whether the level is managed by hardware or by the operating system.
  2. Compute effective access times. For the following hierarchy, compute the effective access time: L1 with 1 ns latency and 96% hit rate, L2 with 4 ns and 80% conditional hit rate, L3 with 15 ns and 70% conditional hit rate, and main memory with 80 ns. Use the multi-level formula from the worked example. 
    EAT = t_L1
    + (1 − h₁) × t_L2
    + (1 − h₁)(1 − h₂) × t_L3
    + (1 − h₁)(1 − h₂)(1 − h₃) × t_mem
    Then compute the EAT if the L1 hit rate drops to 80 percent, and if it rises to 99 percent. How much does each change affect the result?
  3. Demonstrate locality. Write the row-major and column-major matrix programs from the interactive activity. Compile both with -O2 and time them. Report the ratio. Then modify the programs so that the matrix is small enough to fit in L1 (for example, 64 × 64 instead of 2048 × 2048) and re-run. Does the ratio change? Why?
  4. Measure cache latency. Run the latency measurement program from the interactive activity. Plot the results with the buffer size on the horizontal axis (log scale) and the nanoseconds per access on the vertical axis. Identify the points at which the latency jumps, and compare them to the cache sizes reported by lscpu. Do the jumps correspond to the cache boundaries?
  5. Count cache misses. Use perf stat to count the L1 data cache loads and load-misses for the row-major and column-major programs. Compute the miss rate for each. Compare the miss rates to the ratio of running times. Is the relationship linear? 
    perf stat -e L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses ./row_major
perf stat -e L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses ./col_major
  6. Design a cache-friendly algorithm. The naive matrix multiplication algorithm accesses one of its inputs column-wise, which has poor spatial locality. Write a blocked version that processes the matrices in sub-blocks small enough to fit in L1, and compare its performance to the naive version. This is the technique called cache blocking or loop tiling. 
    /* Naive: for i, for j, for k: C[i][j] += A[i][k] * B[k][j]
   Blocked: for ii, for jj, for kk:
              for i in block, for j in block, for k in block:
                  C[i][j] += A[i][k] * B[k][j] */
    How much faster is the blocked version for a 512 × 512 matrix? What block size is best?
  7. Explain the memory wall. Write a short paragraph (150–200 words) explaining the memory wall to a programmer who has never heard of it. Your explanation should include: what the wall is, why it arose, what the consequences are for a program that accesses memory inefficiently, and what the programmer can do about it. Do not use the word "cache" more than three times.
  8. Reflect. In your own words, explain why the memory hierarchy is necessary — that is, why a computer cannot simply have one kind of memory that is fast, large, and cheap. Then describe one situation in your own experience — a program you have written or used — where the memory hierarchy could plausibly have affected performance. What was the access pattern, and what would you do differently now?

10 Summary

  • Memory is a hierarchy of storage levels — registers, L1/L2/L3 cache, main memory, SSD, and magnetic disk — spanning seven orders of magnitude in latency and ten in capacity.
  • Each level makes a different trade-off between capacity, latency, and cost per byte. Fast memory is small and expensive; large memory is slow and cheap. No single technology can be all three.
  • Each level caches the level below it: it holds a copy of the most recently or most frequently used data, so that a request that hits is served quickly and a request that misses is passed down and, when satisfied, copied upward.
  • The hierarchy works because of locality of reference: the empirical observation that programs access a small subset of their memory repeatedly (temporal locality) and access nearby locations soon (spatial locality).
  • A high hit rate is what makes the hierarchy effective. A 99 percent hit rate in a 1 ns cache backed by a 100 ns memory gives an effective access time of about 2 ns — fifty times faster than the slow memory alone.
  • The memory wall is the growing gap between CPU speed and memory latency. Processor performance has grown by about four orders of magnitude since 1980 while memory latency has grown by about one and a half, so a main-memory access now costs hundreds of CPU cycles.
  • The caches (L1, L2, L3) are managed entirely by the hardware and are transparent to software. Main memory and below are managed by the operating system.
  • The operating system has three responsibilities in memory management: allocation (deciding which processes get which memory), protection (ensuring processes cannot interfere with each other), and transparency (presenting physical memory as the clean address-space abstraction).
  • The operating system's involvement arises from three requirements: multiprogramming (several processes share memory), isolation (they must not interfere), and overcommitment (the total demand often exceeds the physical memory).
  • The performance of a program is often dominated not by its instruction count but by its memory access pattern. The worked example's row-major and column-major matrix traversals perform identical arithmetic but differ by nearly an order of magnitude in running time, purely because of spatial locality.

Looking ahead

This lesson established the physical basis for the rest of the memory unit: the hierarchy, locality, the memory wall, and the operating system's three responsibilities. Lesson 8.2 introduces address binding: the problem of translating the symbolic addresses a program is written in into the physical addresses the hardware uses. It presents the three binding times (compile, load, and execution) and the mechanisms — relocatable code, dynamic loading, and the memory-management unit — that make each possible. The address-space abstraction introduced in this lesson is what makes those mechanisms necessary, and the protection requirement is what makes them complex.

11 References

  • Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 6, The Memory Hierarchy. The definitive treatment from the programmer's perspective.
  • Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Section 9.1.
  • Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Sections 3.1–3.2.
  • Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 13–14. Available online at ostep.org.
  • Hennessy, J. L., & Patterson, D. A. Computer Architecture: A Quantitative Approach, 6th ed., Chapter 2, Memory Hierarchy Design.
  • Wulf, W. A., & McKee, S. A. Hitting the Memory Wall: Implications of the Obvious. ACM SIGARCH Computer Architecture News, 1995. The paper that named the memory wall and framed the problem for a generation of architects.
  • Drepper, U. What Every Programmer Should Know About Memory. Red Hat, 2007. An extended treatment of cache behaviour, memory latency, and their consequences for programming.
  • Linux man-pages: man 1 lscpu, man 1 lstopo, man 1 perf-stat, man 3 getpagesize, man 2 mmap, man 5 proc.
👤