Memory Management

Why This Chapter Matters

Memory management is tested in every GATE OS section — 6-10 marks. Paging, segmentation, page replacement algorithms, and TLB calculations are all favourite questions.

Core Concepts

1. Logical vs Physical Address

Logical address: generated by CPU (process perspective)

Physical address: actual RAM address

MMU (Memory Management Unit): translates logical -> physical

2. Paging

Logical address = page number + offset

Page size = 2^n bytes -> offset = n bits

Number of pages = logical space / page size

Page table: Maps page number -> frame number in physical memory.

Physical address = frame number x page size + offset

Page table size: (number of pages) x (entry size)

For 32-bit address, 4KB pages: 2^20 pages. Each entry = 4 bytes. Page table = 4MB!

TLB (Translation Lookaside Buffer): Hardware cache for page table entries.

Effective Access Time (EAT) = hit rate x (TLB time + memory) + miss rate x (TLB time + 2 x memory)

Multi-level paging: Split page number into multiple parts to reduce page table size.

For 32-bit address, 4KB pages, 2-level paging: 10-bit outer page, 10-bit inner page, 12-bit offset.

3. Segmentation

Programs divided into logical segments (code, data, stack, heap).

Segment table: base address + limit for each segment.

Logical address = segment number + offset. Check offset < limit.

4. Page Replacement Algorithms

FIFO: Replace oldest page. Belady's anomaly (more frames can give more faults).

Optimal (OPT): Replace page not used for longest time in future. Theoretical minimum page faults. Not implementable (requires future knowledge).

LRU (Least Recently Used): Replace page not used for longest time in past. Good approximation of OPT. No Belady's anomaly.

LRU Approximation — Clock algorithm (Second Chance): Reference bit. If bit=0, replace. If bit=1, give second chance (set bit=0, advance pointer).

PYQs

GATE 2024: System with 3 frames. Reference string: 1 2 3 4 1 2 5 1 2 3 4 5. Page faults with LRU?

Trace: 1(F),2(F),3(F),4(F-evict1),1(F-evict2),2(F-evict3),5(F-evict4),1(F-evict2),2(F-evict1),3(F-evict5),4(F-evict1),5(F-evict2)

Count page faults = 12.

GATE 2023: 32-bit logical address space, page size = 4KB. Number of bits for page number and offset?

Offset = log2(4KB) = log2(4096) = 12 bits. Page number = 32-12 = 20 bits.

GATE 2022: Belady's anomaly occurs in which algorithm?

FIFO — more frames can sometimes cause MORE page faults.

Revision Notes

PAGING:
Logical address = page number | offset
offset bits = log2(page size)
Physical address = frame * page_size + offset

EAT with TLB:
EAT = h*(t_tlb + t_mem) + (1-h)*(t_tlb + 2*t_mem)
h = hit rate, t_tlb = TLB access time, t_mem = memory access time

PAGE REPLACEMENT:
FIFO: Belady's anomaly possible
OPT: Minimum page faults (theoretical)
LRU: No Belady's anomaly, good performance

WORKING SET: Set of pages process is currently using (locality principle)
THRASHING: Process spends more time paging than executing