Paging in operating system design is a memory management technique that splits memory into fixed-size blocks. A process’s memory is divided into pages, and physical RAM is divided into frames of the same size. The OS can place any page into any free frame, so a process no longer needs one large continuous block of RAM.
This guide explains how address translation works, what page tables and the TLB do, how demand paging and page faults work, and how page replacement algorithms choose which page to remove.
Why paging exists
Early systems gave each process one contiguous region of memory. Over time, free memory broke into small gaps that were too small to use. This is external fragmentation. Paging removes it, because any free frame can hold any page. The trade-off is a small amount of internal fragmentation: the last page of a process may not be completely full.
How address translation works
The CPU generates a logical (virtual) address. The memory management unit (MMU) splits it into two parts:
- page number: which page of the process;
- offset: the position inside that page.
The MMU looks up the page number in the process’s page table, finds the frame number and adds the offset. The result is the physical address.
Example: with 4 KB pages (4,096 bytes), the logical address 0x3A7F has page number 3 and offset 0xA7F. If the page table maps page 3 to frame 9, the physical address is 9 × 4,096 + 0xA7F = 0x9A7F.
Page tables and the TLB
Each process has its own page table. Besides the frame number, each entry holds flags, such as:
- valid/present: the page is in RAM;
- read/write: whether writes are allowed;
- user/supervisor: whether user code may access it;
- dirty: the page changed since it was loaded;
- accessed: the page was recently used.
Looking up the page table for every memory access would be slow. Therefore, CPUs cache recent translations in a translation lookaside buffer (TLB). Most accesses hit the TLB, so translation adds little delay. On 64-bit systems, page tables have several levels, such as four or five on x86-64, to save memory.
Demand paging and page faults
With demand paging, the OS loads a page only when a process first uses it. When a process touches a page that is not in RAM, the CPU raises a page fault. The OS then:
- checks that the access is legal;
- finds a free frame, or frees one with a replacement algorithm;
- reads the page from disk or swap;
- updates the page table;
- restarts the instruction.
Page faults are normal, but too many of them cause thrashing: the system spends more time swapping pages than doing useful work.
Page replacement algorithms
When RAM is full, the OS must choose a page to evict.
| Algorithm | Rule | Notes |
|---|---|---|
| FIFO | Remove the oldest loaded page | Simple, but can remove busy pages |
| LRU | Remove the least recently used page | Good in practice; costly to track exactly |
| Optimal | Remove the page used furthest in the future | Best possible, but needs knowledge of the future |
| Clock (second chance) | Like FIFO, but skips pages with the accessed bit set | Cheap approximation of LRU |
Example: with three frames and the reference string 1, 2, 3, 1, 4, 2, 5, FIFO causes 5 page faults, LRU causes 6 and Optimal causes 5. So, LRU is usually good, but not always the best for every pattern.
Real operating systems use variants. For instance, Linux uses active and inactive page lists and, in newer kernels, multi-generational LRU.
Paging vs segmentation
| Paging | Segmentation |
|---|---|
| Fixed-size pages | Variable-size segments, such as code, stack and data |
| No external fragmentation | External fragmentation possible |
| Invisible to the programmer | Matches the program’s logical structure |
Modern x86-64 systems rely almost entirely on paging.
Related guides
Sources
Running Linux servers in production? Our Linux server hardening & security audit checks configuration, patching, SSH and logging. You can also use our free Linux server hardening checklist, or contact us.
Pingback: Virtual Memory - Youngster Company