Virtual Memory and Demand Paging

Virtual memory separates the logical memory a program sees from the physical memory it occupies, so that a process need not be entirely in memory to run. Programs often contain error-handling code that rarely runs, arrays declared larger than they are used, and features few users touch. Loading only what is referenced lets a program be larger than physical memory, lets more processes share memory, and makes process start-up faster.

The usual implementation is demand paging: Paging, Page Tables and TLB, bringing a page into use when it is first referenced. A reference to a legal page that is not currently mapped/present causes a page fault. A major, disk-backed fault reads backing storage; a soft fault may instead map an already resident frame, and demand-zero allocation supplies a zero-filled page without a backing-storage read. Disk-backed faults are very expensive compared with memory accesses, so keeping their rate tiny matters; excessive paging activity can cause thrashing.

The valid-invalid bit, the page-fault service sequence, effective access time with faults, copy-on-write, frame allocation, the locality and working-set models, and thrashing are the standard facts. Choosing which page to evict is in Page Replacement Algorithms.

Each page-table entry has a valid-invalid bit. In this simplified present-mapping model, valid means a legal page is present in this mapping. Invalid means either an illegal address or a legal page whose mapping is absent: it may require a disk read, a mapping to an already resident frame, or demand-zero allocation. A reference to an invalid entry traps to the OS, which looks at its own records (usually in the PCB) to tell the two cases apart.

Restarting the instruction. The hardware must be able to restart any instruction after a fault, as if it had never started. This is hard for an instruction that modifies memory and can fault part-way, such as a block move whose source and destination overlap, or an instruction with auto-increment addressing. Hardware either checks both ends of the operands before starting, or saves enough state to undo the partial effect (Tanenbaum 3.6.3 calls this instruction backup).

Minimum number of frames. The architecture fixes a minimum: every page that one instruction can touch must be in memory at once. A memory-to-memory move instruction whose own bytes, source operand and destination operand can each straddle a page boundary can touch 6 pages, so such a machine needs at least 6 frames per process.

For this disk-backed-fault cost model, let $m$ be the memory access time, $S$ the fault service time and $p$ the disk-backed-fault rate (faults per memory reference). Then

$S$ is dominated by the disk read (and a write-back for a dirty victim): milliseconds, against nanoseconds for $m$, so even a tiny $p$ matters.

Example 1. $m = 100$ ns, $S = 5$ ms $= 5{,}000{,}000$ ns, $p = 0.001$:

about 51 times slower than with no faults. To keep the slowdown within 10% (EAT at most 110 ns) we need $100 + p \times 4{,}999{,}900 \le 110$, that is $p \le 1/499{,}990$: fewer than one fault in about half a million references.

Example 2, dirty victims. $m = 120$ ns; servicing a fault takes 6 ms when the victim is clean and 15 ms when it is dirty and must be written back first; 40% of victims are dirty. The mean service time is $0.6 \times 6 + 0.4 \times 15 = 9.6$ ms $= 9{,}600{,}000$ ns. For EAT at most 240 ns:

Convention. Some questions write $\text{EAT} = m + pS$, counting the memory access even on a fault (the restarted instruction does access memory). The difference is $p\,m$, negligible unless $p$ is large; use the form the question gives.

Combine the TLB from Paging, Page Tables and TLB with faults. Let the TLB lookup take $t = 10$ ns, memory $m = 100$ ns, the TLB hit ratio be 0.9, and suppose that 1% of the references that miss the TLB also fault, with $S = 2$ ms. State the model: a TLB miss costs $t + m$ for the page-table read; if the page is present, one more $m$ for the data; if it faults, $S$ and then a restarted reference that hits the now-updated TLB, $t + m$.

The fault term contributes 2,000.22 of those nanoseconds, although only 0.1% of references fault.

Memory access $m = 100$ ns, TLB time negligible, a two-level page table, TLB hit ratio 0.95. Of the references that miss the TLB, 0.1% fault; a fault takes 5 ms with a clean victim and 10 ms with a dirty one, and 30% of victims are dirty. After a fault the instruction restarts and hits the TLB.

Counting a population of 2,000,000 references path by path (1,900,000 hits, 99,900 present misses, 70 clean and 30 dirty faults) gives the same 435 ns. Without any faults the EAT would be $95 + 0.05 \times 300 = 110$ ns, so 100 faults in 2,000,000 references make it almost four times larger.

int A[128][128] with 4-byte integers, stored row by row, and 512-byte pages, with the array beginning on a 512-byte page boundary, so each row ($128 \times 4 = 512$ bytes) fills exactly one page. The process has one frame for the array, and the array is not in memory at the start.

With cold start, no other references/replacement interference, and FIFO or LRU, 2 frames leave the counts unchanged, and 128 frames (the whole array) are required for the column order to drop to 128 faults. These threshold claims are not policy-independent; OPT can obtain hits with fewer frames. Under the stated FIFO/LRU assumptions, loop order drives the difference.

With $F$ free frames and processes of sizes $s_i$ (in pages), equal allocation gives each of $n$ processes $\lfloor F/n \rfloor$ frames, and proportional allocation gives process $i$

With $F = 64$ and sizes 25, 75 and 200 pages, proportional allocation gives 5, 16 and 42 frames (from 5.33, 16 and 42.67); the floors leave 1 frame in the free pool. Equal allocation gives 21 each, also leaving 1. Priority can be mixed in by weighting the sizes.

Global versus local replacement. With global replacement a faulting process may take a frame from any process; throughput is usually better, but a process's fault rate depends on the others. With local replacement it replaces only its own pages, so its behaviour is predictable but memory may sit idle in other processes.

In the simple counting model, parent and child retain their shared private writable COW mappings until the first write, with neither unmapping/exiting first; explicitly shared mappings are excluded. After fork(), eligible private writable pages are shared and temporarily write-protected for copy-on-write. The first write by either process to a shared page traps; the OS copies that page into a free frame, maps the copy writable for the writer, and lets the write proceed. Pages never written are never copied, so a child that immediately calls exec() costs almost nothing. If the child writes to 3 distinct pages (several times each) and the parent writes to none, exactly 3 pages are copied. See Process Creation and fork() for the process side.

A process that does not have enough frames for the pages it is actively using faults, evicts a page it will need almost at once, and faults again. It spends more time paging than executing: it thrashes. With global replacement, thrashing spreads: faulting processes steal frames from others, CPU utilisation falls, a naive scheduler admits more processes to raise utilisation, and the fault rate rises further.

The working set $W(t, \Delta)$ is the set of distinct pages referenced in the last $\Delta$ references up to time $t$ (the working-set window). Its size is $\text{WSS}$. If the total demand $D = \sum_i \text{WSS}_i$ exceeds the number of frames $m$, some process lacks its working set and the system will thrash; the OS should then suspend a process (swap it out) rather than admit another.

Example. Reference string 1 2 1 3 2 1 4 4 5 4 5 6 5 4 6 6 (times 1 to 16), $\Delta = 4$:

The program moves from a locality {1, 2, 3} to a locality {4, 5, 6}; the working set is largest (4 pages) at the transition. A $\Delta$ that is too small misses parts of a locality; one that is too large spans several localities.

Admission. Four processes with working-set sizes 30, 45, 60 and 25 need $D = 160$ frames; with 150 frames the system is over-committed and one process should be suspended.

A simpler control measures each process's fault rate directly: above an upper bound the process gets more frames, below a lower bound it loses some. If no frames are free when a process needs more, a process is suspended.

Common misconceptions.