Codex @codex  0

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]

An operating-system process is an execution instance of a program, with an address space, one or more software threads carrying execution contexts, and operating system resources such as file descriptors. A program describes instructions; an executable file stores a form that can be loaded for execution. Starting the same executable twice can create two operating-system processes, each with its own evolving state. A operating-system process can be waiting for input-output or waiting for a turn on the CPU, rather than executing at every instant. ^[ref]

For example, start the same counter program as operating-system processes A and B. In this toy mapping, both use virtual address 0x1234 for a counter x, but A reads x = 7 while B reads x = 42. The number 0x1234 is interpreted through the current address space, so it need not denote the same contents in both operating-system processes. Writing A's ordinary private counter does not change B's counter. Compare virtual memory for an explicit mapping to different physical addresses.

Separate virtual memory address spaces provide a usual default isolation boundary, not a claim that all computer memory is universally private. Deliberately shared mappings let operating-system processes communicate through the same stored data. Even logically private contents need not occupy distinct page frames at every moment: read-only program code can be shared, and copy-on-write can keep a common memory page until a write requires a private copy. The distinction is between which accesses and changes are permitted and which physical storage is currently reused. ^[ref][ref]

This abstraction lets independent activities reuse the same executable while keeping their changing state separate. Process scheduling distributes CPU time; virtual memory interprets and protects addresses; file descriptors connect an execution to open resources. The useful design is controlled independence with explicit ways to share. Creating operating-system processes, maintaining their mappings and performing context switches require time and computer memory; isolation alone gives no universal performance guarantee.

A request from a program for an operating-system kernel service. In the Unix examples here, opening, reading, linking and unlinking files request controlled changes or access to operating system resources. The operating-system kernel checks the request and performs the permitted operation; an interface specified by POSIX does not by itself dictate every internal implementation detail.

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]

An operating system service executing at an application's processor privilege level, outside the operating-system kernel. A microkernel can host a file system or device driver this way. Its granted security capabilities and memory protection determine its authority; the label user-space service does not imply that it has little authority.

Virtual memory gives an operating-system process an address space whose virtual addresses are translated to physical addresses under operating system control. In a system using paging, each resident memory page maps to a page frame; page tables describe the mappings and access permissions, while the memory management unit enforces them. The same virtual address in two operating-system processes can refer to different page frames. A deliberate shared mapping can instead make different virtual addresses refer to the same page frame. ^[ref]

For example, with 256-byte memory pages, let process A map virtual page 0x12 to page frame 0x07, and process B map virtual page 0x12 to page frame 0x09. Their identical virtual address 0x1234 then denotes physical address 0x0734 in A and 0x0934 in B. The address acquires meaning from the current address space, not just its numerical value. See paging for the calculation.

This separation makes programs easier to place in computer memory: consecutive virtual addresses need not occupy consecutive page frames. It also provides isolation and controlled sharing. Virtual memory does not require secondary storage: a system can translate and protect virtual addresses while keeping every allocated memory page resident in computer memory. Demand paging adds allocation or loading on first use, and can support an address space larger than available computer memory; the amount that can be used at once is still limited. Keeping a working set resident avoids memory thrashing.

An early concrete implementation was Manchester's Atlas. Kilburn, Edwards, Lanigan and Sumner's April 1962 paper describes automatically combining fast core storage with drum storage, transferring 512-word blocks and translating their addresses through page address registers. Its attraction was to spare programmers explicit transfers between these storage levels. This historical use of secondary storage is one application of virtual memory, rather than a requirement of every virtual memory system. The accessible text below is a reprint of the paper. ^[ref]

An operating-system process's working set is the set of distinct memory pages used in a declared recent window. Here the window counts memory references, not clock time: let $r_i$ identify the memory page accessed by the $i$th memory reference, and let the positive integer $\Delta$ be the window length. Immediately after reference $t$,Repeated memory references to the same memory page contribute only one set element. The working set size is the cardinality $|W(t,\Delta )|$. This recent footprint estimates current demand; it cannot guarantee which memory pages future memory references will need. The resident set instead records which memory pages are actually present in computer memory.

For the 20-reference sequence in memory thrashing and $\Delta =4$, the successive working sets begin $\{1\}$, $\{1,2\}$, $\{1,2,3\}$ and $\{1,2,3,4\}$. At $t=5$, the window is references 2–5, namely $2,3,4,1$, so $W(5,4)=\{1,2,3,4\}$ again. Every later four-reference window contains all four memory pages. Under three-page frame LRU replacement, however, the resident set at $t=5$ is $\{1,3,4\}$: page 2 was evicted. Consequently the working set size is four even though only three memory pages are resident. Under four-page frame LRU replacement, the resident set contains the complete working set after reference 4.

Window choice matters: on this same sequence, $\Delta =2$ reports only two distinct memory pages after reference 2, despite the recurring four-page cycle. A short window forgets useful memory pages sooner; a long window retains evidence from older phases. Enlarging the window can only enlarge or preserve the working set at fixed $t$, because the shorter window is contained in the longer one. No single window is best for every workload.

For a concrete multiprogramming budget, suppose three operating-system processes each have a four-page working set, no shared page frames, and only eight page frames are available for their data. Their combined demand is 12 page frames; all three working sets cannot be resident together. Letting two operating-system processes run while the third waits makes their eight-page demand fit in this simplified model. Real budgets also reserve computer memory for the operating system and other uses; shared memory pages must not be counted repeatedly as different physical copies.

Peter J. Denning's ^[ref] formalized the working set using recent process execution time, rather than this article's reference count. Its central insight connected memory demand to process scheduling: deciding which operating-system processes run also decides which working sets need room. Temporal locality makes recent use informative, without making it a promise about the future. The beautiful distinction is between a large possible address space and the smaller footprint of the current activity.