GATE CS Mastery
Cheat sheets

GATE CS 2023 · Operating Systems

Question 58

NAT2 marksNo negative markingEasy (estimate)

Question

Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with LL levels for virtual to physical address translation. The page size is 4 KB (1 KB=1024 B1\text{ KB} = 1024\text{ B}) and a page table entry at any of the levels occupies 8 bytes.

The value of LL is _______.

Official answer and solution
Official answer
5
From
Official GATE 2023 answer key

Solution

Calculate the page offset bits and index bits per page table level for the 57-bit address space.

  1. Page Offset:
    Page size = 4 KB=212 bytes  ⟹  4\text{ KB} = 2^{12}\text{ bytes} \implies page offset requires 12 bits.
  2. Virtual Page Number (VPN):
    Virtual address length = 57 bits.
    Bits remaining for page table translation: 57−12=45 bits57 - 12 = 45\text{ bits}.
  3. Page Table Entry (PTE) Capacity:
    Each page table is exactly one page (4 KB=4096 bytes4\text{ KB} = 4096\text{ bytes}). With each PTE occupying 8 bytes8\text{ bytes}:
    Number of entries per page table=4096 B8 B=512=29\text{Number of entries per page table} = \frac{4096\text{ B}}{8\text{ B}} = 512 = 2^9
    Therefore, each level of the page table hierarchy uses log⁡2(512)=9\log_2(512) = 9 bits of the virtual address.
  4. Number of Levels (LL):
    L=45 bits9 bits/level=5 levelsL = \frac{45\text{ bits}}{9\text{ bits/level}} = 5\text{ levels}
Final answer

5

Common trap

Dividing 57 directly by 9 without subtracting the 12 page offset bits first.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2023 Computer Science and Information Technology (CS)
Question
58 of 65
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.