🧠 Module 05: Memory Management & Virtual Memory

Focus: Logical vs Physical Addressing, MMU, Contiguous Allocation (First/Best/Worst Fit), Paging & Multi-Level Page Tables, TLB & EAT Math, Segmentation, Virtual Memory, Page Replacement (FIFO, LRU, Optimal, Clock), Belady's Anomaly, Thrashing, and Kernel Allocators (Buddy/Slab).

📑 Table of Contents

1. Address Binding, MMU & Memory Protection
2. Contiguous Memory Allocation & Fragmentation
3. Paging Fundamentals & Hardware Translation
4. Multi-Level & Inverted Page Tables
5. Translation Lookaside Buffer (TLB) & EAT Math
6. Segmentation vs Paging
7. Virtual Memory & Page Fault Lifecycle
8. Page Replacement Algorithms (With Traces)
   • 8.1 FIFO & Belady's Anomaly Proof
   • 8.2 Optimal Page Replacement (OPT)
   • 8.3 Least Recently Used (LRU)
   • 8.4 Clock / Second-Chance Algorithm
9. Thrashing & The Working Set Model
10. Kernel Memory Allocators: Buddy System & Slab Allocator
11. Common Mistakes & Gotchas
12. Step-by-Step Numerical Practice Problems
13. High-Yield Interview Questions & Answers

1. Address Binding, MMU & Memory Protection

The Memory Management Unit (MMU) & Hardware Registers

The MMU is a dedicated hardware component on the CPU chip that maps Logical (Virtual) Addresses to Physical Addresses in RAM in real time.

Base & Limit Registers (Hardware Isolation)

To prevent a process from accessing operating system memory or other processes' data:

1. Base Register: Stores the smallest legal physical memory address.
2. Limit Register: Stores the size/range of the address space.

• If $\text{Address} \ge \text{Limit}$, the CPU generates a hardware trap (General Protection Fault / Segmentation Fault).

2. Contiguous Memory Allocation & Fragmentation

In early systems, each process was allocated a single contiguous chunk of physical RAM.

Dynamic Memory Allocation Strategies

3. Paging Fundamentals & Hardware Translation

Paging is a non-contiguous memory allocation scheme that eliminates external fragmentation entirely:

• Logical Memory is divided into fixed-size blocks called Pages.
• Physical RAM is divided into identical fixed-size blocks called Frames (typically $4\text{ KB}$).

Address Translation Arithmetic:

• Let Page Size $= 2^k$ bytes (e.g., $4\text{ KB} = 2^{12} \text{ bytes} \implies k = 12 \text{ bits for Offset } d$).
• If Logical Address space is $2^m$ bytes ($m=32 \implies 4\text{ GB}$):
  • Page Number bits $p = m - k = 32 - 12 = \mathbf{20\text{ bits}}$ ($2^{20} = 1,048,576\text{ pages}$).
• Physical Address Translation: $$\text{Physical Address} = (\text{Frame Number} \times \text{Page Size}) + \text{Offset}$$

4. Multi-Level & Inverted Page Tables

Why Single-Level Page Tables Fail:

On a 32-bit system with $4\text{ KB}$ pages, a single process page table has $2^{20}$ entries. If each Page Table Entry (PTE) $= 4\text{ bytes}$: $$\text{Page Table Size} = 2^{20} \times 4\text{ bytes} = 4\text{ MB per process!}$$ If 200 processes run, $800\text{ MB}$ of RAM is wasted just on page table metadata.

Two-Level Paging (Hierarchical)

The page table itself is paged. Unused virtual memory regions don't allocate sub-page tables:

64-bit Architecture (4-Level Paging in x86-64)

x86-64 uses 48-bit canonical addressing divided into 4 levels (9 bits each) + 12-bit offset: $$\text{PML4 (9 bits)} \longrightarrow \text{PDPT (9 bits)} \longrightarrow \text{Page Directory (9 bits)} \longrightarrow \text{Page Table (9 bits)} \longrightarrow \text{Offset (12 bits)}$$

5. Translation Lookaside Buffer (TLB) & EAT Math

Because a multi-level page table requires 2 to 4 separate memory accesses for every single load/store instruction, CPUs use a specialized, ultra-fast associative hardware cache called the Translation Lookaside Buffer (TLB).

