Appearance
2.5.3 — Page Faults, Page Replacement & Thrashing
2.5.1 ended with a strange result. The photo-upload service asked for 1 GB of memory, and its use of RAM did not change at all. Only when it touched the memory, one 4 KB page at a time, did RAM fill up. Every first touch of a page caused a page fault, the kernel quietly found a frame, and the program carried on without noticing.
A page fault sounds like an error. Usually it is not. It is the kernel's way of doing work only when it is needed. But the same mechanism is also how a program crashes with a segmentation fault, and how a server can slow down by a factor of a hundred when it runs short of RAM. This page follows a page fault from start to finish, explains the three verdicts the kernel can reach, works out which page to throw out when RAM is full, and ends with the failure every engineer meets eventually: thrashing.
1. What happens during a page fault
A program reads or writes an address. The memory management unit (2.5.1) looks up the page in the TLB and then the page tables (2.5.2). Suppose the entry says "not present", or the access breaks a permission, such as writing to a read-only page. The MMU cannot finish the access, so it raises an exception and jumps into the kernel. That exception is the page fault.
The CPU hands the kernel two facts: the address that failed, and what the program was trying to do (read, write or run code). The kernel then works through these steps.
- Find the region. The kernel keeps, for every process, a list of the regions of address space the process was given: "the heap runs from here to here, readable and writable", "this library's code runs from here to here, readable and runnable". Each entry is called a memory region (in Linux, a VMA, virtual memory area). The kernel looks for the region that contains the failed address.
- Decide the verdict. Is the address inside a region at all? Is the access allowed by that region's permissions? Section 2 lists the possible answers.
- If it is allowed, get a frame. Take a free physical frame. If none is free, make one free by evicting some other page (section 4).
- Fill the frame. Depending on the region, fill it with zeros, copy it from another frame, or read it from a file or the swap area on disk.
- Update the page table. Point the entry at the new frame and set it present.
- Return and retry. Return to the program, and run the failed instruction again. This time it succeeds.
Step 6 is what makes page faults invisible. The program is not told anything. The instruction that faulted simply runs a second time, and works.
2. Three verdicts: minor, major and invalid
The kernel can reach three different verdicts, and they have very different costs.
| Verdict | What it means | Rough cost |
|---|---|---|
| Minor fault | page can be filled without reading the disk | about a microsecond |
| Major fault | page must be read from the disk | 0.1 ms (SSD) to 10 ms (hard disk) |
| Invalid | no region, or the access is not allowed | the process is sent SIGSEGV |
(The costs are rough orders of magnitude. They depend heavily on the machine.)
Minor faults: cheap and constant
A minor fault is one the kernel can satisfy from memory. There are three common cases.
- First touch of new memory. Our 1 GB buffer was marked "allocated but not present". On first touch, the kernel finds a frame, fills it with zeros so the process never sees another process's old data, and maps it. This is demand paging: memory is given out only when demanded.
- Copy-on-write. After
fork, parent and child share pages marked read-only (2.2.2). A write faults. The kernel sees the region is really writable, copies just that page, maps the copy, and retries. - The page is already in memory, just not mapped here. A shared library's code may already be in RAM because another program uses it. The kernel only needs to point this process's page-table entry at the existing frame.
A busy program has thousands of minor faults a second. They are completely normal.
Major faults: when the disk gets involved
A major fault needs data from the disk. That happens when the page belongs to a file that is not in memory yet, such as the first run of a program or the first read of a memory-mapped file (2.5.4), or when the page was moved out to the swap area earlier (section 4). The process sleeps, in the blocked state from 2.2.1, while the disk works. One major fault can cost as much as a hundred thousand minor ones. A few at startup are normal. A steady stream of them on a running server is a warning sign.
Invalid accesses: the segmentation fault
The third verdict is that the access is simply wrong. The address is in no region the process was given, such as address 8 from a null pointer. Or it breaks the region's rules, such as a write into read-only code, or an attempt to run code from data marked no-execute. This is not a page to load. It is a bug.
So the kernel sends the process the signal SIGSEGV (2.2.3), whose default action ends the process. That is the famous "Segmentation fault" message. A segmentation fault is a page fault that the kernel decided was a bug instead of a chance to load a page. Same hardware event, different verdict. The name comes from older hardware that divided memory into segments rather than pages; the name stayed when the hardware changed.
SIGSEGV.3. When RAM fills up
So far there was always a free frame to hand out. Eventually there is not. The upload service, the browser, the kernel's own caches and everything else have filled RAM. A process touches a new page. Where does the frame come from?
The kernel must take a frame away from some other page, called evicting it. What it does with the old contents depends on what kind of page it was.
- A page backed by a file, and unchanged. Program code and file data that has only been read can simply be dropped. If it is needed again, it can be read from the file again.
- A page backed by a file, and changed. Its dirty bit (2.5.1) is set. It must be written back to its file before the frame is reused.
- Anonymous memory. A heap or stack page belongs to no file. If it holds data, it must be written somewhere, or the data is lost. That somewhere is the swap area: a partition or file on disk set aside for exactly this. Windows calls it the page file. When the page is needed again, it causes a major fault and is read back.
So RAM behaves like a cache for a larger memory that lives partly on disk. This is the memory hierarchy of 1.6 once again, one level further down.
Much of what fills RAM on a healthy machine is the page cache: copies of file data the kernel keeps in otherwise unused memory, so that reading a file a second time is instant (2.6.2). That is why "free" memory on a Linux server often looks almost zero. The memory is not wasted; it is caching files, and the kernel gives it up the moment a program needs it.
4. Which page should go? Replacement algorithms, worked
Every eviction raises one question: which page should be thrown out? Throw out a page that is about to be used again, and you pay for a major fault almost immediately. The rule that decides is called a page replacement policy. To compare policies, textbooks use a short list of page numbers in the order a program touches them, called a reference string, and count the faults. Here is the classic one, with RAM holding just 3 frames:
text
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1And here is a simulator that counts the faults for three policies.
ts
// page-replacement.ts — count page faults for FIFO, LRU and the optimal policy
type Policy = "FIFO" | "LRU" | "OPT";
function faults(refs: number[], frames: number, policy: Policy): number {
const inRam: number[] = []; // (1) pages currently in RAM
const lastUsed = new Map<number, number>();
let count = 0;
refs.forEach((page, t) => {
if (inRam.includes(page)) { lastUsed.set(page, t); return; } // (2) hit: nothing to load
count++; // (3) miss: a page fault
if (inRam.length === frames) { // (4) RAM full: choose a victim
let victim = 0; // FIFO: the oldest arrival is index 0
if (policy === "LRU")
victim = inRam.reduce((v, p, i) => (lastUsed.get(p)! < lastUsed.get(inRam[v])! ? i : v), 0);
if (policy === "OPT") {
const nextUse = (p: number) => { const k = refs.indexOf(p, t + 1); return k < 0 ? Infinity : k; };
victim = inRam.reduce((v, p, i) => (nextUse(p) > nextUse(inRam[v]) ? i : v), 0);
}
inRam.splice(victim, 1); // (5) evict it
}
inRam.push(page);
lastUsed.set(page, t);
});
return count;
}
const refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1];
for (const p of ["FIFO", "LRU", "OPT"] as const) console.log(`${p}, 3 frames: ${faults(refs, 3, p)} faults`);
const belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];
console.log(`FIFO, 3 frames: ${faults(belady, 3, "FIFO")} faults; 4 frames: ${faults(belady, 4, "FIFO")} faults`);
// Prints:
// FIFO, 3 frames: 15 faults
// LRU, 3 frames: 12 faults
// OPT, 3 frames: 9 faults
// FIFO, 3 frames: 9 faults; 4 frames: 10 faults(1)inRamis the list of pages in the 3 frames, kept in the order they arrived.(2)If the page is already in RAM, it is a hit. We note when it was last used, for LRU.(3)Otherwise it is a page fault.(4)If all frames are full, each policy picks a victim in its own way, explained below.(5)The victim leaves, and the new page joins at the end.
Here are the first eleven references, step by step, so you can follow each policy's choices. Each cell shows what is in RAM after that reference, and which page was evicted.
| # | Page | FIFO | LRU | OPT |
|---|---|---|---|---|
| 1 | 7 | fault: 7 | fault: 7 | fault: 7 |
| 2 | 0 | fault: 7 0 | fault: 7 0 | fault: 7 0 |
| 3 | 1 | fault: 7 0 1 | fault: 7 0 1 | fault: 7 0 1 |
| 4 | 2 | out 7: 0 1 2 | out 7: 0 1 2 | out 7: 0 1 2 |
| 5 | 0 | hit | hit | hit |
| 6 | 3 | out 0: 1 2 3 | out 1: 0 2 3 | out 1: 0 2 3 |
| 7 | 0 | out 1: 2 3 0 | hit | hit |
| 8 | 4 | out 2: 3 0 4 | out 2: 0 3 4 | out 0: 2 3 4 |
| 9 | 2 | out 3: 0 4 2 | out 3: 0 4 2 | hit |
| 10 | 3 | out 0: 4 2 3 | out 0: 4 2 3 | hit |
| 11 | 0 | out 4: 2 3 0 | out 4: 2 3 0 | out 4: 2 3 0 |
FIFO: throw out the oldest
First in, first out evicts the page that has been in RAM longest, like the oldest carton of milk in the fridge. It is simple, but it ignores whether a page is still being used. Look at step 6: FIFO evicts page 0, the oldest, even though page 0 was used just one step earlier and is used again at step 7. So step 7 faults at once. Over all 20 references, FIFO makes 15 faults.
OPT: throw out the page needed furthest in the future
The best possible policy, called optimal or OPT, evicts the page whose next use is furthest away. László Bélády described it in 1966 and proved that nothing can beat it. At step 8, the pages in RAM are 0, 2 and 3. Page 2 is next used at step 9, page 3 at step 10, and page 0 not until step 11. So OPT evicts page 0, and steps 9 and 10 become hits. OPT makes only 9 faults.
There is one problem. OPT needs to know the future, and a real kernel does not. So OPT is never used in practice. It is the yardstick: a real policy is judged by how close it comes to 9.
LRU: use the past to guess the future
Least recently used evicts the page whose last use was longest ago. The bet is that the recent past predicts the near future, because of locality (1.6): a page used a moment ago is likely to be used again soon. At step 6, LRU sees that page 1 was last used at step 3, longer ago than 0 or 2, and evicts it. That keeps page 0 for step 7, which becomes a hit. LRU makes 12 faults, between FIFO and the optimum.
Belady's anomaly: more memory, more faults
The last line of output is a famous surprise. With the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 frames, but 10 faults with 4 frames. Adding memory made things worse. This is Bélády's anomaly, found in 1969.
It happens because FIFO's choice depends on arrival order, not on use, so a bigger RAM can change the order of evictions in an unlucky way. LRU and OPT can never show this anomaly. With them, the pages in a bigger RAM are always a superset of the pages in a smaller one, so adding frames can only remove faults. That property is one more reason real systems approximate LRU rather than FIFO.
What kernels really do: the clock algorithm
Exact LRU would mean recording the time of every memory access, billions per second, which is impossible. Real kernels approximate it cheaply using the accessed bit, which the hardware sets in a page-table entry whenever the page is used (2.5.1).
The classic approximation is the clock algorithm, also called second chance. Picture all the frames arranged in a circle, with a hand pointing at one of them, like a clock.
- When a frame is needed, look at the page under the hand.
- If its accessed bit is 1, the page was used recently. Give it a second chance: clear the bit to 0 and move the hand on.
- If its accessed bit is 0, the page has not been used since the hand last passed. Evict it.
A page that is in constant use keeps getting its bit set again before the hand comes round, so it is never evicted. A page nobody touches loses its bit on one pass and is evicted on the next. Linux uses a more elaborate version with "active" and "inactive" lists of pages, and since Linux 6.1 a newer scheme with several generations of pages, but the idea is the same: use the hardware's accessed bits to find pages that have not been touched lately.
5. The working set and thrashing
Every program has a working set: the pages it is actively using right now. Peter Denning introduced the idea in 1968. For the upload service handling a steady flow of photos, the working set might be its code, its request buffers and the parts of its heap holding photos in progress, perhaps a few hundred megabytes. Pages outside the working set, such as start-up code it ran once, can be evicted at almost no cost.
As long as the working sets of all running programs fit in RAM, page replacement works beautifully. The pages evicted are ones nobody needs, and major faults are rare.
Now suppose they do not fit. The combined working sets need 20 GB, and the machine has 16 GB. Then every page the kernel evicts is a page some program is about to use. It evicts a page, which immediately faults back in, which forces another page out, which immediately faults back in. Every program spends its time waiting for the disk. This is thrashing.
The symptoms are unmistakable, and frightening the first time:
- The machine becomes extremely slow. Simple commands take seconds or minutes to respond.
- The disk is busy all the time, even though no program is "doing" disk work. The kernel is doing it, moving pages in and out.
- The CPU is mostly idle, because every process is blocked waiting for a page.
On Linux, the command vmstat 1 prints a line every second. Two of its columns, si and so, show how much memory is being swapped in and out per second. On a healthy server they are 0. On a thrashing server they are large and steady.
The fixes all make the working sets fit again: add RAM, run fewer programs on the machine, fix whatever is growing (a memory leak, or a cache with no size limit), or reduce how much each program keeps in memory. Thrashing is the reason servers are sized so that the working set fits in RAM with room to spare, and the reason many server teams run with little or no swap at all. They would rather a program fail quickly than have the whole machine crawl.
6. Overcommit and the out-of-memory killer
There is one more piece, and it explains a behaviour that confuses many people. On Linux, malloc almost never fails, even when you ask for more memory than the machine has. Then, later, a program is suddenly killed with no error at all.
The reason is overcommit. Because of demand paging, a program that asks for memory is only given virtual addresses, not frames (2.5.1). Many programs ask for far more than they ever touch. So by default, Linux hands out more virtual memory than it could ever back with real RAM and swap, betting that not everyone will use all of theirs at once. It refuses only requests that are obviously impossible.
Usually the bet pays off. When it does not, and processes really do touch more memory than exists, the kernel has a problem: a page fault needs a frame, and there are none left to take. So it runs the out-of-memory killer, often called the OOM killer. It scores every process, mostly by how much memory it uses, and kills the one with the highest score, freeing its memory at once. The kernel log records it with a line such as "Out of memory: Killed process 4012 (node)".
The killed process gets no warning. It receives SIGKILL (2.2.3), which cannot be caught, so it ends with exit code 137. In a container, the same thing happens when the container exceeds its own memory limit, even if the machine has memory to spare, because the limit is enforced per container (14.1.3). Kubernetes reports it as OOMKilled.
Administrators can change the bet. Linux has a setting that refuses to promise more memory than exists, so malloc fails honestly instead, and a per-process score adjustment that protects important processes, such as a database, from the OOM killer.
What the interviewer will push on
"What is a page fault? Is it an error?" They are checking that you know most page faults are normal. A good answer separates the three verdicts: minor faults filled from memory, major faults that read the disk, and invalid accesses that become a segmentation fault. The tell is saying the faulting instruction is retried, which is why the program never notices.
"What actually is a segmentation fault?" A page fault that the kernel found was outside any region the process was given, or broke that region's permissions. The kernel sends SIGSEGV. Mention null pointers landing in the unmapped first page.
"Compare FIFO, LRU and optimal page replacement." Know that OPT evicts the page used furthest in the future and is the unbeatable yardstick, LRU evicts the least recently used and approximates it, and FIFO evicts the oldest and can show Bélády's anomaly. Be ready to count faults on a short reference string by hand.
"How do real kernels approximate LRU?" The clock algorithm, using the hardware's accessed bit: clear it on the first pass, evict on the second if it is still clear.
"What is thrashing, and why does adding RAM fix it?" When the working sets do not fit, every eviction removes a page that is needed at once, and the machine spends its time swapping. More RAM lets the working set fit, so evictions stop hitting live pages.
"Why can a Linux process be killed although malloc never failed?" Overcommit and the OOM killer. The memory was promised as virtual addresses, and when it was actually touched there were no frames left.
Something to volunteer that nobody asks for: "free memory" near zero on a Linux server is usually healthy, because the page cache fills spare RAM with file data and gives it back instantly. The numbers to watch are swapping (si and so) and major faults, not free memory.
Recall
- A page fault is an exception when a page is not present or an access breaks its permissions. The kernel finds the memory region, gets and fills a frame, updates the page table and retries the instruction.
- There are three verdicts. A minor fault is filled from memory: first touch with demand paging, copy-on-write, or a shared page. A major fault reads the disk and is about 100,000 times slower. An invalid access gets SIGSEGV, a segmentation fault.
- When RAM is full, the kernel evicts pages: clean file pages are dropped, dirty ones written back, anonymous ones sent to swap. Spare RAM holds the page cache.
- Replacement: first in, first out (15 faults on the classic string, and it suffers Bélády's anomaly), least recently used (12), optimal (9, needs the future). Kernels approximate LRU with the clock algorithm and the hardware's accessed bit.
- When the combined working set exceeds RAM, the machine thrashes. Linux overcommits memory, and when it truly runs out, the out-of-memory killer sends
SIGKILLto the largest process (exit 137,OOMKilledin containers).
Self-test: Why does a program never notice a minor page fault? What makes a fault major rather than minor? At step 6 of the trace, why does LRU keep page 0 when FIFO evicts it? How can 4 frames give more faults than 3? A server's disk is busy, its CPU idle, and si/so are large. What is happening and what fixes it?
Quiz Bank
FoundationalWhat is a page fault, and how can the same mechanism be both routine and fatal?
A page fault is a hardware exception raised when a program touches a page that is not present in RAM, or accesses a page in a way its permissions forbid. The kernel looks up which region of the process's address space the address belongs to.
Routine: if the address is in a region the process may use, the kernel gets a frame, fills it with zeros, a copy or data from disk, maps it, and retries the instruction. That is a minor or major fault, and the program never notices. Fatal: if the address is in no region, or the access breaks the region's rules, the kernel sends SIGSEGV, which ends the process with a segmentation fault. Same event, different verdict.
FoundationalWhat is the difference between a minor and a major page fault?
A minor fault can be handled entirely in memory: zero-filling a newly touched page, copying a page for copy-on-write, or mapping a page that is already in RAM because another process uses it. It costs around a microsecond. A major fault needs data from the disk, either from a file that is not cached or from the swap area. The process sleeps while the disk reads it, which costs from about a tenth of a millisecond on an SSD to about ten milliseconds on a hard disk. A steady stream of major faults on a running server usually means it is short of RAM.
AppliedWith 3 frames and the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, how many faults do FIFO, LRU and OPT make, and why do they differ?
FIFO makes 15, LRU makes 12 and OPT makes 9. FIFO evicts the page that arrived first, regardless of use, so at the sixth reference it evicts page 0, which was just used and is needed again next, causing an immediate fault. LRU evicts the page used least recently, page 1 at that point, so it keeps page 0. OPT evicts the page whose next use is furthest in the future, which is provably the minimum number of faults, but it needs knowledge of the future, so real kernels can only approximate it, usually with LRU-like methods.
InterviewWhat is thrashing, and why does adding RAM fix it?
Thrashing happens when the combined working sets of the running programs, the pages they are actively using, exceed physical RAM. The kernel must evict pages that are needed again almost immediately, so each eviction causes a major fault that forces out another needed page. The machine spends nearly all its time moving pages between RAM and disk, which is about 100,000 times slower, and almost none doing useful work: the disk is busy, the CPU is idle, and everything crawls.
Adding RAM fixes it because, once the working sets fit, evictions only remove pages nobody needs, so the constant faulting stops. Reducing what runs on the machine, or fixing a leak, has the same effect.
InterviewWhat is Bélády's anomaly?
Bélády's anomaly is the surprising result that, for some reference strings, giving the FIFO page replacement policy more frames causes more page faults. With the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 frames and 10 with 4. It happens because FIFO evicts by arrival order, which a larger memory can change unluckily. Policies such as LRU and OPT never show it, because the pages they keep in a larger memory always include the pages they would keep in a smaller one.
StaffA production service runs fine for hours, then latency jumps a hundredfold and the host's disk saturates, although the application does no disk work. Diagnose using this page.
A sudden hundredfold slowdown with a saturated disk and an application that does no disk work strongly suggests the host has started swapping and is thrashing. Over the hours, something grew: a memory leak, a cache with no size limit, or simply more load. Eventually the working set no longer fit in RAM, so the kernel began evicting live pages to swap and faulting them back. Ordinary memory accesses now sometimes wait for the disk. The disk traffic is the kernel moving pages, not the application.
Confirm it with vmstat (steady non-zero si and so), the major-fault counts per process, and each process's memory over time. In the short term, relieve memory pressure: restart or scale out the growing process, cap its memory, or move load elsewhere. Permanently, find why it grew, and size the host so the working set fits with headroom. Many teams also run with little or no swap, so that a process hitting its limit fails fast instead of dragging the whole host into thrashing.
Scenario Drill
DrillThe photo-upload service runs in a container with a 512 MB memory limit. It is killed a few times a day with exit code 137, although its average memory use is 300 MB and the host has 20 GB free. Using this page, explain what is happening and what you would change.
Exit code 137 is SIGKILL, and with a memory limit involved the likely sender is the out-of-memory killer, enforcing the container's limit. The host's free memory is irrelevant, because the limit applies to the container alone. The average of 300 MB hides peaks. A burst of large uploads, each held in memory while being processed, can push the service past 512 MB for a moment, and that is enough.
Because the kill is SIGKILL, the service gets no warning and cannot shut down gracefully, so uploads in progress are lost.
To fix it, first measure the peak, not the average, and set the limit above the real peak with headroom. Then bound the peak itself: stream uploads to disk instead of holding whole photos in memory (3.8.4), limit how many uploads are processed at once, and check for a leak if memory keeps climbing between bursts. Raising the limit alone only delays the problem if memory use is unbounded.
Next: we have seen the kernel hand out pages. But programs do not ask for pages; they ask for a 300-byte object, or a 5 MB photo buffer. Page 2.5.4 covers the two layers in between: mmap, which maps whole regions and even files into memory, and the memory allocator, which turns pages into the small pieces your program actually uses.