Multilevel Paging MCQs: 12 Solved Questions with Explanations

The earlier Memory & Paging MCQs set covers basics, hierarchy, protection and mixed paging. These 12 questions stay on multilevel page tables: derive address splits, level counts, PTE widths, table occupancy and TLB access time. Solve each on paper before checking the result.

Multilevel paging: build the four-line method before solving

Compute offset = log2(page size), entries = page size/PTE size, then index bits and levels. For 48-bit addresses, 4 KB pages and 8-byte PTEs: offset = 12, entries = 4096/8=2^9, VPN = 36, levels = 36/9=4, split [9|9|9|9|12].

Multilevel-paging levels and address splits: Questions 1-2

Question 1

In Multilevel Paging, how many levels of page tables are used?

• (a) One

• (b) Two

• (c) Three or more

• (d) Variable

Answer: (d) Variable. Designs can use two, three, four or more levels. Address width, page size, PTE size and architecture determine the count.

Question 2

Suppose you have a 47-bit virtual address space with a page size of 16KB and that page table entry takes 8 bytes. How many levels of page tables would be required to map the virtual address space if every page table is required to fit into a single page?

• (a) 2

• (b) 3

• (c) 4

• (d) 5

Answer: (b) 3. A 16 KB page gives a 14-bit offset. Since 16 KB / 8 B = 2^11 entries, the 33 VPN bits need 33 / 11 = 3 levels.

Page-offset and table-level calculations: Questions 3-4

Question 3

A computer with a 32-bit address uses a two-level page table. Virtual addresses are split into a 9-bit top-level page-table field, an 11-bit second-level page-table field and an offset. How large are the pages?

• (a) 2 KB

• (b) 4 KB

• (c) 8 KB

• (d) 16 KB

Asked in: TPSC 2026, Computer Science, System Analyst.

Answer: (b) 4 KB. The indexes use 9 + 11 = 20 bits, leaving a 12-bit offset. Thus page size is 2^12 = 4096 bytes = 4 KB. See the full worked solution.

Question 4

A computer uses 46-bit virtual address, 32-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 (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 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 KB in this computer?

• (a) 2

• (b) 4

• (c) 8

• (d) 16

Asked in: BARC 2013, Computer Science.

Answer: (c) 8 KB. A 2^P-byte page holds 2^(P - 2) four-byte PTEs, so each index uses P - 2 bits. Then 3(P - 2) + P = 46 gives P = 13 and page size 2^13 bytes = 8 KB; cache data is irrelevant. See the full worked solution.

Index-bit calculations: Questions 5-6

Question 5

Assuming a page size of 1 KB and that each page-table entry (PTE) takes 4 bytes, how many page-table levels are required to map a 34-bit virtual address if every page table fits into a single page?

• (a) 2

• (b) 3

• (c) 4

• (d) 5

Answer: (b) 3. A 1 KB page gives 10 offset bits, while 1024 / 4 = 2^8 PTEs give 8 index bits. The 24 VPN bits therefore need 24 / 8 = 3 levels.

Question 6

A computer system supports a logical address space of 2^32 bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a 𝑏-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size.

The value of 𝑏 is ___________ . (Answer in integer)

Asked in: GATE 2025, Computer Science, Set 2.

Answer: 11. The 4096-byte page gives 12 offset bits. The inner table holds 4096 / 8 = 2^9 entries, leaving b = 32 - 12 - 9 = 11. See the full worked solution.

Virtual-address partitions and PTE pointers: Questions 7-8

Question 7

Consider a processor with 50-bit virtual addresses, 32-bit physical addresses and 16 KB pages. Each table at every page-table level occupies one physical-memory page. A page-table entry needs the physical frame number plus 14 special-purpose bits. Which division of the virtual address is correct?

• (a) <12, 12, 12, 14 >

• (b) <6, 10, 10, 10, 14 >

• (c) <10, 12, 14, 14 >

• (d) <14, 12, 10, 14>

Answer: (a) <12, 12, 12, 14>. The offset leaves 32 - 14 = 18 frame bits; adding 14 control bits makes a 32-bit, 4-byte PTE. One 16 KB table holds 2^12 PTEs, so the 36 VPN bits split into three 12-bit indexes.

Question 8

A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows

• Bits 30-31 are used to index into the first level page table

• Bits 21-29 are used to index into the second level page table

• Bits 12-20 are used to index into the third level page table, and

• Bits 0-11 are used as offset within the page

The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively.

• (a) 20, 20 and 20

• (b) 24, 24 and 24

• (c) 24, 24 and 20

• (d) 25, 25 and 24

Asked in: GATE 2008, Computer Science.

Answer: (d) 25, 25 and 24. A frame pointer needs 36 - 12 = 24 bits. Each lower-level table has 2^9 four-byte entries, occupies 2^11 bytes, and needs a 36 - 11 = 25-bit aligned pointer; hence 25, 25 and 24. See the full worked solution.

Physical-space and page-table occupancy: Questions 9-10

Question 9

What is the size of the physical address space in a paging system which has a page table containing 64 entries of 11 bit each (including valid and invalid bit) and a page size of 512 bytes?

• (a) 2^11

• (b) 2^15

• (c) 2^19

• (d) 2^20

Asked in: Indian Space Research Organization 2014, Computer Science.

Answer: (c) 2^19. Removing the valid bit leaves 10 frame bits. Adding the 9-bit offset for a 512-byte page gives 2^(10 + 9) = 2^19 bytes; the 64 entries affect logical span. See the full worked solution.

Question 10

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = 2^10 bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry. An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let X denote the minimum and Y denote the maximum number of pages across the two levels of the page table of the process.

The value of X + Y is ________.

Asked in: GATE 2024, Computer Science, Set 2.

Answer: 1028. Packing 2000 pages needs ceil(2000 / 1024) = 2 inner tables plus one outer, so X = 3. Spreading them can occupy all 1024 inner tables plus the outer, so Y = 1025 and X + Y = 1028. See the full worked solution.

TLB and effective-access-time calculations: Questions 11-12

Question 11

Assume that a main memory access takes 100 ns. If we are using a two-level page table and have a 50% TLB hit ratio, the effective memory access time is (assume no memory cache and no page faults):

• (a) 100 ns

• (b) 200 ns

• (c) 300 ns

• (d) 400 ns

Answer: (b) 200 ns. With no separate TLB time, a hit costs 100 ns and a miss costs 300 ns. Thus 0.5 x 100 + 0.5 x 300 = 200 ns.

Question 12

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns. Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)

• (a) 1.5 ns

• (b) 2 ns

• (c) 3 ns

• (d) 4 ns

Asked in: GATE 2003, Computer Science.

Answer: (d) 4 ns. A TLB hit averages 0.9 x 2 + 0.1 x 12 = 3 ns. A miss averages 0.9 x 22 + 0.1 x 32 = 23 ns after two page-table reads. Therefore 0.96 x 3 + 0.04 x 23 = 3.8 ns, which rounds to 4 ns. See the full worked solution.

Match each mistake to one paging rule

Missed Q1-Q6? Recompute offset, VPN width, entries and index bits. Missed Q7-Q10? Separate PTE width, pointer alignment and occupancy. Missed Q11-Q12? Draw TLB hit/miss paths and count accesses.

Use Virtual Memory and Demand Paging MCQs for demand paging and replacement. Continue with GATE Guidance by Sanchit Sir, the GATE Test Series or the GATE course category.