Paging and Virtual Memory

A program uses virtual addresses. Physical memory holds the bytes in frames. Paging divides the virtual address space into equal-sized pages and physical memory into frames of the same size. The operating system can put any page into any free frame. Page 0 might occupy frame 12 and page 1 frame 3; the program still sees consecutive virtual addresses.

This removes external fragmentation for individual page allocations. With variable-sized segments, a request can fail because free space is split into holes that are too small. With paging, a free frame always fits one page. A sparse address space can leave a large gap between heap and stack without reserving physical frames for that gap.

Measure unused space inside pages

Paging still has internal fragmentation. A region must occupy whole pages even when its final page is partly empty. A 9,000-byte region needs three 4 KiB pages: two pages hold 8,192 bytes, leaving 808 bytes for the third. The allocation occupies 12,288 bytes, of which 3,288 bytes are unused. KiB means 1,024 bytes; MiB means 1,048,576 bytes. Some books use KB and MB for these binary quantities.

Split the address into fields

An address identifies both a page and a byte within it. For a page size of $2^k$ bytes, the low $k$ bits are the offset. The remaining high bits are the virtual page number, or VPN. A 32-bit address with 4 KiB pages has 12 offset bits and 20 VPN bits. There are $2^{20}$ possible virtual pages in that address space.

For 0x00403A7C, the last three hexadecimal digits give offset 0xA7C, because each hex digit represents four bits. The first five digits give VPN 0x00403. This shortcut works here because the field boundary falls between hex digits. For a different page size, count bits before splitting the written hex value.

Decimal arithmetic gives the same result:

Here $P$ is the page size in bytes. With 1,024-byte pages, virtual address 5,000 has VPN 4 and offset 904. Four complete pages account for 4,096 bytes; the remaining 904 bytes locate the address inside page 4. Offsets start at zero, so this page's offsets range from 0 through 1,023.

Translation replaces the VPN with a physical frame number. It copies the offset unchanged: byte 904 of a virtual page is byte 904 of its frame. The page number alone is not a byte address. Multiply a frame number by the page size to find the frame's starting address, then add the offset.

Choose a page size

Larger pages reduce the number of mappings and let each cached translation cover more bytes. They also waste more space in partially used pages and move more data when a page is loaded. A common base page size is 4 KiB; other systems use 16 KiB or 64 KiB. x86-64 also supports large mappings such as 2 MiB pages.

A page table records a process's mappings. In a linear page table, the VPN indexes an array: entry 4 describes virtual page 4. Each process has its own table, so the same virtual address can refer to different physical bytes in different processes. On a context switch, the operating system selects the new process's table through a page-table base register.

Read entry state and permissions

A page table entry, or PTE, contains a physical frame number (PFN) and control information. In the teaching model, a valid bit says that the page belongs to the address space; a present bit says that its contents are resident in physical memory. Protection bits control reads, writes, execution, and user access. A dirty bit records writes since it was last cleared. An accessed bit records use since it was last cleared; it is also called the reference or use bit.

These are conceptual roles, not a promise of identical hardware layouts. x86 has no separate valid bit in a PTE. When present is clear, the operating system consults its own records to distinguish an unused address from a valid page stored elsewhere. On x86, hardware sets the accessed and dirty bits; the operating system manages and clears them.

Locate the entry and the byte

To translate an address with a linear table:

1. Split the virtual address into VPN and offset.
2. Locate its entry at $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}+\mathrm{V}\mathrm{P}\mathrm{N}\times \mathrm{P}\mathrm{T}\mathrm{E}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}$.
3. Check whether the mapping exists, is present, and permits this access.
4. Form the physical address from $\mathrm{P}\mathrm{F}\mathrm{N}\times \mathrm{p}\mathrm{a}\mathrm{g}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}+\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}\mathrm{t}$.
5. Read or write the byte at that physical address.

With 1,024-byte pages, virtual address 5,000 gives VPN 4 and offset 904. Suppose PTE 4 is present and allows the requested read, with PFN 9. Frame 9 starts at 9,216, so the physical byte address is 10,120. The table's own address is a separate calculation: if entries occupy 4 bytes, PTE 4 lies 16 bytes after the table base.

