Paging

Paging divides an address space into fixed-size memory pages and main computer memory into equally sized page frames. Here assume byte addressing, one memory page size $P=2^b$ bytes, and an unsigned virtual address $v$. Its virtual page number $q$ and offset $d$ areThe brackets denote the floor function, and $\mathrm{mod}$ gives the remainder in Euclidean division. If the page table maps $q$ to physical frame number $f$ and permits the access, the physical address isThe low $b$ bits are unchanged; the other bits select the memory page or page frame. A bit shift and bit mask can extract these fields. ^[ref]

For a 16-bit virtual address and $P=256=2^8$ bytes, take $v=0x1234=4660$ in hexadecimal. Then $q=18=0x12$ and $d=52=0x34$. A mapping to $f=7=0x07$ givesThus the eight high bits choose a mapping; the eight low bits choose the same position in the resulting page frame. The 256-byte size is for illustration, not a claim about an actual architecture's supported memory page sizes.

The useful freedom is that adjacent memory pages can occupy unrelated page frames. In the diagram, virtual pages 0x12 and 0x13 occupy page frames 0x07 and 0x02; virtual addresses 0x12ff and 0x1300 are consecutive, but translate to physical addresses 0x07ff and 0x0200. Uniform units simplify placement and page replacement, at the cost of page table storage and unused bytes within partly filled memory pages. For example, placing 300 bytes in exclusive 256-byte page frames requires two page frames, leaving $512-300=212$ bytes unused.

A contiguous unit of an address space used for paging. In the example, virtual page 0x12 consists of virtual addresses 0x1200 through 0x12ff.

A slot in main computer memory that can hold one memory page of the selected size. Physical frame number 0x07 with 256-byte page frames starts at physical address 0x0700.

Making a memory page resident when it is first accessed, using a page fault to request the work. It can involve loading stored contents or allocating newly initialized contents.

// Target: computer-science.bigb

Choosing a resident memory page to evict when another memory page needs an occupied page frame. An unused page frame needs no eviction. A dirty memory page requires preservation before reuse, accounted for separately as page writeback. A page replacement policy balances likely future reuse against the overhead of tracking past memory references.

The opportunity comes from temporal locality: retaining a recently accessed memory page can spare a later nonresident page fault. Spatial locality helps consecutive accesses reuse the same memory page until they cross its boundary. A working set describes recent demand, while the resident set describes what is actually present. A small active footprint can fit in the available page frames even when the whole address space cannot. These are useful workload tendencies, not guarantees about future memory references.^[ref]

The page-reference trace below uses the counterexample discussed in Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others (chapter 22, p. 5) and makes the decisions explicit. FIFO page replacement ranks arrival time, LRU replacement ranks last access, CLOCK page replacement samples recent use, and optimal page replacement knows the remaining sequence in advance. Count misses first; page-replacement cost accounting separately counts page writeback and explains why fewer misses need not mean less total service time.

// Destination: computer-science.bigb

Keep page frames in a circular list with a reference bit and a scanning hand. Clear set reference bits while scanning; choose the first eligible page frame with a clear reference bit. This second chance approximates LRU replacement with cheaper tracking. When hardware reference flags are absent, revoking a mapping and handling its first later page fault can supply a software reference observation.

For the page-reference trace, number the three page frames 1–3 and initially point the hand at 1. Every access sets the referenced page frame's reference bit to 1. On a miss, scan from the hand: stop at an empty page frame or a resident one with reference bit 0; otherwise clear its reference bit and advance cyclically. Install the requested memory page with reference bit 1 and advance the hand to the next page frame. Hits leave the hand where it is. This fixes a particular variant; clean-victim preference is excluded.^[ref]

After the first three accesses, all reference bits are 1 and the hand is back at page frame 1. Access 4 clears all three reference bits, returns to page frame 1, evicts memory page 1, installs memory page 4, and leaves the hand at page frame 2 with reference bits $(1,0,0)$. This variant gives nine misses for three page frames and ten for four on the displayed sequence. Approximating LRU replacement therefore does not inherit the LRU stack property.

