Virtual Memory: Demand Paging, Page Replacement and Thrashing

What virtual memory is and why it matters

In the memory management lesson every page of a process sat in a physical frame. Virtual memory removes that requirement: a process can run even when only some of its pages are in RAM. The rest live on disk (in a swap area or in the file they came from) and are brought in only when touched.

This gives you three big wins:

1. Programs larger than RAM can run, because only the part in use needs to be resident.
2. More programs fit at once, because each one occupies only its working pages. That raises CPU utilisation.
3. Cheaper process creation and sharing, through tricks like copy-on-write and memory-mapped files.

The cost is complexity: the OS must decide which pages to keep, which to throw out, and how to avoid spending all its time moving pages around. Interviewers probe exactly these decisions. Expect to trace FIFO, LRU and Optimal on a reference string by hand, explain Belady's anomaly, define thrashing and the working set, and describe what happens on a page fault. On the practical side, copy-on-write after fork(), mmap, huge pages and the Linux OOM killer come up often in backend and systems interviews.

Demand paging

Demand paging means a page is loaded into RAM only when the process first accesses it, never in advance. A process starts with few or no pages resident; each first touch of a page causes a page fault, and the OS loads that page. A loader that brings in nothing until it is needed is sometimes called a lazy swapper, though the right word is pager, since it moves pages, not whole processes.

The page table's valid bit (also called the present bit) drives this:

• valid = 1: the page is in RAM and the frame number is correct.
• valid = 0: the page is either not part of the address space at all, or it is legal but currently on disk.

  Page table              RAM frames        Disk (backing store)
  page frame valid        +--------+        +---------------+
   0     4     1          |  ...   |        | pages 0..7    |
   1     -     0  ------------------------> | page 1 here   |
   2     6     1          | frame 4: pg 0   |               |
   3     -     0  ------------------------> | page 3 here   |
                          | frame 6: pg 2   |               |
                          +--------+        +---------------+

What happens on a page fault

A page fault is the trap the MMU raises when a process touches a page whose valid bit is 0. Here are the steps the OS takes, in order:

1. The MMU finds valid = 0 and traps to the kernel. The CPU saves the user registers and the faulting address (on x86 the address goes into the CR2 register).
2. The kernel checks whether the access is legal: is the address inside a region the process owns (a mapped area), and does the access type (read, write, execute) match its permissions?
3. If it is illegal, the kernel sends the process a signal, SIGSEGV on Linux, and usually the process dies with "Segmentation fault".
4. If it is legal, the kernel finds a free frame. If none is free, it runs the page replacement algorithm to pick a victim frame; if the victim is dirty, it is written back to disk first.
5. The kernel schedules a disk read of the needed page into the frame. The faulting process is blocked, and the CPU runs another process meanwhile.
6. When the disk interrupt signals completion, the kernel updates the page table entry: frame number and valid = 1.
7. The process becomes ready again. When it is scheduled, the faulting instruction is restarted from the beginning, and this time it succeeds.

 process        MMU          kernel             disk
    | load X     |              |                 |
    |----------->| valid=0      |                 |
    |            |--trap------->| check legal     |
    |            |              | pick frame      |
    |            |              |--read page----->|
    |   (blocked; other processes run)            |
    |            |              |<--interrupt-----|
    |            |              | PTE valid=1     |
    |<----------restart instruction---------------|

Restarting instructions is subtle: the hardware must be able to undo or re-execute any instruction that faults halfway. Instructions that modify several locations (for example a block move whose source and destination overlap) need special hardware support. This is why demand paging needs both an MMU with valid bits and restartable instructions.

Minor and major faults

Linux distinguishes two kinds of page fault:

• A major (hard) fault needs disk I/O: the page really is on disk.
• A minor (soft) fault needs no I/O: the page is already in RAM, perhaps in the page cache or shared with another process, and the kernel only needs to fix up the page table. First touch of a freshly allocated anonymous page, which the kernel fills with zeros, is also a minor fault.

You can see both counters with ps -o min_flt,maj_flt -p <pid> or /usr/bin/time -v on Linux.

Performance of demand paging

The effective access time (EAT) with a page-fault rate p is:

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

Assume a memory access takes 200 ns and servicing a page fault takes 8 ms (8,000,000 ns), which is reasonable for a hard disk.

• If 1 access in 1000 faults (p = 0.001): EAT = 0.999 x 200 + 0.001 x 8,000,000 = 199.8 + 8000 = 8199.8 ns, about 8.2 microseconds. The machine runs about 40 times slower than with no faults.
• To keep the slowdown under 10 percent (EAT under 220 ns): 220 > 200 + p x (8,000,000 - 200), so p < 20 / 7,999,800, which is about 2.5 x 10^-6. That is fewer than one fault per 400,000 accesses.

