Paging is a memory-management technique in which a computer’s virtual address space is divided into fixed-size blocks called pages, while physical memory is divided into corresponding blocks called page frames. A mapping associates each accessible virtual page with a physical frame and records permissions and other attributes. Because consecutive virtual pages need not occupy consecutive frames, paging allows programs to use a continuous range of addresses even when the underlying physical memory is scattered.
Paging is a central mechanism of virtual memory in modern operating systems. It supports separate address spaces, controlled sharing, demand loading, and the movement of memory contents between RAM and secondary storage. These capabilities are related but distinct: a system can use paging without moving pages to disk, and a page fault need not involve disk access. Paging also underlies memory-mapped files, efficient process creation, and hardware-assisted virtualization.
The mechanism combines processor hardware, translation data structures, and operating-system policy. Hardware translates addresses and checks permissions; the operating system establishes mappings, handles faults, and decides which contents should remain resident. Its performance depends not only on available RAM but also on translation caches, page sizes, access patterns, and the cost of reclaiming or retrieving pages.
Address spaces, pages, and frames
A program normally generates virtual addresses rather than directly selecting locations in physical memory. Each process can therefore have an address space whose layout is independent of the physical frames currently holding its instructions and data. The same numerical virtual address in two processes can refer to different physical locations. Conversely, different virtual addresses, whether within one process or across several processes, can refer to the same physical frame.
For a page size of bytes, a virtual address divides into a virtual page number and an offset:
The translation mechanism maps the virtual page number to a physical frame number, , while preserving the offset. The resulting physical address is
With 4 KiB pages, the low 12 address bits specify a byte within the page. For example, a 32-bit virtual address then contains a 20-bit page number and a 12-bit offset. The division is particularly convenient in binary hardware because extracting the fields requires bit selection rather than general integer division.
Fixed-size frames remove the requirement that a process occupy one contiguous physical region. If a process needs another ordinary page, the operating system can usually assign any suitable free frame. This avoids external fragmentation for base-page allocation: free frames do not need to be adjacent. It does not eliminate all fragmentation. The final page of an allocation can be only partly used, creating internal fragmentation, and a request for a physically contiguous large page can fail even when many smaller frames remain free.
Paging differs from segmentation, which divides an address space into variable-size logical regions, traditionally such as code, data, and stacks. A segment can have its own base, limit, and protection attributes, whereas ordinary page translation treats pages as equal-size units. Some architectures combine both schemes. On 32-bit x86, segmentation produces a linear address that paging subsequently translates; common operating systems largely flatten the segment layout and rely on paging for isolation and placement.
The page is a mapping and protection granularity, not necessarily an application’s allocation unit. A memory allocator can divide one page among many small objects or combine many pages into a large allocation. Similarly, a single machine instruction can access bytes on two pages, requiring both translations and their associated permission checks. Distinguishing virtual allocation, page mapping, and physical residency is essential: reserving an address range does not necessarily allocate physical frames, and allocating frames does not necessarily make them accessible to a particular process.
Page tables and translation structures
The operating system records mappings in a page table, a hardware-defined or software-managed data structure associated with an address space. A page-table entry commonly contains a physical frame number, a present or valid indication, access permissions, and memory attributes. Many architectures also provide accessed and dirty indicators, recording whether a mapping has been used and whether a write has occurred. The exact interpretation of these fields depends on the processor architecture.
A simple linear page table has one entry for every possible virtual page. Its storage cost is
where is the virtual-address width in bits, is the page size in bytes, and is the entry size in bytes. A 32-bit address space with 4 KiB pages and four-byte entries requires 4 MiB for a complete table. For a 48-bit virtual address space with 4 KiB pages and eight-byte entries, the corresponding flat table would occupy 512 GiB. Most applications use only a small fraction of such a large address space, making a fully populated linear representation wasteful.
Multilevel page tables address this problem by dividing the virtual page number into several indexes. An upper-level table points to lower-level tables, and the final entry identifies the frame. Missing subtrees represent large unmapped address ranges without requiring leaf entries for every page. This hierarchical organization resembles a fixed-depth tree. It reduces storage for sparse address spaces, although widely scattered mappings can still require many intermediate tables.
A common four-level x86-64 arrangement divides a 48-bit virtual address into four nine-bit indexes and a 12-bit offset. Each table contains 512 eight-byte entries and occupies one 4 KiB page. A conventional 48-bit implementation requires the upper address bits of a 64-bit pointer to extend bit 47 appropriately; not all 64-bit bit patterns are valid virtual addresses. Five-level x86 paging extends the translated virtual-address width to 57 bits. These are architectural examples rather than universal page-table formats.
Some designs use hashed or inverted page tables. An inverted table organizes information around physical frames rather than providing an ordinary leaf entry for every mapped virtual page. Hashed schemes use an address-space identifier and virtual page number to locate candidate mappings. Such designs can reduce certain storage costs but require different lookup and sharing mechanisms. The choice depends on address-space size, hardware support, and expected workloads.
Page-table memory is itself part of the system’s physical-memory consumption. Creating a sparse mapping may require allocating intermediate tables before allocating or attaching a data page. Updating entries also requires coordination with concurrent execution: a processor must not use a half-initialized entry, and a table page cannot be freed while hardware or another processor could still be traversing it.
Translation caches and address-translation costs
Looking up every address through several page-table levels would add substantial work to ordinary memory access. Processors therefore cache recent translations in a translation lookaside buffer (TLB). A TLB entry associates a virtual page, usually together with an address-space identifier, with a physical frame and relevant permissions. On a hit, the processor can obtain the translation without repeating the full table walk.
A TLB miss is not the same event as a page fault. The required mapping may already be valid in the page tables, in which case hardware can walk the tables and refill the TLB without entering the operating system. Other architectures use software-managed TLBs: a miss transfers control to privileged code that finds and installs the translation. A page fault instead indicates that the requested access cannot proceed under the current translation state, for example because the page is absent or a write is prohibited.
Processors commonly have separate first-level instruction and data TLBs, with additional shared translation capacity at later levels. They may also cache intermediate page-table information. Page-table entries can benefit from the ordinary CPU cache hierarchy, so a four-level walk does not necessarily require four accesses to main memory. Out-of-order execution can overlap some translation activity with other work, although dependencies and permission checks constrain that overlap.
A simplified model expresses average translation overhead as
where is the TLB hit rate and is the additional cost of a miss. This model omits overlapping execution, multiple TLB levels, page-walk caches, and cache-access timing, but captures why translation locality matters. TLB reach is the amount of memory represented by cached translations. For entries each mapping pages of size , its nominal value is , though associativity and competition can reduce effective coverage.
Changing a page-table entry does not automatically remove every cached copy of its old translation. Before reusing a frame or relying on revoked permissions, the operating system must invalidate affected translations according to the architecture’s rules. In a multiprocessor system, this can require a TLB shootdown: one processor requests that other processors invalidate relevant entries and waits for the required synchronization. Frequent unmapping or permission changes can therefore incur costs well beyond the table update itself.
Address-space identifiers allow entries from several processes to coexist in the TLB without confusing identical virtual addresses. x86 process-context identifiers and other architectures’ ASIDs serve this general purpose. They can reduce the need to flush translations during a context switch, but the identifier space is finite. Reusing an identifier requires care to prevent an old translation from being mistaken for a mapping in a new address space.
Demand paging and page-fault handling
Demand paging makes page contents available when they are first required rather than loading an entire program or data region in advance. An operating system can establish the logical description of an address range while leaving its individual pages without resident frames. On the first access, the processor raises a page fault, allowing the operating system to determine whether the access is legitimate and how the page should be supplied.
A fault handler first identifies the faulting address and access type, then checks the process’s memory-region metadata. If the address belongs to a valid region, the handler may allocate a zero-filled frame, attach a page already present in a file cache, retrieve data from secondary storage, or perform a copy required by a write. If the address is outside permitted regions, or the requested operation violates an unresolvable protection restriction, the operating system reports an access error to the process. On Unix-like systems this can result in signals such as SIGSEGV or, for certain mapped-file failures, SIGBUS.
Anonymous memory illustrates why a page fault need not perform storage input/output. Newly allocated private memory must not reveal data left by another process. The system can satisfy the first access with a freshly zeroed frame, or initially map a shared read-only zero page and allocate a private frame only on a write. Both techniques can create faults without reading a disk. Similarly, a mapped file page may already be in RAM because another process or an earlier operation brought it into the page cache.
Faults are often classified as minor when they can be resolved without fetching the page from backing storage, and major when such input/output is required. Exact accounting differs among operating systems. A minor fault can still be expensive: it may require taking locks, allocating and clearing memory, updating tables, and invalidating translations. A major fault can additionally block the faulting thread until storage completes, while the scheduler runs another thread.
A schematic effective-access-time model is
where is the probability that a reference causes a fault. The model is deliberately simplified, but it highlights the disparity between ordinary memory access and fault handling. If a hypothetical storage-backed fault takes 1 millisecond while a resident access takes 100 nanoseconds, one such fault per 10,000 accesses contributes roughly another 100 nanoseconds per access on average.
Correct fault handling must account for concurrency. While one thread waits for data, another may unmap the region or resolve the same fault. The handler must recheck relevant state before installing a mapping. Once a recoverable fault is resolved, execution normally resumes so that the interrupted access can complete; precise restart behavior depends on the instruction set.
Page replacement, locality, and thrashing
When free physical frames become scarce, the operating system must reclaim memory. Page replacement selects which resident pages to remove or repurpose. The choice depends on whether pages are actively used, whether their contents can be reconstructed, whether they contain modifications that require preservation, and which process or memory group should bear the cost. Replacement is therefore both an algorithmic problem and a resource-allocation policy.
The theoretical optimal replacement rule evicts the page whose next use lies farthest in the future. Because ordinary systems cannot know future references, the rule serves as a benchmark rather than a general implementation. Least recently used replacement approximates future behavior through the assumption that recently used pages are likely to be used again. Exact LRU maintenance on every memory reference is usually too costly at page granularity, so systems commonly use approximations based on hardware access information and periodic scanning.
Clock-style algorithms arrange candidate pages in a circular sequence and examine a reference indicator. A recently referenced page receives another opportunity to remain resident; an unreferenced page becomes a candidate for eviction. More elaborate schemes maintain active and inactive sets or several age generations. Their purpose is not merely to count references but to distinguish recently useful memory from contents that occupy RAM without contributing to current execution.
Replacement algorithms can have counterintuitive properties. First-in, first-out replacement can suffer Bélády’s anomaly, in which adding frames increases the number of faults. For the reference sequence
FIFO incurs nine faults with three initially empty frames but ten with four. Algorithms with the stack property, including idealized LRU and optimal replacement, do not exhibit this anomaly under the standard demand-paging model: the pages held with fewer frames remain a subset of those held with more frames.
The working-set concept relates memory requirements to recent execution. A working set contains the pages referenced within a chosen window of recent activity. If the active working sets of running processes substantially exceed available frames, the system can enter thrashing: pages are repeatedly evicted and soon needed again, so fault handling and data movement dominate useful work. This is more severe than an isolated burst of faults during program startup.
Local replacement confines a process’s victims to its own allocation, while global replacement allows processes to compete for a broader pool. Real systems often combine global reclaim with per-process or group-level controls. Under severe pressure, they may reduce concurrency, compress eligible memory, or terminate selected workloads rather than continue ineffective reclamation indefinitely. The resulting behavior depends on protection priorities as well as reference patterns; a technically reclaimable page is not necessarily the most appropriate victim.
Backing storage, mapped files, and shared pages
Resident pages can have different kinds of backing. File-backed pages correspond to data in a file, including executable code and memory-mapped datasets. Anonymous pages hold contents such as private heaps and stacks without a directly corresponding ordinary file. A clean file-backed page can often be discarded because its contents can be reread. Modified anonymous data generally needs some other means of preservation before its frame can be reclaimed.
Swap space provides backing storage for eligible anonymous memory and related pageable contents. It may be implemented using a dedicated partition or a file, and some systems use compressed RAM as a storage tier for such pages. Paging to secondary storage should not be confused with the historical practice of swapping an entire process at once. Nor does enabling virtual memory imply that every page has a preassigned slot on disk.
Memory-mapped files connect paging with the file system. A process accesses file contents through ordinary load and store instructions after establishing a mapping. The kernel’s page cache can supply the same physical page to multiple mappings and, in many systems, to conventional file input/output as well. A fault may initiate a read of one page or trigger read-ahead of additional pages. Consequently, the page is a translation unit, but the storage system’s transfer unit need not be exactly one page.
A shared writable mapping allows updates to affect a common underlying object. A private mapping instead presents changes as private to the process, commonly using copy-on-write. Initially, processes can share read-only physical pages. When one attempts to modify a shared private page, a protection fault lets the operating system allocate a new frame, copy the contents, and redirect that process’s mapping. The other mappings retain the original contents.
Copy-on-write is especially important for process creation on Unix and related systems. After fork, parent and child can initially share much of their memory rather than immediately copying every resident page. Only pages subsequently modified need private copies. This can make a fork followed by loading another executable substantially cheaper than eagerly duplicating the original address space. The optimization nevertheless requires bookkeeping, and write-heavy workloads can later incur allocation and copying costs.
Dirty-page handling connects replacement to durability and storage scheduling. Modified shared file pages may be written back in the background to prevent long bursts of forced writeback during reclamation. A store through a mapping does not by itself imply that the change has reached persistent storage; synchronization and durability guarantees depend on operating-system interfaces, file-system behavior, and the storage device. Conversely, removing a virtual mapping need not evict the underlying page from the cache if other users or likely future accesses justify retaining it.
Page size, large pages, and memory placement
Page size determines several important trade-offs. Small pages permit fine-grained allocation, protection, and reclamation. They reduce the amount of unused space tied to a partly occupied page and avoid fetching or retaining large regions when only a few bytes are useful. Larger pages reduce the number of translations required for a given memory footprint and can reduce page-table storage and page-walk overhead.
A 1 GiB region mapped entirely with 4 KiB pages contains 262,144 pages. At eight bytes per leaf entry, the leaf entries alone occupy 2 MiB, excluding upper-level tables. Mapping the same aligned region with 2 MiB pages requires only 512 such mappings. Common x86-64 paging configurations support 4 KiB pages and 2 MiB large pages, and many processors also support 1 GiB pages. Other architectures provide different sizes and combinations; a 4 KiB base page is widespread but not universal.
Huge pages can substantially increase TLB reach for large, densely accessed memory regions. They are useful for workloads such as databases, scientific computing, and large in-memory services when translation overhead is significant. Their benefits are workload-dependent. If a program touches only a small portion of each large page, the system may retain much more physical memory than necessary. Large pages also make independent protection or reclamation of small subregions harder unless the mapping is split.
Physical contiguity is another constraint. A large page generally requires a suitably aligned, contiguous physical extent. A system with plenty of free memory can still lack an extent of the required size because allocated frames are interspersed with free ones. Memory compaction can move movable contents to consolidate free space, but moving pages consumes processor time and memory bandwidth and may require coordination with devices or pinned mappings.
Operating systems expose different large-page policies. Explicit mechanisms let applications request or reserve large-page memory. Transparent mechanisms attempt to build large mappings automatically and may later split them. On Linux, hugetlb facilities and transparent huge pages represent distinct management approaches. Their accounting, allocation guarantees, and interactions with reclaim differ, so “using huge pages” does not identify one uniform behavior.
Paging also interacts with non-uniform memory access (NUMA). A frame can reside in memory attached to one processor socket or locality domain, making access costs depend on which processor executes the thread. First-touch allocation often places memory near the processor that first faults it in, subject to system policy. Later migration can improve locality, but moving a large page may transfer many bytes that were not responsible for the placement problem. Page size therefore affects not only translation efficiency but also the granularity of physical-memory placement and adaptation.
Protection, virtualization, and device access
Page mappings are a principal enforcement point for memory isolation. Entries can distinguish readable, writable, executable, supervisor-only, and user-accessible memory, depending on the instruction set architecture. This lets an operating system protect its own code and data from ordinary applications and prevent one process from accessing another’s private frames. Read-only mappings can also catch unintended writes, while non-executable mappings restrict instruction fetching from data regions.
These controls operate at page granularity. Two objects sharing one page cannot ordinarily receive different page-table permissions without being separated into different pages or using an additional mechanism. Guard pages exploit this granularity deliberately: an inaccessible page placed next to a stack or allocation can turn certain out-of-bounds accesses into immediate faults. Such protection does not detect every buffer overflow, because an invalid access can remain within an otherwise accessible page.
Permission changes require the same attention to cached translations as changes of frame mapping. Marking an entry read-only in memory is insufficient if another processor can still use a cached writable translation. Correct implementation combines entry updates, ordering rules, invalidation, and synchronization. This is especially important for executable-memory transitions, copy-on-write, and revoking access before a frame is reassigned.
Virtualization introduces another translation boundary. In a virtual machine, guest software uses guest virtual addresses, while the guest operating system manages what it regards as physical memory. Hardware-assisted nested paging adds a mapping from guest physical addresses to host physical addresses. Intel’s Extended Page Tables and AMD’s Nested Page Tables implement this general arrangement. Both translation stages contribute permissions and can generate distinct classes of faults or exits.
Nested translation can make a TLB miss more expensive because guest page-table accesses themselves require translation through the second stage. Hardware caches combined translations and intermediate results to reduce this cost. An alternative approach, shadow page tables, has the hypervisor maintain mappings that directly express the effective guest-virtual-to-host-physical relationship. Shadowing avoids some nested-walk work but requires the hypervisor to track guest changes to memory-management state.
Devices introduce a related but separate problem. A device performing direct memory access does not necessarily use the processor’s ordinary page tables. An input–output memory management unit can translate device-visible addresses and restrict which physical pages a device may access. Without coordinated mapping and lifetime rules, a device could continue writing into a frame after the operating system repurposes it. Pinning pages prevents certain relocation or reclamation operations, but extensive pinning reduces the memory available for ordinary paging. Some modern platforms provide closer integration between processor and device address spaces, including device-side translation caches and mechanisms for reporting recoverable device memory faults.
Historical development and operating-system practice
Paging emerged from attempts to make programs less dependent on the limited capacity and detailed organization of early main memory. Before automatic virtual-memory systems, programmers often used overlays: explicitly arranged program portions that occupied the same memory region at different times. Overlays could support programs larger than available RAM, but their organization placed substantial responsibility on programmers and language tools.
The University of Manchester’s Atlas computer, brought into service in 1962, was a landmark in automatic virtual storage. Developed with Ferranti and associated with Tom Kilburn and his colleagues, Atlas used a “one-level store” that made core memory and drum storage appear through a unified programming model. Its paging machinery transferred fixed-size blocks between storage levels, while the Atlas Supervisor managed their use. This established an influential practical example of hardware and system software cooperating to hide physical-memory limitations.
During the 1960s, virtual-memory systems became an important subject of both engineering and theory. IBM’s System/360 Model 67 provided dynamic address translation and supported work on systems including CP-67. The subsequent VM/370 system, announced in 1972, helped establish virtualization on mainframes. Multics combined segmentation and paging, using segments as named logical objects while bringing their contents into memory in pages. These systems demonstrated that address translation could support sharing and protection as well as capacity extension.
Research clarified the relationship between paging and program behavior. László Bélády’s 1966 work on replacement algorithms supplied a major theoretical reference point, including the optimal replacement benchmark. Peter Denning’s 1968 working-set paper connected recent reference behavior to memory demand and process scheduling. Such work helped explain why simply increasing multiprogramming could reduce useful throughput when active memory demands exceeded available frames.
Paging later became standard in general-purpose microprocessor systems as address-translation hardware became widely available. The Intel 80386, introduced in 1985, added paged memory management to the 32-bit x86 architecture. Unix-derived systems, Microsoft Windows, and other general-purpose operating systems built increasingly elaborate virtual-memory facilities around hardware paging. The transition to 64-bit systems expanded practical address spaces and increased the importance of sparse multilevel tables and translation-cache efficiency.
Contemporary systems retain the same basic page-to-frame abstraction while varying widely in policy. Desktop and server systems commonly combine demand paging, file caching, shared mappings, copy-on-write, and storage-backed reclamation. Mobile systems may rely heavily on compressed memory and process-lifecycle management rather than conventional disk swap. A real-time operating system may restrict or avoid demand paging for time-critical execution because an unpredictable fault conflicts with bounded response times. Across these implementations, paging remains a mechanism whose guarantees depend on the surrounding allocation, residency, and scheduling policies.