Neural Sync Active

Memory Management — Paging, Segmentation, TLB

Registry Synced

Memory Management — Paging, Segmentation, TLB

1104 words

6 min read

Reading compass

Now · 🎯 Learning Objectives

Memory Management — Paging, Segmentation, TLB

🎯 Learning Objectives

Translate logical addresses to physical addresses for paging
Design page table structures (single-level, multi-level, inverted)
Calculate TLB hit/miss ratios and effective access time
Compare paging with segmentation

1. Introduction to Memory Management

1.1 Intuition

The OS manages memory to let multiple processes share RAM without interfering. Each process gets its own logical address space that maps to physical memory. The mapping is managed by the Memory Management Unit (MMU) using page tables. (Diagram)

1.2 Key Concepts

Concept	Definition
Logical address	Address generated by CPU (process's view)
Physical address	Actual address in RAM
MMU	Hardware device that maps logical to physical
Relocation register	Base address for dynamic relocation
Limit register	Upper bound of accessible memory

2. Paging

2.1 Intuition

Paging divides physical memory into fixed-size frames and logical memory into same-size pages. A page table maps each logical page to a physical frame. This eliminates external fragmentation. (Diagram)

2.2 Address Translation

Logical address = Page number (p) + Page offset (d)


pseudo
If page size = 4 KB (2^12), then:
- Offset: 12 bits
- Remaining bits = page number
Example: 32-bit address with 4KB pages
- Bits 0-11: offset (12 bits)
- Bits 12-31: page number (20 bits) → 2^20 = 1M pages

Translation: Physical = Frame number × Page size + Offset


text
Logical address: 0x12345678
Page size: 4KB = 0x1000
Page number = 0x12345  (0x12345678 >> 12)
Offset      = 0x678
Frame       = PageTable[0x12345] = 0x2ABC
Physical    = 0x2ABC × 0x1000 + 0x678 = 0x2ABC678

2.3 Page Table Structure

Entry Field	Description
Frame number	Physical frame mapped to this page
Valid bit	Is the page in memory?
Present bit	Is the page in physical memory?
Dirty bit	Has the page been modified?
Reference bit	Has the page been accessed?
Protection bits	Read/write/execute permissions

2.4 Multi-Level Page Table

For 32-bit address space with 4KB pages: need 2^20 page table entries. With 4 bytes each, that's 4 MB per process — too large. Multi-level paging reduces memory usage. (Diagram) Two-level paging (32-bit):

Field	Bits	Description
P1	10	Index into outer page table
P2	10	Index into inner page table
Offset	12	Offset within page

Memory advantage: Outer table is always in memory (4KB). Inner tables are allocated only if pages exist in that range.

2.5 Inverted Page Table

For 64-bit systems, multi-level tables grow too large. An inverted page table has one entry per physical frame, not per virtual page.


pseudo
Inverted page table size = Physical memory size / Page size

Trade-off: Reduces memory but increases search time (use hashing).

3. Translation Lookaside Buffer (TLB)

3.1 Intuition

A TLB is a hardware cache for page table entries. Most programs exhibit temporal locality (accessing same address repeatedly) and spatial locality (accessing nearby addresses), so the TLB dramatically speeds up address translation.

3.2 Effective Memory Access Time

EMAT = TLB hit ratio × (TLB access + memory access) + (1 - hit ratio) × (TLB access + page table access + memory access) Example:

TLB access: 1 ns
Memory access: 100 ns
Hit ratio: 99%


pseudo
EMAT = 0.99 × (1 + 100) + 0.01 × (1 + 100 + 100)
     = 0.99 × 101 + 0.01 × 201
     = 99.99 + 2.01
     = 102 ns

Hit Ratio	EMAT	Speedup vs No TLB
0%	201 ns	1x (same as no TLB)
50%	151 ns	1.33x
90%	111 ns	1.81x
99%	102 ns	1.97x

3.3 TLB Miss Handling

(Diagram)

4. Segmentation

4.1 Intuition

Segmentation divides memory into variable-sized units (segments) that match the logical structure of a program: code segment, data segment, stack segment, etc. (Diagram)

4.2 Segmentation Address Translation

Logical address = Segment number (s) + Offset (d) A segment table maps each segment to a base address and limit:

Segment	Base	Limit	Permissions
Code	0x400000	0x10000	Read-Execute
Data	0x500000	0x8000	Read-Write
Stack	0x7FFFF0000	0x1000	Read-Write

4.3 Paging vs Segmentation

Aspect	Paging	Segmentation
View	Computer-centric (fixed size)	Programmer-centric (logical units)
Size	Fixed (2^n)	Variable
Fragmentation	Internal (within last page)	External (between segments)
Protection	Per-page bits	Per-segment permissions
Sharing	Page-level sharing possible	Natural sharing of logical units

5. Common Pitfalls

Pitfall 1: Confusing page table size with frame size

Mistake: Thinking "page size = 4KB means page table has 4KB entries." Correction: Page size is the unit of data. Page table has entries = virtual address space / page size.

Pitfall 2: Ignoring TLB in performance calculations

Mistake: Forgetting that even a TLB miss requires two memory accesses (page table + data). Fix: Use the EMAT formula: EMAT = hit_ratio × (TLB + mem) + miss_ratio × (TLB + PT + mem)

Pitfall 3: External vs internal fragmentation

Mistake: Thinking paging has external fragmentation. Correction: Paging has internal fragmentation (wasted space in last page). Segmentation has external fragmentation (gaps between segments).

6. 📐 Key Formulas / Concepts

Concept	Formula
Page offset bits	`log2(page_size)`
Page table entries	`2^(address_bits - offset_bits)`
Page table size (bytes)	`entries × entry_size`
EMAT (no TLB)	`2 × memory_access_time`
EMAT (with TLB)	`h × (t + m) + (1-h) × (t + 2m)`
Physical address	`frame × page_size + offset`

7. 📝 Practice Questions

Q1: For a 32-bit system with 4KB pages and 4-byte page table entries, what is the single-level page table size?

Answer: 2^20 pages × 4 bytes = 4 MB per process. With 100 processes, that's 400 MB just for page tables! Q2: Calculate EMAT for TLB hit ratio 95%, TLB access 2ns, memory access 50ns.

Answer: EMAT = 0.95 × (2+50) + 0.05 × (2+50+50) = 0.95×52 + 0.05×102 = 49.4 + 5.1 = 54.5 ns Q3: Convert the logical address 0x00A3B2C1 to physical address using a two-level page table. Page size = 4KB, P1 = bits 22-31, P2 = bits 12-21, offset = bits 0-11. Assume P1 index = 0x0A returns frame for L2 table = 0x30F000, and P2 index = 0x3B2 returns frame = 0x5C.

Answer: Physical = frame 0x5C × 0x1000 + offset 0xC1 = 0x5C000 + 0xC1 = 0x5C0C1 Q4: Why does segmentation lead to external fragmentation?

Answer: As segments of varying sizes are loaded and removed, free memory becomes divided into small non-contiguous holes. A new segment may not fit even though total free space is sufficient, because it's spread across multiple holes. Q5: What is the advantage of multi-level page tables?

Answer: They save memory by not allocating inner page tables for unused regions of the virtual address space. The outer table is always resident (small), and inner tables are allocated on demand.

8. 🔗 Cross-References

Week 8 - Virtual Memory: Page faults, demand paging
Week 2 - Threads: Each thread has its own stack in the address space
BSCS3031 (CSD): Memory hierarchy, TLB, cache memory Join Discord PreviousDeadlocksNextVirtual Memory