// Destination: computer-science.bigb

Evict the least recently accessed eligible item. Exact recency tracking on every memory reference can be expensive, whereas accesses to a buffer cache already pass through software. Recency captures temporal locality but a long scan can evict frequently reused items before their next use.

For page replacement, update recency on hits as well as misses; evict only when a miss requires a page frame and all eligible page frames are occupied. The four-page cycle in memory thrashing shows how exact LRU replacement behaves at capacities three and four.^[ref]

The LRU stack property compares different capacities on one fixed page-reference trace; it does not say that LRU replacement always beats FIFO page replacement. On the displayed sequence, three-page frame LRU replacement has ten misses, versus nine for FIFO page replacement, while four-page frame LRU replacement has only eight.

A finite-capacity cache using LRU replacement: accessing an item makes it most recent, and a miss evicts the least recently used item when the cache is full.

For exact LRU replacement, let $R_k(t)$ be the resident set after the first $t$ accesses of a fixed page-reference trace with capacity $k$. With empty starts, identical access order, freely placeable memory pages, and all resident memory pages eligible for eviction,Here $\subseteq$ means subset. At every time, form one capacity-independent ordered list of distinct memory pages, most recently accessed first. An access moves its memory page to the front, preserving the order of the others. Exact LRU replacement with $k$ page frames retains the first $k$ entries, or all entries if fewer than $k$ have appeared. The first $k$ entries are contained in the first $k+1$, proving the property. This recency list is not the push/pop interface of a LIFO stack.^[ref]

Apply inclusion immediately before an access: a hit with $k$ page frames must also hit with $k+1$. Thus cumulative misses with $k+1$ cannot exceed those with $k$, at any prefix of the same page-reference trace. On the displayed sequence, the counts decrease from ten to eight when capacity increases from three to four. Arbitrary initial contents, different access orders, protected victims, or clean-victim preference fall outside the proof. Nor does it prove monotonic page writeback costs, or apply automatically to CLOCK page replacement just because that policy approximates LRU replacement.

// Destination: computer-science.bigb

Evict the memory page loaded earliest among currently resident memory pages, without refreshing its position on access. It is simple but ignores temporal locality and can evict a frequently accessed memory page.

Implement this ranking with a FIFO queue of resident memory pages: append on loading, remove the oldest on eviction, and leave the queue unchanged on a hit. Belady anomaly shows why preserving arrival order can give more misses with more page frames. The comparison uses the same page-reference trace and empty initial resident sets in both runs.^[ref]

A finite-capacity cache that evicts the oldest inserted item when full. A hit leaves the insertion order unchanged, so its behavior differs from an LRU cache.

A memory access trace reduced to the ordered sequence of accessed memory page identities, retaining repetitions. An address-only reduction loses read/write information, so annotate writes when studying dirty memory pages. Use the following classic Belady anomaly sequence, where the numbers label memory pages, not physical addresses:Start with three empty, equal-sized page frames allocated to one operating-system process. Every memory page can occupy any page frame, and every resident memory page is eligible for eviction. Use demand paging: a hit finds the requested memory page in the resident set; a miss causes exactly one nonresident page fault and loads it before the next access. Fill the lowest-numbered empty page frame, then reuse the victim's page frame. Assume only reads, no fetching ahead of requests, no competing operating-system processes, and no external removal of memory pages. CLOCK page replacement uses its declared hand rule, which fills the same initial page frames here. The memory page labels alone do not determine the result without these assumptions.

Each column shows the state after servicing that access. Rows keep physical page frame positions fixed, rather than silently sorting the resident set. The CLOCK page replacement entries also show reference bits and the next hand position. The independently computed totals are:

The first three misses fill unused page frames; the fourth miss needs eviction. At access 4, FIFO page replacement and LRU replacement evict memory page 1. Optimal page replacement instead evicts memory page 3: the next uses of resident memory pages 1, 2 and 3 are at indices 5, 6 and 10. At access 10, FIFO page replacement evicts memory page 1 while LRU replacement evicts memory page 5. Consequently the last access to memory page 5 hits under FIFO page replacement but misses under LRU replacement. Matching totals for FIFO page replacement and CLOCK page replacement on this sequence do not make the policies equivalent. The generators compute every displayed state; a separate search over all legal victims confirms the seven-miss optimal page replacement bound for three page frames.