Effective Access Time (EAT) Formula

$$\text{EAT} = (\text{Hit Ratio } h) \times (\text{TLB Access} + \text{RAM Access}) + (1 - h) \times (\text{TLB Access} + (N + 1) \times \text{RAM Access})$$ Where $N$ is the number of page table levels.

6. Segmentation vs Paging

7. Virtual Memory & Page Fault Lifecycle

Virtual Memory provides an illusion to applications of a massive, contiguous memory space, allowing programs larger than physical RAM to execute via Demand Paging.

8. Page Replacement Algorithms (With Traces)

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 (Allocated 3 Frames in RAM).

8.1 FIFO & Belady's Anomaly Proof

• FIFO: Evicts the page that has been in memory the longest.

Belady's Anomaly:

Belady's Anomaly is the counter-intuitive phenomenon where increasing the number of physical page frames results in MORE page faults for certain reference strings under FIFO replacement.

Classic Proof / Counterexample Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• With 3 Frames $\implies$ 9 Page Faults.
• With 4 Frames $\implies$ 10 Page Faults! (More frames yielded worse performance!)
• Stack Algorithms (like LRU and Optimal) are mathematically proven to be immune to Belady's Anomaly because the set of pages in $N$ frames is always a strict subset of pages in $N+1$ frames.

8.2 Optimal Page Replacement (OPT)

• Rule: Replace the page that will NOT be used for the longest period of time in the future.
• Serves as the theoretical benchmark for maximum possible efficiency.

8.3 Least Recently Used (LRU)

• Rule: Replace the page that has not been referenced for the longest period in the past.
• Implemented in hardware via timestamp counters or an LRU double-linked list stack.

8.4 Clock / Second-Chance Algorithm

Approximates LRU in software with minimal hardware overhead using a Reference Bit (0 or 1) per page and a circular pointer:

9. Thrashing & The Working Set Model

What is Thrashing?

Thrashing occurs when a system spends more time servicing page faults and swapping pages in/out of disk than executing actual user instructions.

Why Thrashing Happens:

1. OS notices low CPU utilization $\rightarrow$ Concludes CPU is underutilized.
2. OS admits more processes into RAM to increase multiprogramming.
3. New processes demand memory frames $\rightarrow$ Total memory demand exceeds physical RAM.
4. Processes constantly page fault $\rightarrow$ CPU idles waiting for disk I/O $\rightarrow$ OS tries to launch even more processes $\rightarrow$ Total system collapse.

Solution: Working Set Model

• Working Set Window ($\Delta$): The set of pages referenced in the most recent $\Delta$ time units.
• Working Set Size ($WSS_i$): The number of unique pages referenced by process $P_i$.
• Total Demand $D = \sum WSS_i$.
• If $D > \text{Total RAM Frames } M$, the OS suspends a process and swaps it out completely to eliminate thrashing.

10. Kernel Memory Allocators: Buddy System & Slab Allocator

1. Buddy Memory Allocator

Allocates physical memory in power-of-two sizes ($2^U$). When a block is freed, it immediately merges with its adjacent "buddy" block:

2. Linux Slab Allocator

The Buddy system suffers from internal fragmentation when allocating small kernel structs (struct task_struct, struct inode, file descriptors).
The Slab Allocator creates dedicated caches of pre-constructed, fixed-size objects:

• Full Slabs: All object slots used.
• Partial Slabs: Contains free and allocated object slots.
• Empty Slabs: Contains all free object slots.
• Benefit: Zero fragmentation for kernel objects; instant $O(1)$ allocation without invoking page tables.

11. Common Mistakes & Gotchas

[!CAUTION]

1. Conflating Page Size with Page Table Size

• Page Size: Size of a data block (e.g., $4\text{ KB}$).
• Page Table Size: Total memory required to store the table array containing mappings for all virtual pages (e.g., $4\text{ MB}$).

[!WARNING]

2. Assuming LRU suffers from Belady's Anomaly

LRU is a Stack Algorithm and is mathematically immune to Belady's anomaly. Only non-stack FIFO-style queues suffer from Belady's anomaly.

