Chapter 29 of 38

Virtual Memory & Demand Paging

Your laptop may have 8 GB of RAM, yet you can open a browser with 40 tabs, an IDE, a music player and a video call at the same time, and the total memory those programs ask for can be more than 8 GB. A single game can be a 60 GB install. How does any of this fit?

The answer is that a program almost never needs all of itself in memory at once. Error-handling code that never runs, menus you never open, the parts of a huge array you have not reached yet: none of these need to occupy RAM right now.

Virtual memory is a technique that separates the logical (virtual) memory seen by a process from the physical memory of the machine, so that a process can run even when only part of it is in RAM. The rest is kept on disk and brought in when needed.

The most common way to implement virtual memory is demand paging: a page is loaded into a frame only when the process actually touches it. In this chapter we will see how the valid bit makes this possible, walk through exactly what happens on a page fault, measure page faults on a real Linux system, compute the performance cost, and see the clever tricks that virtual memory enables, such as copy-on-write after fork().


Why Not Load the Whole Program?

Up to now (Paging, Page Tables & TLB, Segmentation) we quietly assumed that the whole process is in memory before it runs. That assumption is wasteful:

  • Programs contain code for unusual cases (error handlers, rarely used features) that may never run.

  • Arrays and tables are often declared bigger than what is actually used.

  • Even code that is used is used at different times. Start-up code is not needed after start-up.

If only the needed parts are in memory, we get big benefits:

Benefit

Why

Programs can be larger than physical memory

Only the part being used must fit in RAM

More processes in memory at once

Each uses fewer frames, so the degree of multiprogramming and CPU utilisation go up

Faster program start

No need to read the whole executable from disk before running

Less I/O overall

Pages that are never touched are never loaded

Easy sharing

Shared libraries and shared memory map the same frames into many processes

Simpler programming

The programmer sees a large, clean address space and does not manage overlays by hand


The Virtual Address Space

Every process gets its own virtual address space: on 64-bit Linux, 128 TB for the user part with 4-level paging. The process sees it as one huge, private range of addresses. Most of it is empty:

High addresses
+-------------------------+
|         stack           |  grows down
|           |             |
|           v             |
|                         |
|   (huge unused gap:     |  no frames, no page-table entries needed
|    costs nothing)       |
|                         |
|           ^             |
|           |             |
|         heap            |  grows up
+-------------------------+
|      data / bss         |
+-------------------------+
|         code            |
+-------------------------+
Low addresses

The gap between heap and stack is called a sparse address space. Pages in the gap do not exist physically. They only get frames if the heap or stack grows into them, or if a library or file is mapped there.

So there are two different sizes to keep in mind:

  • Virtual memory size of a process: how much address space it has reserved. In Linux tools this is VSZ or VIRT.

  • Resident set size (RSS): how many of those pages are actually in RAM right now. Shown as RSS or RES.

It is completely normal for a browser to show VIRT in the tens of GB and RES of a few hundred MB.


Demand Paging

In demand paging a page is brought into memory only when it is first referenced, that is, "on demand". It is similar to swapping, but lazy and page by page: instead of loading the whole process, the OS loads nothing (or very little) at the start and lets page faults pull in what is needed. The part of the OS that does this is called the pager (sometimes called a lazy swapper).

Taken to the extreme, pure demand paging starts a process with zero pages in memory. The very first instruction causes a page fault, and the process "faults its way" into memory.

The Valid–Invalid Bit

Recall from Page Tables & TLB that every page-table entry has a valid (present) bit. Demand paging is built on it:

  • valid (1): the page is legal for this process and is in a frame. Translation proceeds normally.

  • invalid (0): either the page is not part of the process at all, or it is legal but currently on disk. Touching it causes a page fault (a trap).

Logical memory     Page table              Physical memory     Disk (backing store)
                   frame  valid
page 0  A          [  4  |  v ]  ------->  frame 4: A
page 1  B          [     |  i ]                                B
page 2  C          [  6  |  v ]  ------->  frame 6: C
page 3  D          [     |  i ]                                D
page 4  E          [     |  i ]                                E
page 5  -- (unused, not part of the process) --   i