For a hexadecimal example, 4 KiB pages split 0x00403A7C into VPN 0x403 and offset 0xA7C. If the permitted mapping holds PFN 0x1F2B5, the physical address is 0x1F2B5A7C. The PTE lies at base + 0x403 × 4 = base + 0x100C. Appending the offset forms a data address; multiplying the VPN by entry size locates the PTE. These two addresses serve different purposes.

A failed check raises an exception. The operating system may bring in a valid nonresident page, provide zeroed memory, or repair another legitimate mapping. An illegal address or forbidden access usually causes a segmentation fault. A present page can still reject a write if its protection forbids writing.

Count table space and memory reads

Linear tables are expensive even for small processes. With 32-bit virtual addresses and 4 KiB pages, every table needs 1,048,576 entries. At 4 bytes each, that is 4 MiB per process, including entries for unused virtual pages. One hundred processes need 400 MiB just for these tables.

They also add a lookup to each memory reference. In a simple model without a translation cache, the processor reads one PTE and then the requested data: two memory accesses. Sharing is still possible: two processes can deliberately map their separate virtual pages to the same PFN, as for read-only program code.

A translation lookaside buffer, or TLB, is a small hardware cache of address translations in the memory-management unit (MMU). It holds recent VPN-to-PFN mappings and access information. It caches translations, while a data cache holds program bytes. A program can miss in one cache and hit in the other.

Follow hits and misses

On a TLB hit, the MMU obtains the PFN from the cached entry, checks the access permissions, and combines the PFN with the unchanged offset. It does not need to read the page table. A hit never removes the need to enforce protection. The TLB's valid bit says that a cached entry is usable; it does not say whether a virtual page belongs to the process's address space.

On a TLB miss, the system must look up the translation in the page table. If the page is present and the access is allowed, it installs the translation and completes or retries the reference. No storage read is needed. If the table instead reports a missing mapping or forbidden access, a page fault requires operating-system handling. A TLB miss alone is not a page fault.

Predict reuse from locality

TLBs can hold far fewer entries than the number of virtual pages, yet they work well because programs show locality. Spatial locality means nearby addresses are used close together in time. Once one translation is cached, many addresses within that page can use it. Temporal locality means recently used addresses are likely to be used again, as with the instructions in a loop.

Consider 16,384 four-byte integers stored consecutively in a page-aligned array. With 4 KiB pages, each page holds 1,024 integers, so the array spans 16 pages. Starting with an empty TLB and no interfering translations, the first integer on each page causes a miss. The next 1,023 on that page hit. There are 16 misses and 16,368 hits in all, giving a hit rate of about 99.9%.

Access order changes that result. In C, int a[1024][1024] stores rows consecutively. Assume four-byte integers, page alignment, 4 KiB pages, and a 64-entry LRU TLB. Each row occupies one page. Row-by-row traversal has one miss per row, or 1,024 misses. Column-by-column traversal visits 1,024 different pages before returning to the first. Its translation has already been evicted, so all 1,048,576 array references miss. The array's size is unchanged; the reuse distance changes.

Average hit and miss costs

The timing model must say what a hit and miss cost. Suppose memory takes 100 ns, the TLB lookup adds no time, and a miss in a linear table adds one memory read. A hit costs 100 ns and a successful miss costs 200 ns. At a 98% hit rate:

This average includes the final data access in both cases. Counting only the extra PTE read as the entire miss cost would understate the total. With multi-level tables, a miss may need several table reads, so locality matters even more.

A TLB miss needs a translation lookup, but architectures divide that work differently. With a hardware-managed TLB, as on x86 and ARM, the MMU walks the page table starting at the selected table root. Hardware defines the format it can walk. If the mapping is usable, it fills the translation cache without calling an operating-system handler for the ordinary miss.

A software-managed TLB, used in classic MIPS and SPARC designs, raises an exception on a miss. An operating-system handler finds the mapping and inserts it using privileged instructions. This gives the operating system more freedom over its table structure. Returning from this exception retries the instruction that missed; returning from a system call normally continues after the call.

Keep the refill handler reachable

The miss handler needs reliable access to its own instructions and data. If servicing a miss immediately triggers the same unresolved kind of miss inside the handler, progress can fail. Designs avoid this with untranslated memory or permanently wired translations for the handler's essential code and data.

Select the right address space

Context switches introduce another problem. Process A might map VPN 7 to frame 20 while process B maps VPN 7 to frame 90. Keeping A's untagged entry after switching to B would send B to the wrong frame. Loading B's page-table root does not by itself make an untagged cached mapping safe.