12. Step-by-Step Numerical Practice Problems

Problem 1: Effective Access Time (EAT) Calculation

Question: A 2-level paging system has:

• TLB lookup time $= 20\text{ ns}$.
• Main memory (RAM) access time $= 100\text{ ns}$.
• TLB Hit Ratio $= 95%$.
• Calculate the Effective Access Time (EAT).

Solution:

1. On TLB Hit (95% of cases):
   • Access TLB ($20\text{ ns}$) + Access Physical RAM data ($100\text{ ns}$) $= 120\text{ ns}$.
2. On TLB Miss (5% of cases):
   • Access TLB ($20\text{ ns}$) + Access Level 1 Page Table in RAM ($100\text{ ns}$) + Access Level 2 Page Table in RAM ($100\text{ ns}$) + Access Physical RAM data ($100\text{ ns}$) $= 320\text{ ns}$.
3. EAT Calculation: $$\text{EAT} = (0.95 \times 120\text{ ns}) + (0.05 \times 320\text{ ns}) = 114\text{ ns} + 16\text{ ns} = \mathbf{130\text{ ns}}$$

Problem 2: Logical to Physical Address Translation

Question: Given:

• 32-bit Logical Address Space, $4\text{ KB}$ Page Size.
• Page Table Entry: Page 7 -> Frame 12.
• Translate logical virtual address 0x00007A3F to its physical RAM address.

Solution:

1. Page Size $= 4\text{ KB} = 4096 = 2^{12}\text{ bytes} \implies$ Offset $= 12\text{ bits} = 3\text{ hex digits}$.
2. In address 0x00007A3F:
   • Offset $d = \text{0xA3F}$.
   • Page Number $p = \text{0x00007} = 7$.
3. Page Table Lookup: Page $7$ maps to Frame $12$ ($\text{0xC}$ in hex).
4. Physical Address $= \text{Frame } \text{0xC} \text{ concatenated with Offset } \text{0xA3F} = \mathbf{\text{0x0000CA3F}}$.

13. High-Yield Interview Questions & Answers

Q1: What is the difference between Internal and External Fragmentation, and how does Paging solve external fragmentation?

Answer:

• Internal Fragmentation: Occurs when memory is allocated in fixed-size blocks and a process requests less than the block size, leaving wasted memory inside the allocated block.
• External Fragmentation: Occurs when total free memory across the system is sufficient to satisfy a request, but the free space is fragmented into non-contiguous blocks, preventing contiguous allocation.
• Paging Solution: Paging allows a process's logical address space to be mapped to non-contiguous physical frames in RAM. Since any free frame can be assigned to any page, external fragmentation is completely eliminated.

Q2: What is Belady's Anomaly and why does it occur in FIFO but not in LRU?

Answer: Belady's Anomaly is the phenomenon where adding more physical page frames increases the total number of page faults. It occurs in FIFO because FIFO does not consider the frequency or recency of page accesses; older pages are blindly evicted even if they are currently hot and frequently accessed.
LRU belongs to the class of Stack Algorithms, where the set of pages in memory for $N$ frames is strictly a subset of the pages that would be in memory for $N+1$ frames, making Belady's Anomaly mathematically impossible under LRU.

Q3: What is a TLB Shootdown and when does it occur in Multicore systems?

Answer: In multi-core systems, each core has its own private TLB caching virtual-to-physical address translations. When one core modifies a page table mapping (e.g., during page eviction, memory unmapping, or permission changes via mprotect), the cached translations on all other CPU cores become invalid.
A TLB Shootdown is the mechanism where the initiating core sends Inter-Processor Interrupts (IPIs) to all other cores, forcing them to flush their local TLBs before the initiating core safely completes the page modification.

Q4: How does Copy-On-Write (COW) optimize memory usage during fork()?

Answer: Instead of duplicating the entire physical memory space of the parent process during fork(), the kernel simply copies the page table pointers and marks all shared pages as Read-Only. Both parent and child read from the same physical RAM frames. Only when either process attempts to write to a page does the CPU MMU raise a page fault exception, prompting the OS kernel to allocate a new physical frame, copy the data, and make that single page private and writeable for the modifying process.

Proceed to Module 06: File Systems & Storage Management!