Virtual Memory

Virtual Memory Concept

Virtual memory allows processes to use more address space than physical RAM by storing pages on disk and loading them on demand. Only referenced pages need to be in memory.

Benefits: - Process address space can exceed physical RAM - Processes isolated from each other - Programs start faster (only needed pages loaded) - Pages can be shared (e.g., shared libraries mapped at same virtual address)

Demand Paging

Pages are loaded from disk only when accessed. A page not in memory has its present bit (P) cleared in the PTE.

Page Fault Handling

CPU accesses virtual address
  → MMU checks PTE: P = 0 → page fault (trap to OS)
  → OS fault handler:
     1. Verify access is valid (legal VA, correct permissions)
     2. Find a free frame (or evict one)
     3. Read page from disk (swap space or file) → frame
     4. Update PTE: set frame #, set P=1
     5. Restart faulting instruction
  → CPU re-executes; this time: TLB miss → page table hit → success

Page fault penalty (disk): ~5–10 ms → millions of CPU cycles. Even a 0.1% fault rate can slow execution by 40×.

Page Replacement Algorithms

When all frames are occupied and a new page must be loaded, a victim page is chosen.

FIFO (First-In First-Out)

Evict the page that has been in memory the longest.

Belady's anomaly: adding more frames can increase page faults with FIFO.

Optimal (OPT / MIN)

Evict the page that will not be used for the longest time in the future. Theoretical minimum fault rate — used as benchmark only (requires future knowledge).

LRU (Least Recently Used)

Evict the page least recently accessed. Good approximation of OPT.

Implementations: - Counter: timestamp every access; evict lowest counter — O(n) scan - Stack: move referenced page to top; evict bottom — O(1) with doubly-linked list - Approximate LRU (clock / second-chance): use the Access bit in PTEs

Clock / Second-Chance Algorithm

Pages in a circular list with a "hand":

On fault:
  inspect page at hand:
    A=1 → set A=0, advance hand (give second chance)
    A=0 → evict this page, advance hand

Enhanced clock: consider (A, D) — prefer (0,0) → evict; (0,1) → write back then evict later; (1,0) → clear A; (1,1) → clear A.

Algorithm Comparison

Numerical Example (LRU vs FIFO, 3 frames)

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2

LRU: 9 faults. FIFO: 10 faults (for this string). FIFO faults at t=7 (ref 0) because 0 — despite the hit at t=5 — is the oldest loaded page and was evicted at t=6; LRU keeps it because recency, not load order, decides the victim.

Frame Allocation

Fixed vs Priority Allocation

Global vs Local Replacement

Thrashing

Thrashing occurs when a process (or system) spends more time paging than executing.

Cause: too many processes compete for too few frames; working sets don't fit in memory.

frames per process decrease
→ more page faults
→ process waits for disk
→ CPU scheduler runs more processes
→ even fewer frames each
→ faults increase further (cycle)

Working Set Model

Working set W(t, Δ) = set of pages referenced in the window [t−Δ, t].

• Δ = working set window (number of references)
• Allocate enough frames to hold each process's working set
• If ∑|WSᵢ| > total frames → suspend lowest-priority process

Page Fault Frequency (PFF) Control

Memory-Mapped Files

Map file content directly into virtual address space. Reads/writes go to memory; OS pages data in/out.

int fd = open("data.bin", O_RDWR);
struct stat st;
fstat(fd, &st);
void *p = mmap(NULL, st.st_size, PROT_READ|PROT_WRITE,
               MAP_SHARED, fd, 0);
// Access p[i] like an array; OS handles I/O
msync(p, st.st_size, MS_SYNC);   // flush to disk
munmap(p, st.st_size);

Copy-on-Write (CoW)

On fork(), parent and child initially share the same frames — both marked read-only. On the first write by either:

1. Page fault → OS detects CoW bit
2. OS copies the page to a new frame
3. Both PTEs updated: each points to own copy, now writable

Benefit: fork() + exec() is nearly free — child immediately replaces its address space.

Huge Pages (Large Pages)

Benefits: fewer TLB entries, less TLB pressure, lower page table overhead. Linux: Transparent Huge Pages (THP) auto-promotes eligible 4 KB ranges; madvise(ptr, len, MADV_HUGEPAGE) to hint.

Swap Space

Disk area where evicted pages are stored (Linux: swap partition or swap file).

swap usage = Σ(process virtual size) − Σ(resident set size)

• Swapping an entire process out/in = medium-term scheduling
• On Linux, anonymous pages (heap/stack) go to swap; file-backed pages go back to the file