GATE CS - OPERATING SYSTEMS:Memory Management
Mastering memory management concepts and implementation.
Memory Management for GATE CS
GATE Memory Management is mostly paging/segmentation numericals and page-replacement traces (FIFO, LRU, Optimal, sometimes CLOCK). Belady’s anomaly is a favourite trap for FIFO.
Address translation
Logical address → (page number, offset). Physical = frame number + offset.
- Pages/frames same size
- Page table maps page → frame (valid bit, dirty bit, protection)
- TLB caches recent translations; effective access time mixes TLB hit/miss and memory/page-fault costs when given
Multi-level page tables reduce the resident size of the page table; GATE may ask how many levels or bits per level.
Segmentation
Variable-size segments (code, stack, heap). Address = (segment #, offset). External fragmentation possible; often combined with paging (paged segmentation).
Page replacement
On a fault with no free frame, choose a victim.
| Policy | Idea | Note |
|---|---|---|
| **FIFO** | Oldest frame | Can show **Belady’s anomaly** (more frames ⇒ more faults) |
| **LRU** | Least recently used | Strong exam favourite; stack property |
| **Optimal** | Replace page used farthest in future | Offline lower bound |
| **CLOCK** | Approximate LRU with reference bits |
Worked: FIFO vs LRU sketch
Reference string: 1 2 3 4 1 2 5 1 2 with 3 frames.
FIFO typically faults on each new page until replacement cycles — count carefully with a queue. LRU updates recency on every use. Optimal needs future knowledge.
If the question shows a filled frame table with * marks for replacements, reverse-engineer which policy fits (GATE 2025-style).
Thrashing and working set
Too many faults ⇒ thrashing. Working-set model keeps recently used pages resident. Prep tip: know the definition; deep OS research detail is rare.
Previous: Process Management. Next: File Systems. Quizzes: GATE hub.