What is the difference between internal and external fragmentation?

Internal fragmentation: wasted space inside an allocated block — occurs in paging when the last page is not fully used (process size not multiple of page size). External fragmentation: total free memory is enough but not contiguous — occurs in variable-size partitioning when free holes are scattered. Paging eliminates external fragmentation but causes internal fragmentation. Segmentation eliminates internal fragmentation but causes external fragmentation.

How is a virtual address translated to a physical address using paging?

Split virtual address into page number (p) and offset (d). Use p to index the page table — get frame number (f). Physical address = f × page_size + d. With n-bit virtual address and page size 2^k bytes: upper (n-k) bits are page number, lower k bits are offset.

What is the effective memory access time with TLB?

EAT = h × (t_TLB + t_mem) + (1-h) × (t_TLB + 2×t_mem). Where h = TLB hit ratio, t_TLB = TLB access time, t_mem = memory access time. On TLB hit: 1 memory access (TLB + data). On TLB miss: 2 memory accesses (page table + data). TLB access time is usually added to both cases.

What is the size of a page table?

Page table size = number of pages × size of each page table entry. Number of pages = virtual address space / page size = 2^(n-k) where n = virtual address bits, k = offset bits. Entry size = enough to hold frame number + flags (typically 4 bytes). Example: 32-bit address, 4KB pages → 2^20 entries × 4 bytes = 4 MB page table per process.

Memory Management in OS for GATE CS

Paging, segmentation, address translation, TLB, fragmentation — complete GATE CS coverage with address calculation examples.

Last updated: April 2026 | GATE CS 2024–2026 syllabus

Key Takeaways for GATE

Paging: fixed-size pages. Eliminates external fragmentation. Causes internal fragmentation.
Physical address = frame_number × page_size + offset.
TLB hit: 1 memory access. TLB miss: 2 memory accesses (page table + data).
EAT with TLB = h(t_TLB+t_m) + (1−h)(t_TLB+2t_m).
Page table size = (virtual address space / page size) × entry size.
Segmentation: variable-size segments. Eliminates internal fragmentation. Causes external fragmentation.
Multilevel paging reduces page table memory by making page table itself pageable.

1. Contiguous Allocation

Each process occupies a single contiguous block of memory.
Fixed partitioning: Memory divided into fixed-size partitions. Simple but causes internal fragmentation.
Variable partitioning: Partitions sized to fit each process. No internal fragmentation, but causes external fragmentation.

Allocation strategies:
First Fit: allocate first hole big enough. Fast, may leave large holes.
Best Fit: allocate smallest hole that fits. Minimises wasted space; leaves tiny unusable fragments.
Worst Fit: allocate largest hole. Leaves largest remaining fragment — generally worst performance.

Compaction: Shuffle processes to consolidate free space. Expensive — requires relocating all processes.

2. Fragmentation

Type	Definition	Occurs in	Solution
Internal	Wasted space inside allocated block	Fixed partitions, Paging	Smaller page size (tradeoff: larger page table)
External	Total free memory enough but not contiguous	Variable partitions, Segmentation	Compaction, Paging

Internal fragmentation in paging:
Process size = 18,500 bytes. Page size = 4096 bytes.
Pages needed = ⌈18500/4096⌉ = 5 pages (5 × 4096 = 20,480 bytes allocated).
Internal fragmentation = 20,480 − 18,500 = 1,980 bytes.

3. Paging

Key idea: Divide physical memory into fixed-size frames. Divide logical memory into same-size pages. Map pages to frames via page table.

No external fragmentation (any free frame can be used).
Internal fragmentation: last page may be partially filled.

Terminology:
Page size = Frame size = 2^k bytes (always power of 2).
Logical address space: 2ⁿ bytes → n-bit logical address.
Physical memory: 2^m bytes → m-bit physical address.
Number of pages = 2^n−k. Number of frames = 2^m−k.

4. Address Translation in Paging

Logical address (n bits):
[Page number (p) — upper n−k bits] [Offset (d) — lower k bits]

Translation:
1. Extract p = logical_address / page_size (or upper n−k bits).
2. Extract d = logical_address mod page_size (or lower k bits).
3. Look up page table: frame_number f = page_table[p].
4. Physical address = f × page_size + d.

Example: Page size = 1KB = 1024 bytes = 2¹⁰. Logical address = 3500.
p = 3500 / 1024 = 3 (page 3). d = 3500 mod 1024 = 428 (offset 428).
If page_table[3] = frame 7: Physical address = 7 × 1024 + 428 = 7596.

5. TLB & Effective Access Time

TLB (Translation Lookaside Buffer): Fast associative cache for recent page table entries. Typical size: 64–1024 entries. Hit ratio h: typically 90–99%.

TLB Hit: Frame found in TLB. Accesses = 1 (TLB) + 1 (data) = t_TLB + t_m
TLB Miss: Must access page table in memory. Accesses = 1 (TLB miss) + 1 (page table) + 1 (data) = t_TLB + 2t_m

EAT = h × (t_TLB + t_m) + (1−h) × (t_TLB + 2t_m)
Simplify: EAT = t_TLB + t_m + (1−h) × t_m = t_TLB + (2−h) × t_m

Example: h=0.90, t_TLB=10ns, t_m=100ns.
EAT = 0.90(10+100) + 0.10(10+200) = 0.90(110) + 0.10(210) = 99 + 21 = 120 ns.
Without TLB: 2 × 100 = 200 ns. With TLB: 120 ns. Speedup significant.

