Lesson 9.5: Page Faults

01 Introduction

Lesson 9.4 introduced demand paging: the mechanism by which a page is loaded into memory only when it is accessed. The mechanism depends on a single event — the page fault — which the memory-management unit raises when an access cannot be completed by the hardware alone. The page-fault handler, part of the operating system's kernel, takes over, brings the page in from disk if necessary, and resumes the faulting instruction. To the process, the whole sequence is invisible: the instruction that faulted executes as though it had never been interrupted.

This lesson examines the page fault itself. It is worth studying in detail for three reasons. First, the fault is the fundamental event that makes virtual memory possible; every other mechanism in Unit 9 — demand paging, page replacement, thrashing — is built on it. Second, the fault handler is one of the most performance-critical pieces of code in a modern operating system, and its design determines whether demand paging is affordable. Third, the fault is a rich event: it carries information about the address that faulted, the type of access, and the reason for the fault, and the handler must interpret all of this to decide what to do.

The lesson begins with the trap mechanism: what the hardware does when it detects a fault, how it delivers the fault address and the error code to the kernel, and what the kernel finds when it begins handling the fault. It then presents the taxonomy of faults — the four kinds of fault that the handler must distinguish: minor faults, major faults, protection faults, and invalid accesses. It walks through the handler step by step, showing what happens in each case, and it explains the requirement that the faulting instruction be restartable — that the fault can be handled and the instruction re-executed without any visible effect on the process. It presents the special case of copy-on-write faults, which are the mechanism behind fork() and memory-mapped files. And it presents the mechanisms that reduce the number of faults: fault-around, prefaulting, and the cluster read-ahead introduced in Lesson 9.4.

The lesson closes with the measured cost of a page fault. The effective access time calculation of Lesson 9.4 assumed a fault time of about 10 ms, but the actual cost depends on whether the page is in the page cache, in the swap area, or on a disk; whether a victim page must be written out; and whether the I/O is scheduled efficiently. The measured cost of a fault on a modern system ranges from a few microseconds (a minor fault that finds the page in memory) to tens of milliseconds (a major fault that reads from a spinning disk under load). Understanding this range is essential to reasoning about the performance of demand-paged systems.

Prerequisites

This lesson builds directly on Lessons 9.1 through 9.4. The paging model, the page-table entry fields (particularly the valid bit, the dirty bit, and the protection bits), the TLB, and the demand-paging mechanism are all assumed. The distinction between file-backed and anonymous memory from Lesson 9.4 is central to the taxonomy of faults. The role of the scheduler in running another process while a fault is being serviced assumes the scheduling material from Unit 5, but no new scheduling concepts are introduced. The page-replacement policy is referenced but not developed; it is the subject of Lesson 9.6.

02 Learning objectives

By the end of this lesson you will be able to

Describe the trap mechanism by which the MMU raises a page fault and delivers information to the kernel.
Distinguish minor faults, major faults, protection faults, and invalid accesses, and describe the handler's response to each.
Trace the page-fault handler step by step for a major fault.
Explain why the faulting instruction must be restartable, and describe the cases in which restart is impossible.
Describe copy-on-write faults, fault-around, and prefaulting, and explain the mechanisms that reduce the fault rate.

This lesson contributes to U9.5 and U9.6, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

