# Paging and virtual memory: GATE CS question with solution

From the GATE Daily set of 26 October 2026, question 9 of 10 (https://gatedaily.in/q/2026-10-26-three-level-page-table-two-regions-memory/). Difficulty: hard.

### Q.9 · Operating Systems · Paging and virtual memory · NAT, 2 marks (answer with a number)

A system uses 39-bit virtual addresses, a page size of 4 KB and a three-level page table ($1\text{ KB} = 2^{10}$ bytes, $1\text{ MB} = 2^{20}$ bytes). A page-table entry is 8 bytes at every level, and every page table at every level occupies exactly one page.

The outermost (first-level) table is allocated when a process is created. A second-level or third-level table is allocated only if it contains at least one valid entry.

A process has exactly two regions of its virtual address space mapped, and every page in both regions is valid:

- a code-and-data region from virtual address 1 MB up to, but not including, 7 MB;
- a stack occupying the highest 1 MB of the virtual address space.

The total memory occupied by this process's page tables, over all three levels, is ______ KB.

(Answer in integer)

**Answer:** 32

**Solution.** **Method: find what one table at each level maps, then count the tables each region touches.**

Entries per table $= 4096 / 8 = 512 = 2^9$, so each level uses 9 index bits: $9 + 9 + 9 + 12 = 39$ bits.

- One third-level table maps 512 pages $= 512 \times 4\text{ KB} = 2$ MB.
- One second-level table maps $512 \times 2\text{ MB} = 1$ GB.
- The first-level table maps $512 \times 1\text{ GB} = 512$ GB, the whole space.

*Region 1, $[1\text{ MB}, 7\text{ MB})$.* It lies inside the first 1 GB, so it needs **one** second-level table. Third-level tables are aligned on 2 MB boundaries: the region touches $[0, 2)$, $[2, 4)$, $[4, 6)$ and $[6, 8)$ MB, so it needs **four** third-level tables, not three.

*Region 2, top 1 MB.* It lies in the last 1 GB, a different second-level table (**one** more), and inside the last 2 MB block (**one** more third-level table).

Tables: $1 + 2 + 5 = 8$ pages, so $8 \times 4 = 32$ KB.

**Traps.**

- Dividing 6 MB by 2 MB gives 3 third-level tables. The region starts at 1 MB, not on a 2 MB boundary, so it straddles four blocks. That slip gives 28 KB.
- The regions lie in the first and last 1 GB spans of the address space, so they need different second-level tables. Sharing one also gives 28 KB.
- Forgetting the always-present first-level table gives 28 KB too.

**What was tested:** the span of one table at each level of a hierarchical page table, and alignment of mapped regions to those spans.

**Remember:** In a hierarchical page table, a table at level k maps a fixed aligned span of the address space (here 2 MB, 1 GB, 512 GB). Count the aligned spans a region overlaps, not its size divided by the span.