Memory Management

5.1 Contiguous Memory Allocation

Fixed partitioning. Memory divided into fixed-size partitions at boot. Internal fragmentation.

Variable partitioning. Partitions created dynamically. External fragmentation.

Allocation strategies:

Theorem 5.1. First-fit and best-fit have roughly equivalent utilisation; first-fit is faster.

5.2 Paging

Divide physical memory into fixed-size frames and logical memory into same-size pages. A page table maps page numbers to frame numbers.

$\mathrm{physical} address = \mathrm{PT}[p] \times F + f$

Where $\mathrm{PT}[p]$ is the frame number for page $p$ and $F$ is the frame size.

Page table entry fields:

Multi-level page tables. A single page table for a 64-bit address space is infeasible. A Two-level scheme uses a page directory indexed by the outer page number, pointing to inner Page tables:

$\mathrm{Address}: \underbrace{p_1}_{\mathrm{outer} \mid \underbrace{p_2}_{\mathrm{inner} \mid \underbrace{d}_{\mathrm{offset}}}}$

X86-64 with 48-bit virtual addresses uses four-level page tables.

Inverted page table. One entry per physical frame (not per virtual page). Reduces memory Overhead but makes searching for a specific virtual page expensive; solved by hashing.

5.3 Segmentation

Segments divide the address space into logical units (code, data, stack, heap). Each segment has a base and limit:

$\mathrm{physical} address = \mathrm{base} + \mathrm{offset}, \quad \mathrm{if} \mathrm{offset} \lt \mathrm{limit}$

Advantages: Reflects program structure; supports sharing individual segments. Disadvantages: External fragmentation (variable-size segments).

5.4 Segmented Paging

Combine segmentation and paging: the segment offset is divided into page number and page offset.

$\mathrm{Address}: \underbrace{s}_{\mathrm{segment} \mid \underbrace{p}_{\mathrm{page} \mid \underbrace{d}_{\mathrm{offset}}}}$

Used by x86 (segmentation + paging).

5.5 Virtual Memory

Virtual memory allows processes to use more memory than physically available by keeping only active Pages in RAM; the rest reside on disk (swap space).

Demand paging. Pages loaded on access, not at process start.

Page fault handling:

1. CPU generates logical address; page table entry has valid bit = 0.
2. Trap to OS page fault handler.
3. Find a free frame (possibly evicting a victim page).
4. Read the page from disk into the frame.
5. Update page table entry (valid bit = 1, frame number).
6. Restart the faulting instruction.

Effective access time (EAT):

$\mathrm{EAT} = (1 - p) \times \mathrm{ma} + p \times \mathrm{pf}$

Where $p$ = page fault rate, $\mathrm{ma}$ = memory access time, $\mathrm{pf}$ = page fault service Time.

For $p = 0.001$, $\mathrm{ma} = 100$ ns, $\mathrm{pf} = 8$ ms:

$\mathrm{EAT} = 0.999 \times 100 + 0.001 \times 8\,000\,000 = 8.1 \; \mu\mathrm{s}$

This is roughly $80\times$ slower than pure memory access, illustrating why a low page fault rate Is critical.

5.6 Translation Lookaside Buffer (TLB)

A TLB is a hardware cache of recently used page table entries, avoiding an extra memory access Per translation.

$\mathrm{EAT} = h \times (\mathrm{TLB} + \mathrm{ma}) + (1 - h) \times (\mathrm{TLB} + \mathrm{ma} + \mathrm{ma})$

Where $h$ is the TLB hit ratio.

For $h = 0.99$, $\mathrm{TLB} = 2$ ns, $\mathrm{ma} = 100$ ns:

$\mathrm{EAT} = 0.99 \times 102 + 0.01 \times 202 = 103 \; \mathrm{ns}$

TLB coherence. When the OS modifies a page table entry, it must invalidate the corresponding TLB entry. On x86-64: invlpg for single-entry invalidation, or reload CR3 to flush the entire TLB.

5.7 Page Replacement Algorithms

When physical memory is full, a victim page must be selected for eviction.

Optimal (OPT/MIN). Replace the page not used for the longest time in the future. Provably Optimal but requires future knowledge; used only as a benchmark.

Theorem 5.2 (Belady”s Optimality). OPT yields the fewest page faults for any reference string.

Proof. If OPT replaces page $x$ (used furthest in future) and another algorithm replaces page $y$ (used sooner), the other algorithm faults at least once more by the time $y$ is next Referenced. $\blacksquare$

First-In, First-Out (FIFO). Replace the oldest page. Simple but may evict heavily used pages. Suffers from Belady’s anomaly: increasing frames can increase faults.

Example of Belady’s anomaly. Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. With 3 Frames: 9 faults. With 4 frames: 10 faults.

Least Recently Used (LRU). Replace the page not used for the longest time. Approximates OPT Well. Does not suffer from Belady’s anomaly.

Theorem 5.3. LRU is a stack algorithm: the set of pages in $n+1$ frames is a superset of the Set in $n$ frames, for any reference string.

Proof. When adding a frame, LRU keeps the $n$ most recently used pages (same as before) plus the New frame. No page in the $n$-frame set can be more recently used than a page outside it, so the $n+1$ set must contain the $n$-frame set. $\blacksquare$

Clock (Second Chance). Pages in a circular list with a reference bit. On replacement:

1. If reference bit is 0, replace the page.
2. If reference bit is 1, clear it and advance.

Approximates LRU with $O(1)$ per operation.

LFU (Least Frequently Used). Replace the page with the smallest access count. May fail to adapt To changing access patterns.

Approximating LRU in practice. Most OSes use a variant of Clock. Linux uses an LRU-like Approximation with active and inactive lists: pages on the active list are protected; pages Not accessed are demoted to the inactive list; eviction targets the inactive list.

:::caution Common Pitfall Belady’s anomaly applies to FIFO but not to LRU or Optimal. Adding more memory does not always Reduce page faults for non-stack algorithms.

5.8 Thrashing

Thrashing occurs when a process spends more time paging than executing. This happens when the Total working set of all active processes exceeds physical memory.

Working set model. $W(t, \Delta)$ is the set of pages referenced in the last $\Delta$ references. If $\sum W_i \gt$ available frames, thrashing occurs.

Solutions:

1. Working set strategy: Admit a process only if its working set fits.
2. Page fault frequency (PFF): Adjust resident set size based on observed fault rate.
3. Local replacement: Restrict eviction to the process’s own frames.

Theorem 5.4. If the sum of all working sets exceeds the number of physical frames, at least one Process must thrash.

Proof. By the pigeonhole principle, if $\sum_{i=1}^{n} \lvert W_i \rvert \gt F$ where $F$ is the Total number of frames, at least one process cannot hold its entire working set in memory. That Process will repeatedly evict pages it needs, causing its page fault rate to dominate its execution Time. $\blacksquare$

5.9 Copy-on-Write (COW)

Copy-on-Write is an optimisation for fork(). Instead of copying all pages, parent and child Share physical frames (marked read-only). On a write to a shared page, a fault triggers a copy of Just that page.

• fork() becomes nearly $O(1)$ instead of $O(n)$ where $n$ is the number of pages.
• If the child immediately calls exec()No copies are ever made.

:::