Operating System Concepts — Chapter 10, Sections 10.2–10.3, Demand Paging and Copy-on-Write. The standard treatment of the page-fault service routine, the four kinds of fault, and the copy-on-write mechanism.
OSTEP — Chapter 21, Swapping: Mechanisms, and Chapter 22, Swapping: Policies (the introductory sections). OSTEP's treatment of the page-fault handler, the swap space, and the interaction between the handler and the scheduler is the clearest available account.
Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.7–9.9. The page-fault handler presented from the programmer's perspective, including the distinction between minor and major faults and the mmap interface.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.3. The page-fault handler and the restartability requirement, presented with the historical context.
Silberschatz et al. — Chapter 10, Sections 10.2–10.3. Read the discussion of the effective access time and the requirements for restartability.
Intel Corporation. — Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 4, Paging, and Chapter 6, Interrupt and Exception Handling. The definitive reference for the x86-64 fault mechanism, including the CR2 register, the page-fault error code, and the page-fault exception (#PF).
Love, R. — Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux implementation of the page-fault handler, including the do_page_fault function, the fault paths for different kinds of mappings, and the OOM killer.
Linux man pages: man 2 mmap, man 2 mprotect, man 2 madvise, man 2 fork, man 5 proc (the /proc/<pid>/stat field maj_flt, and the /proc/<pid>/smaps fields), man 1 perf-stat, man 1 ltrace, man 1 strace, man 2 process_vm_readv.

Reading strategy

Read the Silberschatz section first for the canonical statement of the handler's steps and the four kinds of fault. Then read the OSTEP chapters on swapping for the interaction between the fault handler and the rest of the kernel, particularly the scheduler and the I/O subsystem. The Intel manual's chapter on interrupt and exception handling is the authoritative reference for the x86-64 fault mechanism; read the sections on the page-fault exception and the error code if you want to understand exactly what the hardware delivers to the kernel. Finally, read the Linux kernel's memory management chapter for the real-world implementation, which includes the paths for anonymous memory, file-backed memory, and copy-on-write.

04 Core content

4.1 The trap mechanism

A page fault begins with the memory-management unit. When the MMU attempts to translate a logical address and finds that the translation cannot be completed — because the page-table entry's valid bit is clear, or because the access violates the page's protection — it does not simply return an error. It raises an exception: a trap to the operating system's kernel.

The trap transfers control to a handler whose address is recorded in the interrupt descriptor table (IDT on x86) or the equivalent structure on other architectures. The handler runs in kernel mode, on the kernel stack of the faulting process. Before it starts, the hardware saves the state that the handler needs to understand the fault and to resume the process afterward.

On x86-64, the page-fault exception is #PF, and the hardware provides two pieces of information to the handler:

The faulting address: Placed in the CR2 control register. The handler reads CR2 to learn which address caused the fault. The address is the logical address — the address the program was trying to access — not the physical address, because the physical address is what could not be computed.
The error code: Pushed onto the stack by the hardware. The error code is a small set of bits that describe the fault: whether the access was a read, a write, or an instruction fetch; whether the fault occurred in user mode or kernel mode; whether the page was present but the access was forbidden (a protection fault) or the page was not present at all (a not-present fault); and, on some processors, whether the fault occurred during an instruction fetch or a data access.

The error code is essential, because the handler's response depends on the kind of fault. A read fault on a not-present page is a demand-paging fault: the handler loads the page and resumes the instruction. A write fault on a read-only page is a protection violation: the handler terminates the process with a signal. A read fault on a page that is marked not-present but is actually part of the process's address space (a page that has been swapped out) is a swap fault: the handler reads the page back from the swap area. And a fault on an address that is not part of the process's address space at all is an invalid access: the handler terminates the process, because the address is a bug.

The trap mechanism has a cost even when the fault is handled successfully. On x86-64, a page fault takes several hundred cycles to enter the handler and return from it, even when no disk I/O is involved. This cost is the price of the trap-and-handle mechanism, and it is why the fault rate must be low: even a fault that does not touch the disk is more expensive than a normal memory access by a factor of a hundred or more.

4.2 The four kinds of fault

Not every page fault is the same. The handler must distinguish four kinds, each with a different cause and a different response. The figure below summarises the taxonomy.

Figure 9.5 — The taxonomy of page faults. The handler examines the fault address and the error code to determine which of four kinds of fault has occurred. Invalid accesses and protection faults are genuine errors, and the process is terminated. Minor faults are handled without disk I/O; major faults require reading the page from disk or from the swap area. Copy-on-write faults are a special case in which the page is present but must be duplicated for the writing process.

4.3 The fault handler step by step

The page-fault handler is one of the most intricate functions in an operating system's kernel. Its exact structure depends on the architecture and on the kernel, but its essential steps are the same everywhere. The following walkthrough presents the handler for a major fault — the most complex case — and then notes how the handler is simplified for the other kinds.

Save the fault state. The hardware has already saved the faulting instruction's address, the fault address in CR2, the error code on the stack, and the process's register state. The handler reads these to understand the fault.
Validate the address. The handler consults the process's virtual memory areas (VMAs on Linux) — the data structures that describe each region of the process's address space — to determine whether the fault address is part of a valid region. If the address is not within any VMA, the fault is an invalid access, and the handler terminates the process with the SIGSEGV signal.
Check the protection. If the address is within a VMA, the handler checks whether the access type (read, write, or execute) is permitted by the region's permissions. A write to a read-only region is a protection fault, and the handler terminates the process with SIGSEGV. (There is one exception: a write to a page that is marked read-only but is part of a copy-on-write region. This is the copy-on-write case, described in section 4.5.)
Determine the fault type. If the address is valid and the access is permitted, the handler determines whether the fault is a minor or a major fault. This depends on where the page's contents are. If the page is a file-backed page that is already in the page cache, the fault is minor. If the page is a file-backed page that is not in the cache, the fault is major, and the handler must read the page from the file. If the page is an anonymous page that has never been allocated, the fault is minor — the handler simply maps a fresh zero-filled frame. If the page is an anonymous page that has been swapped out, the fault is major, and the handler must read the page from the swap area.
Obtain a free frame. If the fault is minor and the page is in the page cache, the handler can map the existing cached page into the process's address space, with no frame allocation and no I/O. If the fault is major, the handler needs a frame to hold the page. It takes one from the free list if one is available; if not, it invokes the page-replacement policy (Lesson 9.6) to choose a victim page, writes the victim back to disk if it is dirty, and uses the victim's frame.
Read the page. For a major fault, the handler initiates an I/O operation to read the page from the file or from the swap area into the frame. Because the I/O is slow, the handler cannot simply wait: it schedules the I/O, blocks the faulting process, and returns control to the scheduler, which runs another process. When the I/O completes, the disk interrupt handler wakes the blocked process.
Update the page table. Once the page is in the frame (either because the I/O completed or because the page was already cached), the handler updates the page-table entry for the faulting page: it sets the frame number, sets the valid bit, and sets the protection bits according to the region's permissions and the page's type.
Update the TLB. The TLB may hold a stale entry for the page (if the page was previously mapped and the mapping has changed) or may simply not have an entry. The handler invalidates the TLB entry for the page, so that the next access will miss in the TLB and re-fetch the translation from the page table. On a multiprocessor, the handler must also send a TLB shootdown (Lesson 9.3) to any other core that might hold a stale entry.
Resume the faulting instruction. The handler returns from the trap, and the CPU re-executes the faulting instruction. This time, the page-table entry is valid, the translation succeeds, and the instruction completes. The process is unaware that a fault occurred.

The handler is markedly simpler for the other kinds of fault. An invalid access or a protection fault terminates the process, with no page allocation and no I/O. A minor fault skips steps 5 and 6 entirely (no frame allocation and no I/O), and it may also skip step 4 (the fault type is determined immediately from the page's presence in the page cache or from the page's status as a fresh anonymous page). A copy-on-write fault is a special case in which the handler duplicates a page instead of reading one; it is discussed in section 4.5.

4.4 Restarting the faulting instruction

A subtle but essential property of the page-fault mechanism is that the faulting instruction must be restartable. When the handler completes, it returns to the faulting instruction's address, and the CPU re-executes the instruction from the beginning. For this to be correct, the instruction must have no visible effect on the process's state when the fault occurs — that is, the instruction must either complete entirely or not at all, with no partial effect.

Most instructions satisfy this requirement naturally. A load instruction that faults has not yet written anything to its destination register; a store instruction that faults has not yet written anything to memory. The instruction's effects are all-or-nothing, and the handler can restart it safely.

Some instructions do not satisfy this requirement naturally, and the hardware must take care to make them restartable. The classic examples are string operations, which process many bytes in a single instruction. On x86, the MOVS instruction copies a block of bytes, and if it faults partway through (for example, because the source or destination crosses into an unmapped page), the instruction may have already copied some of the bytes. The hardware saves the state of the string operation — specifically, the count and the source and destination pointers — so that the handler can restart the instruction from the point at which it faulted, rather than from the beginning. The REP MOVS form is restartable in this sense; the handler adjusts the instruction's operands before returning.

The requirement for restartability has several consequences for the design of the memory system.

The fault must be reported before any effect. The hardware must detect the fault before the instruction writes anything, so that the restart is clean. This is why the MMU raises the fault on the translation, not after the data access.
The handler must preserve the process's state. The handler runs on the kernel stack and must not modify the process's registers (except as required to restart the instruction). If the handler needs to use registers, it saves and restores them.
The handler must not have visible side effects. The handler's work — reading the page from disk, updating the page table — must not be visible to the process except through the resumed instruction. In particular, the handler must not change the process's address space in a way that the process could observe before the faulting instruction completes.
The hardware must cooperate. On architectures with complex instructions (string operations, vector operations, transactional memory), the hardware must save enough state for the handler to restart the instruction. This is one reason these instructions are more expensive to fault on.

The combination of these requirements makes the page-fault handler one of the most delicate pieces of kernel code. It must operate transparently, correctly, and efficiently, and any bug in the handler — a missed register save, an incorrect restart address, a race with another core — produces symptoms that are extremely difficult to debug.

4.5 Copy-on-write faults

Copy-on-write (COW) is one of the most elegant applications of the page-fault mechanism. It allows two processes to share a page of memory, but ensures that each process has its own private copy as soon as it writes to the page. The mechanism is implemented entirely through a special kind of page fault.

The setup is straightforward. When a page should be shared but will eventually need to be private — the classic case is a page of a parent process's address space that is being inherited by a child via fork — the operating system maps the same physical frame into both processes' page tables, but marks the pages read-only in both. The processes share the page, and neither can write to it because it is marked read-only.

When one of the processes attempts to write to the shared page, the MMU raises a protection fault: the access is a write, but the page is marked read-only. The error code tells the handler that this is a write to a read-only page. The handler then checks the process's VMAs and finds that the page is part of a copy-on-write region. Instead of terminating the process (which is what it would do for a genuine protection fault), the handler performs the copy:

Allocate a new frame. Take a frame from the free list (or evict a victim, as in a major fault).
Copy the page. Copy the contents of the shared frame into the new frame. On modern processors, this copy is fast (a few hundred nanoseconds per page) because it is entirely in memory.
Update the writing process's page table. Change the writing process's page-table entry to point to the new frame, with write permission.
Update the TLB. Invalidate the TLB entry for the page in the writing process, so that the next access will fetch the new translation.
Resume the faulting instruction. The process re-executes the write, which now succeeds because the page is writable.

The other process, the one that did not write, continues to share the original frame. Its page-table entry is unchanged, and the page remains read-only in its address space. If it later writes to the page, a copy-on-write fault occurs in its turn, and the same procedure creates a private copy for it.

The effect is that the two processes share the page until one of them writes, at which point only the written page is duplicated. For a parent process that forks and immediately calls execve — the common case for launching a new program — no page is ever written in either process, so no page is ever copied, and the fork is nearly free. For a parent process that forks and then continues to run, the pages that the parent and child both use are shared, and only the pages that one of them modifies are copied. This is a substantial memory saving on workloads that fork frequently.

Copy-on-write is used in several other contexts besides fork. Memory-mapped files that are mapped with MAP_PRIVATE are copy-on-write: the file is mapped read-only, and a write to a mapped page triggers a copy-on-write fault that creates a private copy for the writing process (without modifying the file on disk). Shared libraries' data pages are shared initially and copied when a process writes to them. Virtual machine snapshots share the running VM's pages until the running VM writes to them. In each case, the mechanism is the same: share the page, mark it read-only, and let the fault handler make the private copy when it is written.

The cost of a copy-on-write fault

A copy-on-write fault is more expensive than a minor fault but much cheaper than a major fault. It requires a frame allocation and a memory copy (a few hundred nanoseconds for 4 KB), but no disk I/O. The fault handler's trap overhead is the same as for any other fault, so the total cost is on the order of a few microseconds. This is why fork is so cheap on modern systems: the pages are shared, and the copies happen lazily, only when they are actually needed.

4.6 Fault-around and prefaulting

The cost of a fault is dominated by the trap overhead, not by the work of bringing in a single page. This observation motivates a set of techniques that reduce the number of faults by handling several pages at once.

Fault-around: When a page fault occurs on a file-backed page, the handler may map several adjacent pages at once, assuming that the process's locality will make them useful. The behaviour is like prepaging (Lesson 9.4), but implemented in the fault handler itself. On Linux, the fault handler maps up to 16 pages around the faulting page for a file-backed mapping, by default. The result is fewer faults: instead of faulting on every page of a sequentially accessed file, the process faults on every sixteenth page, and the intervening pages are already mapped when it reaches them. The trade-off is that the fault-around may map pages that the process never uses, wasting address space (though not necessarily physical memory, because the mapping is lazy).
Prefaulting: An application can explicitly request that a region of memory be mapped in advance, rather than waiting for the first access to fault. On Linux, the MAP_POPULATE flag to mmap populates a mapping in advance, and the madvise(MADV_WILLNEED) call advises the kernel that a region will be accessed soon. Prefaulting is useful for applications that know their access patterns — a database that knows it will scan a table, a program that knows it will read a file — and can avoid the per-page fault overhead by requesting the pages in bulk.
Fault-free access: For regions of memory that are accessed very frequently, the fault overhead can be avoided altogether by ensuring that the region is fully populated before the hot loop begins. This is sometimes called touching the memory: the application touches every page of the region once (for example, by writing a zero to each page) so that the faults occur in a controlled phase rather than in the middle of a hot loop. The faults still happen, but they are paid for upfront, and the hot loop runs without interruption. This is a standard technique in high-performance computing and in real-time systems.

The techniques have a common structure: they trade an increase in address-space or memory usage for a decrease in the number of faults. The optimal trade-off depends on the workload's locality and on the cost of a fault. A workload with good locality benefits from fault-around, because the pages it prefetches are the pages it will use. A workload with poor locality is hurt by fault-around, because the prefetched pages are wasted. The kernel's policy must balance the two.

4.7 The measured cost of a fault

The effective access time calculation of Lesson 9.4 assumed a fault cost of about 10 ms — the latency of a random access to a spinning magnetic disk. On a modern system, the actual cost of a fault varies enormously depending on the kind of fault and on the state of the system. The following table summarises the measured costs for the four kinds of fault on a typical 2025-era system.

Measured cost of page faults on a typical system
Fault type	Typical cost	Notes
Invalid access	~0.5 µs	The handler detects the invalid address and delivers `SIGSEGV`. The cost is the trap overhead and the VMA lookup.
Protection fault	~0.5 µs	The handler detects the protection violation and delivers `SIGSEGV`. Same cost as an invalid access.
Minor fault (fresh anonymous page)	~1–2 µs	The handler allocates a zero-filled frame (or maps a pre-zeroed frame) and updates the page table. No disk I/O.
Minor fault (page in page cache)	~1 µs	The page is already in the page cache; the handler maps it into the process's address space. No disk I/O and no frame allocation.
Copy-on-write fault	~2–5 µs	The handler allocates a frame and copies 4 KB from the shared page. Memory copy is fast but not free.
Major fault (SSD)	~100–200 µs	The handler reads the page from an NVMe SSD. The read itself is ~100 µs, plus the handler overhead.
Major fault (HDD, no queueing)	~5–10 ms	The handler reads the page from a spinning disk. The dominant cost is the seek time and the rotational latency.
Major fault (HDD, queued)	~5–20 ms	The I/O is queued behind other I/Os; the fault's effective latency includes the queueing delay.
Major fault (with writeback)	~10–40 ms	The handler must first write a dirty victim page to disk, then read the new page. Two disk accesses instead of one.

The range is striking: from 0.5 µs for an invalid access to tens of milliseconds for a major fault that requires writeback. The gap between the fast cases (minor faults, copy-on-write) and the slow cases (major faults) is four orders of magnitude, and this gap is the reason the fault rate must be so low for demand paging to be practical. A workload whose faults are mostly minor runs nearly at full speed; a workload whose faults are mostly major runs at a small fraction of the memory system's capability.

The distinction between minor and major faults is therefore central to the practical performance of demand paging. Systems that keep their working sets in memory — because they have enough memory, or because their page-replacement policies are effective — experience mostly minor faults, and their performance is close to the no-fault case. Systems whose working sets exceed their memory experience mostly major faults, and their performance collapses. The transition between the two regimes is the subject of Lesson 9.7 on thrashing.

4.8 The interaction with the scheduler

A major fault requires disk I/O, and disk I/O takes milliseconds — an eternity compared to the microseconds of a normal instruction. During the I/O, the faulting process cannot run, because the page it needs is not yet in memory. The operating system's response is to block the faulting process and run another process in its place.

The mechanism is straightforward. The page-fault handler schedules the I/O (by submitting a request to the disk driver) and marks the faulting process as waiting for I/O. It then returns control to the scheduler, which picks another process to run. When the disk I/O completes, the disk interrupt handler runs, marks the faulting process as ready, and returns to the scheduler, which may switch back to the faulting process if it is the highest-priority ready process.

This interaction between the fault handler and the scheduler has several consequences.

The system stays busy during the fault. The CPU is not idle while the disk I/O is in progress; the scheduler runs other processes. This is one of the reasons multiprogramming is valuable: even a single process that is faulting heavily does not waste the CPU, because other processes can use it.
The faulting process's latency is not the system's latency. The faulting process waits for the I/O, but the system as a whole continues to make progress. A system with a faulting process can still serve other requests; a system with only a faulting process is idle.
Faults can be pipelined. On a system with multiple processes, several faults can be outstanding at once: process A faults and waits for its page, then process B faults and waits for its page, and so on. The disk driver can queue the requests and service them in an order that minimises seek time (Lesson 11.5), so the effective throughput is higher than the sum of the individual fault times.
The scheduler's policy affects the fault rate. A scheduler that keeps a process running for a long quantum gives it a chance to bring its working set into memory, which reduces future faults. A scheduler that switches processes frequently gives each process only a short time before its pages are evicted, which increases the fault rate. This interaction between scheduling and paging is one of the reasons real schedulers are complex.

The interaction between the fault handler and the scheduler also produces a subtle class of problems. If a process faults and blocks on I/O, and the scheduler runs another process that immediately faults and blocks, and the third process does the same, the system can be in a state where most of its processes are waiting for I/O and the CPU is idle. This is a form of thrashing (Lesson 9.7), and it is one of the failure modes that a good page-replacement policy is designed to avoid.

4.9 Common misconceptions

"Every page fault requires a disk read."

No. A minor fault does not require any disk I/O, because the page is already in memory (in the page cache, or as a fresh zero-filled page). Only major faults require disk I/O. On typical workloads, minor faults vastly outnumber major faults.

"A page fault means the process has a bug."

In demand paging, a page fault is a normal event. The process is using its address space as intended, and the operating system is bringing in the pages it needs. A page fault indicates a bug only when the fault is an invalid access or a protection fault.

"The fault handler can allocate memory freely."

The fault handler runs in a restricted context. It cannot sleep (on most kernels), cannot allocate memory in ways that would themselves fault, and cannot block on locks held by the faulting process. This is why the handler's code is so carefully written.

"A copy-on-write fault is a protection fault."

A copy-on-write fault appears as a protection fault to the MMU: it is a write to a read-only page. But the handler distinguishes the two by checking the process's virtual memory areas; if the page is part of a copy-on-write region, the fault is a copy-on-write fault, not a genuine protection violation. The two have very different responses: the copy-on-write fault succeeds (with a copy), and the genuine protection fault terminates the process.

"Fault-around always improves performance."

Fault-around improves performance for workloads with spatial locality, because the pages it maps in advance are the pages the process will use. For workloads with poor locality, it wastes address space (and possibly memory), because the pages it maps are never used.

"The faulting instruction is not re-executed."

It is. The handler returns to the faulting instruction's address, and the CPU re-executes the instruction from the beginning. This is why the instruction must be restartable — that is, why it must have no partial effect when the fault occurs.

"A major fault is always slower than a minor one."

A major fault is usually slower, because it requires disk I/O, but the difference depends on the storage device. A major fault on an NVMe SSD (~100 µs) is faster than a major fault on a spinning disk (~10 ms) by a factor of a hundred. And a minor fault on a busy system may take longer than its nominal cost because the CPU is contended.

"A page fault always blocks the faulting process."

A minor fault does not block the process: the handler completes the fault inline, and the process resumes immediately. Only a major fault (which requires I/O) blocks the process, and even then, the scheduler runs another process while the I/O is outstanding.

05 Worked example

The following example traces the page-fault handler for a specific fault, showing the state of the process, the page table, and the physical memory at each step. It then computes the total cost of a typical page-fault sequence and shows how the cost is amortised over a process's life.

A major fault on a file-backed page

Consider a process that has mapped a 64 KB file with mmap and is reading it sequentially. The file is not in the page cache (it has not been read recently). The process has just read the first 4096 bytes of the file (page 0), which faulted in and was loaded into frame 12. Now the process reads the next byte, at offset 4096 — the start of page 1.

The state before the fault:

Item	Value
Faulting logical address	0x7F0000001000
Page number	page 1 of the mapping
Page-table entry	valid = 0
Page-table entry's protection	r--
Page 0's frame	frame 12 (in memory)
Page 1's frame	none (page 1 is not in memory)
Free frames	3 (frames 20, 21, 22)
File (on disk)	page 1 is at file offset 4096

Step 1: the CPU raises the fault

The process executes a load instruction that reads the byte at logical address 0x7F0000001000. The MMU looks up the page-table entry for the page containing that address and finds the valid bit clear. The MMU raises a page fault: it stores the faulting address in CR2, pushes an error code onto the stack, and transfers control to the kernel's page-fault handler. The error code indicates that the fault was a read (not a write) on a not-present page (not a protection fault).

Step 2: the handler validates the address

The handler reads CR2 and finds the faulting address. It looks up the address in the process's virtual memory areas (VMAs) and finds the mapping for the file. The address 0x7F0000001000 is within the mapping's range, and the region's permissions are r-- (read-only, as is typical for a MAP_PRIVATE file mapping). The handler checks that the access type (read) matches the region's permissions; it does.

The address is valid, and the access is permitted. The fault is therefore a legitimate demand-paging fault, not an invalid access or a protection violation.

Step 3: the handler determines the fault type

The handler checks whether the page is in the page cache. The file has not been read recently, so page 1 of the file is not in the cache. The fault is therefore a major fault, and the handler must read the page from the file.

Step 4: the handler obtains a free frame

The handler consults the free list and finds frame 20 available. It takes frame 20 for page 1. If no frame had been available, the handler would have invoked the page-replacement policy (Lesson 9.6) to choose a victim, and would have written the victim back to disk if it was dirty. In this case, a free frame is available, so the handler proceeds.

Step 5: the handler reads the page

The handler schedules an I/O operation to read page 1 of the file (4096 bytes at file offset 4096) into frame 20. Because the I/O is slow (say, 150 µs for an NVMe SSD or 8 ms for a spinning disk), the handler cannot simply wait. It marks the faulting process as blocked on I/O, and returns to the scheduler. The scheduler picks another process (if one is ready) and runs it.

When the disk I/O completes, the disk interrupt handler runs, marks the faulting process as ready, and returns to the scheduler. The scheduler may switch back to the faulting process if it is the highest-priority ready process.

Step 6: the handler updates the page table

Once the page is in frame 20, the handler updates the page-table entry for page 1:

Frame number: set to 20.
Valid bit: set to 1.
Protection bits: set to the region's permissions (read-only, matching the mapping).
Accessed bit: set to 1 (the page has been accessed).
Dirty bit: set to 0 (the page has not been written; it is a read-only mapping).

The handler also updates the process's memory accounting structures: the process's RSS (resident set size) is increased by one page, and frame 20 is marked as allocated to the process.

Step 7: the handler updates the TLB

The TLB may hold a stale entry for page 1 (if the page was mapped before and then unmapped, or if the page's mapping has changed). The handler invalidates the TLB entry for the faulting address, using the appropriate instruction (INVLPG on x86-64, or a TLB shootdown if the mapping is shared with other cores). The next access will miss in the TLB and re-fetch the translation from the page table.

Step 8: the handler resumes the faulting instruction

The handler restores the process's register state, returns from the trap, and the CPU re-executes the faulting instruction. This time, the page-table entry is valid, the translation succeeds, and the load instruction completes. The process reads the byte at offset 4096 of the file, and continues its sequential scan.

The cost of this fault

The total cost of the fault is the sum of the trap overhead, the handler's work, and the I/O:

Component	Cost (NVMe SSD)	Cost (spinning disk)
Trap into the kernel	0.3 µs	0.3 µs
Address validation (VMA lookup)	0.2 µs	0.2 µs
Page-cache lookup	0.1 µs	0.1 µs
Frame allocation	0.3 µs	0.3 µs
I/O scheduling and disk read	100 µs	8,000 µs
Page-table update	0.3 µs	0.3 µs
TLB invalidation	0.1 µs	0.1 µs
Return from trap	0.3 µs	0.3 µs
Total	~101 µs	~8,001 µs

The I/O dominates the cost in both cases. On the NVMe SSD, the I/O is about 100 µs, and the handler's own overhead is about 1.6 µs — less than two percent of the total. On the spinning disk, the I/O is about 8 ms, and the handler's overhead is negligible. This is why the choice of storage device matters so much for demand-paging performance: an NVMe SSD is about eighty times faster than a spinning disk for a page fault, and this difference dominates the total cost.

Amortising the cost over a process's life

A single major fault is expensive, but a process typically experiences only a small number of major faults — one per page in its working set that is not already in the page cache. The cost of those faults is amortised over the process's entire lifetime, which is typically millions of accesses. Consider a process that:

Has a working set of 1000 pages (4 MB).
Experiences a major fault on each page (worst case: none of the pages are in the page cache initially).
Runs for 10⁹ memory accesses.
Has a fault rate of 10⁻⁶ in steady state (the working set is resident, and occasional faults occur from eviction).

The cost of the initial fault-in is 1000 × 100 µs = 100 ms (on an NVMe SSD) or 1000 × 8 ms = 8 seconds (on a spinning disk). The cost of the steady-state faults is 10⁹ × 10⁻⁶ × 100 µs = 100 seconds (NVMe) or 8,000 seconds (spinning disk). Note that the steady-state cost dominates, even though the fault rate is very low — because the process runs for so long.

The steady-state cost is the price of the process's working set not fitting perfectly in memory. A process with a working set that fits exactly, and a replacement policy that keeps it resident, experiences no steady-state faults, and its performance is limited only by the memory system's speed. This is why the page-replacement policy (Lesson 9.6) is so important: it determines whether the working set stays resident.

A copy-on-write fault in the same process

Suppose the same process, after forking a child, attempts to write to a page that is shared with the child (because the page was inherited via fork). The page is marked read-only in both processes. The write fault occurs, and the handler distinguishes it from a genuine protection fault by checking the VMA: the region is a copy-on-write region, so the fault is a copy-on-write fault.

The handler's steps are:

Allocate a new frame (frame 25, say).
Copy the 4 KB of the shared page into frame 25.
Update the writing process's page-table entry to point to frame 25, with write permission.
Invalidate the TLB entry for the page.
Resume the faulting instruction.

The cost is a frame allocation (~0.3 µs) plus a 4 KB memory copy (~0.5 µs) plus the trap overhead (~1.5 µs), for a total of about 2.5 µs. The child process's page-table entry is unchanged; it still points to the original frame, and its page remains read-only. If the child later writes to the same page, a copy-on-write fault occurs in its turn, and the same procedure creates a private copy for it.

Copy-on-write faults are cheap compared to major faults, but they are much more expensive than normal memory accesses. A program that writes to a shared page after forking pays a copy-on-write fault for each page it writes. This is why the traditional advice is to fork and immediately exec — the child calls execve before writing anything, so no copy-on-write faults occur and the fork is nearly free. A child that writes to its memory before exec'ing pays the copy cost.

06 Interactive activity

Activity · observe and measure page faults on a live system

The goal of this activity is to observe the page-fault mechanism on a real system, distinguish minor from major faults, and measure the cost of a fault. Work through the steps in your course VM.

Observe minor and major faults with /usr/bin/time. The /usr/bin/time -v utility reports the minor and major fault counts separately. Run a small program and observe its fault counts.
```
/usr/bin/time -v ./hello
# Look for:
#   Minor (reclaiming a frame) page faults:  N
#   Major (requiring I/O) page faults:       M
```
Typically, the minor faults vastly outnumber the major faults, because most of the program's pages are already in the page cache (the C library, the dynamic linker, the program's own code). What is the ratio in this case?
Force major faults by clearing the page cache. On a Linux system, you can force the page cache to be cleared by writing to /proc/sys/vm/drop_caches (with root privileges). Run a program before and after the cache is cleared, and compare the major fault counts.
```
# Warm cache
/usr/bin/time -v ./hello

# Clear the cache
sync
echo 3 | sudo tee /proc/sys/vm/drop_caches

# Cold cache
/usr/bin/time -v ./hello
```
The cold run should have many more major faults than the warm run. This is the demand-paging mechanism in action: the pages are loaded on demand, and the page cache holds them for subsequent accesses.

Distinguish the four kinds of fault. Write four small programs, each of which triggers a different kind of fault:

/* 1. Invalid access: read from NULL */
int main(void) {
    volatile int *p = (int *)0;
    int x = *p;         /* invalid access → SIGSEGV */
    return x;
}

/* 2. Protection fault: write to a read-only page */
#include <sys/mman.h>
#include <string.h>
int main(void) {
    void *p = mmap(NULL, 4096, PROT_READ,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    memset(p, 0, 4096);   /* protection fault → SIGSEGV */
    return 0;
}

/* 3. Minor fault: touch a fresh anonymous page */
#include <stdlib.h>
int main(void) {
    char *p = malloc(4096);
    p[0] = 1;             /* minor fault on first touch */
    return 0;
}

/* 4. Major fault: read a file that is not cached */
#include <fcntl.h>
#include <unistd.h>
int main(int argc, char **argv) {
    int fd = open(argv[1], O_RDONLY);
    char buf[4096];
    read(fd, buf, 4096);
    return 0;
}

Run each program with /usr/bin/time -v and observe the fault counts and the program's behaviour. The first two programs should terminate with SIGSEGV; the third should have a few minor faults; the fourth should have one major fault (for the file's first page) if the cache is cold.

Observe copy-on-write faults. Write a program that allocates a large buffer, forks, and then writes to one page of the buffer in the child. Use /proc/<pid>/smaps or /usr/bin/time -v to observe the fault behaviour.
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    size_t n = 10 * 1024 * 1024;   /* 10 MB */
    char *buf = malloc(n);
    memset(buf, 1, n);              /* touch every page */

    pid_t pid = fork();
    if (pid == 0) {
        /* child */
        buf[0] = 2;                 /* copy-on-write fault */
        buf[4096] = 3;              /* another COW fault */
        _exit(0);
    }
    wait(NULL);
    free(buf);
    return 0;
}
```
Run the program with /usr/bin/time -v and observe the fault counts. The parent's touches before the fork cause minor faults (for the buffer's pages). The child's writes cause copy-on-write faults, which count as minor faults in the report. How many faults does the child experience? Why?
Measure the cost of a major fault. On a VM with an NVMe SSD, write a program that reads a file twice: once with a cold cache (after clearing the cache) and once with a warm cache. Measure the time for each read, and derive the cost of a major fault.
```
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

