Lesson 9.4: Demand Paging

01 Introduction

Lesson 9.1 introduced paging: the division of the logical address space into fixed-size pages and physical memory into frames of the same size. Lesson 9.2 presented the multi-level page table, the structure that makes the translation feasible, and Lesson 9.3 presented the translation lookaside buffer, the small hardware cache that makes the translation fast. Those three lessons all assumed that a page, once accessed, is in memory: the page table holds the frame number for every page of the process's address space, and an access to a page simply reads from or writes to the frame.

That assumption is not always justified. A process's address space may be larger than the physical memory available to hold it: a program's code, data, heap, and stack may exceed the total physical memory of the machine, or the sum of the address spaces of the processes running at the same time may exceed it. In either case, it is impossible to have every page of every process in memory at once. What happens when a process accesses a page that is not in memory?

Demand paging is the answer. The idea is that the operating system does not load a page into memory until it is actually needed. A page that has never been accessed is not in memory at all, and the page-table entry for it has its valid bit (Lesson 9.1) cleared. When the process accesses such a page, the MMU raises a page fault, which transfers control to the operating system's page-fault handler. The handler brings the page in from disk — from a region called the backing store or swap area — installs it in a free frame, updates the page table, and resumes the faulting instruction. The process continues as though nothing had happened, and the page is now present in memory for any subsequent accesses.

Demand paging is the mechanism that makes overcommitment possible — the situation in which the total memory demanded by the processes in a system exceeds the physical memory available. It is what allows a machine with 8 GB of RAM to run processes whose combined address spaces exceed 8 GB, and it is what allows a single process with a 4 GB address space to run on a machine with 1 GB of memory. It is one of the most important ideas in operating-system design, and it is the foundation on which the rest of Unit 9 builds.

This lesson presents the mechanism. It defines demand paging, describes the role of the valid bit and the backing store, and presents the outline of the page-fault service routine. It presents pure demand paging and prepaging, and explains why locality of reference makes demand paging work. It presents the effective access time calculation, which quantifies the cost of a page fault and shows why the fault rate must be very low for demand paging to be practical. It presents memory-mapped files and the role of demand paging in their implementation, and it closes with a discussion of the trade-offs and the practical considerations. The detailed page-fault handling procedure is the subject of Lesson 9.5, and the choice of which page to evict when memory is full is the subject of Lesson 9.6.

Prerequisites

This lesson builds directly on Lessons 9.1, 9.2, and 9.3. The paging model (pages and frames), the page table and its entry fields (particularly the valid bit), and the TLB are all assumed. The memory hierarchy from Lesson 8.1 — in particular the enormous latency gap between main memory and disk, and the concept of locality of reference — is used throughout. The distinction between the memory-hierarchy levels that the hardware manages (caches, TLB) and those the operating system manages (main memory, disk) is important, because demand paging is an operating-system mechanism that operates at the main-memory/disk boundary. No prior knowledge of the page-fault handler, the backing store, or the effective access time calculation is assumed.

02 Learning objectives

By the end of this lesson you will be able to

Define demand paging and explain why it makes overcommitment possible.
Describe the role of the valid bit, the backing store, and the pager.
Distinguish pure demand paging from prepaging and explain the trade-off between them.
Compute the effective access time with a given page-fault rate, and explain why the fault rate must be low.
Describe how memory-mapped files and shared libraries are implemented with demand paging.

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

03 Required reading

Operating System Concepts — Chapter 10, Sections 10.1–10.3, Background, Demand Paging, and Copy-on-Write. The standard treatment of the demand-paging mechanism, the valid bit, and the page-fault service routine.
OSTEP — Chapter 21, Swapping: Mechanisms, and Chapter 22, Swapping: Policies (the introductory sections). OSTEP's treatment of the swap space, the page-fault mechanism, and the relationship between demand paging and the memory hierarchy is the clearest available account, and it is the basis for the worked example in this lesson.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.3, Virtual Memory, through the subsection on demand paging. A complementary treatment that develops the mechanism from first principles.
Silberschatz et al. — Chapter 10, Sections 10.1–10.3. Read the discussion of the effective access time and the worked examples of the fault-rate calculation.
Denning, P. J. — Virtual Memory. ACM Computing Surveys, 1970. The paper that framed the demand-paging mechanism and the working-set concept for a generation of system designers.
Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.7–9.10. The programmer's view of demand paging, including memory-mapped files and the mmap interface.
Linux kernel documentation — Documentation/admin-guide/mm/ and Documentation/vm/, which contain the Linux kernel's documentation of the page-fault handler, the swap subsystem, and the memory-mapping interface.
Linux man pages: man 2 mmap, man 2 mprotect, man 2 madvise, man 2 fork, man 2 swapon, man 5 proc (the /proc/<pid>/stat, /proc/<pid>/status, and /proc/<pid>/smaps interfaces, which report page-fault counts and swap usage).

Reading strategy

Read the Silberschatz section first for the formal statement of the mechanism and the effective access time calculation. Then read the OSTEP chapters on swapping for the modern view of how demand paging interacts with the memory hierarchy, including the role of the swap area and the relationship between the page cache and the memory-mapped files. Pay particular attention to the effective access time calculation: the numbers are stark, and they show why the fault rate must be extremely low — on the order of one fault per million accesses or less — for demand paging to be practical. The formula and the reasoning behind it are the core of this lesson's quantitative content.

04 Core content

4.1 The demand paging idea

In the paging schemes of Lessons 9.1–9.3, the page table is assumed to contain a valid frame number for every page of the process's address space. Every page is in memory, and every access is either a TLB hit (fast) or a TLB miss followed by a page-table walk (slower, but still bounded by the memory latency). The process's entire address space must fit in physical memory, and the sum of the address spaces of all running processes must fit as well.

Demand paging relaxes this assumption. The operating system does not load a process's pages into memory at startup. Instead, it marks every page as not present in the page table — the valid bit is cleared — and begins executing the process with an empty frame allocation. When the process accesses a page that is not in memory, the MMU raises a page fault, and the operating system's page-fault handler brings the page in from disk. The handler installs the page in a free frame, updates the page table to mark the page as present, and resumes the faulting instruction. The process continues as though the page had been in memory all along.

The key insight is that a process does not need all its pages to be in memory at once. A program's execution has locality (Lesson 8.1): at any moment, the process is actively using a small fraction of its address space, and the pages it will access next are near the pages it accessed recently. If the operating system loads only the pages that are actually accessed, it can run a process whose address space exceeds physical memory, because the pages that are not being used do not need to be present.

