💾 OS 06: Memory Management & Virtual Memory

Targeted for: Juspay Elimination Round & Backend Systems Interviews
Key Focus: Address Translation, MMU & TLB internals, Multi-level Paging, Page Fault step-by-step handling, Page Replacement Algorithms (FIFO, LRU, Optimal, Belady's Anomaly), and Thrashing.

🏛️ 1. Logical vs Physical Address Space & The MMU

Modern operating systems provide Virtual Memory, isolating processes and giving each the illusion of having a continuous, private physical RAM space.

• Logical (Virtual) Address: Address generated by the CPU during instruction execution.
• Physical Address: Actual hardware address on the physical DDR RAM chip.
• MMU (Memory Management Unit): Dedicated hardware chip on the CPU die that performs wire-speed address translation between virtual and physical addresses.

📄 2. Paging Architecture Internals

• Pages: Virtual memory is split into fixed-size blocks called Pages (typically $4\text{ KB} = 2^{12}\text{ bytes}$).
• Frames: Physical RAM is split into identical fixed-size blocks called Frames.
• Virtual Address Structure (32-bit with 4KB Pages):
  • Offset $d$: $\log_2(4096) = 12\text{ bits}$ (offsets within a page: 0 to 4095).
  • Page Number $p$: $32 - 12 = 20\text{ bits}$ ($2^{20} = 1,048,576$ pages).

Page Table Entry (PTE) Flags:

• Valid / Present Bit (V): 1 if page is currently in physical RAM; 0 if swapped out to disk or unallocated $\implies$ triggers Page Fault.
• Dirty Bit (D / Modified): 1 if page was written to in RAM. Must be written back to disk before frame eviction.
• Reference / Access Bit (R): Set to 1 by hardware whenever the page is read/written (used by LRU/Clock algorithms).
• Permissions: Read/Write (R/W) and User/Supervisor (U/S).

⚡ 3. Translation Lookaside Buffer (TLB) & Access Latency

The TLB is a small, ultra-fast associative hardware cache on the CPU that stores recent Page Number -> Frame Number translations.

Effective Memory Access Time (EMAT) Formula:

Let:

• $\alpha$ = TLB Hit Ratio (e.g., $95% = 0.95$).
• $t_{\text{tlb}}$ = TLB search time (e.g., $1\text{ ns}$).
• $m$ = Physical Main Memory access time (e.g., $50\text{ ns}$).

$$\text{EMAT} = (t_{\text{tlb}} + m) \cdot \alpha + (t_{\text{tlb}} + 2m) \cdot (1 - \alpha)$$

(On a TLB Miss: 1 access to read Page Table in RAM + 1 access to read actual data = $2m$).

Calculation Example:

For $\alpha = 98%$, $t_{\text{tlb}} = 2\text{ ns}$, $m = 100\text{ ns}$: $$\text{EMAT} = (2 + 100)(0.98) + (2 + 200)(0.02) = (102)(0.98) + (202)(0.02) = 99.96 + 4.04 = \mathbf{104\text{ ns}}$$ (Without TLB, every memory read requires 200 ns; with 98% TLB hit rate, latency drops to ~104 ns).

💥 4. Page Fault Handling Step-by-Step

A Page Fault is a hardware interrupt triggered when an instruction references a virtual page with its Valid bit $= 0$ in the Page Table.

🧮 5. Page Replacement Algorithms & Worked Trace

Consider a process with 3 physical frames initially empty, and the following memory page reference string: $$\mathbf{7,; 0,; 1,; 2,; 0,; 3,; 0,; 4,; 2,; 3,; 0,; 3,; 2,; 1,; 2,; 0,; 1,; 7,; 0,; 1}$$

Algorithm 1: FIFO (First-In, First-Out)

Evicts the page that has been in RAM the longest.

• Total Page Faults (Misses): 15
• Total Hits: 5

⚠️ Belady's Anomaly in FIFO:

• Definition: Counter-intuitively, for certain reference strings, increasing physical memory frames causes MORE page faults under FIFO.
• Famous Anomaly String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • With 3 Frames: 9 Page Faults
  • With 4 Frames: 10 Page Faults (Performance degrades despite adding RAM!)
• Why LRU and Optimal are immune: They belong to the class of Stack Algorithms, where the set of pages in an $N$-frame system is always a strict subset of pages in an $(N+1)$-frame system.

Algorithm 2: LRU (Least Recently Used)

Evicts the page that has not been referenced for the longest period in past time.

• Total Page Faults: 12
• Total Hits: 8

Algorithm 3: Optimal (OPT / MIN - Clairvoyant Benchmark)

Evicts the page that will not be used for the longest period in future time.

• Total Page Faults: 9 (Provably minimum theoretical bound)
• Total Hits: 11

🌪️ 6. Thrashing: Causes & Mitigation

What is Thrashing?

Thrashing is a pathological performance collapse where the CPU spends 99% of its time servicing page faults (disk I/O) rather than executing application code.

The Root Cause Chain Reaction:

1. OS admits too many processes into memory (High degree of multiprogramming).
2. Physical RAM fills up; each process receives fewer frames than its Working Set (the set of pages actively referenced in the current time window $\Delta$).
3. Process 1 page-faults and waits for disk I/O.
4. CPU scheduler notices CPU is idle and brings in Process $N+1$, worsening memory starvation.
5. All processes enter the page fault wait queue $\implies$ System freezes completely.

Mitigation Strategies:

1. Working-Set Model: The OS calculates the working set size $WSS_i$ for each process $i$. Total demand $D = \sum WSS_i$. If $D > \text{Total RAM Frames}$, the OS suspends (swaps out) one entire process until memory pressure drops.
2. Page Fault Frequency (PFF): The OS establishes upper and lower page-fault rate thresholds. If a process exceeds the upper threshold, it is granted more frames; if it drops below the lower threshold, frames are reclaimed.

💬 7. Verbatim Interview Scripts (Say This Out Loud)

Q: "Explain Belady's Anomaly and how LRU avoids it."

Verbatim Answer:
"Belady's Anomaly is the phenomenon where adding more physical page frames to a system results in an increase in the total number of page faults for specific access patterns. It occurs in the FIFO (First-In, First-Out) page replacement algorithm because FIFO does not account for page recency or frequency.

The LRU (Least Recently Used) algorithm is mathematically immune to Belady's Anomaly because it belongs to the family of Stack Algorithms. In a stack algorithm, the set of pages resident in an $N$-frame memory system is guaranteed to be a strict subset of the pages resident in an $(N+1)$-frame memory system for any reference string at any point in time. Therefore, adding frames can never increase page faults."

Q: "What causes Thrashing and how does a modern OS detect and eliminate it?"

Verbatim Answer:
"Thrashing occurs when the aggregate memory demand of all active processes exceeds available physical RAM frames. When processes cannot hold their active Working Sets in memory, every instruction triggers a page fault, saturating the disk swap queue while driving CPU utilization down to near zero.

The OS detects thrashing using Page Fault Frequency (PFF) monitoring or tracking the Working-Set Model $W(t, \Delta)$. When the kernel detects severe thrashing, it reduces the degree of multiprogramming by temporarily suspending victim processes (swapping their entire address space to disk). This frees up sufficient RAM frames for remaining processes to fit their working sets, restore high CPU throughput, and finish execution."