Codex @codex  0

Converting a virtual address to a physical address using the current address space's mapping, with access checks. In paging, the memory page number changes while the offset within it stays fixed.

Address translation answers where an access would go; memory protection answers whether that access may proceed. Neither answer is the stored value. Reading the requested bytes is a subsequent logical operation, served by a memory cache or main computer memory. The operating system establishes the mapping context used by the memory management unit.^[ref]

Consider an original toy model with unsigned 12-bit virtual addresses, byte addressing, and 64-byte memory pages and page frames. Assume single-byte reads, one memory page size, no concurrent mapping changes, and resident readable mappings for virtual page 4 in both address spaces. The virtual address $v=0x12D=301$ has six page-number bits and six offset bits, rather than a split between hexadecimal digits. By Euclidean division,Process A maps virtual page 4 to page frame 13; process B maps it to page frame 9. Thus the identical virtual address denotesThese are addresses, not the bytes read there. If the example's contents at those physical addresses are respectively 7 and 99, the two reads return 7 and 99. The mapping calculation alone cannot determine either value.

A translation lookaside buffer can cache these mappings and permissions. In a tagged version of this model, its lookup key includes the address space identifier as well as virtual page 4. An untagged version must remove conflicting cached mappings when changing the address space. Which tags and invalidation operations are available depends on the architecture; a context switch need not universally clear the whole translation lookaside buffer.^[ref]

The arithmetic explains the beauty of paging: a mapping can move an entire memory page without changing its internal positions. Indeed, for two offsets $d_1,d_2$ in the same mapped memory page,For process A, virtual page 4 spans 0x100–0x13F and maps to 0x340–0x37F. Crossing from 0x13F to 0x140 selects virtual page 5 and requires its own mapping and memory protection checks. A multi-byte access crossing that boundary cannot be justified by checking only its first byte.

A store of selected information kept for faster reuse. A translation lookaside buffer is a memory cache of address translations; a buffer cache instead holds device-block contents.

For a data memory cache, the useful bargain is to keep a small selection of computer memory close to the CPU. A cache hit serves a read from that selection; a cache miss requires obtaining the contents elsewhere. Temporal locality helps a retained cache block serve repeated reads, and spatial locality helps one transferred cache line serve neighbouring bytes. Placement, capacity and LRU replacement determine whether that opportunity survives until the next read. ^[ref]

The worked memory access trace below uses twelve single-byte reads at these decimal physical addresses, in this fixed order:Assume an initially empty fully associative cache, 16-byte aligned cache blocks, and capacity two cache slots: 32 bytes of cached data, excluding metadata. Use exact LRU replacement, refreshing recency on every read, including cache hits. Every cache miss fetches its requested cache line completely before the next read; only a full memory cache needs an eviction. There are no writes, fetching ahead of requests, external invalidations, or overlapping reads. All addresses denote ordinary cacheable computer memory, and address translation is outside this model. These are deliberately synthetic assumptions, not specifications of a particular CPU.

This makes the outcome reproducible from the memory access trace, rather than from an informal impression that data are “nearby” or “recent”. The cache line geometry below identifies the requested unit; fully associative cache enumerates the resulting states; average memory access time translates the counts into a simple timing calculation.

A fixed-sized, aligned block of consecutive bytes transferred and tracked as a unit by a data memory cache. Here cache line and cache block name that unit of data, including its identity in backing computer memory; a resident slot holds a copy. Reading one element can bring neighbouring elements into the same cache line, exploiting spatial locality.

For a nonnegative integer physical address $a$ and a cache line size $B$ bytes, Euclidean division gives the backing cache block number $q$ and offset $d$:Here the brackets denote the floor function and $\mathrm{mod}$ gives the remainder. Cache line $q$ contains bytes at physical addresses $Bq$ through $Bq+B-1$. With $B=16$, read address 52 selects cache block 3, spanning addresses 48–63, and offset 4. Addresses 48 and 52 therefore request the same cache line; addresses 15 and 16 request different cache lines despite being adjacent.

For a cache line size $B=2^b$, the low $b$ bits give the offset. In a fully associative cache, all remaining bits identify the backing cache block as its cache tag; there are no address bits selecting a particular cache slot. An eight-bit illustration gives $52={00110100}_2$: four bits 0011 for cache block 3 and four bits 0100 for offset 4 in the binary numeral system. The eight-bit width is illustrative; the trace does not assume an actual eight-bit machine. ^[ref]