One solution is to flush the relevant TLB entries on a switch. Their valid bits are cleared, forcing the new process to refill them. Another solution tags entries with an address-space identifier (ASID). Lookup then matches both the virtual page and its address-space tag. x86 calls its tag a process-context identifier, or PCID. Entries for several address spaces can remain cached while the hardware selects only those belonging to the current context. Tag reuse still has to be managed so that an old entry cannot be mistaken for a new address space.

Invalidate changed mappings

A PTE change also makes a cached translation stale. Suppose the operating system removes write permission in memory but leaves a writable TLB entry. The processor might continue allowing writes through that old entry. The operating system must invalidate affected translations. On a machine with several cores, every core that could cache the mapping must participate. This coordination is called a TLB shootdown.

Calculate translation coverage

Capacity matters as well as correctness. TLB reach is the amount of memory represented by the cached translations:

A 64-entry TLB reaches 256 KiB with 4 KiB pages and 128 MiB with 2 MiB pages. Reach describes mapping coverage, not the capacity of physical memory. Real processors may have separate TLB capacities for different page sizes, so this calculation compares a fixed entry count.

When a TLB is full, it replaces a translation. LRU favors recently used entries; random replacement chooses without tracking recency. Cycling through one more page than fits defeats LRU because each translation is evicted just before it is needed again.

A linear page table reserves one entry for every possible virtual page. Most processes use only a small part of their address space: code and heap lie near one end, stack near the other, and a large gap separates them. A table with millions of invalid entries still consumes memory. Shrinking this cost means changing page size, table organization, or both.

Reduce the page count

Larger pages reduce the number of VPNs. With a 32-bit address space and 16 KiB pages, 14 bits form the offset and 18 bits form the VPN. A linear table then needs 262,144 entries. At 4 bytes each it occupies 1 MiB, compared with 4 MiB for 4 KiB pages. This saves table space even though the process can still address 4 GiB of virtual bytes.

The cost moves elsewhere. A small allocation can waste more of its last page, and bringing a page into memory transfers more bytes. Increasing page size does not distinguish a densely used part of the address space from an unused gap; it merely gives both fewer entries.

Omit gaps with separate segment tables

A segmentation-and-paging hybrid gives code, heap, and stack their own page tables. Each segment has a table base and a bound on its page numbers. The gap between segments needs no entries. Translation first selects the segment, checks its bound, and then looks up the page within that segment.

This approach depends on a useful division into segments. Its tables can have different lengths and may need contiguous physical space, reintroducing external fragmentation for the tables themselves. The process's data pages remain fixed-size; the fragmented objects are now the variable-sized page tables.

Index physical frames instead

An inverted page table changes what an entry describes. It has one entry per physical frame for the whole machine, recording the occupying process and VPN. With 16 GiB of physical memory and 4 KiB frames, it needs 4,194,304 entries regardless of how many processes have large virtual address spaces. Entry size is still needed to turn that count into a byte total.

An ordinary table uses the VPN as a direct array index. An inverted table instead searches for the pair consisting of address-space identity and VPN. A hash structure can make this efficient, but collisions may require extra probes. Shared frames also need extra handling because one frame may have several virtual names. Hashed page tables, such as those used in PowerPC systems, use related lookup ideas; a hashed table is not necessarily a strict one-entry-per-frame inverted table.

Allocate tables by used region

Multi-level page tables retain indexed lookup while allocating lower-level table pages only where mappings are needed. An upper-level entry can mark an entire unused range without allocating its lower-level table. This is the common solution on modern systems. The saving is greatest for sparse address spaces, while a TLB miss needs more lookup steps.

Choose comparisons by asking what controls size. A linear table scales with virtual pages per process. An inverted table scales with physical frames for the system. A hierarchy scales with the table branches needed for the mappings. None of these counts is the number of bytes of program data currently resident.

A two-level page table divides a large linear table into page-sized pieces. A page directory points to those pieces. The directory is allocated, but a lower-level page-table page is allocated only when its region needs mappings. An absent directory entry can represent a whole unused range.

Derive the 10/10/12 split

Take a 32-bit virtual address, 4 KiB pages, and 4-byte entries. Each page-table page holds 1,024 entries, so a 10-bit index selects an entry. The address splits into 10 directory bits, 10 table bits, and 12 offset bits. Each lower-level table maps 1,024 pages, covering 4 MiB of virtual addresses. The directory also has 1,024 entries and occupies one 4 KiB page.

