📄 Paging
Paging divides memory into fixed-size pages. It eliminates external fragmentation and enables virtual memory through page tables and replacement algorithms.
Page Size, Number & Offset
Address Breakdown
Page Number (PN)
High-order bits of virtual address. Indexes into the page table to find the physical frame.
20 bitsOffset
Low-order bits. Specifies the exact byte within the page. Not translated — passed through directly.
12 bitsPage Size
Typical page size: 4KB. Larger pages = smaller page tables but more internal fragmentation.
4 KBPage Number (PN) — 20 bits | Offset — 12 bits
Multi-Level Page Tables
Problem: Huge Page Tables
32-bit address, 4KB pages → 2²⁰ PTEs (~4MB per process). 64-bit → exabyte-sized tables.
Multi-level tables: only allocate levels that are actually used. Sparse address spaces become efficient.
Levels (x86-64 example)
📱 Interactive: Page Replacement Simulator
Try It
Replacement Algorithms
FIFO
Evict the oldest-loaded page (first in, first out). Simple but suffers from Belady's anomaly.
LRU
Evict the least recently used page. Good performance but requires hardware support or costly timestamp tracking.
Optimal
Evict the page that won't be used for the longest time. Theoretical benchmark only (needs future knowledge).
Clock
Approximates LRU using a reference bit and circular scan. Efficient and practical — used in many real OS kernels.
Thrashing
What is Thrashing?
Signs of Thrashing:
- CPU utilization drops (CPU waiting on paging)
- Page fault rate skyrockets
- Disk I/O saturates (constant swap activity)
- System throughput approaches zero
Solutions:
Reduce degree of multiprogramming, increase RAM, use working set model, or implement page fault frequency control.
Code Example: Page Replacement
python
def fifo(pages, frames):
memory = []
faults = 0
for page in pages:
if page not in memory:
faults += 1
if len(memory) >= frames:
memory.pop(0) # evict oldest
memory.append(page)
return faults
def lru(pages, frames):
memory = []
faults = 0
for page in pages:
if page in memory:
memory.remove(page) # re-order: most recent at end
else:
faults += 1
if len(memory) >= frames:
memory.pop(0) # evict LRU (front)
memory.append(page)
return faults
# Optimal: evict page used furthest in future
def optimal(pages, frames):
memory = []
faults = 0
for i, page in enumerate(pages):
if page not in memory:
faults += 1
if len(memory) >= frames:
future = pages[i+1:]
# evict page with furthest next use (or none)
evict = max(memory, key=lambda p: future.index(p) if p in future else float('inf'))
memory.remove(evict)
memory.append(page)
return faultsInterview Questions
What is the difference between paging and segmentation?
Paging divides memory into fixed-size pages (e.g., 4KB). No external fragmentation but internal fragmentation possible. Segmentation divides memory into variable-sized logical segments (code, data, stack). No internal fragmentation but suffers from external fragmentation. Many systems combine both (seg-paged).
Explain Belady's Anomaly.
Belady's Anomaly occurs in FIFO page replacement: increasing the number of page frames can paradoxically increase the number of page faults. Example: reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames has 9 faults, but with 4 frames has 10 faults. LRU and Optimal do not suffer from this anomaly (they satisfy the stack property).
How does the Clock (Second Chance) algorithm work?
Clock arranges pages in a circular list with a reference bit. When a page must be evicted: scan clockwise. If reference bit = 0, evict this page. If reference bit = 1, clear it to 0 and move to next. This approximates LRU without the cost of timestamps. Used in Linux, BSD, and many other OS kernels.
What is thrashing and how do you prevent it?
Thrashing = excessive paging that degrades throughput to near zero. Prevention: use a working set model (track the set of pages a process is actively using), employ page fault frequency control (if fault rate exceeds threshold, allocate more frames or suspend a process), and manage the degree of multiprogramming to ensure total working set fits in RAM.