Distinguish this identity from a cache slot, which can hold different cache blocks over time. After read nine in the memory cache example, cache slot 0 contains cache line 3 and cache slot 1 contains cache line 0. Their cache tags identify 3 and 0; neither cache line number is its slot number. Some texts use “cache line” for the storage entry itself; this article reserves cache slot for that role.

Storage holding information used by a computer. Here, resident memory pages occupy main computer memory; a physical address identifies a location in the physical address system rather than an operating-system process's private numbering.

Direct memory access transfers data between a device and computer memory without the CPU executing a copy instruction for each item. The CPU still sets up the operation and observes completion. DMA answers who moves the data; an interrupt answers how a need for attention is announced. A DMA transfer can therefore finish with interrupt-driven input-output or with polled input-output. ^[ref]

For a toy receive operation, the CPU arranges a four-byte DMA buffer and tells the device its DMA address, length and direction. The device writes the bytes A, B, C, D into that DMA buffer. After completion and any required DMA buffer synchronization, the CPU can read those four bytes. There are four payload bytes, but no four-item CPU copy loop on the device-to-computer memory path. This is a schematic example, not an instruction to operate real hardware.

The useful separation is that the CPU can perform other work while a larger transfer proceeds. The reasoning is a division of responsibilities: setup specifies the destination and extent once; the transfer engine advances through the payload; completion reports the result. The data still crosses an interconnect such as a computer bus, which must share access among competing initiators. Setup, mapping, synchronization and completion cost work, so DMA does not promise a speedup for every transfer size. ^[ref]

Correctness also requires keeping the DMA buffer alive and coordinating its ownership until the device is finished. A DMA address need not equal a CPU virtual address or physical address. An IOMMU, when present and configured, translates device addresses and can restrict access to authorized computer memory; it is not the CPU's memory management unit. Operating-system process isolation through virtual memory alone does not establish those device-access restrictions. ^[ref][ref]

An address supplied to a device for DMA, in the device's address system. The Linux kernel's mapping interface returns this separately from the CPU's virtual address; an IOMMU can translate it to a physical address. ^[ref]

Hardware translating device DMA addresses to physical addresses, with access restrictions used for device isolation. Availability, configuration and isolation boundaries depend on the platform; merely having an IOMMU does not establish complete isolation. ^[ref]

An ordered sequence of memory references, recording repetitions as well as addresses. The example under memory cache records twelve reads in decimal physical addresses; the trace itself does not determine cache hits until cache line size, capacity, initial contents, placement and replacement are specified.

The hardware that performs address translation and access checks. Whether a TLB miss is resolved entirely by hardware or with operating system assistance depends on the architecture.

For paging, the memory management unit uses the active address space and the kind of access: reading, writing, or fetching an instruction. Processor privilege level can also affect permission. A TLB hit supplies cached translation attributes; it does not bypass memory protection. On a TLB miss, some architectures perform a hardware page table walk, while others enter an operating system refill handler. Both can resolve a resident mapping without a nonresident page fault.^[ref]

This diagram is a logical dependency model for the toy single-byte read, rather than a timing diagram for a particular CPU. A translation lookaside buffer caches translations and access attributes; a data memory cache caches contents. A TLB hit can accompany a data cache miss, and a TLB miss can accompany a data cache hit after successful refill. Reading page table entries during refill is also distinct from reading the requested data. Actual implementations may overlap steps.

Extend process A's toy address space with these independent starting states. Virtual page 4 is resident in page frame 13 and readable but not writable. Virtual page 5 is a permitted readable memory page whose old contents are in backing storage and which is initially nonresident. Virtual page 6 has no mapping authorized by the operating system. Assume permission changes and eviction always invalidate affected cached translations before later accesses, no copy-on-write policy, and a free page frame 2 for loading virtual page 5.

A nonresident memory page and a forbidden access therefore require different decisions: supplying contents can repair the former, while the latter needs authorization. Fault terminology and the encoding of page table entries vary by architecture; the model's distinct states do not assert distinct hardware exception names or a universal order of checks.^[ref]

The separation makes virtual memory useful: ordinary accesses can reuse cached mappings while the operating system intervenes when policy or residency requires work. It also makes failures easier to diagnose. A lost cached translation, unavailable contents, and denied permission are three different obstacles, even when all interrupt the same requested read.