On a miss with all page frames occupied, evict the resident memory page whose next access is farthest in the remaining page-reference trace. Treat no further access as farther than any finite next-use index; in the diagram, ties choose the lowest-numbered page frame. This is an offline, clairvoyant benchmark: a general operating system cannot know its future memory references. It minimizes miss count in the stated fixed-capacity demand paging model, rather than predicting the future from temporal locality.^[ref]

In the page-reference trace, seven misses with three page frames is therefore a lower bound for any policy using the same assumptions; with four page frames the corresponding minimum is six. The benchmark is useful for judging how much improvement is possible on a recorded workload. Its objective counts each miss equally. Different page writeback costs or unequal loading costs require a different objective; minimum misses alone does not prove minimum elapsed time.

Increasing the number of page frames can increase misses under a given page replacement policy on the same page-reference trace. For FIFO page replacement on the displayed twelve-reference sequence, an empty start with three page frames gives nine misses, while an empty start with four gives ten. The larger run hits only at indices 5 and 6; it misses at 1–4 and 7–12. These are miss counts, not observed running times.^[ref]

The explanation is visible before the final count. After access 6, the three-page frame queue is $(4,1,2)$ and the four-page frame queue is $(1,2,3,4)$, both oldest first. Loading memory page 5 at access 7 removes memory page 4 in the smaller run but memory page 1 in the larger. Their resulting resident sets are $\{1,2,5\}$ and $\{2,3,4,5\}$. The smaller resident set is not a subset of the larger: its next access to memory page 1 hits while the larger run misses. Different earlier evictions create different histories; an extra page frame is not simply an extra unchanged slot. FIFO page replacement can improve on other sequences; the anomaly is an existence claim, not a claim that more page frames usually hurt.

A resident memory page with modifications that must be preserved in its backing storage before its page frame can be reused. In the simple model here, a write sets its dirty flag, and successful page writeback clears it. A clean memory page with a recoverable backing copy can be discarded without an outgoing data write.^[ref]

Preserving the modified contents of a dirty memory page in its backing storage. The reference model waits for successful page writeback before reusing the victim's page frame; failure cannot authorize losing its modifications. A reference bit records recent access, while the dirty flag records a write obligation: reading can set the first without setting the second. Buffer cache writeback concerns the analogous obligation for a buffered device block.

Let $n$ be the number of accesses, $M$ the miss count and $D$ the number of dirty-victim page writebacks. Assume every requested memory page has a backing copy, every miss reads it, writes modify only part of its contents, transfers succeed and occur serially, and there is no background or final flushing. With common access cost $h$, additional load cost $r$ per miss, and additional outgoing write cost $w$ per dirty victim, an illustrative total service time isBookkeeping and other operating system costs are omitted. The two transfer directions are separate: a miss can require a read with no write, or both a victim write and a requested-page read. A retained dirty memory page contributes no outgoing write to this finite-page-reference trace count until evicted. Future flushing would need its own accounting boundary.

For three-page frame FIFO page replacement on the displayed page-reference trace, all reads give $(n,M,D)=(12,9,0)$. Change only access 1 to a partial write of memory page 1. Its initial miss still loads the old contents, the write marks it dirty, and eviction at access 4 adds exactly one page writeback. Later loads of memory page 1 are clean because the remaining accesses read. The result is $(12,9,1)$: identical residency and nine misses, but one extra outgoing write. With illustrative $h=100$ nanoseconds, $r=1$ millisecond and $w=2$ milliseconds, total service time changes from $9.0012$ to $11.0012$ milliseconds. These are model costs, not hardware measurements.

