Official PYQ · 2013Q52Memory Management and Virtual MemoryMCQ1 mark

GATE CS 2013 Q52 — Memory Management and Virtual Memory

A computer uses $46\text{-bit}$ virtual address, $32\text{-bit}$ physical address, and a three–level paged page table organization. The page table base register stores the base address of the first-level table $\text{(T1)}$ , which occupies exactly one page. Each entry of $\text{T1}$ stores the base address of a page of the second-level table $\text{(T2)}$ . Each entry of $\text{T2}$ stores the base address of a page of the third-level table $\text{(T3)}.$ Each entry of $\text{T3}$ stores a page table entry $\text{(PTE)}.$ The $\text{PTE}$ is $32$ bits in size. The processor used in the computer has a $1\;\textsf{MB}\; 16$ way set associative virtually indexed physically tagged cache. The cache block size is $64$ bytes.

What is the size of a page in $\textsf{KB}$ in this computer?

View worked solution

Answer: C

Let the page size be $2^p$ bytes. Thus, the page offset requires $p$ bits.

Since the virtual address is $46$ bits, the Virtual Page Number (VPN) has $46 - p$ bits. This VPN is split into three parts for the three-level page table: $d_1$ bits for $\text{T1}$ , $d_2$ bits for $\text{T2}$ , and $d_3$ bits for $\text{T3}$ . Therefore:

d_1 + d_2 + d_3 = 46 - p

The size of a Page Table Entry (PTE) is $32\text{ bits} = 4\text{ bytes} = 2^2\text{ bytes}$ . Assuming the entry size at all levels of the page table is $4$ bytes:

Since $\text{T1}$ occupies exactly one page, its size is $2^p$ bytes. The number of entries in $\text{T1}$ is $2^{d_1} = \frac{2^p}{4} = 2^{p-2}$ , which gives $d_1 = p - 2$ .
Similarly, to index a single page of the next level table, we have $d_2 = p - 2$ and $d_3 = p - 2$ .