Follow directory and table entries

The walk follows physical pointers:

1. Add $\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ to the directory's physical base. Read that page directory entry (PDE).
2. If it points to a table page, multiply its PFN by 4,096 to obtain that table's physical base.
3. Add $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ and read the PTE.
4. Check the leaf mapping and combine its PFN with the offset.

The PDE points to a table, while the PTE points to the requested data page. Confusing these roles sends a reference into page-table memory instead of the program's data.

For virtual address 0x00803ABC, the directory index is 2, the table index is 3, and the offset is 0xABC. Suppose directory entry 2 points to frame 0xA1. Its table starts at 0xA1000. Entry 3 is 12 bytes into that table, at 0xA100C. If the permitted, present PTE contains PFN 0x2F3C4, the data address is 0x2F3C4ABC.

Notice the two different multipliers. A table index counts entries, so multiply it by entry size. A PFN counts frames, so multiply it by page size. The offset counts bytes within the final page and needs neither multiplier. The directory base and pointers used during the walk are physical addresses; using virtual pointers would demand another translation to perform this translation.

Count tables and lookup reads

Space depends on how mappings are distributed. Suppose a process uses the bottom 8 MiB of its 4 GiB space and the top 4 MiB, with both regions aligned to directory boundaries. The low region needs two table pages, and the high region one. Adding the directory gives four pages, or 16 KiB, instead of a 4 MiB linear table. Mapping the same number of data pages sparsely across many directory regions could need more table pages.

In the basic teaching scheme, an invalid PDE means that none of the pages in its 4 MiB region belong to the address space. The walk stops without reading a PTE. Complete operating systems can also use missing entries for lazy allocation, so their software records decide the meaning of a hardware nonpresent entry.

The hierarchy saves space by adding work on a TLB miss. An uncached two-level walk reads a PDE and a PTE before accessing data: three memory reads in all, compared with two for a linear table. A TLB hit bypasses those table reads. This makes a high hit rate especially valuable as the hierarchy gets deeper.

The number of table levels follows from three quantities: the implemented virtual address width, the page size, and the entry size. First calculate the offset width. Then calculate how many entries fit in one table page and how many bits select an entry. Finally divide the remaining VPN bits into index fields, rounding the number of levels up if needed.

Derive the four levels

For four-level x86-64 paging, the implemented virtual address width is 48 bits. A 4 KiB page supplies 12 offset bits. An 8-byte entry gives 512 entries per table page, selected by 9 bits. The VPN has 36 bits, so four 9-bit indices are needed. An uncached successful walk follows four entries and then accesses the data.

The levels are PML4, page-directory-pointer table, page directory, and page table. Their indices occupy bits 47–39, 38–30, 29–21, and 20–12. CR3 identifies the physical root. Linux names the corresponding levels PGD, PUD, PMD, and PTE; its generic hierarchy includes a P4D level, which is folded away when the architecture uses only four levels.

Distinguish address width from RAM

A 48-bit implemented address space contains 256 TiB of addressable bytes. Addresses are still held in 64-bit values: in the ordinary canonical form, bits above bit 47 repeat that bit. The valid low and high ranges are separated by a noncanonical gap. Calling this a 48-bit address space does not mean every 64-bit pattern is usable or that a process receives 256 TiB of RAM.

A linear table would be enormous. There are $2^{36}$ virtual pages; multiplying by 8-byte entries gives $2^{39}$ bytes, or 512 GiB per process. A hierarchy represents unused ranges with absent branches instead of reserving all those entries.

Processors supporting five-level paging can use 57 implemented virtual address bits when that mode is enabled. One more 9-bit index is added above the PML4, giving 128 PiB of addressable bytes and one more possible table read. The upper bits of a canonical address then repeat bit 56. Processor support and the enabled paging mode determine which width applies.

Stop the walk at a large page

Large pages stop the walk early. On x86-64, an entry at page-directory level can directly map a 2 MiB page, leaving 21 offset bits. A page-directory-pointer entry can map a 1 GiB page, leaving 30 offset bits. Lower bits that would otherwise select lower-level entries now select bytes within that large page.

