GATE Daily

Monday26 October 2026

GATE CS & IT · 2027 · Ten questions a day

Past sets26 Oct 2026OS

Paging and virtual memory: GATE CS question with solution

Q.9

A system uses 39-bit virtual addresses, a page size of 4 KB and a three-level page table ( bytes, 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)

One try. It counts in your 26 Oct 2026 set.
Show solution
RememberIn 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.

Solution NAT · 2 marks · no negative marking

Answer: 32

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

Entries per table , so each level uses 9 index bits: bits.

  • One third-level table maps 512 pages MB.
  • One second-level table maps GB.
  • The first-level table maps GB, the whole space.

Region 1, . 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 , , and 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: pages, so 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.

Copied. Paste it into the new chat.Too long to send. Copy the question and solution by hand.