Paging, Multi-Level Page Tables & The TLB
“Translating logical addresses, calculating page table sizes, and computing Effective Memory Access Time (EMAT).”
1.The Fundamental Problem: External Fragmentation
§ 6.1.Early operating systems allocated contiguous physical memory blocks to processes. As processes loaded, terminated, and departed, free memory was carved into hundreds of tiny, disconnected holes. Even if total free memory was 20 MB, a new 5 MB process could not load because no single contiguous hole of 5 MB existed. This is External Fragmentation.
To eradicate external fragmentation, modern computer architecture invented Paging.
In paging, physical memory is divided into fixed-size blocks called Frames, and logical (virtual) memory is divided into blocks of the exact same size called Pages (typically 4 KB). Any virtual page can now be placed into ANY available physical frame anywhere in physical RAM.
A virtual address is the address generated by a process; a physical address is the location in RAM. The page table maps the virtual page number (p) to a frame number (f). Each page-table entry (PTE) stores that frame mapping plus control bits such as a valid bit, protection bits, and a dirty bit. The page offset (d) is copied unchanged during translation.
If the PTE says the page is not resident, the hardware raises a page fault. The operating system then loads the page from secondary storage, chooses a free frame or victim page, updates the PTE, and restarts the interrupted instruction. This is demand paging: pages are brought into RAM when referenced rather than loading eagerly.
A TLB (Translation Lookaside Buffer) caches recent page-to-frame translations. A TLB hit avoids a page-table walk; a TLB miss requires consulting the page table in RAM.
2. Virtual address to physical address
[ VIRTUAL ADDRESS ]
┌──────────────────────┬──────────────┐
│ page number (p) │ offset (d) │
└──────────┬───────────┴──────┬───────┘
│ │ copied unchanged
▼ │
┌────────────┐ │
│ TLB │ │
└─────┬──────┘ │
hit│ miss │
▼ │
┌────────────┐ │
│ Page table │ p → frame│
└─────┬──────┘ │
▼ ▼
┌──────────────────────┬──────────────┐
│ frame number (f) │ offset (d) │
└──────────────────────┴──────────────┘
[ PHYSICAL ADDRESS ]3. Address Translation Mechanics in Paging
| Virtual Address Size32 bits (4 GB virtual memory) | Page Size4 KB = 2^12 bytes | Physical RAM Size512 MB = 2^29 bytes |
Since page size is 4 KB = 2^12 bytes, the offset requires 12 bits in both logical and physical addresses.
The remaining higher-order bits identify which page of the process is being referenced.
In physical memory (512 MB = 2^29 bytes), with 12-bit offset, the frame bits identify the physical frame.
4. Effective Memory Access Time (EMAT) with TLB
| TLB Hit Ratio (h)0.90 | TLB Access Time10 ns | Memory Access Time100 ns |
On a hit, the translation is found in the TLB (10 ns). Then, one main memory access is made to fetch the actual operand/data (100 ns).
On a miss, we search TLB (10 ns), then access main memory to read the Page Table Entry (100 ns), then access main memory again to fetch the actual data (100 ns).
Weighted average of hit and miss times.
5. GATE Lens & Exam Practice
Syllabus focus, recurring numerical patterns, common traps, and clearly labelled exam practice. Questions remain source-pending until an official paper and answer key are attached.
Paging address translation, multi-level page table size calculations, and EMAT equations are recurring GATE-style problem patterns. Verify historical frequency against the official paper archive.
- •Determining the minimum number of levels required in a hierarchical page table so that each page table fits inside a single frame.
- •Calculating EMAT with TLBs, multi-level page tables, and page fault rates.
- •Don't forget that Page Table Size = (Number of Entries) * (Page Table Entry Size in bytes).
- •In Multi-Level paging with k levels, each TLB miss requires k + 1 memory accesses, not 2!
Exam Practice / Source Verification Required
1 problemConsider a system with a two-level paging scheme. The TLB search time is 20 ns and main memory access time is 100 ns. The TLB hit ratio is 80%. What is the effective memory access time (in ns)?
6. 1-Minute Panic Revision
“Paging eliminates external fragmentation. Virtual Address = Page Number (p) + Offset (d). Physical Address = Frame Number (f) + Offset (d).”
- •Page Offset bits = log2(Page Size).
- •Number of Page Table Entries = 2^(Virtual Address Bits - Offset Bits).
- •Page Table Size = (Number of Entries) * (PTE size in bytes).
- •EMAT = h(t_tlb + t_m) + (1-h)(t_tlb + (k+1)*t_m) for k-level paging.
- •Paging STILL suffers from INTERNAL fragmentation (on the very last frame of a process, avg 1/2 page size).
- •Offset bits never change between virtual and physical addresses.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Official slides on page tables, frame allocation, Translation Lookaside Buffer (TLB), and multi-level hierarchy.
Free chapter PDF detailing virtual page number (VPN) to physical frame number (PFN) mapping and page table entries.
Full chapter analyzing TLB hit vs miss algorithms, context switch TLB invalidation, and TLB coverage.
If the textbook derivation did not click immediately, consult these targeted video lessons:
First-principles explanation of logical vs physical address spaces, page size = frame size, and why paging eliminates external fragmentation.
Breakdown of how to fit page tables within a frame and calculate total paging levels without memory waste.
Curated lectures on Logical-to-Physical Translation, Page Tables, TLBs, Multi-level Paging & Internal Fragmentation:
Crystal-clear mental models of base register indexing and physical frame lookup.
Definitive step-by-step formula derivation for multi-level address bit partitioning.
Blackboard mathematical rigor on single-level and multi-level TLB penalty calculations.
Intense numerical drilling on calculating exact memory consumption of hierarchical tables.