This reduces both walk length and the number of translations needed for a given region. It increases TLB reach, which can help databases and other large workloads. The physical mapping needs a suitably aligned contiguous run of frames, and a partly used large page can waste much more memory. Linux supports explicit huge-page allocation and transparent huge pages; the supported sizes depend on the architecture.

The simple cost count assumes no cached table entries. Real processors cache paging structures, and table reads can hit in ordinary caches. Four levels therefore do not guarantee four main-memory delays on every TLB miss. They describe the dependency chain and its uncached cost.

Virtual address spaces can together exceed physical memory because not every page must stay resident. Swap space stores displaced page contents on a disk or SSD. Linux can use a swap partition or swap file; Windows uses a page file. Physical memory holds the currently resident subset of pages.

Paging moves individual pages. A page-out writes a page to backing storage before its frame is reused; a page-in reads it back. Historically, swapping also meant moving an entire process. In modern discussions, the word often refers to page movement, so identify the object being moved.

Interpret the missing mapping

A PTE's present bit tells hardware whether a resident mapping is available. If a valid page has been swapped out, the operating system records where its contents can be found, either in software-defined entry bits or separate metadata. A present bit of zero does not itself identify swap: it can also describe unallocated or lazily allocated memory.

A page fault is an exception caused by an access that cannot complete with the current mapping. It can report absence or a protection violation. The handler decides whether the access is legitimate and how to resolve it. Successful handling can load stored bytes, supply zeroed memory, map an existing resident frame, or make a private copy. A truly invalid access usually results in a segmentation fault.

Restore a saved page

Follow a swapped-page read with 1,024-byte pages:

1. Virtual address 5,000 gives VPN 4 and offset 904.
2. The TLB has no usable translation. The page-table walk finds the valid page nonpresent; software records identify swap block 37.
3. The handler obtains frame 9. If no frame is free, memory reclamation must first make space.
4. The operating system reads block 37 into frame 9. The faulting process waits; another runnable process can use the CPU.
5. On completion, the operating system installs PFN 9, sets the mapping present, and makes the process runnable.
6. The instruction is retried. Translation now reaches physical address 10,120.

The instruction resumes its intended operation after the bytes are available. Advancing past the failed instruction would lose a load or store. The process may observe a delay, but its virtual address has not changed.

Classify the fault and predict demand

A major fault needs a storage read. A minor fault is resolved without that I/O, such as by providing a zero-filled frame or mapping a frame already resident. A large count of minor faults therefore does not imply the same device traffic as the same count of major faults. On Linux, /usr/bin/time -v reports the two counts for a command.

Demand paging waits until a page is touched before supplying it. This lets a program begin without loading all of its contents. Prefetching brings in pages expected to be needed soon. Good predictions avoid later waits; poor predictions consume bandwidth and memory for pages never used.

Keep the events distinct. A TLB miss asks for a translation lookup. A page fault asks the operating system to handle a mapping problem. A segmentation fault is a usual outcome for a forbidden access. A resident, permitted page can cause a TLB miss without either of the other events.

A rare storage read can dominate average memory time. Let $p$ be the probability that a reference causes a major fault, $M$ the ordinary access time, and $F$ the total service time for a faulting reference. A simple two-case model gives:

Here $F$ includes the storage read, operating-system work, and any required dirty-victim write-back. It is the total fault case, not merely a small PTE lookup penalty.

Calculate the effect of rare faults

Assume an ordinary access takes 100 ns and a major fault takes 8 ms in total. Convert 8 ms to 8,000,000 ns before averaging. With one fault per 1,000 references:

This is about 81 times the ordinary access time. A fault rate of 0.1% sounds small, but a fault costs as much as many thousands of memory references.

For a slowdown below 10%, require an average below 110 ns. Rearranging gives:

That is fewer than roughly one major fault per 800,000 references. The allowed probability depends on the assumed service time. For an illustrative SSD service time of 0.1 ms, the wait is shorter, but it is still 100,000 ns: one thousand 100-ns accesses.

Keep frames ready

The operating system tries to have frames ready before a fault needs one. A background page daemon, such as Linux's kswapd, reclaims memory when free frames fall below a low watermark. In the basic watermark model, it continues toward a high watermark. This avoids making every fault wait for a victim to be selected and prepared.

Preserve changes before reuse

A dirty page contains changes since the dirty state was last cleared. Before its frame is reused, those changes must be preserved if the page remains part of a process's memory. Writing it back can happen in the background. After successful write-back, the resident page can be marked clean; a later write makes it dirty again.

