Introduction
Paging is a memory management scheme that eliminates the need for contiguous allocation by dividing a process's logical address space into fixed-size blocks called pages, and dividing physical memory into equally sized blocks called frames. Any page can be placed in any free frame, anywhere in physical memory, so a process no longer needs one unbroken chunk of RAM. This completely removes external fragmentation, at the cost of a small amount of internal fragmentation in the last, partially used page of a process.
Cricket analogy: Paging is like splitting a squad's accommodation into identical fixed-size hotel rooms that any player can occupy in any hotel, rather than needing one giant house for the whole team — this eliminates the problem of finding one huge contiguous venue, though the last room might have a spare unused bed (internal fragmentation).
Explanation
Every logical address generated by the CPU is split by hardware into two parts: a page number (p) and a page offset (d). If the page size is 2^n bytes, the low-order n bits of the address form the offset, and the remaining high-order bits form the page number. The page number indexes into a per-process page table maintained by the OS, which stores the frame number that page currently occupies. The MMU computes the physical address as (frame_number * page_size) + offset. Because looking up the page table in memory on every single access would double memory traffic, the hardware also keeps a Translation Lookaside Buffer (TLB): a small, fast, associative cache of recent page-number to frame-number mappings. A TLB hit gives the frame number in one cycle; a TLB miss requires a full page-table walk in memory, after which the mapping is cached in the TLB for next time.
Cricket analogy: Every scorecard reference splits into an innings number (page number) and a ball-within-over offset; the scorer's master ledger (page table) maps each innings to its physical scorebook page, and the scorer keeps a quick memory (TLB) of recently referenced innings so they don't have to flip through the whole ledger every time.
Example
#include <stdio.h>
#include <stdint.h>
#define PAGE_SIZE 4096u /* 4 KB pages -> 12 offset bits (2^12 = 4096) */
#define OFFSET_BITS 12u
typedef struct {
int valid;
unsigned int frame_number;
} PageTableEntry;
unsigned int translate(unsigned int logical_addr, PageTableEntry *page_table) {
unsigned int page_number = logical_addr >> OFFSET_BITS; /* high bits */
unsigned int offset = logical_addr & (PAGE_SIZE - 1); /* low 12 bits */
PageTableEntry entry = page_table[page_number];
if (!entry.valid) {
printf("Page fault: page %u is not in memory\n", page_number);
return 0xFFFFFFFF;
}
unsigned int physical_addr = (entry.frame_number * PAGE_SIZE) + offset;
printf("Logical 0x%08X -> page %u, offset 0x%03X\n", logical_addr, page_number, offset);
printf("Page %u maps to frame %u -> Physical 0x%08X\n", page_number, entry.frame_number, physical_addr);
return physical_addr;
}
int main(void) {
PageTableEntry page_table[2048] = {0};
page_table[1027].valid = 1;
page_table[1027].frame_number = 57; /* page 1027 -> frame 57 */
unsigned int logical_addr = 0x00403A9C; /* page 1027, offset 0xA9C (2716) */
translate(logical_addr, page_table);
return 0;
}Output
With 4 KB pages, the low 12 bits of any address are the offset, and the remaining bits are the page number. Logical address 0x00403A9C splits as offset = 0xA9C = 2716 (the last 3 hex digits) and page number = 0x403 = 1027 (the remaining hex digits). Since page_table[1027] maps to frame 57 (0x39 in hex), the physical address is frame_number * PAGE_SIZE + offset = 57 * 4096 + 2716 = 236188, which in hex is simply the frame number's hex digits followed by the offset's hex digits: 0x39000 + 0xA9C = 0x39A9C. This byte-for-byte concatenation trick works precisely because the page size is a power of two, which is why real systems always choose page sizes like 4 KB or 4096 = 2^12.
Cricket analogy: Just like a scorer computing a physical scorebook page by combining the innings number with the ball offset — innings 1027 mapping to physical scorebook 57, ball 2716 — the neat digit-concatenation trick works because the ball-count-per-over convention is a fixed power-of-two-like unit, mirroring how 4KB page sizes let hex digits simply concatenate.
Key Takeaways
- A logical address splits into a page number (high-order bits) and a page offset (low-order n bits, where page size = 2^n).
- The page table maps page numbers to frame numbers; physical_address = frame_number * page_size + offset.
- Paging eliminates external fragmentation entirely because any free frame can hold any page; it introduces at most (page_size - 1) bytes of internal fragmentation per process.
- The TLB is a hardware cache of recent page-table lookups; a TLB hit avoids an extra memory access, a TLB miss triggers a full page-table walk.
- Because page size is always a power of two, offset/page-number extraction is a simple bit-shift and bit-mask, not division or modulo.
Practice what you learned
1. With a page size of 4096 bytes, how many bits of a logical address are used as the page offset?
2. Given page size 4096 bytes, logical address 0x00403A9C, and page 1027 mapped to frame 57, what is the resulting physical address?
3. What does a TLB miss force the MMU to do?
4. Why does paging eliminate external fragmentation compared to contiguous allocation?
Was this page helpful?
You May Also Like
Memory Management Basics
How an OS tracks, allocates, and protects the memory used by processes running on a system.
Segmentation
Dividing a program's address space into variable-sized, logically meaningful segments such as code, stack, and heap.
Page Replacement Algorithms
How an OS decides which page to evict on a page fault when all frames are full, compared via FIFO, LRU, and Optimal.