6. Page Table Size

Number of page table entries = Virtual address space / Page size = 2ⁿ / 2^k = 2^n−k
Page table size = Number of entries × Entry size

Example: 32-bit virtual address, 4KB page size, 4-byte entry:
Entries = 2³²/2¹² = 2²⁰ = 1,048,576 entries.
Page table size = 2²⁰ × 4 = 4MB per process.
With 100 processes: 400MB just for page tables! Problem → solution: multilevel paging.

Entry size calculation: Must hold frame number. If physical memory = 2^m, frame number needs m−k bits. Remaining bits = valid, dirty, reference, protection flags.

7. Multilevel Paging

Idea: Page the page table itself. Only the portions of the page table that are needed are kept in memory.

Two-level paging (32-bit, 4KB pages, 4B entries):
Logical address: [p1 (10 bits)] [p2 (10 bits)] [offset (12 bits)]
Translation: outer page table[p1] → inner page table[p2] → frame → physical address.
Memory accesses (without TLB): 3 (outer PT + inner PT + data).

k-level paging: k+1 memory accesses per reference without TLB.
With TLB: TLB caches the final (p → frame) mapping — still 2 accesses on hit.

Inverted page table: One entry per physical frame (not per virtual page). Space = O(physical memory). Search time O(n) — use hash table for O(1) avg.

8. Segmentation

Memory divided into variable-size segments (code, data, stack, heap). Each has a base and limit.

Logical address: <segment number s, offset d>
Translation: Check d < segment_table[s].limit (else trap). Physical = segment_table[s].base + d.

vs Paging:

Property	Paging	Segmentation
Division	Fixed-size pages	Variable-size segments
Internal fragmentation	Yes (last page)	No
External fragmentation	No	Yes
User visibility	Transparent	User-defined segments
Sharing	Page sharing possible	Segment sharing easy (e.g., shared code segment)

Segmented paging: Combine both — segments divided into pages. Eliminates both fragmentation types.

9. GATE Examples

GATE 2019 — Address translation:
Page size = 512 bytes. Logical address = 2500. Page table: page 0→frame 3, page 1→frame 7, page 2→frame 2, page 3→frame 4, page 4→frame 5.
p = 2500/512 = 4 (page 4). d = 2500 mod 512 = 452.
Frame 5. Physical = 5×512+452 = 2560+452 = 3012.

GATE 2021 — EAT calculation:
TLB access = 20ns. Memory access = 100ns. TLB hit ratio = 80%.
EAT = 0.8(20+100) + 0.2(20+200) = 0.8(120) + 0.2(220) = 96 + 44 = 140 ns.

GATE 2022 — Page table size:
64-bit virtual address, 4KB page (12-bit offset), 8-byte page table entry.
Entries = 2⁶⁴⁻¹² = 2⁵². Size = 2⁵² × 8 = 2⁵⁵ bytes = 32 PB per process.
This is why 64-bit systems use 4-level or 5-level paging in practice.

10. Common Mistakes

Confusing page size with number of pages: Page size is in bytes (e.g., 4KB). Number of pages = virtual address space / page size. These are very different quantities.
EAT formula with/without TLB access time: Some formulations include t_TLB in both hit and miss. Always check which formula GATE uses — verify by re-reading the question. When in doubt, add t_TLB to both.
Multilevel paging memory accesses: 2-level paging = 3 memory accesses (outer PT + inner PT + data). k-level = k+1 accesses. TLB reduces this to 2 (TLB lookup + data) on hit.
Internal vs external fragmentation: Paging causes internal (last page not full); segmentation causes external (scattered free space). Both together (segmented paging) eliminate both.
Physical address formula: Physical = frame × page_size + offset. A common error is using page number instead of frame number, or adding instead of multiplying.

11. FAQ

What is the difference between internal and external fragmentation?: Internal fragmentation is wasted space inside an allocated memory block — e.g., a 4KB page given to a process that only needs 3.5KB wastes 0.5KB. External fragmentation is when total free memory is sufficient but it is not contiguous — many small free holes exist but no single hole is large enough. Paging eliminates external fragmentation; segmentation eliminates internal fragmentation.
How is a virtual address translated to a physical address using paging?: Divide the virtual address into page number p (upper bits) and offset d (lower k bits, where page size = 2^k). Use p as index into the page table to get frame number f. Physical address = f × page_size + d. Since page size is a power of 2, you can also concatenate frame number bits with offset bits to form the physical address directly.
What is the effective memory access time with TLB?: EAT = h × (t_TLB + t_mem) + (1−h) × (t_TLB + 2×t_mem), where h is TLB hit ratio. On a TLB hit, only one memory access is needed (the TLB gives the frame directly). On a miss, one extra access to the page table in memory is required before accessing the data. TLB access time t_TLB is typically much smaller than t_mem (e.g., 5–20ns vs 100ns).
What is the size of a page table?: Page table size = (virtual address space / page size) × entry size. For a 32-bit system with 4KB pages and 4-byte entries: 2^32/2^12 = 2^20 entries × 4 bytes = 4MB per process. This is why multilevel paging is used — unused portions of the page table don’t need to be kept in memory, saving space for processes with sparse address spaces.

Memory Management in OS – Paging, Segmentation and TLB | GATE CS