A clean page can be discarded without a new write only when its contents can be recovered or regenerated. Unmodified program code can be read again from the executable. A page with an up-to-date swap copy can be read from swap. A clean anonymous page with no recoverable copy cannot simply be forgotten. The dirty bit alone does not prove that backing storage exists.

If a fault must evict a dirty page synchronously, it can require a victim write followed by the demanded read. Preferring a clean, recoverable victim avoids that write on the fault's critical path. Clustering combines several writes into larger transfers, especially useful on disks.

Page faults are useful control points for postponing work. A mapping can belong to a process before the operating system assigns it a private frame. With demand zeroing, the first access obtains zero-filled memory. This avoids allocating and clearing every reserved page up front. Zeroing also prevents a process from seeing another process's leftover data.

The fault needs no disk read because the required contents are zeros, not saved bytes. It is a minor fault. A system can optimize the implementation, but the visible result remains that newly supplied memory has the required zero contents.

Share read-only code

Separate page tables do not require separate copies of every page. Two PTEs can hold the same PFN, even at different virtual addresses. Processes running the same program can share read-only code. Fifty processes using an editor can refer to one resident copy of each shared code page. Read-only protection stops one process from changing those instructions for everyone.

Create private contents on a write

Copy-on-write (COW) permits initial sharing of pages that may later need private contents. After fork(), parent and child have separate address spaces but can share their ordinary private data frames. The operating system marks their writable private mappings read-only and records that they are COW mappings. Reads succeed without copying.

When either process first writes a shared COW page, the write violates its current protection and causes a page fault. The handler recognizes the legitimate COW case, allocates a private frame, copies the page, installs a writable mapping for the writer, and retries the instruction. The other process retains the original contents. The operating system must also make cached translations agree with the changed mappings.

For a process with 400 MiB of resident private data, suppose its child writes three distinct 4 KiB pages before calling exec(). The data copied because of those writes total 12,288 bytes. Repeated writes to one already-private page do not cause a fresh full-page copy each time. Page-table creation and other process bookkeeping still have costs; COW avoids eagerly copying all 400 MiB of data.

This is especially useful when fork() is soon followed by exec(), which replaces the child's address space. Copying all the old data immediately would perform work the child may never use. Intentionally shared writable mappings have different semantics: COW describes the private mappings that must diverge on a write.

A read-only PTE alone does not establish COW. A write to genuinely read-only program code is an error; a write to a COW-protected data page can be repaired. Software records distinguish the cases, so the same hardware protection exception can produce either a successful retry or a segmentation fault.

Protect kernel mappings

Kernel mappings also use protection. A traditional design maps kernel memory into each process's address space with supervisor-only access, allowing kernel entry without selecting a wholly different mapping. User-mode code cannot access those pages just because they have addresses. Kernel page-table isolation, introduced on affected systems after Meltdown became public in 2018, removes most kernel mappings while user code runs and switches mappings on kernel entry.

A replacement policy chooses a resident page to evict when a needed page has no free frame available. Physical memory acts as a cache of page contents. The policy tries to keep pages whose future use will avoid expensive faults. A replacement miss is an abstract residency event; whether it needs I/O depends on where the missing contents come from.

Record hits and misses

Compare policies using the same reference string, the same frame count, and the same initial state. A reference string lists page numbers in access order. For each reference, first ask whether the page is resident. If it is, record a hit. Otherwise record a miss, load the page, and evict a victim only if memory is already full.

First references are misses even while free frames remain. These compulsory misses cannot be avoided by choosing another victim. Later misses caused by insufficient capacity are capacity misses. Page replacement has no placement conflicts: a page can occupy any frame. Conflict misses belong to caches with restricted placement, not this fully flexible frame model.

Choose the farthest future use

The optimal policy, OPT or MIN, chooses the page whose next use is farthest in the future. A page never used again is an ideal victim. This produces the fewest misses for a known reference string, but a running operating system cannot know arbitrary future references. OPT provides a benchmark for practical policies.

Use three initially empty frames and the string 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. The first three references fill memory and miss. The next 1 hits. At reference 5, page 4 arrives: resident pages 1, 2, and 3 are next used at positions 6, 8, and 11. Evict 3, whose next use is farthest away.

