GATE CS 2021 Set 2 Q.58 (CS Q.48): Memory Management and Virtual Memory

Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below.

A 39-bit virtual address bit layout divided into four fields: Level 1 offset of 9 bits, Level 2 offset of 9 bits, Level 3 offset of 9 bits, and Page offset of 12 bits. — 39-bit virtual address breakdown

The page size is 4KB ( $1\text{ KB} = 2^{10}\text{ bytes}$ ) and page table entry size at every level is 8 bytes. A process $P$ is currently using 2GB ( $1\text{ GB} = 2^{30}\text{ bytes}$ ) virtual memory which is mapped to 2GB of physical memory. The minimum amount of memory required for the page table of $P$ across all levels is ______ KB.

Your answer

Official answer and solution

Official answer: 4108
From: Official GATE 2021 answer key

Solution

Calculate the number of pages mapped, determine the number of page table frames required at each level for minimum fragmentation, and sum their sizes.

The 39-bit virtual address breakdown is:

Level 1 index: 9 bits ( $2^9 = 512$ entries per L1 table)
Level 2 index: 9 bits ( $2^9 = 512$ entries per L2 table)
Level 3 index: 9 bits ( $2^9 = 512$ entries per L3 table)
Page offset: 12 bits ( $2^{12} = 4096\text{ bytes} = 4\text{ KB}$ page size)

Size of each page table:
Each page table at any level has 512 entries, and each entry is 8 bytes:

\text{Size of one page table} = 512 \times 8\text{ bytes} = 4096\text{ bytes} = 4\text{ KB}

The process uses $2\text{ GB} = 2^{31}\text{ bytes}$ of memory. The number of virtual pages used is:

\text{Number of pages} = \frac{2^{31}}{2^{12}} = 2^{19}\text{ pages}

To minimize the number of page tables, assume the $2^{19}$ pages are placed contiguously in virtual address space:

Level 3: Each Level 3 table maps 512 pages ( $2^9$ ). The number of Level 3 page tables needed is: $\frac{2^{19}}{2^9} = 2^{10} = 1024\text{ Level 3 tables}$
Level 2: Each Level 2 table points to 512 Level 3 tables. To point to 1024 Level 3 tables: $\left\lceil \frac{1024}{512} \right\rceil = 2\text{ Level 2 tables}$
Level 1: A single root Level 1 table can hold 512 entries, which easily accommodates the 2 entries pointing to the 2 Level 2 tables: $1\text{ Level 1 table}$

Total number of page tables across all three levels:

\text{Total tables} = 1024 + 2 + 1 = 1027\text{ tables}

Total memory required for the page table:

\text{Total memory} = 1027 \times 4\text{ KB} = 4108\text{ KB}

Final answer

4108

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

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 58 of 65, printed as CS Q.48
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.

Question

Solution

Source