Part 3: Memory Management & Virtual Memory

1. Virtual Memory: The “Magic” of Modern OS

Virtual Memory is a technique that allows the execution of processes that may not be completely in physical memory.

• Demand Paging: Instead of loading the entire program into RAM, the OS loads only the pages it needs right now. If a program attempts to access a page not currently in RAM, a Page Fault occurs.
• The Page Fault Sequence:

1. OS checks an internal table to see if the reference was valid.
2. If invalid (segfault), terminate process.
3. If valid but not in RAM, find a free frame in physical memory.
4. Schedule a disk operation to read the desired page into the frame.
5. Update the page table to show the page is now in memory.
6. Restart the instruction that caused the trap.

2. Paging Address Translation & the TLB

• Address split: a logical address is divided into a page number and an offset. The page number indexes the page table; the frame number from the table + the offset = the physical address.
• Page table location: a flat page table is itself large, so real systems use multi-level (hierarchical) page tables — the top-level entries point to lower-level tables, and unused ranges cost nothing. Trade-off: an extra memory access per level.
• TLB (Translation Lookaside Buffer): a small, ultra-fast hardware cache of recent logical→physical mappings.
• TLB hit: translation done in one cycle — no memory access to the page table.
• TLB miss: fall back to the page table (slower), then reload the TLB.
• The TLB makes paging fast enough to be practical; the page table + TLB together turn logical addresses into physical ones, with the MMU doing the work.

3. Thrashing: The “Death Spiral”

Thrashing is a performance collapse that occurs when a system spends more time moving pages between RAM and disk than actually executing code.

• The Cause: The sum of the “Working Sets” (the pages a process is actively using) of all running processes exceeds the available physical RAM. The OS tries to free up space by swapping a page out, but immediately needs it back, leading to constant disk I/O.
• The Solution:
• Working Set Model: The OS monitors how many pages each process is actively using. If the total is too high, it suspends one or more processes to free up frames for the others.
• User level: Decrease the degree of multiprogramming (close some apps) or add more physical RAM.

4. Page Replacement Algorithms

When a page fault occurs and there are no free frames, the OS must choose a “victim” page to evict.

• FIFO (First-In-First-Out): Replaces the oldest page.

• Flaw: Belady’s Anomaly—increasing the number of page frames can actually increase the number of page faults for certain access patterns.

• LRU (Least Recently Used): Replaces the page that hasn’t been accessed for the longest time.

• Logic: It assumes that if you haven’t used a page in a long time, you are unlikely to use it soon (Temporal Locality). It is generally considered the best practical algorithm. A stack algorithm, so it never suffers Belady’s anomaly.

• Optimal (OPT/MIN): Replaces the page that will not be used for the longest period of time.

• Note: This is impossible to implement in reality because it requires future knowledge, but it serves as the benchmark to measure other algorithms (provably minimal faults).

• Clock (Second-Chance): the practical approximation of LRU — uses a reference bit; pages with the bit set get a second chance, others are evicted in FIFO order. Nearly as good as LRU at a fraction of the cost.

• Dirty bit: if a victim page was modified, it must be written back to disk before eviction (a dirty page costs more to replace than a clean one) — so the OS prefers to evict clean pages.

5. Worked Example — Counting Page Faults (FIFO vs LRU)

Given: reference string 7 0 1 2 0 3 0 4 2 3 0 3 2, 3 frames.

• FIFO (evict the oldest loaded page) → 10 faults.
• LRU (evict the least recently used) → 9 faults.

Walk through FIFO: 7,0,1 fault in (3), 2 evicts 7 (4), 0 hit, 3 evicts 0 (5), 0 evicts 1 (6), 4 evicts 2 (7), 2 evicts 3 (8), 3 evicts 0 (9), 0 evicts 4 (10), then 3,2 are hits → 10 total. LRU keeps recently-used pages, so later misses are fewer → 9 total.

Method for any algorithm:

1. Walk the reference string one page at a time.
2. Page already in a frame → hit, no fault.
3. Page not present → fault: load into a free frame, or evict per the rule (FIFO: oldest; LRU: least recently used) and load.
4. Count every load as one fault.

• Watch-outs: a page already present is a hit even if it’s next in line for eviction; FIFO can show Belady’s anomaly (more frames → more faults), LRU never does. Always draw the frame table column by column under pressure.

6. Advanced Memory Structures

• Copy-on-Write (COW): When a process (like a parent) forks a child, the OS doesn’t immediately copy all the memory. It marks pages as “read-only” and shared. If either process tries to modify a page, the OS then creates a private copy of just that page. This makes process creation near-instantaneous.

• Multi-level Page Tables: flatten the page table into a tree so sparse address spaces don’t waste memory; the top-level entries index sub-tables. Cost: one extra memory access per level (partly hidden by the TLB).

---

Scenario-Based Problem Solving (For Interviews)

Scenario	Diagnosis	Solution/Reasoning
System is crawling, disk LED is flickering constantly.	Thrashing	The OS is swapping pages continuously. Reduce active processes.
Need to share a library (e.g., libc) between 10 processes.	Shared Memory	Map the same physical page frames into the virtual address space of all 10 processes.
Two processes need to update a shared file/buffer.	Critical Section	Use a Mutex to ensure one process finishes its I/O before the next begins.
A system needs to handle massive numbers of tiny, short-lived tasks.	Containers/Threads	Use containers or threads; avoid heavy fork() processes.
Designing a system for an airbag deployment.	RTOS	Use an RTOS (Real-Time OS). Determinism (guaranteed response time) is more important than raw throughput.

Critical Thinking Tip: When an interviewer asks “Which algorithm is best?”, never say a single name. Say: “It depends on the access pattern. If we have high temporal locality, LRU is excellent. If we have a very limited-resource embedded system, we might prefer a simpler algorithm like FIFO or Clock to save on CPU overhead.”