3.1 Why Virtual Memory?
Virtual memory gives every process the illusion of a huge, private, contiguous address space, while physical RAM holds only the currently useful pieces. Benefits: programs larger than RAM, isolation between processes, relocation without recompiling, and sharing. Mechanism: CPU issues virtual addresses (VA); the MMU translates them to physical addresses (PA) page by page.
3.2 Paging: The Address Split
Memory is divided into fixed-size pages (virtual) and frames (physical) of the same size — fixed size means no external fragmentation, only internal (average half a page wasted per process, the standard trade-off question).
32-bit VA, 4 KB pages:
offset = log2(4096) = 12 bits, VPN = 32 - 12 = 20 bits (2^20 = 1M pages)
VA 0x004032A7 -> VPN = 0x00403, offset = 0x2A7
Page table[0x00403] = frame 0x1F2
PA = frame || offset = 0x001F2 2A7 = 0x001F22A7The page table (one entry per virtual page) holds: frame number + valid bit (page in RAM?) + dirty bit (modified?) + referenced bit (for replacement) + protection bits (R/W/X). A flat 1M-entry table per process is huge — hence multi-level page tables, which allocate table pages only for used regions.
3.3 TLB: Caching Translations
Without help, every access needs 2 memory reads (page table + data). The TLB (Translation Lookaside Buffer) is a small fully-associative cache of recent VPN→frame translations.
EMAT with TLB time 10 ns, memory 100 ns, TLB hit ratio 0.9:
hit : 10 + 100 = 110 ns
miss : 10 + 100 + 100 = 210 ns (extra read: page table)
EMAT = 0.9 x 110 + 0.1 x 210 = 99 + 21 = 120 ns3.4 Page Faults and Replacement Algorithms
Accessing a page with valid = 0 triggers a page fault: trap to OS → find/free a frame (evicting a victim; write it back if dirty) → read the page from disk → update tables → restart the instruction. Since a fault costs milliseconds, the replacement algorithm matters enormously.
Worked reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 frames.
FIFO (evict the oldest):
| Ref | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frames | 1 | 1,2 | 1,2,3 | 2,3,4 | 3,4,1 | 4,1,2 | 1,2,5 | 1,2,5 | 1,2,5 | 2,5,3 | 5,3,4 | 5,3,4 |
| Fault? | F | F | F | F | F | F | F | H | H | F | F | H |
FIFO = 9 faults. Now run FIFO with 4 frames on the same string: faults = 1,2,3,4 (compulsory), then 5,1,2,3,4,5 all miss → 10 faults. More frames, more faults — Belady's anomaly, unique to FIFO-like algorithms and a guaranteed exam talking point.
- LRU (evict least recently used): same string, 3 frames → 10 faults. LRU obeys locality and never exhibits Belady's anomaly (it's a stack algorithm), but needs recency tracking (counters or a stack).
- Optimal (evict the page needed farthest in the future): same string → 7 faults. Unimplementable (needs the future) but the yardstick every real algorithm is measured against.
Summary here: OPT 7 ≤ FIFO 9 ≤ LRU 10 on this particular string — note LRU is usually better than FIFO in practice; single strings can flip the order, another nuance worth stating.
3.5 Segmentation
Segmentation divides a program by logical units — code, data, stack — each a variable-length segment addressed as (segment number, offset). The segment table stores base and limit: if offset ≥ limit → protection trap, else PA = base + offset. Example: segment 2 has base 4300, limit 400 → address (2, 53) → 4300 + 53 = 4353; address (2, 500) → trap (500 ≥ 400).
| Aspect | Paging | Segmentation |
|---|---|---|
| Division | fixed-size, physical | variable-size, logical |
| Visible to programmer | no | yes |
| Fragmentation | internal | external |
| Table entry | frame number | base + limit |
| Sharing/protection unit | page (coarse) | whole logical module (natural) |
Real systems (x86 heritage) combined both: segmentation with paging — segments provide the logical view, each segment is paged underneath. Finally, know thrashing: too few frames → constant faulting → CPU utilisation collapses while disks saturate.
🎯 Exam Focus
- A 24-bit virtual address uses 2 KB pages. Give the VPN/offset split and the number of page-table entries; translate VA 0x3A7C4 if its page maps to frame 0x5D.
- What does a page-table entry contain? Explain the role of the valid, dirty and referenced bits.
- With TLB access 20 ns, memory 150 ns and TLB hit ratio 0.85, compute the effective memory access time.
- For the reference string 7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames, count faults under FIFO, LRU and Optimal.
- State Belady's anomaly and demonstrate it using the string of Section 3.4 with 3 vs 4 frames under FIFO.
- Differentiate paging from segmentation (any six points) and define thrashing.