Memory Management | Computer Science

flowchart TD
    A[5_Memory Management] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

Memory management answers: how do you give every process its own address space while sharing limited physical RAM? The solution is virtual memory — each process sees a private, contiguous address space that maps to scattered physical pages. This provides isolation (one process can’t corrupt another) and enables overcommitment (using more total memory than physically available).

Paging intuition: Physical memory is divided into fixed-size frames; virtual memory into pages of the same size. A page table maps each virtual page to a physical frame. When a process accesses a page not currently in RAM, a page fault occurs and the OS loads it from disk. This is slow (milliseconds vs nanoseconds for RAM), so the OS tries to keep frequently-used pages in memory.

Replacement algorithm intuition: When physical memory is full, the OS must evict a page. LRU (Least Recently Used) approximates the principle that recently-used pages will be used again. The working set model tracks which pages a process actively uses — if its working set doesn’t fit in RAM, the process thrashes (spends more time paging than computing).

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.

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.

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).

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).

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.

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.

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.

• Process Management — Each process has its own address space managed by the operating system’s memory management subsystem.

• Virtualization — Memory virtualization extends basic memory management to support multiple virtual machines.

• File Systems — Memory-mapped files blur the boundary between memory management and file system operations.

• Discrete Mathematics

• Algorithm Implementation

1. Confusing virtual addresses with physical addresses. Processes always see virtual addresses. The MMU translates them to physical addresses using page tables. A virtual address 0x7fff0000 in one process maps to a completely different physical frame than the same virtual address in another process.

2. Believing LRU is always optimal. LRU is a practical approximation but not optimal for all access patterns. Sequential scans of large files can evict the entire working set from memory (Bélády’s anomaly for FIFO, and LRU thrashing under scan patterns). Optimal replacement is theoretically best but requires future knowledge.

3. Confusing thrashing with poor algorithm choice. Thrashing occurs when the total working set of all processes exceeds physical memory, not because a page replacement algorithm is “bad.” Adding more frames or reducing the number of concurrent processes is the correct fix, not switching algorithms.

4. Ignoring the cost of page faults. A single page fault requires a disk access (milliseconds), which is orders of magnitude slower than a memory access (nanoseconds). Code that triggers frequent page faults — e.g., iterating over a large array with poor locality — will be dramatically slower than code with good spatial and temporal locality.

5. Assuming fork() is expensive without COW. Without copy-on-write, fork() would need to copy every page of the parent’s address space, making it O(n) in the number of pages. With COW, only modified pages are copied, making fork() followed by exec() extremely cheap since the child’s pages are never actually copied.