Paging: Basic Concept

Paging is a memory management scheme that permits a process's physical address space to be non-contiguous by partitioning memory into fixed-size blocks. The virtual (logical) address space of a process is divided into equal-sized units called pages; physical memory is divided into blocks of the identical size called frames. A page and a frame are always the same size, typically a power of two such as 4 KiB, and this size is fixed by the hardware's memory management unit (MMU), not chosen freely by the operating system for each process. Every virtual address a program generates is really a pair, even though the programmer writes it as a single number. Let the page size be $2^d$ bytes, so $d$ bits are needed to name a byte within a page (this is the offset, sometimes called the displacement). The remaining high-order bits of the virtual address name which page is being referenced — this is the page number $p$. So an $m$-bit virtual address decomposes as:

Because $d$ is fixed by the page size, this split requires no arithmetic at all — it is a pure bit-slice. The operating system maintains, for each process, a mapping from page number $p$ to frame number $f$ (the mechanism that stores this mapping is the The Page Table, covered separately). Translation replaces $p$ with $f$ and leaves $d$ untouched, since the offset within a page is identical to the offset within the frame that holds it:

The crucial structural property is that pages and frames are the same size. This is what distinguishes paging from Segmentation, where segments have logically meaningful but variable sizes (a code segment, a stack segment) and therefore require a variable-sized free-space allocator prone to external fragmentation, exactly as in Contiguous Memory Allocation. With paging, any free frame is a valid destination for any page — there is no notion of a frame being "the wrong shape." The operating system need only track which frames are free, typically with a simple bitmap or free list, and hand any of them out.

The mechanism has two independent parts: how the operating system tracks free frames and assigns them to a process's pages, and how the hardware translates an address at run time using the resulting mapping.

Step 1 — allocation at process load/growth time. When a process is created or grows, the operating system computes how many pages it needs and finds that many free frames anywhere in physical memory (they need not be adjacent). It records the page-to-frame assignment. Any free frame will do, so a simple free-frame list suffices — no best-fit or worst-fit search is needed, unlike contiguous allocation.

Step 2 — address translation at run time. Every memory reference a running instruction makes — for an instruction fetch, a load, or a store — is a virtual address that the MMU must translate before the memory bus is touched. The translation is a table lookup (page number → frame number) followed by a concatenation, not a computation: ``` function TRANSLATE(virtual_address, page_size_bits, page_table): d = page_size_bits # number of offset bits p = virtual_address >> d # page number: top bits offset = virtual_address AND ((1 << d) - 1) # offset: bottom d bits if p >= length(page_table): raise SEGMENTATION_FAULT # page number outside process's table entry = page_table[p] if not entry.valid: raise PAGE_FAULT # page not currently mapped/resident f = entry.frame_number physical_address = (f << d) OR offset return physical_address ``` ``` function ALLOCATE_PAGES(process, num_pages_needed, free_frame_list): if length(free_frame_list) < num_pages_needed: raise OUT_OF_MEMORY page_table = new array of size num_pages_needed for p in 0 .. num_pages_needed - 1: f = free_frame_list.remove_any() # any free frame — order irrelevant page_table[p] = { frame_number: f, valid: true } process.page_table = page_table return page_table ``` Three properties of `TRANSLATE` deserve emphasis. First, splitting the address into $p$ and $d$ is a bit-shift and a bit-mask — $O(1)$ hardware operations with no search. Second, the lookup `page_table[p]` is a direct array index, not a search through a free-list of variable-sized holes — this is what makes paging's bookkeeping cheap compared to contiguous allocation's coalescing and best/worst-fit scans. Third, `offset` is copied verbatim; the hardware never needs to touch or reinterpret the low-order bits, which is only correct because pages and frames share the identical size $2^d$.

Time complexity of translation. Splitting the virtual address into $p$ and $d$ is a shift and a mask: $O(1)$ regardless of address-space size or number of pages, because $d$ is a compile-time hardware constant. Looking up `page_table[p]` is a direct array index — $O(1)$ time — because the page table is indexed by $p$ itself, not searched. (In practice, real page tables are multi-level structures for space reasons, which changes lookup to $O(k)$ for $k$ levels; that refinement belongs to The Page Table and does not affect the basic single-level model analyzed here.) Reassembling the physical address is another shift-and-OR, $O(1)$. So end-to-end translation is $O(1)$ per memory reference under the basic flat-table model — a sharp contrast to searching a free list of variable-sized holes in contiguous allocation, which is $O(n)$ in the number of free holes for best-fit or worst-fit search.

Space complexity. A single-level page table needs one entry per page in the virtual address space, so its size is $\Theta\!\left(\dfrac{2^m}{2^d}\right)$ entries, where $m$ is the number of virtual address bits and $d$ the page-offset bits. This is the classic space cost paging must pay for its $O(1)$ translation: the table must have a slot for every possible page, even unused ones, unless sparsified — again a concern deferred to The Page Table.