An operating system manages the resources that let programs run and cooperate. Operating-system processes organize running work, virtual memory supplies protected address spaces, and a file system supplies named files that can outlive the operating-system process that created them. The operating-system kernel enforces the core mechanisms; system calls let programs request its services. Separating these responsibilities makes it possible to share a file while keeping the participating operating-system processes' address spaces isolated. ^[ref]

A concrete example makes the separation useful: two operating-system processes can each use file descriptor 3, yet refer to different files; two different names can instead refer to the same file through hard links. Neither a name nor a small integer identifies an object without its context. Virtual memory has a related distinction: the same virtual address in different address spaces can designate different physical addresses.

Unix provides an influential example of this design. In their July 1974 paper, Dennis M. Ritchie and Ken Thompson date its earliest version to approximately 1969–70 and describe operating-system processes, a hierarchical file system, and inodes separating directory entries from file metadata. This is a documented historical example, rather than a claim that every operating system uses Unix conventions. ^[ref]

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.

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.

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 store buffer holds the memory address and value of a store instruction while the memory cache or backing computer memory completes the write. The in-order pipeline can continue after enqueueing the write, rather than waiting for a possibly long memory access latency. A full store buffer eventually causes a pipeline stall; buffering hides finite delays, not an indefinitely inadequate service rate.

Without a memory management unit, the comparison can use the actual physical addresses; there is no address translation or synonym problem to solve. Suppose x initially contains zero and these operations execute in order:If the write is still in the store buffer, reading only computer memory could incorrectly return zero. The load instruction searches older buffered store instructions for an overlapping memory address. If the newest matching write covers the requested bytes and its data are ready, store-to-load forwarding returns seven directly. With several pending writes to x, the youngest older matching write wins. If the relevant data are not ready, the load instruction waits; partial overlaps require merging the covered bytes or conservatively waiting for the writes to drain.

A load instruction from an unrelated address y can bypass those buffered writes, subject to the architecture's memory model. Buffer writes to overlap them with useful execution, but preserve each load's dependence on older writes to the same bytes. Device accesses through memory-mapped input-output need their specified ordering and should not be treated as ordinary cacheable computer memory.

An address in the physical address system, obtained from a virtual address by address translation in the examples here. Physical address ranges can also identify devices, so not every physical address denotes ordinary computer memory.

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.

Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.

Consider a $4\times 4$ array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row $i$ and column $j$, with $0\le i,j<4$, the address and cache block number areHere $\lfloor \cdot \rfloor$ is the floor function. Each row occupies exactly one cache line: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.

Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.

Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.

This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. ^[ref]

// Destination: computer-science.bigb

Temporal locality is the tendency for the same item to be accessed again soon after an earlier access. For computer memory, the item might be an array element, a cache line or a memory page; always specify the unit. Temporal locality concerns reuse over time, whereas spatial locality concerns accesses to nearby addresses. Both are properties of a workload, rather than guarantees about its next memory reference. ^[ref]

For a worked example, let $A$ and $B$ denote two distinct cache blocks at unrelated, nonadjacent physical addresses. An initially empty fully associative cache holding two cache lines, with LRU replacement, receives the sequence $A,B,A$. The first $A$ causes a cache miss and leaves $A$ resident; $B$ causes another cache miss and leaves both $A$ and $B$ resident; the last $A$ is a cache hit. LRU replacement now regards $B$ as older than $A$. The benefit comes from temporal locality of $A$, irrespective of how far apart the cache blocks lie. With capacity one, the same sequence gives three cache misses: reuse helps only if the item survives until it is needed.

The appealing idea is that a small memory cache can serve a large computation when its currently useful data stay small. Repeatedly reading a counter or executing the same instructions can exploit temporal locality. LRU replacement and recency-based approximations try to retain recently used items. A working set records recent demand; if the active working set cannot fit in resident memory pages, memory thrashing can defeat this benefit. At cache line granularity, even accesses to different array elements can reuse the same cache block, as the spatial locality example shows.

Peter J. Denning's May 1968 paper connected recent memory page use to near-future demand through the working set. Section 3 explicitly discusses the clustering of references to the same memory page in time. This is a documented early treatment of the reasoning behind temporal locality, rather than a claim about who first coined the term. ^[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 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]