Multilevel page tables and sparse address spaces

Goals and conventions

Build a two-level address split, count only required lower-level tables, and calculate a page-walk cost without confusing metadata with application data. Prerequisite: the memory-management lesson's page number/offset and flat-table arithmetic. We use byte addressing, KiB=2^10 bytes, MiB=2^20 bytes, zero-based indices, and a conventional per-process two-level table. Page-table blocks are resident in RAM, and all requested mappings in examples are valid and permitted. There are no huge pages, inverted tables or translation faults in the main model.

1. A catalogue with optional volumes

A single giant catalogue reserves a line for every possible book even when most shelves are unused. A directory of optional catalogue volumes can leave empty sections without allocating their volumes. Similarly, a multilevel page table stores a top-level directory and allocates lower-level tables only for virtual regions that need mappings. An absent directory entry can represent an unmapped whole region. This saves metadata for sparse address spaces; it does not change the page offset or make the application data itself free.

The tradeoff is a longer walk on a translation-cache miss. A multilevel table does not necessarily save space for a fully populated address space, because its upper levels are additional metadata. Nor does one mapped data page always require one distinct lower-level table: many nearby virtual pages share a table.

2. Derive the bit split

Take 32-bit virtual byte addresses, 4 KiB pages, 4-byte directory entries and 4-byte leaf entries. Each page-sized table holds 4096/4=1024=2^10 entries. The offset needs 12 bits. There are 32−12=20 virtual page-number bits, split as 10 directory bits and 10 leaf-table bits. Thus the address layout, high to low, is directory[10] | leaf[10] | offset[12]. The 4-byte entry size is the storage occupied by an entry; it is not a four-bit frame number.

A single leaf table maps 1024 pages, or 1024×4096=4 MiB of virtual address space. The directory has 1024 entries and spans 1024×4 MiB=4 GiB, matching 2^32 bytes. The coverage of a table is not its own size: each leaf occupies 4 KiB but describes a 4 MiB region.

3. Worked translation through both levels

Use virtual address 0x0040307A, whose decimal value is 4,206,714. Divide by 4096: VPN=1027 and offset=122 (0x07A). Divide VPN by 1024: directory index=1, leaf index=3. First read directory entry 1 to locate the leaf table, then read that table's entry 3 to find the data frame. If it gives physical frame 9, the data address is 9×4096+122=36,986.

The directory entry's frame number locates a page-table page; it is not automatically the final data frame. A common error uses the first-level result as the application address and skips the leaf lookup. Another error reuses a physical frame number as a virtual index. Keep each level's role explicit.

4. Sparse tables: group by directory index

Suppose exactly virtual pages {0,1,1023,1024,2048} are mapped, and the implementation allocates only necessary leaf tables plus one root directory. Compute floor(VPN/1024): pages 0,1,1023 share directory index 0; page 1024 uses index 1; page 2048 uses index 2. Thus three leaf tables are needed, not five. Metadata=one root+three leaves=4×4096=16384 bytes=16 KiB. Five data pages consume 20 KiB separately. Combined table-plus-data allocation is 36 KiB under this model, excluding all other structures.

A full flat table for the same virtual address width needs 2^20 entries×4 bytes=4 MiB even if only these five pages are mapped. The multilevel structure's advantage here comes from sparsity. If all 1024 leaf tables are allocated, metadata becomes 1025×4096=4,198,400 bytes=4 MiB+4 KiB, slightly larger than the flat table. “Multilevel always uses less memory” is false.

A region that crosses a 4 MiB boundary may require two leaf tables even if its byte size is small. For example, pages 1023 and 1024 are adjacent but use different directory entries. Count distinct higher-level indices rather than dividing only the total number of mapped pages by 1024 and rounding.

5. Walk cost and TLB hits

Assume no relevant caches except a TLB. A TLB hit directly supplies the final translation and needs one data-memory access. A miss needs directory read, leaf read and data read: three memory accesses. The root-table address is known from a register; do not invent another memory read to obtain it. If table pages could themselves fault, the simple cost model would no longer suffice.