After 1 hits, page 5 arrives at position 7. Residents 1, 2, and 4 are next used at positions 9, 8, and 10, so OPT evicts 4. The next 2 and 1 hit. Page 4 misses at position 10; either 2 or 5 can go because neither is used again. Page 3 then misses and removes another page with no future use. The final 1 hits.

Compare totals and workloads

The trace has 7 misses and 5 hits. Counting all 12 references, the hit rate is 5/12, or about 41.7%. There are five distinct pages, hence five compulsory misses. If the reported rate excludes those misses, it becomes 5/7, or about 71.4%. Both rates can describe the same trace, so always identify the denominator.

To avoid losing your place, keep the current reference separate from the future suffix. OPT compares the next use of each resident page after the current position; it does not choose whichever page has the greatest numeric label or was loaded first. If two pages are never used again, either choice preserves optimality.

Workloads affect how much policy matters. When references are equally likely across all pages, past use provides little guidance. With locality, a small hot set receives many references, and preserving it improves hit rate. The gap between a practical policy's miss count and OPT's count measures possible improvement on that workload.

FIFO evicts the page loaded earliest among the current residents. A queue tracks arrival order. A hit does not move the page to the back of that queue. This makes FIFO easy to maintain, but it can evict a page that is still used frequently simply because it arrived long ago.

Track last use instead of arrival

LRU, least recently used, tracks the most recent use of every resident page. On a hit, that page becomes the most recently used; on a miss with full memory, the page with the oldest last use leaves. This follows temporal locality: recent use often predicts near-future use. Arrival time and last-use time are different histories.

Random replacement chooses a resident victim randomly without maintaining recency order. Its result varies across runs. It can avoid the deterministic failure pattern of LRU on a cyclic workload, but it can still make unlucky choices. LFU, least frequently used, tracks counts instead of recency. Without aging, it can retain a page that was popular in an earlier program phase but is now unused.

Trace policies on the same string

Compare three empty frames on 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. Pages 1, 2, and 3 first fill memory. The hit on 1 leaves FIFO's order unchanged, so the arriving 4 evicts 1. LRU instead treats 1 as recent and evicts 2. The following reference to 1 therefore misses under FIFO and hits under LRU.

For LRU, the later misses evict 3 for page 5, 4 for page 2, 5 for page 4, and 2 for page 3. It finishes with 8 misses and 4 hits. FIFO makes 10 misses and 2 hits. OPT makes 7 misses on the same string. LRU improves on FIFO here but does not reach the future-aware optimum.

Explain Belady’s anomaly

More frames do not improve every policy on every string. Belady's anomaly is an increase in misses when FIFO receives more frames. For 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO has 9 misses with three frames and 10 with four. Extra capacity changes the queue's later victims, so its resident sets are not necessarily nested.

LRU and OPT are stack algorithms: with consistent handling of ties, the resident set for a smaller frame count is contained in the set for a larger count. Increasing capacity therefore cannot turn a smaller-memory hit into a larger-memory miss. LRU gives 10 misses with three frames and 8 with four on the anomaly string.

Recognize poor recency workloads

LRU still has poor workloads. Cycle three times through pages 1, 2, 3, 4 with three frames. Each new page evicts the one that will be needed next, producing 12 misses. OPT needs 6. Random replacement can retain useful pages across a cycle and performs better on average here. A one-time scan can likewise push a useful hot set out of an LRU cache.

A policy comparison must include its workload and frame count. Locality makes recency useful in many programs, which motivates approximations of LRU in real systems. A periodic loop just beyond capacity rewards a different choice; no observed advantage on one short trace establishes a universal ranking.

Exact LRU needs work on every memory reference. With timestamps, each reference updates a timestamp and victim selection searches for the oldest. With an ordered list, the victim is available at the tail, but each reference must move its page to the front. Updating this structure in software on every load and store would be too expensive.

Read the use bit

Hardware offers a cheaper signal: the use bit, also called the accessed or reference bit. Hardware sets it when a page is read or written. The operating system clears it to begin another observation interval. A set bit means at least one use since the last clearing; it is not a frequency count and does not reveal the exact last-use order.

Scan for a victim

The clock algorithm places frames in a circle and keeps a hand pointing to the next candidate. On replacement, it examines the candidate's use bit. If the bit is 1, the hand clears it and advances. If the bit is 0, that frame is the victim. The new page enters with its use bit set, and the hand advances past it. A hit sets the referenced page's bit without moving the hand.

