Two numerical families dominate the virtual memory questions in GATE CS: page table size arithmetic and effective memory access time (EMAT) with a TLB. They are usually set as NAT questions, so there is no option elimination to save you, and a single bit counted wrong costs the full mark. This post works both families to the byte, including the multi-level page table extension where most attempts go wrong.
Page table size: the three formulas that decide everything
Paging splits every virtual address into two fields: a virtual page number (VPN) and an offset within the page. The page size fixes the offset width, the remaining address bits fix the number of pages, and the number of pages fixes the number of page table entries (PTEs). Every size numerical in this topic is some rearrangement of the table below.
Quantity | Formula |
|---|---|
Offset bits | log2(page size) |
Number of pages (PTE count) | 2(virtual address bits − offset bits) |
Page table size | number of entries × size of one entry |
Entries per page (multi-level) | page size ÷ PTE size |
Number of levels | ceil(VPN bits ÷ bits resolved per level) |
One discipline saves most mistakes: the number of entries comes from the virtual address, while the width of each entry comes from the physical address (the entry must hold a frame number). Mixing these two is the single most common error in this numerical.
Worked example 1: single-level page table size
A machine has a 32-bit virtual address, 4 KB pages, and 4-byte page table entries. Find the page table size per process.
4 KB = 212 bytes, so the offset is 12 bits.
VPN = 32 − 12 = 20 bits, so the table has 220 entries (about a million).
Page table size = 220 × 4 B = 222 B = 4 MB per process.
That is 4 MB of page table per process before it touches a byte of data; a hundred processes would need 400 MB. This cost is exactly why multi-level page tables exist.
Worked example 2: deriving the PTE size yourself
Many questions refuse to hand you the entry size. Suppose the physical address is 34 bits, pages and frames are 4 KB, and each entry stores the frame number plus a valid bit and a dirty bit.
Frame number width = 34 − 12 = 22 bits.
Add the 2 control bits: 22 + 2 = 24 bits.
Assuming byte-packed entries and no extra alignment or architecture bits, round to whole bytes: each PTE is 3 bytes.
If the question asks for the answer in bits, stop at step 2. Read which unit the NAT box wants before you type.
Multi-level page tables: computing the number of levels
A 4 MB single-level table has to sit in contiguous physical memory, which defeats the point of paging. The fix is to page the page table itself: chop it into page-sized pieces and build an outer table that points to them. The rule that generates every levels numerical: each piece of the page table must fit in exactly one page. Entries per page = page size ÷ PTE size, and each level resolves log2 of that many bits.
Worked example 3: how many levels for the 32-bit machine
Same system as example 1: 32-bit virtual address, 4 KB pages, 4-byte PTEs.
Entries per page = 4 KB ÷ 4 B = 1024 = 210, so each level resolves 10 bits.
VPN = 20 bits, so levels = ceil(20 ÷ 10) = 2 levels.
The virtual address splits as 10 (outer index) + 10 (inner index) + 12 (offset).
Check the outer table: 210 entries × 4 B = 4 KB, exactly one page. That clean fit is your built-in sanity check.
Worked example 4: the 48-bit case
A machine has a 48-bit virtual address, 4 KB pages, and 8-byte PTEs.
Offset = 12 bits, so VPN = 48 − 12 = 36 bits.
Entries per page = 4096 ÷ 8 = 512 = 29, so each level resolves 9 bits.
Levels = ceil(36 ÷ 9) = 4 levels, splitting the address as 9 + 9 + 9 + 9 + 12.
This matches the classic four-level x86-64 layout for 48-bit virtual addresses; systems using five-level paging or different page sizes split the address differently.
One conceptual line worth remembering: multi-level tables do not shrink the worst case (a fully mapped 32-bit space still needs 4 KB of outer plus 4 MB of inner tables). They win because unmapped regions of a sparse address space need no inner tables at all.
EMAT with a TLB: the hit ratio formula, solved
Every page table level adds one extra memory access on the translation path, so hardware caches translations in the TLB (translation lookaside buffer). Let the TLB lookup take c, one memory access take m, the hit ratio be h, and the page table have k levels. With a sequential lookup and no page faults:
EMAT = h × (c + m) + (1 − h) × (c + (k + 1) × m)
On a hit you pay the TLB search plus the data access. On a miss you pay the TLB search, k memory accesses to walk the page table, and then the data access.
Worked example 5: single-level EMAT
TLB access takes 10 ns, a memory access takes 100 ns, and the hit ratio is 90 percent, with a single-level page table.
Hit path = 10 + 100 = 110 ns.
Miss path = 10 + 100 + 100 = 210 ns.
EMAT = 0.9 × 110 + 0.1 × 210 = 99 + 21 = 120 ns.
Worked example 6: the same system with a two-level table
Only the miss path changes: 10 + 100 + 100 + 100 = 310 ns. EMAT = 0.9 × 110 + 0.1 × 310 = 99 + 31 = 130 ns.
Each extra page table level costs only (1 − h) × m, which is 10 ns here, not a full 100 ns. A good TLB is what makes multi-level translation affordable, and a GATE-style question can test exactly this comparison.
The classic trap is the wording of the TLB path. Some questions state that the TLB is searched in parallel with the page table access, or that hit time is negligible; then the hit path is just m and the formula changes. Others fold a page fault rate p on top, giving EMAT with faults = (1 − p) × EMAT + p × (page fault service time). Do not paste a memorised formula. Rebuild the hit path and the miss path from the question's own words, then take the weighted average.
How GATE tests page table and EMAT numericals
These appear as NAT questions asking for an exact size in bytes or an exact time in nanoseconds. Four traps account for most lost marks: For cycle-specific paper rules and scoring, use the official GATE portal.
Answering PTE size in bits when the question asked bytes, or the reverse.
Using physical address bits to count entries (entries come from the virtual side; entry width comes from the physical side).
Forgetting that a k-level table costs k extra accesses on a TLB miss, not one.
Not checking whether the TLB time is charged on both paths, only the miss path, or ignored.
Where this sits in the wider syllabus is mapped in our Operating Systems for GATE breakdown. To drill the theory with worked solutions, the Operating System, Memory Management learn module covers exactly this ground, backed by a large published question bank across the GATE subjects.
For cycle-specific paper rules and scoring, use the official GATE portal.
The short version, and where to drill it
Four lines carry the whole topic. Offset bits come from the page size. Entry count comes from the virtual address, entry width from the physical address. Levels = ceil(VPN bits ÷ bits per level), where bits per level come from how many PTEs fit in one page. EMAT = h × (hit path) + (1 − h) × (miss path), built from the question's own wording.
Then confirm it under a clock. The GATE Test Series has 46 tests, with subject-wise grand tests on Operating Systems and seven full-length mocks, so you meet this numerical under exam pressure before the real paper does it for you. Everything else in your preparation starts from the GATE category page.
Solve examples 1 through 6 by hand once, without looking at the steps. If your six answers match, this numerical is no longer a risk. It is marks you have already banked.