Demand paging is one of the two mechanisms that make virtual memory possible. The other is page replacement (Lesson 9.6), which chooses which page to evict when a new page must be brought in and no frame is free. Together, demand paging and page replacement allow a system to run processes whose combined address spaces far exceed the physical memory, without any involvement from the programmer and without any change to the program.

Figure 9.4 — Demand paging. Most of the process's pages are marked as not present in the page table, and their contents are on disk in the backing store. A few pages are present in memory and mapped to frames. When the process accesses a page that is not present, the MMU raises a page fault, the operating system reads the page from the backing store into a free frame, updates the page table and the TLB, and resumes the faulting instruction. The process never knows that the page was not in memory.

4.2 The valid bit and the backing store

The mechanism of demand paging depends on two things: the valid bit in the page-table entry, and the backing store on disk.

The valid bit (called the present bit on x86-64) indicates whether the page-table entry corresponds to a page that is currently in memory. When the bit is set, the entry contains a valid frame number, and an access to the page proceeds normally. When the bit is clear, the entry's frame-number field is meaningless (or, in some designs, contains information about where the page lives on disk), and an access to the page raises a page fault. The operating system's page-fault handler interprets the fault, brings the page in from disk, sets the valid bit, and updates the frame number to point to the newly-loaded page.

The backing store is a region of disk that holds the pages that are not currently in memory. On modern systems, it is a file or a partition called the swap area (or swap space). The swap area is divided into blocks that correspond to pages, and each page that is not in memory has a swap slot in the swap area where its contents are stored.

For a page that is file-backed — a page of a memory-mapped file or of a shared library's code — the backing store is the file itself, not the swap area. When such a page faults, the operating system reads the page from the file, not from the swap area. The distinction matters because the file may be shared among processes: if the page has been loaded before and is still in memory, the second process's access to it may not require any disk I/O at all, because the page is already in the page cache. This is one of the reasons shared libraries are efficient: their code pages are loaded once, into the page cache, and subsequent uses by other processes simply map the same physical frames.

For a page that is anonymous — a page of a process's heap or stack, which has no corresponding file — the backing store is the swap area. When such a page is evicted, its contents are written to a swap slot; when it faults again, its contents are read back from the slot. The swap area is therefore the backing store for anonymous memory, and its size determines how much anonymous memory the system can allocate in total (physical memory plus swap space).

File-backed versus anonymous memory

The distinction between file-backed and anonymous memory is important for understanding demand paging. A file-backed page is a page of a file that has been mapped into the address space; its contents are always available on disk (in the file), so evicting it requires no write-back. An anonymous page is a page that has no file behind it — the heap, the stack, and memory allocated with malloc are anonymous — so evicting it requires writing it to the swap area. The two kinds of pages share the same demand-paging mechanism but differ in where their contents come from when they fault and where they go when they are evicted.

4.3 Pure demand paging and prepaging

Two variants of demand paging differ in how aggressively pages are loaded.

Pure demand paging: No page is loaded until it is accessed. The process starts with an empty frame allocation, and every page it uses is brought in by a page fault. The advantage is minimal memory use: no page is loaded that the process does not actually need. The disadvantage is the fault storm at startup: the process's first accesses to each page in its working set all fault, which can produce a burst of disk I/O that delays the process's progress and stresses the I/O subsystem.
Prepaging: Pages are loaded in advance of being accessed, on the assumption that if a process accessed one page it will soon access pages nearby. When the operating system detects a page fault, it can load not only the faulting page but also several of its neighbours, on the theory that the process's locality will make the neighbours useful. The advantage is fewer faults: by loading a batch of pages in one I/O operation, the operating system amortises the per-fault overhead and reduces the total number of faults. The disadvantage is that the pages loaded may not be used: if the process's locality does not extend to the neighbouring pages, the prepaged pages are wasted, and the memory they occupy could have been used for other pages.

In practice, most operating systems use a combination of both. They use pure demand paging as the default — the first access to a page faults, and the page is loaded — but they also employ read-ahead and clustering, which load a batch of pages around the faulting page. The number of pages in a batch (the cluster size) is a tunable parameter: a larger cluster amortises the I/O overhead more, at the cost of loading more pages that may not be used. The optimal cluster size depends on the workload's locality and on the characteristics of the disk.

On Linux, the read-ahead policy is implemented by the readahead subsystem, which tracks the access patterns of each file and adjusts the amount of read-ahead based on observed behaviour. Files that are read sequentially get aggressive read-ahead (many pages at once); files that are read randomly get less. The same principle applies to the swap subsystem: a fault on a swap page can trigger the read of several adjacent swap slots, on the assumption that the pages the process evicted together will be needed together.

4.4 The page-fault service routine in outline

The page-fault service routine is the operating-system code that handles a page fault. Its full detail is the subject of Lesson 9.5, but an outline is useful here to see the mechanism as a whole.