Preferring a clean victim can save an immediate page writeback, but evicting a soon-needed clean memory page can add later misses. This tradeoff is why a miss-minimizing optimal page replacement benchmark and a minimum-cost policy are different questions. Real page faults can also initialize a new memory page or perform copy-on-write without reading backing storage; those cases require different load costs.

// Destination: computer-science.bigb

A page fault transfers control to the operating system when an access cannot proceed under the current paging translation or protection rules. The term includes both unavailable translations and forbidden accesses on x86. Intel's manual distinguishes these causes; AMD's error code likewise distinguishes ordinary not-present faults from protection violations. Other architectural causes, including malformed page table entries, also exist. ^[ref][ref]

The illustrative page table in paging separates three situations:

A page fault is not necessarily a program error or a storage-device read. Demand paging can allocate a zero-filled page frame without reading secondary storage. A copy-on-write write deliberately encounters read-only permissions; the operating system supplies a private copy and enables the write. A truly forbidden access may instead terminate the operating-system process. The handler interprets the fault using both architectural fault information and its own mapping policy. ^[ref]

For a nonresident memory page whose contents must be loaded, the handler obtains a page frame, possibly invokes page replacement, supplies the contents, updates the page table, arranges any necessary translation lookaside buffer invalidation, and resumes the operation. If no mapping or permission can legally be supplied, it reports failure. This mechanism lets ordinary accesses request work only when it becomes necessary. ^[ref]

// Target: computer-science.bigb

For a specified interval of memory references, the number causing a page fault divided by the total number of memory references. In the nonresident-only toy model in memory thrashing, this equals the miss fraction used as probability $p$ in the expected value calculation. Startup and later intervals can have very different page fault rates.

A translation lookaside buffer is a small hardware memory cache of virtual address to physical address mappings and their access attributes. A TLB hit finds a usable cached mapping for the current address space; access permissions still apply. A TLB miss means that mapping is absent from the translation lookaside buffer. It says nothing by itself about whether the memory page is resident. Evicting a translation lookaside buffer entry removes a cached translation, not the memory page's contents. ^[ref]

For the 256-byte example, a cached virtual page 0x12 to physical frame 0x07 mapping covers every offset from 0x00 to 0xff. Reads at virtual addresses 0x1234 and 0x1235 can reuse it to reach physical addresses 0x0734 and 0x0735. If the translation lookaside buffer is initially empty, the first read instead requires a page table walk; with a resident, readable mapping, it completes without a page fault. A write can fault even on a TLB hit because cached permissions deny it.

The diagrams show an ordinary x86 model with hardware page table walks. Some architectures use an operating system handler to refill the translation lookaside buffer after a TLB miss; that refill event alone is not a nonresident page fault. Temporal locality helps a small translation lookaside buffer serve repeated accesses, and one entry can cover many bytes. ^[ref]

A context switch does not universally flush the whole translation lookaside buffer. An address space identifier can distinguish translations with the same virtual page number in different address spaces; Intel's PCIDs support retaining translations across appropriate switches. The operating system must still invalidate stale translations when mappings or permissions change, following the architecture's rules, including coordination with other processors that could use them. ^[ref]

A lookup that finds a valid cached address translation for the relevant address space. The access can still cause a page fault if the cached permissions forbid it.

For the 64-byte toy model in address translation, a cached process A page-4 mapping covers reads at both 0x12D and 0x12E, yielding physical addresses 0x36D and 0x36E. The TLB hit reuses the mapping; it does not guarantee that either requested byte is in a data memory cache.

A lookup that fails to find the required cached address translation. A successful refill can leave the memory page resident throughout and cause no page fault.

For process A's resident virtual page 4 in address translation, discarding only its translation lookaside buffer entry makes the next read a TLB miss while its contents remain in page frame 13. Page replacement would instead remove the resident memory page; these operations invalidate different kinds of cached information.

A tag distinguishing cached address translations belonging to different address spaces. Tags can be reused, but reusing a tag for a different mapping context requires appropriate invalidation.

// Target: computer-science.bigb