The lesson: page faults must be extremely rare. Locality of reference makes that possible, and good replacement algorithms keep it that way. On an SSD the fault service time is far smaller (tens to hundreds of microseconds) but it is still thousands of times slower than RAM.

Page replacement

When a page fault occurs and every frame is in use, the OS must evict a page to make room. This is page replacement. The page that is evicted is the victim.

The basic procedure:

1. Find the needed page on disk.
2. Find a free frame. If there is none, choose a victim with the replacement algorithm.
3. If the victim's dirty bit is set (it was modified), write it back to disk. If it is clean, just discard it; a copy already exists on disk.
4. Read the needed page into the freed frame, update both page table entries, and restart the process.

The dirty bit halves the cost of replacing clean pages, since only one disk transfer is needed. Code pages are always clean.

To compare algorithms we use a reference string: the sequence of page numbers a program accesses. We count page faults for a given number of frames. Fewer faults is better. In all traces below, the first reference to each page is a fault even when frames are free (these are called compulsory or cold-start misses).

FIFO (first in, first out)

Evict the page that has been in memory the longest. Implementation is a simple queue: new pages join the tail, the victim comes off the head. FIFO ignores how often or how recently a page is used, so it happily evicts a heavily used page just because it was loaded early.

Optimal (OPT, also called MIN or Belady's algorithm)

Evict the page that will not be used for the longest time in the future. It provably gives the fewest faults possible for a given number of frames. It cannot be implemented in a real OS because it needs to know the future, but it is the benchmark you compare other algorithms against.

LRU (least recently used)

Evict the page that has not been used for the longest time in the past. The idea: the recent past predicts the near future (temporal locality). LRU is OPT looking backwards. It often comes close to OPT on real workloads, but implementing it exactly needs hardware help on every memory access:

• Counters: stamp each page table entry with a clock value on every access; evict the smallest stamp. Needs a search and a write on every access.
• Stack: keep a doubly linked list of pages; on access move the page to the top; evict from the bottom. Needs several pointer updates on every access.

No mainstream hardware does either on every memory reference, so real systems use approximations (Clock and friends, below).

Worked example 1: one string, four algorithms

Reference string (12 references), 3 frames:

2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2

In each table, columns are references, rows F0 to F2 are frames, and F in the bottom row marks a fault. A page stays in the same frame row until it is evicted.

FIFO trace

Ref    2  3  2  1  5  2  4  5  3  2  5  2
F0     2  2  2  2  5  5  5  5  3  3  3  3
F1     -  3  3  3  3  2  2  2  2  2  5  5
F2     -  -  -  1  1  1  4  4  4  4  4  2
       F  F     F  F  F  F     F     F  F

Step by step through the interesting moments:

• Refs 1 to 4: 2, 3 (faults), 2 (hit), 1 (fault). Load order: 2, 3, 1.
• Ref 5 = 5: frames full. Oldest is 2, evict it. Queue: 3, 1, 5.
• Ref 6 = 2: fault. Oldest is 3, evict. Queue: 1, 5, 2.
• Ref 7 = 4: fault. Evict 1. Queue: 5, 2, 4.
• Ref 8 = 5: hit.
• Ref 9 = 3: fault. Evict 5. Queue: 2, 4, 3.
• Ref 10 = 2: hit.
• Ref 11 = 5: fault. Evict 2. Queue: 4, 3, 5.
• Ref 12 = 2: fault. Evict 4.

FIFO: 9 faults. Notice FIFO evicted page 2 twice even though 2 is the most popular page in the string.

Optimal trace

Ref    2  3  2  1  5  2  4  5  3  2  5  2
F0     2  2  2  2  2  2  4  4  4  2  2  2
F1     -  3  3  3  3  3  3  3  3  3  3  3
F2     -  -  -  1  5  5  5  5  5  5  5  5
       F  F     F  F     F        F

• Ref 5 = 5: frames hold 2, 3, 1. Next uses: 2 at ref 6, 3 at ref 9, 1 never. Evict 1.
• Ref 7 = 4: frames 2, 3, 5. Next uses: 2 at ref 10, 3 at ref 9, 5 at ref 8. Farthest is 2. Evict 2.
• Ref 10 = 2: frames 4, 3, 5. Next uses: 4 never, 3 never, 5 at ref 11. Either 4 or 3 can go; we evict 4. (Ties among never-used pages can be broken any way; the count is the same.)

Optimal: 6 faults. No algorithm can do better on this string with 3 frames.

LRU trace

Ref    2  3  2  1  5  2  4  5  3  2  5  2
F0     2  2  2  2  2  2  2  2  3  3  3  3
F1     -  3  3  3  5  5  5  5  5  5  5  5
F2     -  -  -  1  1  1  4  4  4  2  2  2
       F  F     F  F     F     F  F

• Ref 5 = 5: last uses were 2 at ref 3, 3 at ref 2, 1 at ref 4. Least recent is 3. Evict it.
• Ref 6 = 2: hit (2 is resident).
• Ref 7 = 4: last uses: 2 at ref 6, 5 at ref 5, 1 at ref 4. Evict 1.
• Ref 8 = 5: hit.
• Ref 9 = 3: last uses: 2 at 6, 5 at 8, 4 at 7. Evict 2.
• Ref 10 = 2: last uses: 3 at 9, 5 at 8, 4 at 7. Evict 4.
• Refs 11 and 12: 5 and 2 are hits.

LRU: 7 faults.

Clock (second chance) trace

Clock is explained in detail below. Each frame has a reference bit; the hand points at the next candidate. A hit sets the page's bit to 1. On a fault the hand moves forward, clearing bits that are 1 and giving those pages a second chance, until it finds a bit of 0 (or an empty frame); that page is replaced, the new page gets bit 1, and the hand advances one step.

Ref  Frames (bits)          Hand after  Result
 2   [2* -  -  ] (1 0 0)       F1       fault
 3   [2  3* -  ] (1 1 0)       F2       fault
 2   [2  3  -  ] (1 1 0)       F2       hit
 1   [2  3  1* ] (1 1 1)       F0       fault
 5   [5* 3  1  ] (1 0 0)       F1       fault: sweep clears all, evicts 2
 2   [5  2* 1  ] (1 1 0)       F2       fault: F1 bit 0, evicts 3
 4   [5  2  4* ] (1 1 1)       F0       fault: F2 bit 0, evicts 1
 5   [5  2  4  ] (1 1 1)       F0       hit
 3   [3* 2  4  ] (1 0 0)       F1       fault: sweep clears all, evicts 5
 2   [3  2  4  ] (1 1 0)       F1       hit
 5   [3  2  5* ] (1 0 1)       F0       fault: F1 cleared, evicts 4
 2   [3  2  5  ] (1 1 1)       F0       hit

* marks the page just loaded. Clock: 8 faults, between LRU (7) and FIFO (9), which is typical: Clock approximates LRU cheaply.

Worked example 2: LRU is not always better than FIFO

Reference string (15 references): 1, 2, 3, 2, 4, 1, 3, 2, 4, 5, 2, 3, 1, 4, 2

3 frames, FIFO:

Ref    1  2  3  2  4  1  3  2  4  5  2  3  1  4  2
F0     1  1  1  1  4  4  4  4  4  5  5  5  5  4  4
F1     -  2  2  2  2  1  1  1  1  1  1  3  3  3  2
F2     -  -  3  3  3  3  3  2  2  2  2  2  1  1  1
       F  F  F     F  F     F     F     F  F  F  F

3 frames, LRU:

Ref    1  2  3  2  4  1  3  2  4  5  2  3  1  4  2
F0     1  1  1  1  4  4  4  2  2  2  2  2  2  4  4
F1     -  2  2  2  2  2  3  3  3  5  5  5  1  1  1
F2     -  -  3  3  3  1  1  1  4  4  4  3  3  3  2
       F  F  F     F  F  F  F  F  F     F  F  F  F

3 frames, Optimal:

Ref    1  2  3  2  4  1  3  2  4  5  2  3  1  4  2
F0     1  1  1  1  1  1  1  2  2  2  2  2  2  2  2
F1     -  2  2  2  4  4  4  4  4  5  5  5  1  4  4
F2     -  -  3  3  3  3  3  3  3  3  3  3  3  3  3
       F  F  F     F        F     F        F  F

Totals with 3 frames: FIFO 11, LRU 13, Optimal 8. Here LRU does worse than FIFO, because this string cycles through four pages with only three frames, and LRU keeps evicting exactly the page that comes back next. With 4 frames the same string gives FIFO 7, LRU 7, Optimal 6.

The takeaway for interviews: LRU is usually good on real programs because real programs have locality, not because it beats FIFO on every input. Looping access patterns larger than memory are LRU's worst case; databases often use different policies for sequential scans for this reason.

Worked example 3: Belady's anomaly

You would expect more frames to mean fewer (or equal) faults. For FIFO that is not guaranteed. Belady's anomaly is the situation where giving an algorithm more frames produces more page faults.

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

FIFO with 3 frames:

Ref    1  2  3  4  1  2  5  1  2  3  4  5
F0     1  1  1  4  4  4  5  5  5  5  5  5
F1     -  2  2  2  1  1  1  1  1  3  3  3
F2     -  -  3  3  3  2  2  2  2  2  4  4
       F  F  F  F  F  F  F        F  F

9 faults.

FIFO with 4 frames:

Ref    1  2  3  4  1  2  5  1  2  3  4  5
F0     1  1  1  1  1  1  5  5  5  5  4  4
F1     -  2  2  2  2  2  2  1  1  1  1  5
F2     -  -  3  3  3  3  3  3  2  2  2  2
F3     -  -  -  4  4  4  4  4  4  3  3  3
       F  F  F  F        F  F  F  F  F  F

10 faults. One more frame, one more fault.

Why it happens: with 4 frames, pages 1 and 2 survive long enough to be hits at references 5 and 6, so 1 and 2 become the oldest pages exactly when they are about to be needed again, and FIFO evicts them right before reuse. With 3 frames the eviction order happens to line up better with the future.

For this string, the fault counts for 1 to 6 frames are:

LRU and Optimal never show the anomaly. They are stack algorithms: the set of pages in memory with n frames is always a subset of the set with n + 1 frames. With that inclusion property, adding a frame can never turn a hit into a miss. FIFO is not a stack algorithm, so it can.

A simulator you can run

Use this to check any trace before an exam or interview:

from collections import OrderedDict, deque

def fifo(refs, frames):
    resident, order, faults = set(), deque(), 0
    for page in refs:
        if page in resident:
            continue
        faults += 1
        if len(resident) == frames:
            resident.remove(order.popleft())
        resident.add(page)
        order.append(page)
    return faults

def lru(refs, frames):
    recent, faults = OrderedDict(), 0      # oldest use first
    for page in refs:
        if page in recent:
            recent.move_to_end(page)
            continue
        faults += 1
        if len(recent) == frames:
            recent.popitem(last=False)
        recent[page] = True
    return faults

def optimal(refs, frames):
    resident, faults = [], 0
    for i, page in enumerate(refs):
        if page in resident:
            continue
        faults += 1
        if len(resident) == frames:
            future = refs[i + 1:]
            victim = max(resident, key=lambda p: future.index(p) if p in future else len(future))
            resident.remove(victim)
        resident.append(page)
    return faults

def clock(refs, frames):
    slots, ref_bit, hand, faults = [None] * frames, [0] * frames, 0, 0
    for page in refs:
        if page in slots:
            ref_bit[slots.index(page)] = 1
            continue
        faults += 1
        while slots[hand] is not None and ref_bit[hand] == 1:
            ref_bit[hand] = 0              # second chance
            hand = (hand + 1) % frames
        slots[hand], ref_bit[hand] = page, 1
        hand = (hand + 1) % frames
    return faults

refs = [2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2]
for algo in (fifo, lru, optimal, clock):
    print(f"{algo.__name__:8} {algo(refs, 3)}")   # 9, 7, 6, 8

belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print("FIFO 3 frames:", fifo(belady, 3), " 4 frames:", fifo(belady, 4))  # 9, 10

LRU approximations

Most hardware provides one reference bit (accessed bit) per page, set automatically whenever the page is read or written. The OS can read and clear it. That single bit is enough to approximate LRU.

Additional reference bits (aging)

Keep an 8-bit history byte per page. At every timer interrupt (say every 100 ms), shift each page's byte one place right and copy the reference bit into the top bit, then clear the reference bit. A page used in the last interval has history 1xxxxxxx; one not used for eight intervals has 00000000. Interpreting the byte as an unsigned number, the page with the smallest value is the least recently used (approximately). For example 11000100 (used in the last two intervals) beats 01110111 (not used in the last interval).

Second chance (Clock)

Second chance is FIFO with one improvement: before evicting the oldest page, check its reference bit.

• Bit = 0: evict it.
• Bit = 1: clear the bit, move the page to the back of the queue as if it had just arrived (its second chance), and check the next page.

The Clock algorithm is the efficient implementation: the frames form a circular list, and a "hand" points at the oldest page. Instead of moving pages, the hand moves.

            +-----+
      +---> | A 1 | ----+
      |     +-----+     v
   +-----+           +-----+
   | D 0 |           | B 0 |  <- hand: B has bit 0, evict B
   +-----+           +-----+
      ^     +-----+     |
      +---- | C 1 | <---+
            +-----+

If every bit is 1, the hand goes all the way round clearing them, and Clock degenerates to FIFO for that fault. Linux's page reclaim is not literally Clock but is built on the same idea: it keeps active and inactive lists per memory zone (with a multi-generational LRU option in recent kernels) and uses accessed bits to decide which pages move between them.

Enhanced second chance (enhanced Clock)

Use both the reference bit R and the dirty bit M. Each page falls into one of four classes:

The hand sweeps looking for a class 0 page; if none, it looks for class 1 while clearing reference bits; it may take up to a few sweeps. Preferring clean pages saves disk writes. This scheme was used in classic Mac OS virtual memory, and the "not recently used" (NRU) algorithm uses the same four classes.

Counting algorithms: LFU and MFU

• LFU (least frequently used): evict the page with the smallest access count. Problem: a page used heavily at start-up keeps a high count and never leaves. A common fix is to decay counts over time (shift right periodically).
• MFU (most frequently used): evict the page with the largest count, on the argument that a page with a small count was probably just brought in and is about to be used.

Neither is common for OS page replacement: they are expensive and do not approximate OPT well. LFU-style ideas do appear in application caches (for example Redis offers an LFU eviction policy).

Page buffering

Real systems also keep a pool of free frames. On a fault, the new page is read into a free frame immediately, and the victim is written out later. Linux keeps free memory above watermarks with the background kswapd thread, so most faults never wait for an eviction.

Frame allocation

Replacement decides which page leaves. Frame allocation decides how many frames each process gets.

Every process needs a minimum number of frames, set by the architecture: enough to hold every page a single instruction might touch (the instruction itself, its operands, and any page-table pages on some designs). Otherwise an instruction could fault forever.

Equal and proportional allocation

• Equal allocation: m frames among n processes gives each m / n. 100 frames and 5 processes: 20 each. Simple but unfair to large processes.
• Proportional allocation: give each process frames in proportion to its size. If process i has size s_i and the total size is S, it gets a_i = (s_i / S) x m.

Worked example: 100 frames; processes of 20, 80 and 150 pages, so S = 250.

• P1: 20 / 250 x 100 = 8 frames
• P2: 80 / 250 x 100 = 32 frames
• P3: 150 / 250 x 100 = 60 frames

8 + 32 + 60 = 100. When the division is not exact, round down and hand out leftovers, and never go below the minimum. A variant allocates in proportion to priority instead of, or as well as, size.

Global versus local replacement

• Local replacement: a faulting process may only evict its own pages. Its fault rate depends only on its own behaviour, which is predictable, but idle frames held by other processes cannot be used.
• Global replacement: a faulting process may take a frame from any process. It uses memory better and gives higher throughput, so most general-purpose OSes (including Linux and Windows) use global replacement. The downside: one process's behaviour affects others' fault rates.

Thrashing

Thrashing is when a system spends more time paging (moving pages in and out) than doing useful work. Here is how it happens, step by step:

1. Processes do not have enough frames to hold the pages they are actively using.
2. Each process faults, evicts a page that another process (or itself) needs right away, which faults again.
3. Processes queue up waiting for the paging disk, so CPU utilisation drops.
4. A naive long-term scheduler sees low CPU utilisation and admits more processes to "use the CPU".
5. The new processes take even more frames, faults get worse, utilisation drops further.

 CPU
 utilisation
   ^
   |            ****
   |        ***     **
   |     **           *
   |   *               *   <- thrashing begins
   |  *                 **
   | *                    ***
   +-------------------------------> degree of
                                      multiprogramming

The cause is that the sum of the processes' localities exceeds the available memory. A locality is a set of pages a program actively uses together, for example a function's code, its stack frame and the data it is working on. Programs move from locality to locality as they run.

The working-set model

The working set of a process at time t, WS(t, Δ), is the set of distinct pages it referenced in the most recent Δ references, where Δ (delta) is the working-set window. It approximates the current locality.

Worked example with Δ = 5. References at times 1 to 12:

time   1  2  3  4  5  6  7  8  9 10 11 12
page   2  6  1  5  7  7  7  7  5  1  6  2

• At t = 5: the window is times 1 to 5: pages 2, 6, 1, 5, 7. WS = {1, 2, 5, 6, 7}, size 5.
• At t = 8: window 4 to 8: pages 5, 7, 7, 7, 7. WS = {5, 7}, size 2.
• At t = 12: window 8 to 12: pages 7, 5, 1, 6, 2. WS = {1, 2, 5, 6, 7}, size 5.

The working set shrinks while the program loops on page 7 and grows again when it moves on. Choosing Δ matters: too small and it misses part of the locality; too large and it spans several localities.

How the OS uses it:

1. Let D = sum of all working-set sizes, the total demand for frames.
2. If D > m (available frames), thrashing will occur, so suspend (swap out) a process and give its frames to the others.
3. If there is spare room, admit another process.

Tracking the exact working set is expensive, so it is approximated with reference bits sampled at timer interrupts.

Page-fault frequency (PFF)

A more direct approach controls the fault rate itself:

• Set an upper and lower bound on the acceptable page-fault rate.
• If a process's fault rate goes above the upper bound, it needs more frames: give it one.
• If it goes below the lower bound, it has more than it needs: take one away.
• If the fault rate is high and no free frames exist, suspend a process.

 page-fault
 rate
   ^
   |\
   | \          upper bound: give frames
   |--\--------------------------------
   |   \
   |    \___
   |--------\_____----------------------
   |              lower bound: take frames
   +------------------------------------> frames allocated

Copy-on-write and fork

fork() creates a child process that is a copy of its parent. Copying every page would be slow, and wasted, because the child often calls exec() immediately and throws the copy away. Copy-on-write (COW) avoids this:

1. On fork(), the kernel does not copy pages. It makes the child's page table point at the same frames as the parent's.
2. It marks those shared pages read-only in both page tables (and records that they are COW).
3. As long as both processes only read, they share the frames.
4. When either process writes to a shared page, the MMU raises a protection fault. The kernel sees it is a COW page, allocates a new frame, copies the page, maps the copy (writable) into the writing process, and restarts the instruction.
5. Pages that are never written are never copied.

 after fork()                    after child writes page B
 parent PT   frames   child PT   parent PT  frames   child PT
  A ---->  [ A ]  <---- A         A ---->  [ A ]  <---- A
  B ---->  [ B ]  <---- B         B ---->  [ B ]
  (all read-only, shared)                  [ B' ] <---- B (writable)

This C program shows the effect. Both processes print the same virtual address for value, but after the child's write they see different values, because that virtual page now maps to different physical frames:

#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void) {
    int value = 10;               /* lives on a page shared after fork */
    pid_t pid = fork();
    if (pid < 0) { perror("fork"); return 1; }
    if (pid == 0) {
        value = 99;               /* write -> page copied for the child */
        printf("child : value=%d at %p\n", value, (void *)&value);
        return 0;
    }
    wait(NULL);
    printf("parent: value=%d at %p\n", value, (void *)&value);
    return 0;
}

Output (addresses vary):

child : value=99 at 0x16ce7e888
parent: value=10 at 0x16ce7e888

Related: vfork() creates a child that borrows the parent's address space with no copying at all, and suspends the parent until the child calls exec() or _exit(). It predates COW and is risky (the child must not modify memory); posix_spawn() is the modern way to start a new program cheaply.

COW is also why a large Redis instance can take a snapshot by forking: the child writes the snapshot from a frozen view while the parent keeps serving, and memory grows only by the pages the parent modifies during the snapshot.

Memory-mapped files

Memory-mapped file I/O maps a file's contents into a process's virtual address space with mmap(). After that, reading p[i] reads the file and writing p[i] writes it, with no read() or write() calls.

How it works with demand paging:

1. mmap() only creates a mapping (a virtual memory area); no data is read yet.
2. The first access to each page causes a page fault; the kernel reads that block of the file into the page cache and maps the cached page into the process.
3. Writes mark the page dirty. With MAP_SHARED, dirty pages are written back to the file eventually, or immediately when you call msync(). With MAP_PRIVATE, writes go to a private COW copy and never reach the file.
4. Several processes mapping the same file with MAP_SHARED share the same physical pages, which makes it a form of shared memory.

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

int main(int argc, char **argv) {
    if (argc != 2) { fprintf(stderr, "usage: %s file\n", argv[0]); return 1; }
    int fd = open(argv[1], O_RDWR);
    if (fd < 0) { perror("open"); return 1; }
    struct stat st;
    if (fstat(fd, &st) < 0 || st.st_size == 0) { fprintf(stderr, "empty file\n"); return 1; }

    char *p = mmap(NULL, st.st_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (p == MAP_FAILED) { perror("mmap"); return 1; }
    close(fd);                    /* the mapping stays valid */

    for (off_t i = 0; i < st.st_size; i++)   /* uppercase in place */
        if (p[i] >= 'a' && p[i] <= 'z') p[i] -= 32;

    msync(p, st.st_size, MS_SYNC);           /* flush dirty pages to the file */
    munmap(p, st.st_size);
    return 0;
}

Running it on a file containing hello world leaves HELLO WORLD in the file.

Where you meet mmap in practice: the dynamic loader maps executables and shared libraries; databases such as LMDB and older MongoDB storage engines map their data files; malloc in glibc uses anonymous mmap (no file behind it) for large allocations, by default those of 128 KB or more. Trade-offs: mapping avoids a copy between kernel and user buffers, but I/O errors show up as signals (SIGBUS) instead of return codes, and you lose control over when pages are read and written.

Huge pages

With 4 KB pages, a process using 64 GB of memory needs 16 million page table entries and the TLB covers only a tiny fraction of it. Huge pages are larger pages: on x86-64, 2 MB and 1 GB; on ARM64 the sizes depend on the base page size (with 4 KB base pages they are 2 MB and 1 GB too).

Benefits:

• One TLB entry covers 2 MB instead of 4 KB, 512 times more, so TLB misses drop sharply for large working sets.
• Page tables are smaller and shallower (a 2 MB page stops the walk one level early).

Costs:

• More internal fragmentation: a 2 MB page that holds 100 KB of data wastes the rest.
• Finding 2 MB of physically contiguous free memory gets harder as memory fragments, so the kernel may need to compact memory.

Linux offers two mechanisms:

• HugeTLB (explicit huge pages): reserved up front (vm.nr_hugepages), used through hugetlbfs or mmap with MAP_HUGETLB. Predictable; common for databases and VMs.
• Transparent Huge Pages (THP): the kernel automatically backs suitable anonymous memory with 2 MB pages and a background thread (khugepaged) merges small pages. Controlled by /sys/kernel/mm/transparent_hugepage/enabled (always, madvise or never). Some databases (Redis and MongoDB have both documented this) recommend disabling THP or using madvise mode, because background compaction and COW of 2 MB pages after fork() can cause latency spikes and memory bloat.

Overcommit and the Linux OOM killer

Because of demand paging, allocating memory and using it are different things. malloc(1 GB) on Linux usually succeeds instantly: the kernel reserves virtual address space, but no frames are used until pages are touched. Promising more memory than exists is called overcommit. It works because most programs never touch everything they allocate, and because COW after fork() would otherwise need to reserve a full copy of the parent's memory.

Linux controls it with vm.overcommit_memory:

The risk of overcommit: if processes actually touch more pages than RAM plus swap can hold, the kernel cannot satisfy a page fault. It then invokes the OOM (out-of-memory) killer, which picks a process and kills it with SIGKILL to free memory.

How it picks a victim, simplified:

• Each process gets a badness score based mainly on how much memory it uses (resident memory, swap and page tables) as a proportion of the total available.
• Users can bias it with /proc/<pid>/oom_score_adj, from -1000 (never kill) to +1000 (kill first). The resulting score is visible in /proc/<pid>/oom_score.
• The process with the highest score is killed, and the kernel logs a message like Out of memory: Killed process 1234 (java) to the kernel log (dmesg).

In containers, the same mechanism works per cgroup: when a container exceeds its memory limit, the OOM killer kills a process inside that cgroup, which is why a Kubernetes pod shows OOMKilled (exit code 137 = 128 + 9, meaning killed by signal 9). See Linux internals for cgroups.

Interview questions

Q1. What is virtual memory and what are its benefits?

Virtual memory separates the logical address space from physical memory, so a process can run with only some of its pages in RAM and the rest on disk. Benefits: programs can be larger than RAM, more processes fit in memory at once, and features like copy-on-write, shared libraries and memory-mapped files become cheap. The cost is page-fault overhead and the complexity of replacement and allocation policies.

Q2. Walk through what happens on a page fault.

The MMU finds the valid bit 0 and traps. The kernel checks whether the address is legal; if not, it sends SIGSEGV. If legal, it finds a free frame or evicts a victim (writing it back if dirty), reads the page from disk while the process blocks, updates the page table, and restarts the faulting instruction.

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

A major fault requires disk I/O because the page is not in memory. A minor fault is resolved without I/O: the page is already in RAM (for example in the page cache or shared by another process) or is a fresh zero-filled page, so the kernel only updates the page table. Major faults cost milliseconds on a disk; minor faults cost around a microsecond.

Q4. Why is the Optimal algorithm not used in practice?

It needs to know the future reference string, which an OS does not know. It is used as a benchmark: an algorithm's fault count is compared with OPT's to see how close to ideal it gets.

Q5. What is Belady's anomaly? Which algorithms suffer from it?

It is when increasing the number of frames increases the number of page faults. FIFO shows it on 1,2,3,4,1,2,5,1,2,3,4,5: 9 faults with 3 frames but 10 with 4. LRU and OPT are stack algorithms (the set of pages with n frames is a subset of the set with n + 1), so they never show it.

Q6. Why is exact LRU hard to implement, and how is it approximated?

Exact LRU needs to update a timestamp or reorder a list on every memory access, which needs hardware support no mainstream CPU provides. OSes approximate it using the hardware reference bit: aging (shifting reference bits into a history byte), Clock/second chance, or active and inactive lists as Linux does.

Q7. Explain the Clock algorithm.

Frames form a circular list with a hand. On a fault, if the page under the hand has reference bit 1, the bit is cleared and the hand advances (the page gets a second chance); if the bit is 0, that page is evicted. Recently used pages survive one sweep, so it approximates LRU at FIFO-like cost.

Q8. Why prefer evicting clean pages?

A clean page has an identical copy on disk, so it can be discarded without a write. A dirty page must be written back first, doubling the I/O for that fault. Enhanced Clock uses the (reference, dirty) pair to prefer not-recently-used clean pages.

Q9. What is thrashing, and how do you detect and fix it?

Thrashing is when processes spend most of their time faulting because the total of their active localities exceeds RAM, so CPU utilisation collapses while disk activity is high. Detect it with high page-fault rates and swap activity (for example si/so in vmstat). Fix it by reducing the degree of multiprogramming, using working-set or page-fault-frequency control, killing or suspending processes, or adding memory.

Q10. What is the working-set model?

The working set is the set of distinct pages referenced in the last Δ references, an estimate of the current locality. If the sum of all working-set sizes exceeds available frames, the OS suspends a process to prevent thrashing; otherwise it may admit more. Δ must be chosen to span one locality without covering several.

Q11. What is copy-on-write and why does fork use it?

After fork(), parent and child share all pages marked read-only. When either writes to a page, a protection fault makes the kernel copy just that page for the writer. Since many children call exec() immediately, most pages are never copied, making fork() fast and memory-efficient.

Q12. What is the difference between global and local replacement?

With local replacement, a process can only evict its own pages, so its performance is isolated but memory may sit idle in other processes. With global replacement, it can take any process's frame, which gives better overall throughput but lets one process hurt another. Linux and Windows use global replacement.

Q13. Why can malloc succeed and the process still be killed for lack of memory?

Linux overcommits by default: malloc reserves virtual address space but no physical frames until pages are touched. If processes later touch more memory than RAM plus swap can hold, the kernel cannot satisfy a fault and the OOM killer kills a process with SIGKILL. Strict overcommit mode (vm.overcommit_memory = 2) makes the allocation fail up front instead.

Q14. What are huge pages and when would you use them?

Huge pages are larger pages (2 MB or 1 GB on x86-64) so that one TLB entry covers much more memory, cutting TLB misses and page-table size for large-memory workloads such as databases and VMs. The costs are internal fragmentation and the difficulty of finding contiguous physical memory. Transparent Huge Pages automate it but can cause latency spikes, so some databases recommend madvise or never.

Q15. Compute the EAT for 100 ns memory, 10 ms fault service time and a fault rate of 1 in 100,000.

p = 0.00001. EAT = 0.99999 x 100 + 0.00001 x 10,000,000 = 99.999 + 100 = about 200 ns. A single fault per 100,000 accesses doubles the average memory access time, which shows why fault rates must be tiny.

Key takeaways

• Demand paging loads a page only on first access; the valid bit marks resident pages and a page fault brings missing ones in, then restarts the instruction.
• EAT = (1 - p) x memory time + p x fault time; because faults cost milliseconds, p must be in the order of one in a million.
• OPT is optimal but needs the future; LRU approximates it from the past; FIFO is simple but can evict hot pages and shows Belady's anomaly.
• LRU and OPT are stack algorithms and never show Belady's anomaly; LRU can still lose to FIFO on looping patterns.
• Clock (second chance) and enhanced Clock approximate LRU with reference and dirty bits at FIFO-like cost.
• Thrashing happens when active localities exceed RAM; working-set and page-fault-frequency control prevent it by limiting multiprogramming.
• Copy-on-write makes fork() cheap; mmap maps files into memory through the page cache.
• Linux overcommits memory; when it truly runs out, the OOM killer sends SIGKILL to the highest-scoring process, per cgroup in containers (exit code 137).

Next lesson

Continue with File systems.