Trap to the kernel. The MMU, on encountering a page-table entry with the valid bit clear, raises a trap. The CPU saves the faulting instruction's address and the faulting access's information, and transfers control to the operating system's page-fault handler.
Determine the cause. The handler reads the faulting address (from a register the MMU fills in) and the fault's type (read, write, or execute). It determines whether the fault is a legitimate demand-paging fault (the page is part of the process's address space but not in memory) or a genuine error (the address is not part of the address space, or the access violates the page's protection).
Locate the page on disk. For a legitimate fault, the handler finds the page in the backing store. For a file-backed page, this means reading from the file; for an anonymous page, this means reading from the swap area. The location is either recorded in the page-table entry itself or in a separate per-page data structure.
Obtain a free frame. If a free frame is available, use it. If not, invoke the page-replacement policy (Lesson 9.6) to choose a victim page, write the victim back to disk if it is dirty, and use its frame.
Read the page into the frame. Initiate an I/O operation to read the page from disk into the frame. Because the I/O is slow — tens of microseconds to milliseconds — the process is blocked during the read, and the scheduler runs another process. When the I/O completes, the operating system wakes the blocked process.
Update the page table and TLB. When the I/O completes, the handler updates the page-table entry: the frame number is set, the valid bit is set, and the protection bits are set according to the page's type. It also 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.
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 outline shows the essential structure of the mechanism. The two expensive steps are the disk read (step 5) and, when no free frame is available, the page-replacement decision and the write-back of the victim (step 4). The other steps are fast, taking a few hundred to a few thousand cycles. A page fault that requires only a disk read — because a free frame was available — is called a minor fault or soft fault; a fault that requires the eviction of a dirty page, and therefore a write to disk, is called a major fault or hard fault. Major faults are much more expensive than minor faults, because they involve both a write and a read. The distinction is examined in detail in Lesson 9.5.

4.5 Effective access time with page faults

The cost of a page fault is enormous compared to the cost of a normal memory access. A main-memory access takes about 80 nanoseconds; a disk access takes about 10 milliseconds — a factor of over 100,000. This enormous disparity means that the fault rate must be extremely low for demand paging to be practical. The effective access time (EAT) calculation makes this quantitative.

Let p be the page-fault rate: the probability that any given memory access causes a page fault. The effective access time is:

EAT = (1 − p) × t_memory + p × t_fault

where t_memory is the time for a normal access (including the TLB lookup and the data access) and t_fault is the total time to service a page fault (the trap, the disk read, the page-table update, and the resumption of the faulting instruction).

A concrete example makes the sensitivity clear. Suppose t_memory = 100 ns and t_fault = 10 ms (10,000,000 ns — a typical disk access). Then:

EAT = (1 − p) × 100 + p × 10,000,000
    = 100 + p × (10,000,000 − 100)
    ≈ 100 + 10,000,000 p

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

Fault rate p	EAT (ns)	Slowdown vs. no faults	Faults per 10⁶ accesses
0	100	1.0×	0
10⁻⁶	110	1.10×	1
10⁻⁵	200	2.0×	10
10⁻⁴	1,100	11×	100
10⁻³	10,100	101×	1,000
10⁻²	100,100	1001×	10,000

The numbers are stark. A fault rate of 10⁻⁶ — one fault per million accesses — slows the system by 10 percent. A fault rate of 10⁻⁵ — ten faults per million accesses — slows it by 100 percent (a factor of two). A fault rate of 10⁻⁴ — one hundred faults per million accesses — slows it by a factor of eleven. And a fault rate of 10⁻³ — one fault per thousand accesses — slows the system by a factor of a hundred, which is catastrophic.

For demand paging to be practical, the fault rate must be in the range of 10⁻⁵ or less. This is the fundamental constraint of the mechanism, and it is why locality is so important: if the process's working set fits in memory, faults are rare (they occur only on the first access to each page), and the system performs nearly as well as if all pages were in memory. If the working set does not fit, faults are frequent, and the system's performance collapses. This collapse is called thrashing, and it is the subject of Lesson 9.7.

Why the fault rate must be so low

The demand paging EAT calculation is one of the clearest illustrations of the memory hierarchy's behaviour (Lesson 8.1). The gap between the fast level (main memory, 100 ns) and the slow level (disk, 10 ms) is a factor of 100,000. Even a tiny fraction of accesses that reach the slow level dominates the average. This is why the fault rate must be so low, and why the operating system's page-replacement policy — the subject of Lesson 9.6 — is so important. The policy's goal is to keep the fault rate as low as possible by keeping the process's working set in memory.

4.6 Memory-mapped files and shared libraries

Demand paging is not only an internal mechanism of the operating system. It is also exposed to applications through the memory-mapped file interface, which allows a file's contents to be mapped into a process's address space and accessed as ordinary memory.

The interface on POSIX systems is mmap. When a process calls mmap on a file, the operating system creates a mapping in the process's page table: the file's pages are mapped into the process's address space, and accesses to those addresses read from and write to the file's pages. The mapping is not immediately loaded into memory; the pages are brought in on demand, exactly as with anonymous memory. When the process reads from a mapped address for the first time, a page fault occurs, the operating system reads the page from the file into a frame, and the process resumes. Subsequent accesses to the same page are normal memory accesses.

Memory-mapped files offer several advantages over the traditional read and write interface.

Simplicity. A program that processes a large file can map the file and access it as an array, without any explicit read or write calls. The operating system's demand paging handles the loading.
Sharing. If two processes map the same file, they share the same physical pages. The first process to access a page causes it to be loaded from disk; the second process's access to the same page finds it already in memory, and no I/O is needed. This is the mechanism by which shared libraries are shared among processes: the library's code pages are mapped into each process's address space, but the physical pages are shared.
Efficiency. Memory-mapped I/O avoids the copying that explicit reads and writes require. A read call copies data from the page cache (where the operating system stores recently read file data) into the process's buffer; a memory-mapped access reads directly from the page cache, with no copy. For programs that process large files sequentially, this can be a significant performance win.
Demand loading. Only the pages that are actually accessed are loaded. A program that maps a 10 GB file but reads only the first 100 MB does not pay for the rest of the file.

The page cache is the operating system's cache of recently read file data. When a file page is needed, the operating system first checks the page cache; if the page is present, no disk I/O is needed. The page cache is the same structure that implements memory-mapped files — a page that is in the page cache can be mapped into a process's address space, and a page that is mapped can be evicted to the page cache rather than to the swap area. This unification is what makes Linux's memory management efficient: the same physical page can be accessed through the file system (via read) and through a memory mapping (via mmap), without duplication.

Shared libraries are a special case of memory-mapped files. A shared library is an ordinary file on disk, with code and data in a format (ELF on Linux, Mach-O on macOS, PE on Windows) that the dynamic linker can map into a process's address space. When a program starts, the dynamic linker maps the library's code and data into the program's address space, and the library's pages are loaded on demand as the program calls into the library. Because the library is shared, its code pages are the same physical pages for every process that uses it, and the page cache holds one copy regardless of how many processes use the library. This is the mechanism that makes shared libraries memory-efficient: a 10 MB library used by 100 processes consumes 10 MB of physical memory, not 1 GB.

4.7 Demand paging and overcommitment

Demand paging is the mechanism that makes overcommitment possible: the situation in which the total memory demanded by the processes in a system exceeds the physical memory available. Without demand paging, every process would need its entire address space in memory, and the number of processes would be bounded by the physical memory. With demand paging, the number of processes is bounded by the sum of physical memory and swap space, and the operating system can run processes whose combined address spaces far exceed the physical memory.

Overcommitment comes in two forms, and they are worth distinguishing.

Conservative overcommit. The operating system commits to providing at most physical memory + swap space worth of anonymous memory. When a process requests memory (through malloc or the equivalent), the kernel reserves a corresponding amount of the physical+swap pool. If the pool is exhausted, the request fails, and the process must handle the failure. This is the traditional Unix behaviour, and it is the behaviour that vm.overcommit_memory = 2 on Linux configures.
Optimistic overcommit. The operating system commits to providing as much memory as each process requests, regardless of the total. It does not reserve swap space at allocation time; it does so only when pages are actually evicted. The result is that a process can allocate more memory than the system has, as long as it does not actually use it all at once. If the processes do use all their allocated memory, the system runs out of physical+swap space and the OOM killer (out-of-memory killer) terminates one or more processes to free memory. This is the behaviour that vm.overcommit_memory = 0 (the default) on Linux configures.

Optimistic overcommit is what allows a system with 8 GB of RAM and no swap to run a machine-learning training job that allocates 100 GB of virtual address space but touches only 4 GB of it. The allocation succeeds because the kernel does not verify that the memory is actually available; the process's page table maps the addresses to invalid pages, and the pages are loaded only when they are touched. As long as the process's working set fits in physical memory, the process runs; if the working set grows beyond the available memory, the OOM killer terminates the process.

The trade-off between conservative and optimistic overcommit is a classic one. Conservative overcommit guarantees that a successful allocation will not fail later, at the cost of being unable to allocate memory that the system does not currently have. Optimistic overcommit allows more memory to be allocated, at the cost of the possibility that the process will be killed later, when the memory it allocated is actually used and the system runs out. Which is better depends on the workload: a workload that allocates and uses memory immediately benefits from conservative overcommit, while a workload that allocates more than it uses benefits from optimistic overcommit. Linux allows the administrator to choose, via the vm.overcommit_memory sysctl.

4.8 Common misconceptions

"Demand paging loads a process's pages at startup."

No — that is the opposite of demand paging. Demand paging loads a page only when it is accessed. At startup, the process has no pages in memory (or almost none), and its first accesses fault.

"A page fault is an error."

A page fault is a normal event in demand paging. It is a trap to the operating system, which brings the page in and resumes the process. A page fault is an error only when the address is not part of the process's address space or the access violates the page's protection.

"Demand paging requires the process to be modified."

No — demand paging is transparent. The process uses its logical addresses as usual, and the operating system handles the faults without the process's knowledge. Any program can run on a demand-paged system, whether it was written for one or not.

"The backing store is only for anonymous memory."

The backing store has two parts: the swap area, for anonymous memory (heap, stack), and the file system, for file-backed memory (memory-mapped files, shared libraries). A file-backed page that is evicted does not need a swap slot, because its contents are already on disk in the file.

"A page fault always requires a disk read."

Not always. A minor fault (soft fault) can occur when the page is already in memory — for example, in the page cache, or in another process's address space because the page is shared. A minor fault does not require a disk read, and it is much cheaper than a major fault.

"Demand paging always improves performance."

Demand paging improves the system's ability to run more processes than fit in memory, but it can degrade performance when the fault rate is high. A system that is thrashing (Lesson 9.7) runs far slower than one with no paging.

"The page-fault rate is the same for all programs."

The fault rate depends entirely on the program's locality and on the amount of physical memory available to it. A program with good locality and a working set that fits in memory has a very low fault rate; a program with poor locality or a working set that exceeds memory has a high fault rate.

"Prepaging always improves performance."

Prepaging amortises the I/O overhead by loading multiple pages at once, but it can waste memory if the loaded pages are not used. The benefit depends on the workload's locality and on the disk's characteristics.

05 Worked example

The following example computes the effective access time for a demand-paged system, and then models the behaviour of a process's working set as it faults in its pages.

Effective access time with a disk-based backing store

A system has the following parameters:

A normal memory access takes 100 ns (including the TLB lookup and the data access).
A page fault takes 10 ms (10,000,000 ns) — this includes the trap, the disk access, the page-table update, and the resumption of the faulting instruction.

The effective access time is:

EAT = (1 − p) × 100 + p × 10,000,000

where p is the fault rate. The table below computes the EAT for a range of fault rates, together with the slowdown relative to a system with no faults.

Fault rate p	EAT (ns)	Slowdown	Faults per million accesses
0	100	1.00×	0
10⁻⁶	110	1.10×	1
5 × 10⁻⁶	150	1.50×	5
10⁻⁵	200	2.00×	10
5 × 10⁻⁵	600	6.00×	50
10⁻⁴	1,100	11.0×	100
10⁻³	10,100	101×	1,000
10⁻²	100,100	1001×	10,000

The pattern is unambiguous. A fault rate of one per million slows the system by 10 percent; one per hundred thousand slows it by 50 percent; one per ten thousand (10⁻⁴) slows it by a factor of eleven; one per thousand (10⁻³) slows it by a factor of a hundred. For demand paging to be practical, the fault rate must be on the order of 10⁻⁵ or less, which means the process's working set must fit in memory.

A process's fault-in sequence

Consider a process with a 1 MB address space (256 pages of 4 KB each) running on a system with only 16 frames (64 KB) available to it. The process's access pattern is sequential within each of its regions — code, data, heap, stack — and it has 5 regions of ~50 pages each. We trace the first 300 accesses, which is a rough approximation of the process's startup.

Initially, the process has no pages in memory. Its first access is to the code page containing its first instruction. The page is not present, so a page fault occurs:

Fault 1: the first code page is loaded into frame 0. The process resumes, and the remaining accesses in this page hit.
Fault 2: after ~1000 accesses, the process moves to the next code page. Fault. The page is loaded into frame 1.
Faults 3–5: the process continues through its code, faulting in each new page as it goes.

The pattern continues: the process faults on each new page it touches, and the pages it has already touched stay in memory (as long as there is a free frame). With 16 frames available and the process touching pages sequentially, the process faults on average once per page (every ~1000 accesses if a page holds 1000 accesses' worth of data), which is a fault rate of about 10⁻³.

Wait — that fault rate is catastrophic, per the table above. The apparent contradiction is resolved by noting that the fault rate is not uniform over the process's life. The process faults frequently at the beginning, when it is loading its working set, and rarely afterward. The startup period lasts as long as it takes to load the working set — a few tens of pages for a small program — and after that the process runs with essentially no faults. Over the process's full lifetime, the fault rate averages out to be much lower than the startup rate.

The following table summarizes the process's fault behaviour over three phases.

Phase	Accesses	Faults	Fault rate	EAT (ns)
Startup (loading working set)	50,000	250	5 × 10⁻³	50,100
Steady state (working set resident)	50,000,000	50	10⁻⁶	110
Overall (both phases)	50,050,000	300	6 × 10⁻⁶	160

The overall fault rate — about 6 × 10⁻⁶ — is much lower than the startup rate, because the startup phase is short compared to the steady state. The overall EAT is about 160 ns, which is 60 percent above the no-fault cost of 100 ns. This is the practical performance of demand paging: a startup cost, followed by a steady state that runs at nearly full speed.

The effect of the working set size

The startup phase's duration depends on the size of the working set. A process whose working set fits in the available memory has a short startup and a long steady state; a process whose working set exceeds the available memory never reaches a steady state and runs continuously at the startup rate. The table below compares three processes with different working set sizes.

Process	Working set	Frames available	Behaviour
A	64 KB (16 pages)	16	Fits exactly; short startup, low steady-state fault rate
B	256 KB (64 pages)	16	Does not fit; thrashing — pages evicted before they can be reused
C	16 KB (4 pages)	16	Fits easily; negligible startup, negligible steady-state fault rate

Process A has a working set that exactly fits the available frames. Its startup loads 16 pages, and after that it runs with no faults (assuming its working set does not change). Process C has a smaller working set and runs with even fewer faults. Process B has a working set that exceeds the available frames: when it faults in a new page, the page-replacement policy must evict a page from the working set, and the evicted page will be needed again soon. Process B is thrashing: it faults on nearly every access to a page that is not resident, and the faults are so frequent that the system spends all its time doing I/O. This is the failure mode that Lesson 9.7 examines in detail.

Memory-mapped file example

Consider a program that maps a 1 GB file with mmap and reads the first 10 MB. The mapping creates the virtual address range, but no pages are loaded. As the program reads through the first 10 MB, it faults in the corresponding pages (about 2560 pages of 4 KB each). The remaining pages of the file — about 99 percent of it — are never accessed, and they are never loaded.

If the program later reads a different 10 MB region, it faults in the pages for that region. The pages from the first region may still be in memory (if there is room) or may have been evicted (if memory is tight). The page cache holds the pages that have been accessed, and the demand-paging mechanism brings them in as needed.

The memory-mapped interface is what makes this efficient. A program that uses read on the same file would have to read the entire 10 MB into a buffer, even if it only needs a few pages of it; the memory-mapped interface allows the program to access exactly the pages it needs, and demand paging loads them on demand.

Overcommitment and the OOM killer

On a Linux system with 8 GB of RAM and no swap, a program that allocates 100 GB of virtual memory (malloc(100 * 1024 * 1024 * 1024)) will succeed, because Linux's default overcommit policy is optimistic. The 100 GB of virtual address space is mapped, but no physical frames are allocated until the pages are actually touched. If the program touches only 4 GB — which is a common pattern for machine-learning training with lazy initialization — the program runs, because 4 GB fits in the 8 GB of RAM.

If the program touches 9 GB, the kernel cannot satisfy the demand for physical frames from the physical memory (8 GB), and there is no swap space to fall back on. When the kernel tries to reclaim memory, it finds no free frames and no pages that can be swapped out (because there is no swap). It invokes the OOM killer, which selects one or more processes to terminate. The selection is based on a heuristic score that combines memory usage, priority, and other factors, and it is deliberately simple: the goal is to free memory as quickly as possible, because the system is in a critical state.

The OOM killer is the price of optimistic overcommit. It allows a program to allocate more memory than the system has, which is convenient for programs whose working set is smaller than their address space, but it means that a program that actually uses all its allocated memory may be killed without warning. The alternative — conservative overcommit — would refuse the 100 GB allocation in the first place, so the program would need to allocate memory in smaller increments and handle the possibility of failure. Which is better depends on the workload, and Linux allows the administrator to choose.

06 Interactive activity

Activity · observe demand paging on a live system

The goal of this activity is to observe the demand-paging mechanism on a real system, measure the page-fault rate of a program, and see the effect of working set size on paging behaviour. Work through the steps in your course VM.

Measure page faults with time and /usr/bin/time. The time builtin and the /usr/bin/time utility report the number of page faults a process experiences. 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
```
The minor faults are the ones that do not require disk I/O — mostly the initial loading of the program's pages from the page cache. The major faults are the ones that require disk I/O — the ones that actually read from disk. How many of each does the program experience?
Measure page faults for a larger program. Run a larger program, such as gcc or python, and observe its fault counts.
```
/usr/bin/time -v gcc --version
/usr/bin/time -v python3 -c "print('hi')"
```
A larger program uses more pages, so it has more minor faults at startup. Does it also have more major faults? Why or why not? (Hint: the page cache may already hold the program's pages if it has been run recently.)
Force major faults by clearing the 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).
```
sync
echo 3 | sudo tee /proc/sys/vm/drop_caches

/usr/bin/time -v ./hello
```
After clearing the cache, the program's pages must be read from disk, so it should experience many more major faults. Run the program a second time immediately; the pages should be in the cache, so the second run should have fewer major faults. This is the demand-paging mechanism in action: pages are loaded on demand, and once loaded they stay in the cache for subsequent use.
Observe the working set size effect. Write a program that allocates a large buffer and touches every page of it (or every N-th byte, where N is the page size). Then run it with different buffer sizes and observe the major fault count.
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv) {
    size_t n = atol(argv[1]);
    char *buf = malloc(n);
    if (!buf) { perror("malloc"); return 1; }

    /* touch every page */
    for (size_t i = 0; i < n; i += 4096)
        buf[i] = 1;

    printf("touched %zu bytes\n", n);
    free(buf);
    return 0;
}
```
Run it with 1 MB, 10 MB, 100 MB, and 1 GB. Then run it again with the same sizes. The first run of each size should have many major faults (loading the pages), and the second run should have fewer (the pages are in the page cache).
```
/usr/bin/time -v ./touch 1048576
/usr/bin/time -v ./touch 1048576   # second run
```

Observe memory-mapped file behaviour. Write a program that uses mmap to map a file and reads the first 4 KB of it.

#include <fcntl.h>
#include <stdio.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

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

    struct stat st;
    fstat(fd, &st);

    char *p = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    if (p == MAP_FAILED) { perror("mmap"); return 1; }

    /* read only the first 4 KB */
    volatile int sum = 0;
    for (size_t i = 0; i < 4096; i++) sum += p[i];

    printf("sum = %d\n", sum);
    munmap(p, st.st_size);
    close(fd);
    return 0;
}

Run it on a large file (say, a 1 GB video or database file). Then check the fault counts with /usr/bin/time -v. The program should have very few faults, because it only accesses the first 4 KB of the file; the rest of the file is never loaded. This is the demand-paging mechanism at work.

Inspect the process's memory map. While a program is running, inspect its memory map with /proc/<pid>/maps and /proc/<pid>/smaps.
```
./touch 100000000 &
PID=$!

cat /proc/$PID/maps | head -20
cat /proc/$PID/smaps | head -40

kill $PID
```
The maps file shows the process's virtual address ranges (code, data, heap, stack, libraries, and the large buffer). The smaps file shows additional information for each mapping: Size, Rss (Resident Set Size — the pages actually in memory), Pss (Proportional Set Size — the process's share of shared pages), Shared_Clean, Shared_Dirty, Private_Clean, Private_Dirty, and Swap. Compare the Size of the buffer's mapping to its Rss. Are they the same? If the program has touched every page of the buffer, they should be; if it has touched only some, the Rss should be smaller.
Force the OOM killer. On a Linux VM, you can force the OOM killer to fire by allocating memory faster than the kernel can reclaim it. Write a program that allocates and touches memory in a loop until the kernel kills it.
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    for (long i = 0; ; i++) {
        size_t n = 100 * 1024 * 1024;   /* 100 MB */
        char *p = malloc(n);
        if (!p) { perror("malloc"); return 1; }
        memset(p, 0, n);                /* touch every page */
        printf("allocated %ld00 MB\n", i + 1);
    }
    return 0;
}
```
Warning: run this only in a VM or container where you can afford to lose the system. The OOM killer will fire, and it may kill processes other than your test program. The system's dmesg output should show the OOM killer's decision — which process it chose and why.
```
dmesg | tail -40
```
Note the "Out of memory: Killed process" message, which reports the victim's name and score. This is the price of optimistic overcommit.
Read the OSTEP chapter. Read OSTEP Chapter 21, Swapping: Mechanisms. Compare its presentation of demand paging to this lesson. What additional considerations does OSTEP raise — for example, the role of the swap space, the structure of the page-table entry's swap-related fields, and the interaction between demand paging and the page cache? Write a short paragraph summarising the differences.

Reflect: demand paging is a mechanism that trades memory for time. The trade is favourable when the process's working set fits in memory, and catastrophic when it does not. The operating system's page-replacement policy (Lesson 9.6) is what determines whether the working set stays resident, and the policy's effectiveness determines whether the system runs at full speed or at a fraction of it. What kinds of workloads are particularly sensitive to the policy? What kinds are not? Consider a web browser, a database, a machine-learning training run, a compiler, a video editor, and a web server. For each, how much of its performance depends on the paging policy, and why?

07 Knowledge check

Check your understanding

Question 1

Define demand paging. What is the role of the valid bit and the backing store, and why is demand paging necessary for overcommitment?

Show answer

Demand paging is the operating-system mechanism of loading a page into memory only when it is actually accessed. Instead of loading a process's entire address space at startup, the operating system marks every page as not present in the page table — the valid bit is cleared — and begins executing the process with an empty frame allocation. When the process accesses a page that is not present, the MMU raises a page fault, and the operating system's page-fault handler brings the page in from disk, installs it in a free frame, updates the page table, and resumes the faulting instruction. The valid bit (also called the present bit) is the mechanism by which the MMU knows whether a page is in memory. If the bit is set, the page-table entry contains a valid frame number and an access proceeds normally. If the bit is clear, the entry's frame-number field is meaningless, and an access raises a page fault. The operating system's handler sets the bit when it loads the page. The backing store is the region of disk that holds the pages that are not currently in memory. It has two parts: the swap area, for anonymous memory (heap, stack), and the file system, for file-backed memory (memory-mapped files, shared libraries). When a page faults, the handler reads it from the appropriate part of the backing store. Demand paging is necessary for overcommitment because overcommitment requires that a process's address space exceed the physical memory. Without demand paging, every process would need its entire address space in memory, and the number of processes would be bounded by the physical memory. With demand paging, only the pages that are actually used are in memory, and the total address space of the processes can be much larger than the physical memory. The unused pages are in the backing store, and they are loaded only when they are needed.

Question 2

Distinguish pure demand paging from prepaging. What are the advantages and disadvantages of each, and which is used in practice?

Show answer

Pure demand paging is the policy of loading no page until it is accessed. The process starts with an empty frame allocation, and every page it uses is brought in by a page fault. Its advantage is minimal memory use: no page is loaded that the process does not actually need. Its disadvantage is the fault storm at startup, when the process's first accesses to each page in its working set all fault, producing a burst of disk I/O that delays the process's progress and stresses the I/O subsystem. Prepaging is the policy of loading pages in advance of being accessed, on the assumption that a process's locality will make nearby pages useful. When a page fault occurs, the operating system loads not only the faulting page but also several of its neighbours, amortising the I/O overhead across the loaded pages. Its advantage is fewer faults and less I/O overhead per page. Its disadvantage is that the pages loaded may not be used: if the process's locality does not extend to the neighbouring pages, the prepaged pages are wasted, and the memory they occupy could have been used for other pages. In practice, most operating systems use a combination. They use pure demand paging as the default — the first access to a page faults, and the page is loaded — but they also employ read-ahead and clustering, which load a batch of pages around the faulting page. The number of pages in a batch (the cluster size) is a tunable parameter; a larger cluster amortises the I/O overhead more but risks loading unused pages. Linux's readahead subsystem tracks the access pattern of each file and adjusts the amount of read-ahead based on observed behaviour: sequential reads get aggressive read-ahead, random reads get less.

Question 3

Compute the effective access time for a demand-paged system with a memory access time of 80 ns and a page fault time of 8 ms. Compute the EAT for fault rates of 0, 10⁻⁶, 10⁻⁵, and 10⁻⁴. What is the fault rate at which the EAT is twice the no-fault cost?

Show answer

The effective access time is:

EAT = (1 − p) × 80 + p × 8,000,000

EAT = 80 + p × (8,000,000 − 80)
                  ≈ 80 + 8,000,000 p

Substituting the given fault rates:

p = 0: EAT = 80 ns.
p = 10⁻⁶: EAT = 80 + 8 = 88 ns (a 10 percent slowdown).
p = 10⁻⁵: EAT = 80 + 80 = 160 ns (a 2× slowdown).
p = 10⁻⁴: EAT = 80 + 800 = 880 ns (an 11× slowdown).

The fault rate at which the EAT is twice the no-fault cost (160 ns) is p = (160 − 80) / 8,000,000 = 10⁻⁵, or one fault per hundred thousand accesses. This is a very low rate, and it illustrates why the fault rate must be so small for demand paging to be practical. At a fault rate of 10⁻⁴, the system is already eleven times slower than a system with no faults; at 10⁻³, it would be a hundred times slower.

Question 4

What are memory-mapped files? How does demand paging make them efficient, and how are shared libraries implemented with the same mechanism?

Show answer

A memory-mapped file is a file whose contents are mapped into a process's address space, so that the process can access the file's bytes as ordinary memory. The interface on POSIX systems is mmap. When a process maps a file, the operating system creates a mapping in the process's page table: the file's pages are mapped into the process's address space, but they are not immediately loaded into memory. Accesses to the mapped addresses fault in the corresponding pages on demand, exactly as with anonymous memory. The demand paging mechanism is what makes memory-mapped files efficient: only the pages that are actually accessed are loaded, so a process that maps a 10 GB file but reads only the first 100 MB does not pay for the rest of the file. The pages that are loaded are stored in the page cache, the operating system's cache of recently read file data, and subsequent accesses to the same pages — by the same process or by any other process — find them in the cache without any disk I/O. Shared libraries are a special case of memory-mapped files. A shared library is an ordinary file on disk, with code and data in a format (ELF on Linux, Mach-O on macOS, PE on Windows) that the dynamic linker can map into a process's address space. When a program starts, the dynamic linker maps the library's code and data into the program's address space, and the library's pages are loaded on demand as the program calls into the library. Because the library is shared, its code pages are the same physical pages for every process that uses it: the first process to access a page causes it to be loaded into the page cache, and subsequent processes' accesses to the same page find it already in memory, so no additional I/O is needed. This is the mechanism that makes shared libraries memory-efficient: a 10 MB library used by 100 processes consumes 10 MB of physical memory, not 1 GB. The page cache unifies the two mechanisms — memory-mapped files and shared libraries — and it is what allows the same physical page to be accessed through the file system (via read) and through a memory mapping (via mmap), without duplication.

Question 5

What is overcommitment? Distinguish conservative from optimistic overcommit, and explain the trade-off between them. What is the OOM killer, and why is it the price of optimistic overcommit?

Show answer

Overcommitment is the situation in which the total memory demanded by the processes in a system exceeds the physical memory available. Demand paging makes overcommitment possible, because a process's pages are loaded only when they are accessed, so the process's address space can be much larger than the physical memory. There are two forms of overcommitment. Conservative overcommit commits to providing at most physical memory + swap space worth of anonymous memory. When a process requests memory, the kernel reserves a corresponding amount of the physical+swap pool; if the pool is exhausted, the request fails. This is the traditional Unix behaviour, and on Linux it is configured with vm.overcommit_memory = 2. Optimistic overcommit commits to providing as much memory as each process requests, regardless of the total, and does not reserve swap space at allocation time. A process can allocate more memory than the system has, as long as it does not actually use it all at once; if the processes do use all their allocated memory, the system runs out and must take action. This is the default on Linux (vm.overcommit_memory = 0). The trade-off between the two is a classic one. Conservative overcommit guarantees that a successful allocation will not fail later, at the cost of being unable to allocate memory the system does not currently have. Optimistic overcommit allows more memory to be allocated, at the cost of the possibility that the process will be killed later, when the memory it allocated is actually used. Which is better depends on the workload: a workload that allocates and uses memory immediately benefits from conservative overcommit, while a workload that allocates more than it uses benefits from optimistic overcommit. The OOM killer (out-of-memory killer) is the mechanism that optimistic overcommit relies on when the system runs out of memory. When the kernel cannot satisfy a memory request from physical memory and swap, it invokes the OOM killer, which selects one or more processes to terminate. The selection is based on a heuristic score that combines memory usage, priority, and other factors. The OOM killer is the price of optimistic overcommit: it allows a program to allocate more memory than the system has, which is convenient for programs whose working set is smaller than their address space, but it means that a program that actually uses all its allocated memory may be killed without warning. The alternative — conservative overcommit — would refuse the allocation in the first place, so the program would need to handle the possibility of allocation failure. Linux allows the administrator to choose between the two policies.

08 Unit discussion

Discussion prompt

Demand paging is one of the great "free lunches" of operating-system design. Without it, a process would have to fit entirely in memory, and the number of processes running at once would be bounded by the physical memory. With it, a process's address space can exceed the physical memory, and the number of processes is bounded by the sum of physical memory and swap space. The mechanism is transparent: programs do not need to be modified to benefit from it, and the vast majority of programs never know that their pages are being loaded on demand.

But demand paging is not free. It trades memory for time: the pages that are not in memory are on disk, and bringing them in costs the difference between the memory latency and the disk latency — a factor of 100,000. The trade is favourable when the process's working set fits in memory, and catastrophic when it does not. The whole art of memory management is to keep the working set resident, and the whole art of writing memory-efficient programs is to have a working set that fits.

This creates a tension. On the one hand, demand paging allows a system to run more processes than fit in memory, which increases utilization and reduces cost. On the other hand, it degrades the performance of each process if the working set does not fit. The system administrator must decide how much overcommitment to allow: a system with no overcommitment runs each process at full speed but cannot run many processes; a system with aggressive overcommitment runs many processes but each may be slow. Where should the line be drawn?

Consider the systems you use. A laptop runs a web browser with dozens of tabs, each of which has its own working set. A server runs many concurrent processes, each of which may be serving different clients. A virtual machine host runs several VMs, each of which has its own memory. For each, how would you set the overcommit policy, and why? What are the consequences of getting it wrong? 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.5. Aim to spend 60–90 minutes on it.

Compute effective access times. For a demand-paged system with a memory access time of 120 ns and a page-fault time of 12 ms, compute the effective access time for the following fault rates:
- 0
- 10⁻⁷
- 10⁻⁶
- 10⁻⁵
- 10⁻⁴
- 10⁻³
Present the results in a table with columns for the fault rate, the EAT, the slowdown relative to no faults, and the number of faults per million accesses. Then state the fault rate at which the slowdown is 10 percent, 50 percent, and 100 percent.
Trace a process's fault-in sequence. Consider a process with a 512 KB address space (128 pages of 4 KB each) and a working set of 32 pages. The process's access pattern is sequential within each of its regions. Trace the process's first 100 faults, showing which pages are loaded and in what order. Then describe what happens in the steady state, and compute the process's overall fault rate assuming its lifetime is 10⁹ accesses.
Design a prepaging policy. A system uses prepaging with a cluster size of 4 pages. The disk has a 5 ms seek time and a 0.1 ms per-page transfer time. Compute the average time to service a fault when the cluster is loaded in a single I/O operation versus when each page is loaded individually. Assume that half of the prepaged pages are actually used (the other half are wasted). Compare the effective access time for the two cases, assuming the process's fault rate is 10⁻⁵ with prepaging and 10⁻⁴ without.
Compare memory-mapped I/O with read/write. Write a short paragraph (200–250 words) comparing memory-mapped I/O (using mmap) with traditional I/O (using read and write). Address: (a) the number of data copies; (b) the ability to access parts of a file; (c) the behaviour when the file is shared among processes; (d) the interaction with demand paging. Then state which you would choose for (i) reading a large file sequentially, (ii) accessing a small portion of a large file, and (iii) sharing a data structure among multiple processes. Justify each choice.
Analyse overcommit policies. A Linux server has 32 GB of RAM and 8 GB of swap. Three workloads are being considered:
- Web server: 100 processes, each using ~100 MB of anonymous memory, with frequent forks and short-lived children.
- Database: 4 processes, each using ~16 GB of anonymous memory, with a memory-mapped data file of 1 TB.
- Machine-learning training: 1 process that allocates 200 GB of virtual address space but touches only ~8 GB of it.
For each workload, state whether you would use conservative or optimistic overcommit, and why. What are the consequences of the wrong choice in each case? How would you configure the system to support each?

Investigate the page cache. On a Linux system, write a program that reads a large file twice and measure the time for each read. Then clear the page cache between reads and measure the third read.

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

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

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

    close(fd);
    return 0;
}

# First read (cold cache)
sudo sh -c 'sync; echo 3 > /proc/sys/vm/drop_caches'
time ./read_file bigfile

# Second read (warm cache)
time ./read_file bigfile

# Third read (cache cleared again)
sudo sh -c 'sync; echo 3 > /proc/sys/vm/drop_caches'
time ./read_file bigfile

Compare the times. The first and third runs are cold (the file is on disk); the second is warm (the file is in the page cache). What is the ratio of warm to cold? This is the speedup that the page cache provides.

Write a program that faults. Write a program that allocates a large buffer, touches it in a way that forces many faults, and then touches it again in the same order. Measure the fault counts (with /usr/bin/time -v) in both passes. The first pass should have many major faults (loading pages from disk or from swap); the second should have none.
Reflect. In your own words, explain why demand paging requires the fault rate to be so low. 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 working set, and how did it affect the performance?

10 Summary

Demand paging is the mechanism of loading a page into memory only when it is actually accessed. It is what makes overcommitment possible — the situation in which the total memory demanded by the processes in a system exceeds the physical memory.
The mechanism depends on the valid bit in the page-table entry and on the backing store on disk. When the valid bit is clear, an access raises a page fault; the operating system's page-fault handler brings the page in from the backing store, installs it in a free frame, updates the page table, and resumes the faulting instruction.
The backing store has two parts: the swap area, for anonymous memory (heap, stack), and the file system, for file-backed memory (memory-mapped files, shared libraries). A file-backed page that is evicted does not need a swap slot, because its contents are already on disk in the file.
Pure demand paging loads no page until it is accessed, minimising memory use but causing a fault storm at startup. Prepaging loads pages in advance, amortising the I/O overhead but risking the loading of unused pages. In practice, operating systems use a combination, with a tunable cluster size for read-ahead.
The page-fault service routine is the operating-system code that handles a page fault. Its essential steps are: trap to the kernel, determine the cause, locate the page on disk, obtain a free frame, read the page into the frame, update the page table and TLB, and resume the faulting instruction.
A minor fault (soft fault) does not require a disk read; a major fault (hard fault) does. Major faults are much more expensive, because they involve disk I/O.
The effective access time of a demand-paged system is EAT = (1 − p) × t_memory + p × t_fault, where p is the fault rate. Because the fault cost is 100,000 times the memory cost, the fault rate must be very low — on the order of 10⁻⁵ or less — for demand paging to be practical. This is why locality is so important: a working set that fits in memory keeps the fault rate low.
Memory-mapped files (the mmap interface) map a file's contents into a process's address space, and demand paging loads the file's pages on demand. Memory-mapped I/O avoids the copies that explicit reads and writes require, supports sharing among processes, and loads only the parts of the file that are actually accessed.
The page cache is the operating system's cache of recently read file data. It unifies memory-mapped files, shared libraries, and the file system: the same physical page can be accessed through read and through mmap, without duplication.
Conservative overcommit commits to providing at most physical memory + swap space worth of anonymous memory; a request that would exceed the pool fails. Optimistic overcommit commits to providing as much memory as each process requests, regardless of the total; when the system runs out, the OOM killer terminates one or more processes. The trade-off is between the guarantee that a successful allocation will not fail later and the ability to allocate more memory than the system has.
The fault rate is not uniform over a process's life. It is high at startup, when the working set is being loaded, and low in the steady state, when the working set is resident. A process whose working set fits in memory has a short startup and a long steady state; a process whose working set exceeds memory never reaches a steady state and runs continuously at the startup rate. This last condition is thrashing, the subject of Lesson 9.7.

Looking ahead

This lesson presented the demand-paging mechanism. It showed that a page is brought into memory only when it is accessed, and that the mechanism depends on the valid bit and the backing store. It presented the page-fault service routine in outline, the effective access time calculation, and the role of demand paging in memory-mapped files and shared libraries. Lesson 9.5 presents the page-fault handling procedure in detail: the exact steps of the page-fault handler, the distinction between minor and major faults, the interaction between the fault handler and the TLB, the handling of protection faults and invalid accesses, and the practical considerations that determine the handler's performance. The lesson also examines the cost of a page fault in detail, and the conditions under which the fault handler can be optimised.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 10, Sections 10.1–10.3.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 21 and 22. Available online at ostep.org.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.3.
Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.7–9.10.
Denning, P. J. Virtual Memory. ACM Computing Surveys, 1970. The paper that framed the demand-paging mechanism and the working-set concept.
Denning, P. J. The Working Set Model for Program Behavior. Communications of the ACM, 1968. The paper that introduced the working-set concept, which is the foundation for understanding demand-paging performance.
Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management, and Chapter 16, The Page Cache and Page Writeback. The Linux implementation of demand paging, the page cache, and the swap subsystem.
Linux kernel documentation: Documentation/admin-guide/mm/ and Documentation/vm/.
Linux man-pages: man 2 mmap, man 2 mprotect, man 2 madvise, man 2 fork, man 2 swapon, man 5 proc, man 1 time.