Memory Management, Paging & Segmentation
Memory management maps logical addresses to physical memory. Paging eliminates external fragmentation; segmentation reflects program structure. GATE tests address translation, page tables, and fragmentation.
Key Points
- ·Logical address: generated by CPU; Physical address: actual memory address
- ·MMU (Memory Management Unit): hardware unit performing address translation
- ·Fixed partitioning: internal fragmentation; variable partitioning: external fragmentation
- ·Compaction: move processes to eliminate external fragmentation (expensive)
- ·Paging: divide logical address space into pages, physical into frames (same size); no external fragmentation
- ·Page table: maps page number → frame number; can be large (4GB / 4KB = 1M entries)
- ·TLB (Translation Lookaside Buffer): hardware cache for page table entries
- ·Effective Access Time = hit_rate × (TLB_time + mem_time) + miss_rate × (TLB_time + 2×mem_time)
- ·Multilevel paging: page table itself paged; inverted page table: one entry per frame
The Memory Problem
Analogy: Your desk is RAM (limited, fast). Your bookshelf is the disk (large, slow). The OS is like your brain deciding what stays on the desk and what goes on the shelf.
When you run a program, the OS must load it into RAM and give it a range of addresses. But the program thinks it owns the whole computer! The OS uses a clever trick: virtual (logical) addresses.
Logical vs Physical Address
Logical address: the address the PROGRAM sees (starts from 0)
Physical address: the ACTUAL location in RAM
The CPU generates logical addresses.
The MMU (Memory Management Unit chip) translates them to physical at runtime.
Program says: "read address 100"
MMU translates: "address 100 is actually at physical RAM location 5100"
Fragmentation — Two Types of Wasted Space
Internal fragmentation: wasted space INSIDE an allocated block
Example: Process needs 35KB, allocated 40KB block → 5KB wasted inside
External fragmentation: wasted space BETWEEN allocated blocks
Example: 50KB free in 10 separate 5KB holes, but a 20KB process can't fit!
Fix: Compaction (move processes together — expensive)
Paging — The Clean Solution
Analogy: Instead of allocating one big continuous room to each guest, the hotel gives guests individual rooms that need not be adjacent. Rooms are all the same size (pages/frames).
Logical address space divided into: PAGES (fixed size, e.g., 4KB)
Physical memory divided into: FRAMES (same size as pages)
Logical address: [Page Number p | Offset d]
←─── bits ───→ ←── bits ──→
Physical address: [Frame Number f | Offset d]
PageTable[p] = f
Physical addr = PageTable[p] × page_size + d
Key properties:
✓ No external fragmentation (all frames same size)
✗ Internal fragmentation (last page of process may be partially full)
Average waste = page_size / 2 (half a page per process)
Address Breakdown Example
Logical address space = 32 bits, Page size = 4KB = 2^12 bytes
Offset bits = 12 (to address within a 4KB page)
Page number bits = 32 - 12 = 20
Number of pages = 2^20 = 1,048,576 pages
Logical address 0x00003500:
In binary: 0000 0000 0000 0000 0011 0101 0000 0000
Page number = top 20 bits = 3
Offset = bottom 12 bits = 0x500 = 1280
If PageTable[3] = 7 (frame 7):
Physical address = 7 × 4096 + 1280 = 29952
TLB — The Fast Lane
Analogy: The page table is a big book in your library (slow to look up). TLB is a sticky note on your desk with the 10 pages you use most (fast).
TLB (Translation Lookaside Buffer) = small hardware cache of recent page→frame mappings
TLB hit (page found in TLB): 1 TLB lookup + 1 memory access = t + m
TLB miss (not found): 1 TLB lookup + 1 page table access + 1 memory access = t + 2m
Effective Access Time (EAT):
EAT = h × (t + m) + (1-h) × (t + 2m)
EAT = t + m + (1-h) × m
= t + (2-h) × m
where h = TLB hit ratio, t = TLB access time, m = memory access time
Example: TLB time = 20ns, Memory time = 100ns, hit ratio = 80%
EAT = 0.8 × (20+100) + 0.2 × (20+200)
= 0.8 × 120 + 0.2 × 220
= 96 + 44 = 140ns
Multilevel Paging — Handling Large Page Tables
The problem: 32-bit address space with 4KB pages = 1M entries × 4 bytes = 4MB page table per process × 100 processes = 400MB just for page tables!
Solution: Page the page table itself!
2-level paging:
Logical address = [p1 (10 bits) | p2 (10 bits) | offset (12 bits)]
Outer page table → Inner page table → Data
On TLB miss: 3 memory accesses (outer + inner + data)
For k-level paging: k+1 memory accesses on TLB miss
Segmentation — Program-Logical Division
Logical address = (Segment number s, Offset d)
Segment table entry: base address + limit (size)
If d >= limit → segment fault (protection violation)
Physical address = base[s] + d
Advantages:
+ Reflects program structure (code, data, stack as separate segments)
+ Easy protection (read-only code segment)
Disadvantages:
- External fragmentation (variable-size segments)
Paging vs Segmentation
| Feature | Paging | Segmentation |
|---|---|---|
| Unit size | Fixed (pages) | Variable (segments) |
| Fragmentation | Internal | External |
| Programmer visible? | No (transparent) | Yes (logical units) |
| Address form | (page, offset) | (segment, offset) |
Quick Check
Q1. Page size = 1KB, logical address = 4KB, physical memory = 8KB. How many pages and frames?
Pages = 4KB / 1KB = 4 pages
Frames = 8KB / 1KB = 8 frames
Offset bits = log2(1024) = 10 bits
Page number bits = log2(4) = 2 bits
Logical address = 12 bits total
Q2. EAT = 200ns, memory access = 100ns, TLB time = 0. Find hit ratio.
EAT = h × 100 + (1-h) × 200 = 200
100h + 200 - 200h = 200
-100h = 0 → h = 0 (TLB gives no benefit at 0% hit ratio)
Wait — let's recalculate: h=0: EAT = 200ns ✓ (0 hits, always 2 memory accesses)
Q3. Why does paging have no external fragmentation? Answer: All pages and frames are the same fixed size. Any free frame can hold any page — there are never holes between allocations that are too small to use.
Key Formulas
- EAT with TLB: EAT = h(t+m) + (1-h)(t+2m) = t + (2-h)m
- Page table size: (2^VA_bits / page_size) × entry_bytes
- Physical address: PA = PageTable[page_num] × page_size + offset
GATE Exam Tips
- ★EAT formula is a guaranteed GATE question — memorise h(t+m) + (1-h)(t+2m).
- ★With k-level paging, a TLB miss needs k+1 memory accesses (k page table levels + 1 for actual data).
- ★Paging has NO external fragmentation — this is a frequent comparison question answer.
- ★Inverted page table has one entry per physical FRAME (not per page) — saves space, slower lookup.
Finished reading this topic?
Mark it complete to track your study progress.