Worked timing: serial TLB lookup is 5 ns, each memory read 100 ns and hit rate is 0.9. Hit cost=5+100=105 ns. Miss cost=5+3×100=305 ns. Effective time=0.9×105+0.1×305=125 ns. The single-level formula from the earlier lesson cannot be copied unchanged because a miss now traverses two table levels. Hardware walk caches or overlapping lookup can change actual costs; the question's model controls the arithmetic.

6. Different structures answer different counts

A conventional per-process table organizes entries around virtual pages. An inverted page table instead organizes entries around physical frames and needs information to identify the owning address-space/page mapping, often with a lookup mechanism such as hashing. Do not use physical-frame count to size the conventional virtual-indexed table in this lesson. Huge pages and mixed page sizes also change offsets and coverage; neither is silently assumed here.

Exam checklist

Derive entries per table from block bytes divided by entry bytes. Separate address bits into levels plus offset. Count distinct occupied index prefixes for sparse tables, include the root once and keep table pages separate from data pages. Write every miss-path access before forming an average, and state residency/cache assumptions.

Original practice: six single-correct MCQs

Choose exactly one option. Each question states its own required assumptions.

PT01. A 32-bit virtual byte address uses 4 KiB pages and page-sized two-level tables with 4-byte entries at both levels. What is directory/leaf/offset bit split?

A. 12/10/10 B. 10/10/12 C. 8/12/12 D. 10/12/10

Answer: B

A: 4 KiB pages require 12 offset bits, not 10.

B: 4096/4=1024 entries need 10 bits per level; offset needs 12.

C: A leaf of 4-byte entries in 4 KiB has 1024 entries, not 4096.

D: The offset would describe 1 KiB rather than 4 KiB pages.

PT02. A leaf table has 1024 entries, each mapping one 4 KiB virtual page. How much virtual address space does it cover?

A. 4 KiB B. 1 MiB C. 4 MiB D. 4 GiB

Answer: C

A: 4 KiB can be the leaf’s own storage, not its coverage.

B: This undercounts 1024×4 KiB.

C: 1024×4096=2^22 bytes=4 MiB.

D: 4 GiB is coverage of all 1024 such leaves.

PT03. Two-level tables have 1024 leaf entries each and occupy 4 KiB per table. Only VPNs 0,1,1023,1024,2048 are mapped. Allocate one root and only necessary leaf tables. What is table metadata size?

A. 12 KiB B. 16 KiB C. 20 KiB D. 24 KiB

Answer: B

A: 12 KiB counts three leaves but omits the root.

B: Directory indices are 0,0,0,1,2: three leaves plus one root=16 KiB.

C: 20 KiB is the five data pages, not table metadata.

D: 24 KiB incorrectly creates a separate leaf for every data page.

PT04. For 4 KiB pages and a 10/10/12 split, virtual address 0x0040307A maps through directory entry 1 and leaf entry 3 to frame 9. What is its physical byte address?

A. 36986 B. 4206714 C. 36864 D. 12410

Answer: A

A: Offset=0x07A=122; 9×4096+122=36986.

B: This is the original virtual address.

C: 36864 is frame 9 base with the byte offset omitted.

D: 12410 uses leaf index 3 as if it were the mapped frame.

PT05. Serial TLB lookup=5 ns, RAM read=100 ns, hit rate=0.9. A hit needs one RAM data read; a two-level miss needs directory, leaf and data reads. No other cache or faults. Effective time?

A. 105 ns B. 115 ns C. 125 ns D. 305 ns

Answer: C

A: 105 ns is only the hit path.

B: 115 ns would use a one-level miss costing 205 ns.

C: 0.9×105+0.1×305=125 ns.

D: 305 ns is only the miss path.

PT06. A two-level structure has one 4 KiB root and all 1024 leaf tables allocated, each 4 KiB. Compared with a 4 MiB flat table, how large is its table metadata?

A. Exactly 4 MiB B. 4 MiB plus 4 KiB C. Only 4 KiB D. 4 MiB minus 4 KiB

Answer: B

A: This omits the extra root directory.

B: 1024 leaves use 4 MiB; the root adds 4 KiB.

C: This counts only the root.

D: The root adds metadata rather than removing it.

Sources and scope

This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.

• Official GATE 2026 CS syllabus, Section 8
• OSTEP: Advanced Page Tables
• OSTEP: Translation Lookaside Buffers

Sources checked 2026-10-14.