Pages 1, 3 and 4 are legal but on disk; page 5 is not part of the process at all. Both cases have the bit set to i, so the OS must look at its own records (kept with the process's PCB) to tell them apart.

Why Does This Work So Well? Locality

If every instruction touched a new page, demand paging would be a disaster. It works because programs show locality of reference: in any short period they use a small set of pages (the current function's code, its stack frame, the part of the array it is scanning). After a few faults to bring that set in, the program runs for a long time without faulting. The Thrashing chapter studies what happens when this assumption breaks.


Handling a Page Fault, Step by Step

When the MMU finds the valid bit is 0, it raises a page-fault trap. The OS then does this:

  1. Trap to the kernel. The hardware saves the user registers and the faulting address (on x86 the address goes into register CR2).

  2. Check whether the reference is legal. The OS looks up the address in the process's memory map (in Linux, the list of VMAs we met in Segmentation). If the address is in no region, or the access breaks the region's permissions, the process is killed with a segmentation fault (SIGSEGV).

  3. Find a free frame from the free-frame list. If there is none, a page replacement algorithm must pick a victim page to evict (next chapter).

  4. Schedule a disk read of the needed page into that frame. The faulting process is now blocked (waiting state) and the CPU scheduler runs another process, because the disk takes milliseconds.

  5. Disk interrupt: the read is complete. The OS updates the page table: frame number filled in, valid bit set to 1.

  6. The process is moved back to the ready queue.

  7. When it runs again, the faulting instruction is restarted from the beginning. This time the page is present and it succeeds. The process never knows anything happened, apart from the delay.

  CPU: load M                       (1) trap
   |                         +-------------------------> OS
   v                         |                           | (2) legal? check memory map
 page table: valid = i  -----+                           | (3) find free frame
                                                         | (4) read page from disk ---> [disk]
                                                         |          ... other processes run ...
                                                         | (5) page arrives in frame
 page table: frame f, valid = v  <-----------------------+     update page table
   |
   v (7) restart "load M": now it hits

Restarting the Instruction

Step 7 sounds simple but needs hardware support. A fault can happen in the middle of an instruction, for example while fetching an operand. The hardware must be able to undo or redo the partial work so the instruction can be re-executed as if it had never started.

The tricky cases are instructions that modify several locations. Imagine a block-move instruction copying 256 bytes where the source and destination overlap and the destination crosses a page boundary. If it faults halfway, part of the source may already be overwritten. Hardware solves this by touching both ends of the blocks before modifying anything, or by keeping temporary registers that hold overwritten values. This is one reason demand paging needs careful CPU design, not just OS code.


Minor vs Major Page Faults

Not every page fault involves the disk. Linux (and most modern OSes) distinguish:

Type

What happens

Typical cost

Minor (soft) fault

The page is already in memory or needs no data from disk: e.g. a fresh heap page that just needs a zero-filled frame, or a shared library page already cached for another process. The OS only updates the page table.

Around a microsecond

Major (hard) fault

The page must be read from disk: from the executable file, a mapped file, or swap space.

Tens of microseconds (SSD) to milliseconds (hard disk)

Invalid access

The address is not legal for the process.

Process gets SIGSEGV

Seeing Demand Paging on Linux

This program asks for 64 MiB of memory with mmap() and counts page faults with getrusage(), first after the allocation, then after writing one byte in each page of the first half, and then after writing those pages again:

#define _DEFAULT_SOURCE
#include <stdio.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <unistd.h>

static long minor_faults(void) {
    struct rusage ru;
    getrusage(RUSAGE_SELF, &ru);
    return ru.ru_minflt;          /* page faults served without any disk I/O */
}

int main(void) {
    const size_t size = 64UL * 1024 * 1024;          /* 64 MiB */
    const size_t page = (size_t)sysconf(_SC_PAGESIZE);

    long f0 = minor_faults();
    char *buf = mmap(NULL, size, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (buf == MAP_FAILED) { perror("mmap"); return 1; }
    madvise(buf, size, MADV_NOHUGEPAGE);             /* keep normal 4 KiB pages */
    long f1 = minor_faults();

    for (size_t i = 0; i < size / 2; i += page)      /* touch the first half */
        buf[i] = 1;
    long f2 = minor_faults();

    for (size_t i = 0; i < size / 2; i += page)      /* touch it again */
        buf[i] = 2;
    long f3 = minor_faults();

    printf("Reserved %zu MiB = %zu pages\n", size >> 20, size / page);
    printf("Page faults during mmap()          : %ld\n", f1 - f0);
    printf("Page faults touching first half    : %ld\n", f2 - f1);
    printf("Page faults touching it again      : %ld\n", f3 - f2);

    munmap(buf, size);
    return 0;
}

Compiled with gcc -std=c17 -Wall -Wextra and run on Ubuntu (WSL2, x86-64, 4 KiB pages):

Reserved 64 MiB = 16384 pages
Page faults during mmap()          : 0
Page faults touching first half    : 8192
Page faults touching it again      : 0

This is demand paging in action:

  • mmap() only reserved address space. It took zero page faults and used no frames.

  • Writing to 8192 pages caused exactly 8192 page faults, one per page, the first time each page was touched. The kernel gave each one a zero-filled frame (a minor fault, since nothing came from disk).

  • Touching the same pages again caused 0 faults: they are now valid in the page table.

  • The other 8192 pages were never touched, so they never got frames at all.

The MADV_NOHUGEPAGE hint stops Linux from backing the region with 2 MiB huge pages, which would turn 512 small faults into one big one and make the numbers less clear. You can watch faults for any command with /usr/bin/time -v ./program, which prints "Major (requiring I/O) page faults" and "Minor (reclaiming a frame) page faults".


Performance of Demand Paging

Let p be the probability that a memory access causes a page fault (0 ≤ p ≤ 1). Then the effective access time is:

EAT = (1 - p) × memory access time  +  p × page-fault service time

The page-fault service time includes the trap, the disk read (which dominates), and restarting the process. Take a memory access time of 200 ns and a page-fault service time of 8 ms (8,000,000 ns) on a hard disk.

Fault rate p

EAT

Slowdown

0

200 ns

1×

1 in 1,000

0.999 × 200 + 0.001 × 8,000,000 = 8199.8 ns

about 41×

1 in 100,000

about 280 ns

1.4×

1 in 1,000,000

about 208 ns

1.04×

Question: What fault rate keeps the slowdown under 10%?

EAT < 1.10 × 200 = 220 ns

(1 - p) × 200 + p × 8,000,000 < 220
        200 + p × 7,999,800  < 220
              p × 7,999,800  < 20
                          p  < 2.5 × 10^-6   (about 1 fault per 400,000 accesses)

The lesson: a page fault is so expensive that the fault rate must be tiny. Anything that lowers p (good locality, enough frames, a good replacement algorithm) matters a lot.

Numerical with Dirty Pages

When there is no free frame, the OS must evict a victim. If the victim was modified (its dirty bit is set), it must be written to disk first, which roughly doubles the service time. Exam questions often include this.

Problem: Memory access = 200 ns. Servicing a fault takes 8 ms if the victim is clean and 20 ms if it is dirty. 40% of victims are dirty. Fault rate p = 10-6. Find the EAT.

Average service time = 0.6 × 8 ms + 0.4 × 20 ms = 4.8 + 8 = 12.8 ms = 12,800,000 ns

EAT = (1 - 10^-6) × 200 + 10^-6 × 12,800,000
    = 199.9998 + 12.8
    ≈ 212.8 ns

Common exam trap: convert milliseconds to nanoseconds (1 ms = 106 ns) before adding.

Where Do Pages Come From?

  • File-backed pages (code, read-only data, memory-mapped files) are read from the file itself. A clean code page can simply be discarded on eviction, because the file still has it.

  • Anonymous pages (heap, stack, MAP_ANONYMOUS) have no file. The first touch gets a fresh zero-filled frame ("zero-fill-on-demand"). If such a page is evicted after being modified, it is written to swap space, a dedicated disk partition or file, and read back from there on the next fault.

On Linux, free -h and swapon --show show the swap space, and the setting /proc/sys/vm/swappiness (default 60) tunes how readily the kernel swaps anonymous pages instead of dropping file cache.


Copy-on-Write: Fast fork()

In Process Creation (fork & exec) we saw that fork() gives the child a copy of the parent's memory. Copying gigabytes on every fork() would be very slow, and most children immediately call exec() and throw that copy away.

Copy-on-write (COW) solves this with virtual memory:

  1. At fork(), the child gets a copy of the parent's page table, not of the pages. Both page tables point to the same frames.

  2. All shared writable pages are marked read-only in both page tables.

  3. Reads work at full speed from the shared frames.

  4. When either process writes a shared page, the hardware raises a protection fault. The OS sees it is a COW page, copies just that one page into a new frame, maps the copy as writable for the writer, and restarts the instruction.

After fork():                         After the child writes page X:

parent PT ---\                        parent PT -----> [ X  ] (original)
              >---> [ X ] (read-only)
child  PT ---/                        child  PT -----> [ X' ] (private copy, writable)

Measuring Copy-on-Write

The parent fills 1000 pages, then forks. The child first reads all 1000 pages, then writes all of them, counting faults each time:

#define _DEFAULT_SOURCE
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <sys/wait.h>
#include <unistd.h>

static long minor_faults(void) {
    struct rusage ru;
    getrusage(RUSAGE_SELF, &ru);
    return ru.ru_minflt;
}

int main(void) {
    const size_t pages = 1000;
    long psz = sysconf(_SC_PAGESIZE);
    size_t size = pages * (size_t)psz;

    char *data = mmap(NULL, size, PROT_READ | PROT_WRITE,
                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (data == MAP_FAILED) { perror("mmap"); return 1; }
    madvise(data, size, MADV_NOHUGEPAGE);
    memset(data, 'P', size);              /* parent fills all 1000 pages */

    pid_t pid = fork();
    if (pid < 0) { perror("fork"); return 1; }

    if (pid == 0) {                       /* child */
        long f0 = minor_faults();
        volatile char sum = 0;
        for (size_t i = 0; i < size; i += (size_t)psz) sum += data[i];   /* read  */
        long f1 = minor_faults();
        for (size_t i = 0; i < size; i += (size_t)psz) data[i] = 'C';    /* write */
        long f2 = minor_faults();
        printf("child : faults while READING 1000 shared pages = %ld\n", f1 - f0);
        printf("child : faults while WRITING 1000 shared pages = %ld\n", f2 - f1);
        printf("child : data[0] = %c\n", data[0]);
        (void)sum;
        fflush(stdout);
        _exit(0);
    }

    waitpid(pid, NULL, 0);
    printf("parent: data[0] = %c (unchanged)\n", data[0]);
    munmap(data, size);
    return 0;
}

Output on Ubuntu (WSL2, x86-64):

child : faults while READING 1000 shared pages = 0
child : faults while WRITING 1000 shared pages = 1000
child : data[0] = C
parent: data[0] = P (unchanged)
  • Reading: 0 faults. The child's page table already pointed at the parent's frames, so nothing had to be copied.

  • Writing: exactly 1000 faults, one per page. Each first write triggered a COW copy of that page only.

  • The parent still sees 'P': after the copy, the two processes really do have separate memory, as fork() promises.

(The parent waits for the child, so the output order here is fixed. The fault counts themselves can differ slightly on other kernels or if transparent huge pages are used, which is why the program disables them for this region.)


Other Tricks Virtual Memory Makes Possible

  • Memory-mapped files (mmap() on a file): the file's blocks appear as memory. Reading memory triggers page faults that load the file data, and dirty pages are written back to the file. Executables and shared libraries are loaded this way.

  • Shared libraries: one copy of libc.so in RAM, mapped read-only into every process.

  • Shared memory IPC (from Inter-Process Communication): two processes map the same frames into their address spaces.

  • Lazy allocation and overcommit: because memory is only given on first touch, Linux by default lets processes reserve more virtual memory than RAM plus swap (heuristic overcommit, vm.overcommit_memory = 0). If everyone really uses their memory, the kernel's OOM killer picks a process to kill.

  • Prepaging: the opposite of pure demand paging. The OS predicts which pages will be needed (for example, the next few pages of a file being read sequentially, or the pages a swapped-out process was using) and loads them early to avoid a burst of faults.


What If There Is No Free Frame?

Sooner or later every frame is in use and a page fault still needs one. The OS must then replace a page:

  1. Choose a victim page using a page-replacement algorithm.

  2. If the victim's dirty bit is set, write it to disk (swap or its file); if it is clean, just discard it.

  3. Mark the victim's page-table entry invalid (and invalidate its TLB entry).

  4. Read the wanted page into the freed frame and continue as in a normal fault.

Which victim to choose has a huge effect on the fault rate p, and therefore on performance. That is the topic of the next chapter, Page Replacement Algorithms. How many frames each process should get, and what happens when there are simply not enough, is covered in Thrashing.


Common Mistakes

  • "Virtual memory means using the disk as RAM." That is only part of it. Virtual memory is the separation of logical and physical addresses; swapping to disk is one thing it enables. Copy-on-write, shared libraries and sparse address spaces work even with no swap at all.

  • Thinking a page fault is an error. A page fault is a normal, expected event in demand paging. Only an access to an illegal address becomes an error (SIGSEGV).

  • Restarting the next instruction. After a page fault, the same faulting instruction is restarted, because it never completed.

  • Mixing units in EAT. Convert ms to ns (× 106) before computing. 8 ms = 8,000,000 ns.

  • Assuming the CPU waits during a major fault. The faulting process blocks; the CPU runs other processes during the disk I/O.

  • Confusing VIRT/VSZ with real memory use. Reserved address space is not the same as resident memory (RSS).


Interview Questions

What is virtual memory?

A technique that separates the virtual address space a process sees from physical memory, so that a process can be larger than RAM and only the parts in use need to be resident. It is usually implemented with demand paging.

What is demand paging?

Loading a page into memory only when it is first referenced. Pages that are never touched are never loaded. Pure demand paging starts a process with no pages in memory.

What is a page fault, and what are the steps to handle it?

A trap raised when a process accesses a page whose valid bit is 0. The OS checks the address is legal, finds a free frame (or replaces a page), reads the page from disk while other processes run, updates the page table, and restarts the faulting instruction.

What is the difference between a minor and a major page fault?

A minor fault is served without disk I/O (zero-filled page, page already in the page cache). A major fault requires reading the page from disk or swap, which is far slower.

Write the effective access time formula for demand paging.

EAT = (1 − p) × memory access time + p × page-fault service time, where p is the page-fault rate.

What is copy-on-write and why is it used?

After fork(), parent and child share the same frames marked read-only. A page is copied only when one of them writes to it. This makes fork() fast and avoids copying memory that exec() would discard anyway.

What is swap space?

Disk space (a partition or file) used to hold anonymous pages that have been evicted from RAM. File-backed pages go back to their files instead.

Why does demand paging not make programs extremely slow?

Because of locality of reference: programs use a small set of pages for long periods, so after a few initial faults most accesses hit pages already in memory and the fault rate stays tiny.

What hardware support does demand paging need?

A page table with a valid/present bit, a page-fault trap, the ability to restart any instruction after a fault, and a backing store (swap/disk) to hold non-resident pages. Reference and dirty bits help with replacement.


Summary

  • Virtual memory separates a process's virtual address space from physical memory; only the pages in use need to be in RAM.

  • Demand paging loads a page on its first reference, using the valid–invalid bit to trigger a page fault.

  • Page-fault handling: trap → check legality → free frame → disk read (process blocks) → update page table → restart the instruction.

  • Faults can be minor (no disk I/O) or major (disk I/O). Our Linux test showed exactly one fault per newly touched page and none on re-access.

  • EAT = (1 − p) × ma + p × fault time. With 200 ns and 8 ms, p must be below about 2.5 × 10-6 to keep the slowdown under 10%.

  • Copy-on-write makes fork() cheap: pages are shared read-only and copied only on the first write (1000 writes, 1000 faults in our test).

  • When no frame is free, a victim must be evicted: the next chapter, Page Replacement Algorithms, explains how to choose it.