int main(int argc, char **argv) {
    int fd = open(argv[1], O_RDONLY);
    if (fd < 0) { perror("open"); return 1; }

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);

    char buf[65536];
    ssize_t n;
    while ((n = read(fd, buf, sizeof(buf))) > 0)
        ;

    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec)
                   + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("%.4f s\n", elapsed);
    return 0;
}
```
Create a 100 MB file (with dd), clear the cache, and read the file. Then read it again without clearing the cache. Compute the difference in time and divide by the number of pages (100 MB / 4 KB = 25,600 pages) to estimate the cost per major fault.
Observe fault-around with strace. Use strace to count the system calls a program makes when it reads a file sequentially.
```
strace -c ./read_file bigfile
```
If the file is read with read, the program makes one system call per 64 KB buffer. If the file is mapped with mmap and read through the mapping, the fault handler maps several pages at a time (fault-around), so the number of faults is much smaller than the number of pages. Compare the two.
Use perf to count page-fault events. Use perf stat to count the page-fault events for a program.
```
perf stat -e page-faults,minor-faults,major-faults ./workload
```
The page-faults event counts all faults; minor-faults and major-faults break them down by type. Run the workload with a cold cache and a warm cache, and compare the counts.
Read the Linux kernel's page-fault documentation. If you have access to the Linux kernel source, read the function do_page_fault in arch/x86/mm/fault.c and the documentation in Documentation/vm/. What are the main paths the handler takes? How does the handler distinguish a minor fault from a major one? How does it handle the copy-on-write case?

Reflect: the page-fault handler is one of the most performance-critical pieces of an operating system's kernel. A minor fault takes a few microseconds, a major fault takes a few hundred microseconds (on an SSD) to a few tens of milliseconds (on a spinning disk). The difference between the two is enormous, and it determines the performance of any workload whose working set does not fit exactly in memory. What can a programmer do to reduce the fault rate? What can the operating system do? What can the hardware do? What is the right balance between these three, and why?

07 Knowledge check

Check your understanding

Question 1

Describe the trap mechanism by which the MMU raises a page fault. What information does the hardware deliver to the handler, and why is each piece of information necessary?

Show answer

When the MMU cannot complete a translation — because the page-table entry's valid bit is clear, or because the access violates the page's protection — it raises an exception: a trap to the operating system's kernel. The trap transfers control to a handler whose address is recorded in the interrupt descriptor table, and the handler runs in kernel mode on the faulting process's kernel stack. On x86-64, the page-fault exception is #PF, and the hardware delivers three pieces of information. First, the faulting instruction's address, saved in the return address on the stack, so that the handler can resume the instruction. Second, the faulting address, placed in the CR2 control register. The handler reads CR2 to learn which logical address caused the fault; the address is logical, not physical, because the physical address is what could not be computed. Third, the error code, pushed onto the stack by the hardware. The error code describes the fault: whether the access was a read, a write, or an instruction fetch; whether the fault occurred in user or kernel mode; whether the page was present but the access was forbidden (a protection fault) or the page was not present (a not-present fault). Each piece of information is necessary. The faulting instruction's address is what allows the handler to resume the instruction after the fault is handled. The faulting address is what allows the handler to determine which page to load and which page-table entry to update. The error code is what allows the handler to distinguish the four kinds of fault — a read on a not-present page is a demand-paging fault, but a write on a read-only page is either a protection fault or a copy-on-write fault, and the two require very different responses.

Question 2

Describe the four kinds of page fault. For each, state the cause, the handler's response, and whether the process continues to run.

Show answer

The four kinds of fault are:

Invalid access. The faulting address is not part of the process's address space — it is not within any of the process's virtual memory areas. The address is a bug: the process has computed a pointer that does not correspond to any mapped region. The handler terminates the process, typically with the SIGSEGV signal. The process does not continue to run.
Protection fault. The faulting address is within a valid region, but the access violates the region's permissions — for example, a write to a read-only region. The fault is also a bug, and the handler terminates the process with SIGSEGV. (The exception is the copy-on-write case, where the page is read-only but the VMA indicates that the fault should be handled as a copy-on-write fault; see below.) The process does not continue to run.
Minor fault. The faulting address is valid, the access is permitted, and the page is already in memory (or can be satisfied without disk I/O, as in the case of a fresh zero-filled anonymous page). The handler updates the page-table entry and resumes the instruction. The process continues to run.
Major fault. The faulting address is valid, the access is permitted, and the page is not in memory. The handler must read the page from the backing store (the file for a file-backed page, the swap area for an anonymous page). The fault is slow — a few hundred microseconds on an SSD, tens of milliseconds on a spinning disk — and the faulting process blocks on the I/O while another process runs. When the I/O completes, the handler resumes the faulting instruction, and the process continues to run.

There is a special case within the protection-fault category: the copy-on-write fault. The fault appears to the MMU as a write to a read-only page, but the handler checks the VMA and finds that the page is part of a copy-on-write region. Instead of terminating the process, the handler allocates a new frame, copies the shared page into it, updates the writing process's page table to point to the new frame with write permission, and resumes the instruction. The process continues to run.

Question 3

Trace the page-fault handler step by step for a major fault on an anonymous page that has been swapped out. Why does the handler block the process, and what happens while the process is blocked?

Show answer

For a major fault on an anonymous page that has been swapped out, the handler proceeds as follows. (1) Trap. The MMU raises the fault, placing the faulting address in CR2 and the error code on the stack. The handler begins execution in kernel mode. (2) Validate the address. The handler reads CR2 and looks up the faulting address in the process's VMAs. The address is within a valid region (the heap or the stack), so it is not an invalid access. (3) Check the protection. The handler checks that the access type matches the region's permissions. If the fault is a read or a write to a writable region, the access is permitted. (4) Determine the fault type. The handler checks whether the page is in memory. The page-table entry's valid bit is clear, and the entry's swap-related fields indicate that the page is in the swap area. The fault is major. (5) Obtain a free frame. The handler takes a frame from the free list, or invokes the page-replacement policy to evict a victim. If the victim is dirty, the handler writes it to disk (or to the swap area) before reusing its frame. (6) Read the page. The handler schedules an I/O operation to read the page from the swap area into the frame. Because the I/O is slow, the handler cannot simply wait: it marks the faulting process as blocked on I/O, saves the process's state, and returns control to the scheduler. (7) The scheduler runs another process. While the faulting process is blocked, the scheduler picks another ready process and runs it. The CPU is therefore not idle during the I/O; the system continues to make progress even though the faulting process is waiting. (8) The I/O completes. The disk interrupt handler runs, marks the faulting process as ready, and returns to the scheduler. The scheduler may switch back to the faulting process if it is the highest-priority ready process. (9) Update the page table. The handler updates the page-table entry: the frame number is set, the valid bit is set, the protection bits are set, and the swap-related fields are cleared. (10) Invalidate the TLB. The handler invalidates any stale TLB entry for the page, so that the next access re-fetches the translation from the page table. (11) Resume the instruction. The handler returns from the trap, and the CPU re-executes the faulting instruction, which now succeeds. The process never knows that a fault occurred. The handler blocks the process because the I/O is slow — milliseconds — and the CPU would otherwise be idle for the entire duration. By blocking the process and running another, the system uses the CPU productively during the I/O. The blocked process is woken when the I/O completes, and it resumes as though nothing had happened.

Question 4

What is the restartability requirement, and why does it matter for the design of the page-fault handler? Give an example of an instruction that is difficult to make restartable.

Show answer

The restartability requirement is the property that the faulting instruction must be re-executable from the beginning after the fault is handled. For this to be correct, the instruction must have no visible effect on the process's state when the fault occurs — it must either complete entirely or not at all. Most instructions satisfy this requirement naturally. A load that faults has not yet written to its destination register; a store that faults has not yet written to memory. The instruction's effects are all-or-nothing, and the handler can restart it safely. The requirement matters for the design of the page-fault handler because the handler must be written to preserve the process's state and to resume the instruction exactly. It must not modify the process's registers (except as required to restart the instruction); it must not change the process's address space in a way that the process could observe before the faulting instruction completes; and it must not have side effects that the process could detect. The handler must also save and restore its own state, because it runs on the kernel stack and may be interrupted by an interrupt. An example of an instruction that is difficult to make restartable is the x86 string operation, such as MOVS with a REP prefix, which copies a block of bytes in a single instruction. If the instruction faults partway through — for example, because the source or destination crosses into an unmapped page — it may have already copied some of the bytes. The hardware saves the state of the string operation — specifically, the count and the source and destination pointers — so that the handler can restart the instruction from the point at which it faulted, rather than from the beginning. The REP MOVS form is restartable in this sense, but only because the hardware and the handler cooperate to preserve the intermediate state. Other complex instructions — vector operations, transactional memory, string operations with overlapping source and destination — require similar hardware support, which is one reason these instructions are more expensive to fault on.

Question 5

What is a copy-on-write fault, and how does the handler distinguish it from a genuine protection fault? Describe the handler's steps for a copy-on-write fault, and explain why copy-on-write is important for the efficiency of fork.

Show answer

A copy-on-write fault is a page fault that occurs when a process writes to a page that is shared with another process and is marked read-only in both processes' page tables. The fault appears to the MMU as a write to a read-only page — a protection fault — but the handler distinguishes it from a genuine protection fault by checking the process's virtual memory areas. If the page is part of a copy-on-write region (a region that is shared and will need to be private if written), the handler treats the fault as a copy-on-write fault, not a protection violation. The handler's steps are: (1) allocate a new frame from the free list (or evict a victim); (2) copy the contents of the shared frame into the new frame; (3) update the writing process's page-table entry to point to the new frame, with write permission; (4) invalidate the TLB entry for the page in the writing process; (5) resume the faulting instruction. The other process, the one that did not write, continues to share the original frame, and its page remains read-only. If it later writes to the same page, a copy-on-write fault occurs in its turn, and the same procedure creates a private copy for it. Copy-on-write is important for the efficiency of fork because the traditional implementation of fork would copy the parent's entire address space into the child. For a parent with a large address space — hundreds of megabytes or gigabytes — the copy would take milliseconds and consume a large amount of memory. With copy-on-write, the child's page table is a copy of the parent's, mapping the same frames, and both page tables are marked read-only. The two processes share all pages until one writes, at which point only the written page is copied. For a process that forks and then immediately calls execve — the common case for launching a new program — no page is ever written, so no page is ever copied, and the fork is nearly free. This is one of the key optimisations that makes the Unix process model efficient.

08 Unit discussion

Discussion prompt

The page-fault handler is the point at which the hardware and the software cooperate most intimately. The hardware detects the fault, saves the minimal state needed to describe it (the faulting address, the error code, the instruction's address), and traps to the kernel. The software interprets the fault, brings the required page into memory, updates the page tables, and resumes the instruction. The process never knows that the fault occurred: the instruction is re-executed, and its result is identical to what it would have been if the page had been in memory all along.

This cooperation works because of a property that the instruction set designers went to considerable trouble to ensure: restartability. Every instruction that can fault must be re-executable from the beginning, with no visible effect on the process's state when the fault occurs. On simple architectures with simple instructions, restartability is easy to ensure. On complex architectures with string operations, vector operations, and transactional memory, ensuring restartability is a substantial burden on the hardware designer, and it is one of the reasons these instructions are expensive.

The tension between functionality and restartability is a recurring theme in computer architecture. Each new feature that an instruction set adds — a new addressing mode, a new vector operation, a new transactional primitive — must be designed with the fault mechanism in mind. A feature that cannot be made restartable cannot be used with virtual memory, or it must be implemented in a way that limits its performance. This is one of the constraints that shapes the design of every processor that supports paging.

Consider the last major architectural features you have used — AVX-512 vector operations, transactional memory, the memcpy instruction on some architectures, the memory-mapped I/O of a GPU. How are they made restartable? What does the hardware save when one of them faults? What would happen if it were not restartable? And what does the answer to these questions tell you about the way hardware and software co-evolve? Post your response to the Unit 9 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 9.6. Aim to spend 60–90 minutes on it.

Classify the faults. For each of the following, state which kind of page fault occurs (invalid access, protection fault, minor fault, major fault, copy-on-write fault), and describe the handler's response.
- Reading from address 0 on a system where page 0 is unmapped.
- Writing to a page of a MAP_PRIVATE file mapping that is currently shared with another process.
- Reading the first byte of a large file that has just been mapped with mmap and is not in the page cache.
- Writing to the code segment of a program.
- Reading a page of a program that has been swapped out to disk.
- Writing to a freshly allocated block of malloc memory that has never been touched.
- Reading a page of a shared library that is already in memory in another process's address space.
Trace a minor fault. Consider a process that has just allocated a 4 KB block with malloc. The block is not yet mapped to a physical frame. Trace the page-fault handler's steps for the first write to the block. What is the cost? How does it compare to the cost of a major fault?
Trace a copy-on-write fault. Consider a parent process that has a 100 MB address space and calls fork. The child then writes to 1 MB of the shared pages. Trace the page-fault handler's steps for the child's writes. How many copy-on-write faults does the child experience? What is the total cost of those faults? Compare this to the cost of a traditional fork that copies the entire 100 MB.
Compute the amortised cost of a page fault. A process runs for 10⁹ memory accesses. Its working set is 500 pages. It has a fault rate of 10⁻⁶ in the steady state, and each fault costs 5 µs (a minor fault, on average). Compute: (a) the total cost of the steady-state faults; (b) the total time the process would take without faults (assuming 100 ns per access); (c) the percentage of time spent on faults.
Design a fault-around policy. A kernel uses fault-around with a window of N pages around the faulting page. The kernel's page-fault rate without fault-around is 10⁻⁴ accesses, and each fault costs 5 µs. With fault-around, the fault rate is reduced by a factor of N, but half of the mapped pages are never used (the kernel wastes address space but not physical memory). Compute the effective fault rate and the effective access time for N = 1, 4, 8, 16, and 32. Which N is optimal? What does the answer depend on?
Measure the cost of a fault on your system. Write a program that allocates a large buffer, touches every page of it, and measures the time. Then run it with the page cache cleared (cold start) and warm (the buffer's pages are already in the page cache from a previous run). Measure the difference, and derive the cost per fault. How does the cost compare to the numbers in the lesson's table?
Explain the scheduler interaction. Write a short paragraph (200–250 words) explaining how the page-fault handler and the scheduler cooperate to keep the CPU busy during a major fault. Your explanation should include: (a) what the handler does when it needs to read a page from disk; (b) what the scheduler does while the I/O is outstanding; (c) what happens when the I/O completes; and (d) why the interaction is important for system performance.
Reflect. In your own words, explain why the faulting instruction must be restartable, and give one example of an instruction that would be difficult to make restartable. Then describe one situation in your own experience — a program you have written or a system you have used — where the page-fault behaviour was important. What was the fault rate, and how did it affect the performance?

10 Summary

A page fault is a trap from the memory-management unit to the operating system, raised when an access cannot be completed by the hardware alone. It is the fundamental event that makes demand paging possible.
On x86-64, the faulting address is placed in the CR2 register and an error code is pushed onto the stack. The error code describes the access type (read, write, execute), the privilege level (user or kernel), and the reason (not-present or protection).
There are four kinds of fault: invalid access (the address is not part of the process's address space), protection fault (the address is valid but the access is forbidden), minor fault (the page is in memory and the handler just updates the page table), and major fault (the page is on disk and the handler must read it in).
A copy-on-write fault is a special case of protection fault: the page is read-only and shared, and the handler duplicates it for the writing process. It is the mechanism behind fork and MAP_PRIVATE file mappings.
The page-fault handler's essential steps are: trap, validate the address, check the protection, determine the fault type, obtain a free frame, read the page, update the page table, invalidate the TLB entry, and resume the faulting instruction.
The faulting instruction must be restartable: it must have no visible effect on the process's state when the fault occurs, so that the handler can re-execute it from the beginning. Most instructions satisfy this naturally; string and vector operations require special hardware support.
Fault-around and prefaulting reduce the number of faults by mapping several pages at once. Fault-around is implemented in the handler; prefaulting is requested by the application.
The measured cost of a page fault varies enormously: from about 0.5 µs for an invalid access to about 40 ms for a major fault on a spinning disk with writeback. The gap between the fast cases (minor faults) and the slow cases (major faults) is four orders of magnitude.
A major fault blocks the faulting process, because the I/O is slow. The scheduler runs another process while the I/O is outstanding, so the CPU is not idle. The blocked process is woken when the I/O completes.
The interaction between the fault handler and the scheduler is what makes multiprogramming valuable even for a single heavily-faulting process. A system with multiple processes can pipeline multiple outstanding faults, so the effective throughput is higher than the sum of the individual fault times.

Looking ahead

This lesson presented the page-fault handler in detail: the trap mechanism, the taxonomy of faults, the handler's steps, the restartability requirement, and the measured cost of a fault. It referred several times to the page-replacement policy, which is the subject of Lesson 9.6. The policy decides which page to evict when a new page must be brought in and no free frame is available. Its choice affects the fault rate, the amount of I/O, and the overall performance of the system. The lesson that follows presents the classical replacement algorithms — FIFO, LRU, clock, and their variants — and analyses their behaviour on realistic workloads.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 10, Sections 10.2–10.3.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 21 and 22. Available online at ostep.org.
Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.7–9.9.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.3.
Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 4, Paging, and Chapter 6, Interrupt and Exception Handling.
Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux implementation of the page-fault handler and the OOM killer.
Gorman, M. Understanding the Linux Virtual Memory Manager. Prentice Hall, 2004. A detailed reference for the Linux memory-management subsystem, including the page-fault handler and the page-replacement policy.
Linux kernel source: arch/x86/mm/fault.c (the x86-64 page-fault handler), mm/memory.c (the generic page-fault handling code), and Documentation/vm/.
Linux man-pages: man 2 mmap, man 2 mprotect, man 2 madvise, man 2 fork, man 5 proc, man 1 perf-stat, man 1 strace, man 1 ltrace, man 1 time.