Suppose the circle holds A with bit 1, B with bit 0, and C with bit 1, with the hand at A. A fault on D clears A and moves to B. B already has bit 0, so D replaces B with bit 1, and the hand ends at C. If the next reference is a fault on E, the hand clears C, then finds A at 0 and replaces A. If A had been accessed between those faults, its bit would be 1 and it would receive another chance.

If every bit is 1 and no new accesses intervene, one sweep clears them all. The hand then evicts its starting page when it returns. That particular selection resembles FIFO's next arrival-order victim, but clock generally follows use history and hand position; it is not always equivalent to FIFO.

A full clock trace needs an initialization convention. Here, empty frames fill in order with bit 1; the hand remains at frame 0 until the first replacement. Hits set bits. Each replacement advances the hand. Under that convention, three frames on 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1 produce 10 misses. A short string can hide the benefit of a recency approximation; clock often tracks locality well over longer runs.

Consider write cost and real variants

Dirty state adds the cost of preserving a victim. An enhanced-clock preference ranks (use, dirty) pairs as (0,0), (0,1), (1,0), then (1,1). This favors a page with neither recent use nor unsaved changes. Implementations differ in how scans clear bits and schedule writes. Background write-back can make a dirty candidate clean before replacement needs it.

Real systems use richer variants. VAX/VMS placed removed pages on clean or dirty lists so a process could reclaim one before its frame was reused. Linux has used active and inactive lists and offers multi-generational LRU, which groups pages by observed recency. These systems use hardware evidence to guide operating-system decisions; the hardware's use bit does not itself choose a victim.

Thrashing occurs when processes spend most of their time faulting pages into memory and evicting pages that are needed again soon. The storage device stays busy while CPU utilization falls, even though programs still have work to do. A low CPU load alone does not identify thrashing; the combination of heavy paging and poor progress is the clue.

The cause is memory demand beyond the available frames. A process needs a useful collection of pages resident to complete its current phase. If several processes' active collections do not fit together, their faults repeatedly displace useful pages. Starting still more processes can worsen this pressure even though the CPU appears underused.

Estimate current page demand

The working set, written $W(t,\mathrm{\Delta })$, estimates a process's current needs. In the reference-window model, it is the set of distinct pages in the last $\mathrm{\Delta }$ references ending at time $t$. Count each page once, even if it appears several times in the window. The working-set size is a number of pages, not the number of references.

With window 5 and the string 1, 2, 1, 3, 2, 1, 4, 5, 4, 5, 4, 6, 5, 4, examine the state after reference 6. The last five references are 2, 1, 3, 2, 1, giving {1, 2, 3}, size 3. After reference 8 the window is 3, 2, 1, 4, 5, giving size 5. After reference 11 it is 4, 5, 4, 5, 4, giving size 2. Demand temporarily peaks while old and new phases overlap.

Control active demand and allocation

A short window can omit pages still needed; an overly long one can include pages from a finished phase. Peter Denning's working-set model links these changing needs to allocation. A working-set policy runs processes only when their combined working sets fit. If they do not, it suspends one or more processes and releases their frames. This is admission control.

Page-fault frequency (PFF) control uses measured fault rates. Above an upper threshold, a process needs more frames. Below a lower threshold, some frames can be reassigned. If a process needs frames and none are available, suspending a process may be necessary. Two thresholds reduce continual adjustments around a single cutoff.

With global replacement, a fault can evict another process's page. This adapts flexibly to changing demand but lets one process increase another's faults. With local replacement, victims come only from the faulting process's allocation. This limits interference but cannot rescue a process whose assigned frames are too few without an allocation change.

Choose remedies for memory pressure

Useful remedies reduce demand or increase capacity: run fewer programs, add physical memory, or improve locality, such as traversing arrays in storage order. Faster swap reduces the cost of each major fault; it does not make an oversized active set fit. Replacing a disk with an SSD may improve progress without removing the cause.

Under extreme pressure, Linux's out-of-memory killer can terminate a selected process when reclaim and swapping cannot free enough memory. Selection uses memory-related badness scoring and policy adjustments, not simply the identity of the largest process. Memory becomes reclaimable as the process exits, and its work is lost. This is a last-resort release of resources, distinct from suspending a process so it can resume later.