Correctness argument — no external fragmentation. Define external fragmentation as the situation where the total free physical memory is enough to satisfy a request, but no single contiguous region is large enough. Claim: paging cannot suffer from this. Proof sketch: a process's memory need is expressed as some number of pages, $\lceil \text{size}/2^d \rceil$. Satisfying this need requires exactly that many free frames, each independently sized $2^d$ — with no requirement that they be adjacent, since the page table can map any page to any frame. Therefore the allocator's obligation reduces to counting free frames, not searching for a contiguous run of them:

Since this condition depends only on the count of free frames and not their spatial arrangement, no distribution of free frames can cause a failure when enough total free space exists. This is exactly the guarantee external-fragmentation-prone contiguous allocation lacks. $\blacksquare$

The tradeoff — internal fragmentation persists. Paging does not eliminate all fragmentation. Because allocation happens in whole-page units, a process requesting size $s$ bytes is rounded up to $\lceil s/2^d \rceil$ pages, and the last page is typically only partially used. The wasted space per process is bounded:

i.e., strictly less than one page size, and on average about half a page per process (assuming sizes are uniformly distributed within a page). Choosing a small page size shrinks this waste but grows the page table (more entries) and can hurt performance elsewhere (more entries to cache, more translation overhead amortized over less data per page) — a tension that motivates hardware caching mechanisms like the Translation Lookaside Buffer discussed elsewhere. Paging trades a fragmentation problem that is unbounded and unpredictable (external) for one that is small and bounded (internal) — a strictly better worst case.

Consider a system with a 16-bit virtual address space (so $m = 16$, giving $2^{16} = 65536$ bytes of addressable virtual space) and a page size of $2^{12} = 4096$ bytes, so $d = 12$ offset bits and $m - d = 4$ page-number bits, meaning up to $2^4 = 16$ pages per process. Physical memory has 10 frames of 4096 bytes each (40 KB total), numbered 0–9. Suppose the operating system has already given this process the mapping shown in the figure above:

Now trace the translation of virtual address `0x3A17` (hexadecimal), which in binary is: ``` 0x3A17 = 0011 1010 0001 0111 (16 bits) \__/\____________/ p d ``` Splitting at $d = 12$ bits from the right:

• Top 4 bits: `0011` = decimal 3 → this is the page number $p$.
• Bottom 12 bits: `1010 0001 0111` = hexadecimal `0xA17` = decimal 2583 → this is the offset.

Look up page 3 in the table: frame $f = 5$. The offset is copied unchanged. The physical address is formed by concatenating frame 5's bits with the offset: ``` physical address = (5 << 12) | 0xA17 = 0x5000 | 0xA17 = 0x5A17 ``` So virtual address `0x3A17` (which the process believes lives near the start of its address space, in its logical page 3) actually resides at byte `0x5A17` in physical memory — inside physical frame 5, which the operating system happened to place far from frames 7, 2, and 9 that hold the process's other pages. The process's four pages are scattered across frames 7, 2, 9, 5 — utterly non-contiguous physically — yet the process's own view of memory (pages 0, 1, 2, 3 in order) remains perfectly linear and contiguous. This is the entire payoff of paging in one trace: the illusion of contiguity is preserved for the program, while the operating system is free to place frames wherever they happen to be available. Now trace a failing case: virtual address `0x4000` has binary page-number bits `0100` = decimal 4. The page table shows page 4 is invalid (this process never requested a fifth page), so `TRANSLATE` raises a page fault — correctly, since this address lies outside the process's allocated space, even though it lies inside the 16-bit address range in principle.

Paging emerged from the practical crisis of running large programs on machines with far less physical memory than programs demanded, and from the parallel need to protect processes from each other on shared machines. The Atlas computer at the University of Manchester is widely credited as the first system to implement paging as a mechanism for automatic, hardware-assisted virtual memory, aiming to give programmers the illusion of a large uniform store built from a small fast core and slower drum storage.

Every modern general-purpose operating system kernel — Linux, the Windows NT kernel, XNU underlying macOS and iOS, and the Linux-derived Android kernel — uses paging as the foundation of its virtual memory subsystem. Processor architectures build dedicated hardware for it: the MMU on x86, ARM, and RISC-V chips performs the page-number-to-frame translation directly in silicon so that ordinary loads and stores are not slowed to software speed. Hypervisors extend the same idea one level deeper with nested/extended page tables, translating guest-physical addresses to host-physical addresses so multiple virtual machines can share physical RAM without contiguous-allocation fragmentation between VMs. Database systems and language runtimes with custom memory managers (garbage collectors, `mmap`-based allocators) rely on the operating system's paging layer to back their own heaps with physical memory on demand rather than requiring a single giant contiguous block up front. Container runtimes such as Docker and Kubernetes depend on paging (via cgroups' memory accounting on top of the kernel's page-based allocator) to isolate and limit memory per container without requiring contiguous physical regions per container. Anywhere a system must run more logical memory than it has physical memory, or must isolate many independent address spaces on shared hardware, the fixed-size, arbitrarily-placeable unit that paging introduces is the load-bearing idea underneath.

Ask the tutor: How does a multi-level page table shrink the space cost of storing translations for a sparse address space?