A page table is the data structure describing an address space's mappings from virtual page numbers to page frames, together with access and status information. A page table entry can describe a resident memory page and its permissions. Nonresident or unmapped memory pages require a representation that lets the operating system distinguish them; a hardware not-present flag alone need not make that distinction. On x86, additional operating system information determines whether a not-present mapping is legitimate. ^[ref]

The four rows drawn under paging are an illustrative model, combining page table and operating system information: virtual page 0x12 is resident in physical frame 0x07 with read-only permission; 0x13 is resident in 0x02 with read/write permission; 0x14 is mapped read/write but nonresident; 0x15 is unmapped. The labels deliberately separate mapping policy, residency and permission. They are not a literal x86 entry layout. A translation lookaside buffer valid flag is a fourth, independent notion: it says that a cached translation can be considered, not that every resident memory page has a cached translation.

A flat array with one page table entry per virtual page would have $2^{16}/256=256$ entries in this example. At an assumed four bytes per entry, it occupies $256\cdot 4=1024$ bytes, whether one memory page or all 256 memory pages are mapped. A multi-level page table saves space in sparse address spaces by allocating lower-level tables only for the regions that need them. The tradeoff is extra dependent lookups during a page table walk; a translation lookaside buffer avoids repeating those lookups on a hit. ^[ref]

One record in a page table, holding a page frame number or a next-level table reference together with architecture-dependent flags. Effective permissions in a multi-level page table can depend on several entries, not just the final one.

A hierarchy of page tables indexed by successive groups of virtual page number bits. Unused regions can omit lower-level tables.

The useful omission is an entire lower-level array, not merely an invalid page table entry. One absent upper-level entry can represent a large unmapped interval of the address space. The Linux kernel's documented hierarchy uses this idea to avoid allocating tables for unused regions; its software levels can also be folded to match the hardware. ^[ref]

Choose an original teaching model with 16-bit virtual addresses, 16-bit physical addresses, and 256-byte memory pages and page frames. The eight high bits identify a virtual memory page; divide these into two four-bit indices. The eight low bits are the offset within the memory page. Thus each page table has 16 entries: the root selects a lower-level page table, and that table selects a data page frame. Every page table entry is four bytes, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.

For a virtual address $v$, extract the root index $i$, lower-level index $j$, and offset $d$ by Euclidean division:Here $\lfloor \cdot \rfloor$ is the floor function and $\mathrm{mod}$ denotes the remainder in Euclidean division. Each index ranges from 0 to 15, and $d$ ranges from 0 to 255. In hexadecimal, virtual address 0x1234 splits into $i=1$, $j=2$, and $d=0x34=52$; its binary numeral system representation is 0001 | 0010 | 00110100.

Fix the requested operation to be a one-byte user read. Assume both table nodes and the data page frame are resident, table reads are allowed, and no mapping changes during the page table walk. The model requires presence at both levels and takes the set intersection of the two entries' read, write, execute, and user-access permissions. This is an explicit memory protection rule for this model; Sv39 page tables use different rules. The root's physical address is 0x8000; the relevant entries are:

The first lookup obtains a table reference, not the final data physical address. The second lookup obtains page frame number 7. Both entries permit a user read, so the original offset is added to the data page frame base:The page table walk therefore reads records at 0x8004 and 0x9008, then the requested read accesses data at 0x0734. All three are distinct physical addresses. These are two dependent table lookups followed by one data access, not a claim of three accesses to main computer memory: a memory cache can satisfy table lookups, and cached intermediate translations can skip them.

Under the same memory protection rule, a user write at 0x1234 fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the page table walk before any lower-level lookup. A page fault then requires the operating system to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish demand paging eligibility.

With an empty translation lookaside buffer, the permitted read causes a TLB miss and this successful page table walk, with no page fault. If the resulting mapping and permissions are cached for the current address space, a later read at 0x1235 can use a TLB hit to reach 0x0735. A later write can cause a protection page fault on a TLB hit because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A TLB miss describes a missing cached translation, while a page fault describes an access that cannot proceed under the translation or protection rules. ^[ref]

