Memory Management: Paging, Segmentation, and Page Replacement

Physical memory is finite and shared, yet every process is written as if it owns a clean, contiguous address space. The memory-management unit and the OS conspire to make that illusion real. This article covers paging, segmentation, address translation, and the page-replacement algorithms interviewers ask you to trace.

Why not just hand out physical memory?

Give each process raw physical addresses and you get three problems: processes can read and clobber each other (no protection), a process must be loaded into one contiguous physical block (external fragmentation), and code compiled for address 0 cannot be relocated. Virtual memory solves all three by giving each process its own virtual address space and translating on every access.

Paging

Paging divides the virtual address space into fixed-size pages and physical memory into equal-size frames (commonly 4 KB). Any virtual page can map to any physical frame, so a process need not be contiguous in RAM. This eliminates external fragmentation entirely; the only waste is internal fragmentation — the unused tail of the last page.

Address translation

A virtual address splits into a page number and an offset. The page number indexes the page table to find the frame number; the offset is appended unchanged:

virtual address = [ page number | offset ]
physical address = [ frame number | offset ]

frame = pageTable[pageNumber].frame
physical = frame * pageSize + offset

Worked example: a system with a 16-bit virtual address and 4 KB pages uses the low 12 bits for the offset (2^12 = 4096) and the top 4 bits for the page number (16 pages). Virtual address 0x1ABC → page 1, offset 0xABC. If page 1 maps to frame 7, the physical address is 7 * 4096 + 0xABC = 0x7ABC.

Each page-table entry (PTE) also carries control bits: valid/present, read/write/execute permissions, dirty (modified since load), accessed/referenced (used by replacement algorithms), and a user/supervisor bit.

The page-table size problem

A single flat page table for a 32-bit space with 4 KB pages needs 2^20 entries — about 4 MB per process, and vastly more for 64-bit. Solutions:

• Multilevel (hierarchical) page tables: page the page table itself; only populate sub-tables that are actually used (x86-64 uses 4 levels).
• Inverted page table: one entry per physical frame instead of per virtual page — size scales with RAM, not with address-space size.

Segmentation

Segmentation divides memory by logical unit — code, stack, heap, a specific data structure — into variable-length segments. An address is [ segment number | offset ], and a segment table gives each segment a base and limit (for bounds checking).

Segmentation matches how programmers think and simplifies sharing and protection at the module level, but variable-length segments reintroduce external fragmentation. Modern systems often combine both: paged segmentation, where each segment is itself paged, capturing segmentation's logical grouping without its fragmentation.

| Aspect | Paging | Segmentation | |--------|--------|--------------| | Unit size | Fixed (page/frame) | Variable (logical segment) | | Divided by | OS, transparent | Programmer's logical view | | Fragmentation | Internal only | External | | Address form | page # + offset | segment # + offset | | Sharing/protection | Per page | Natural per segment |

Page replacement

When a needed page is not resident and all frames are full, the OS must evict a resident page to make room. The page-replacement algorithm chooses the victim, and its goal is to minimize page faults. Step through FIFO, LRU, and Optimal on the same reference string below:

FIFO

Evict the page that has been in memory longest, regardless of use. Simple to implement with a queue, but it can evict a hot page just because it arrived early.

Bélády's anomaly: with FIFO, adding more frames can increase page faults — a deeply counterintuitive result that appears in interviews. The reference string 1,2,3,4,1,2,5,1,2,3,4,5 produces more faults with 4 frames than with 3. Stack-based algorithms (LRU, Optimal) never suffer this.

LRU (Least Recently Used)

Evict the page not used for the longest time, betting that the recent past predicts the near future. LRU is a strong approximation of Optimal and immune to Bélády's anomaly, but exact LRU is expensive: it needs a timestamp or a moved-to-front list on every memory access. Practical systems approximate it.

• Clock (second-chance): frames sit in a circular list; each has a reference bit set by hardware on access. The clock hand sweeps: if the bit is 1, clear it and give a second chance; if 0, evict. This gives near-LRU quality with O(1) hardware cost.

Optimal (OPT / Bélády's)

Evict the page whose next use is farthest in the future. OPT yields the minimum possible faults but is unrealizable — it requires knowing the future. It exists as a benchmark: measure real algorithms against OPT to judge how close they get.

| Algorithm | Rule | Bélády's anomaly? | Practicality | |-----------|------|-------------------|--------------| | FIFO | Evict oldest-loaded | Yes | Simple, weak | | LRU | Evict least-recently-used | No | Great, costly exactly | | Clock | Second-chance via ref bit | No | LRU approximation, cheap | | Optimal | Evict farthest-future use | No | Benchmark only |

Frame allocation

How many frames does each process get? Equal allocation splits frames evenly; proportional allocation gives more to larger processes. Replacement scope matters too: local replacement evicts only from the faulting process's own frames (stable behavior), while global replacement can steal a frame from any process (better utilization but one greedy process can hurt others).

Common follow-ups and gotchas

• "Paging vs segmentation in one line?" Paging is fixed-size and OS-transparent (internal fragmentation); segmentation is variable-size and programmer-visible (external fragmentation).
• "Does paging cause external fragmentation?" No — fixed frames make any free frame usable. It causes only internal fragmentation in the last page.
• Bélády's anomaly applies to FIFO, not to LRU or OPT. Naming it and the fact that stack algorithms avoid it is a strong signal.
• Dirty bit optimization: on eviction, a clean page can be dropped instantly; only a dirty page must be written back to disk, so replacement often prefers clean victims.
• Don't confuse the page table with the TLB: the page table lives in memory; the TLB is a small cache of recent translations (covered in the virtual-memory article).