Use the two-level address translation model and map exactly four resident virtual memory pages, numbered 0x12, 0x13, 0xa0, and 0xa1. Assign their data page frames to 0x07, 0x02, 0x05, and 0x06, respectively. Only two root indices occur: 1 and 10. Allocate exactly three table nodes: the root at 0x8000, the lower-level table for root index 1 at 0x9000, and the lower-level table for root index 10 at 0xa000. Root entries 1 and 10 reference those tables; all other root entries are absent. Lower-level entries 2 and 3 in the first table and entries 0 and 1 in the second table hold the four mappings; every other lower-level entry is absent. Use the read-only permissions already specified for virtual memory page 0x12; let the other three mappings permit user reads and writes, with no execution, and let both populated root entries permit user reads and writes.

Each root index covers 16 virtual memory pages, hence $16\cdot 256=4096$ bytes of the address space. A compact table node occupies $16\cdot 4=64$ bytes. The three nodes therefore require $3\cdot 64=192$ bytes of table storage, including the root and all absent entry slots in the allocated nodes. A single-level array requires $256\cdot 4=1024$ bytes for the same address space, saving $1024-192=832$ bytes in the compact model. Four data page frames occupy another $4\cdot 256=1024$ bytes; those contents are separate from table storage.

If instead the allocator dedicates a whole 256-byte page frame to every table node, the three nodes consume 768 bytes, leaving $3(256-64)=576$ bytes unused within those allocations. The single-level table fills four such page frames and still consumes 1024 bytes. Thus this example saves 256 bytes of allocated table storage under that alternative policy. Neither accounting includes allocator metadata, operating-system process records, or translation lookaside buffer storage; data allocations are the same in both designs.

Placement matters as well as mapping count. Four virtual memory pages 0x12, 0x42, 0x72, and 0xa2 require the root plus four lower-level tables: five nodes, 320 compact bytes, or 1280 bytes with a dedicated page frame per node. Only four data page frames are still required. Let $g$ be the number of distinct root indices represented by the mappings. With no retained empty lower-level tables, table storage is $64(1+g)$ compact bytes or $256(1+g)$ allocated bytes under the dedicated-page frame policy. Even an empty address space retains the root in this accounting, so $g=0$ costs 64 or 256 bytes.

For a fully populated address space, $g=16$: 17 nodes cost 1088 compact bytes or 4352 allocated bytes. The single-level table remains 1024 bytes. Sparse allocation is therefore a conditional space benefit; scattered mappings, node allocation granularity, and the root's overhead can reverse it. Additional dependent lookups on a TLB miss also have a cost, but node counts alone establish no universal execution-time ordering.

The actual Sv39 page table geometry uses three nine-bit indices and a twelve-bit offset for base 4096-byte memory pages. Each table contains 512 eight-byte page table entries, exactly one 4096-byte memory page; the satp processor register identifies the root. A 64-bit virtual address must repeat bit 38 in bits 63 through 39. Higher-level terminal entries can also map aligned larger memory pages, shortening the page table walk. These rules differ from the 16-bit, four-byte-entry two-level address translation model. ^[ref]

For ordinary Sv39 page tables, valid nonterminal page table entries reference the next table with read, write, and execute flags clear; those clear flags do not prohibit reading the eventual data. The terminal entry supplies access permissions, with additional processor privilege level and status checks. An invalid entry, malformed encoding, or denied access can cause a page fault. Thus the model's set intersection of read/write permissions at both levels must not be applied mechanically to Sv39 page tables. ^[ref]

In xv6 RISC-V source code, root allocation is separate from lower-level allocation: uvmcreate() allocates and clears a root page table, while walk() with allocation enabled allocates and clears missing lower-level tables and installs valid references to them. With allocation disabled, a missing table makes walk() return failure. This software routine finds a page table entry for the operating system; it is not the hardware's complete permission-checking page table walk. ^[ref]

Looking up page table entries to obtain a page frame number and effective access attributes. On ordinary x86 hardware paging, a TLB miss can initiate this lookup without entering the operating system.

// Target: computer-science.bigb