📝 Hierarchical paging in Structure of the Page Table (18 MCQs)

📖 From Operating System • 8. Main Memory • 18 questions available

←Previous Topic:Shared Pages in Paging of Operating System📝 Hierarchical paging in Structure of the Page TableHashed page tables:Next Topic→

What is Hierarchical paging in Structure of the Page Table?

Definition:
Hierarchical paging organizes page tables in multiple levels to avoid allocating huge contiguous tables for sparse address spaces saving memory.

Example:
Two-level paging with $2^{10}$ entries per level covers $2^{32}$ address space using only $4 \text{ KB} \times 2 = 8 \text{ KB}$ instead of $4 \text{ MB}$ flat table.

Reason:
Multi-level structure matches typical sparse memory usage patterns dramatically reducing page table overhead for large virtual address spaces.

Easy

Medium

Hard

📝 All Hierarchical paging in Structure of the Page Table MCQs

Q1. What is the main advantage of using hierarchical paging over a single‑level page table?

A.It reduces the amount of memory needed for page tables ✅

B.It increases the total virtual address space

C.It eliminates the need for a TLB

D.It simplifies CPU micro‑code

💡 Difficulty: easy | ✅ Correct: A

📖 Explanation: Hierarchical paging divides a large linear page table into several smaller tables, allocating only those second‑level tables that correspond to active virtual pages. This selective allocation cuts down on memory consumption, especially for sparse address spaces. Option A captures this benefit. Options B, C, and D describe effects that do not stem from hierarchical paging: the address space size stays the same, a TLB remains useful, and CPU design is unaffected.

Q2. How does a two‑level hierarchical page table translate a virtual address?

A.The first level gives the physical frame directly

B.The first level provides an index to a second‑level table that contains the frame number ✅

C.Both levels are combined into one large table

D.Translation is done without page tables

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: In a two‑level scheme, the virtual address is split into three fields: a first‑level index, a second‑level index, and an offset. The first‑level index selects an entry that points to a second‑level page table; the second‑level index then yields the physical frame number. Therefore option B correctly describes the process. Option A is wrong because the first level never holds the final frame, C misrepresents the structure, and D ignores the essential role of page tables.

Q3. A system uses a two‑level hierarchical paging scheme with a 16‑bit virtual address, 4 KB page size, and an 8‑bit first‑level index. How many entries does the first‑level page table contain?

A.64

B.128

C.256 ✅

D.512

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: A 4 KB page size corresponds to a 12‑bit offset ( $2^{12}=4096$ ). The remaining 4 bits of the virtual address form the page number, but the design specifies an 8‑bit first‑level index, meaning the first‑level table must have $2^{8}=256$ entries. Option C matches this calculation. Options A and B are too small, while D is larger than required, making them incorrect.

Q4. In a three‑level hierarchical paging system, which level typically holds the final physical frame number?

A.Level 1

B.Level 2

C.Level 3 ✅

D.Level 0

💡 Difficulty: easy | ✅ Correct: C

📖 Explanation: Each level of a hierarchical page table refines the translation: the first level points to a second‑level table, the second points to a third‑level table, and the third level finally contains the physical frame number. Thus the third level (Level 3) stores the actual frame. Options A and B describe earlier steps, and Level 0 is not part of the hierarchy, so they are incorrect.

Q5. Why does hierarchical paging allow operating systems to support sparse address spaces efficiently?

A.It stores only needed second‑level tables ✅

B.It allocates all possible entries in advance

C.It uses larger pages

D.It eliminates the need for swapping

💡 Difficulty: medium | ✅ Correct: A

📖 Explanation: When many virtual pages are unused, hierarchical paging allocates second‑level tables only for those first‑level entries that are actually referenced. Unused portions remain unallocated, saving memory. Option A captures this selective allocation. Option B is the opposite of what hierarchical paging does, C describes a different technique (large pages), and D is unrelated to the memory‑saving mechanism.

Q6. What impact does increasing the number of levels in a hierarchical page table have on TLB hit rate?

A.It increases the hit rate because fewer entries are needed

B.It decreases the hit rate due to more memory accesses ✅

C.No effect

D.TLB is not used with hierarchical paging

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: More levels mean that each virtual‑to‑physical translation requires additional memory references to walk the page‑table hierarchy. Each extra memory access provides an opportunity for a miss, which reduces the overall TLB hit probability. Therefore option B is correct. Option A reverses the relationship, C ignores the extra accesses, and D is false because TLBs are employed regardless of hierarchy depth.

Q7. How does the size of a first‑level page table relate to the size of the virtual address space and the number of bits allocated to the first‑level index?

A.It is independent of both

B.It equals

2^{\text{first‑level bits}}

C.It equals the page size

D.It equals the number of physical frames ✅

💡 Difficulty: medium | ✅ Correct: D

📖 Explanation: The first‑level table contains one entry for each possible value of the first‑level index. If the index uses $n$ bits, the table must have $2^{n}$ entries, directly linking the table size to the index width. Option D correctly reflects this relationship. Option A is false because the size depends on the index bits, C confuses table size with page size, and B describes the number of entries, not the overall memory size.

Q8. In hierarchical paging, what is the purpose of a page‑table entry that is marked as 'invalid'?

A.Indicates the page is already in memory

B.Triggers a page fault when accessed

C.Means the page is read‑only

D.Improves cache performance ✅

💡 Difficulty: medium | ✅ Correct: D

📖 Explanation: An invalid entry signals that the corresponding virtual page has no physical frame allocated. When the CPU tries to use such an entry, the memory‑management unit raises a page‑fault exception, prompting the operating system to load the page. Option D correctly identifies this behavior. Options A and C misinterpret the meaning of invalid, and D (cache performance) is unrelated.

Q9. Which of the following best describes the trade‑off when choosing the number of bits for each level in a hierarchical page table?

A.More bits per level reduces table depth but increases memory waste

B.Fewer bits per level reduces memory waste but increases table depth

C.Both A and B are true ✅

D.Neither A nor B is true

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: Choosing a larger bit field for a level reduces the number of levels needed (shallower hierarchy) but creates larger tables that may contain many unused entries, leading to waste. Conversely, using fewer bits creates smaller tables but deeper hierarchies, requiring more memory accesses. Both statements are correct, making option C the right choice. Options A and B present only one side of the trade‑off, while D denies the existence of any trade‑off.

Q10. A 32‑bit virtual address uses a three‑level hierarchical page table with 10 bits for each level and a 12‑bit page offset. How many total page‑table entries exist across all levels?

2^{30}

3 \times 2^{10}

✅

2^{10}+2^{10}+2^{10}

D.3072

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: Each level contains $2^{10}=1024$ entries because 10 bits are allocated per level. With three levels, the total number of entries is $3 \times 1024 = 3072$ . Option B expresses this product correctly. Option A dramatically overestimates the count, Option C adds the same numbers without multiplication (still 3072 but presented differently), and Option D repeats the correct total without the explicit multiplication, making B the most precise representation.

Q11. If a process accesses a virtual address whose first‑level index points to a null second‑level table, what hardware event occurs?

A.Successful translation

B.TLB miss

C.Page fault ✅

D.Cache hit

💡 Difficulty: medium | ✅ Correct: C

📖 Explanation: When the first‑level entry references a second‑level table that does not exist (null), the memory‑management unit cannot complete the translation and raises a page‑fault exception. The operating system must then allocate the missing second‑level table or bring in the required page. Option C accurately describes this outcome. A successful translation is impossible, a TLB miss (option B) is unrelated to the missing table, and a cache hit (option D) does not address the translation failure.

Q12. Consider a system with a two‑level hierarchical page table where each page table entry is 4 bytes. If the first level has 128 entries and each second‑level table also has 128 entries, what is the total memory required for the page tables when all second‑level tables are allocated?

A.64 KB ✅

B.128 KB

C.256 KB

D.512 KB

💡 Difficulty: medium | ✅ Correct: A

📖 Explanation: The first‑level table occupies $128 \times 4 = 512$  bytes. Each second‑level table also uses $128 \times 4 = 512$  bytes, and there are 128 such tables, giving $128 \times 512 = 65{,}536$  bytes. Adding the first‑level memory yields $65{,}536 + 512 = 66{,}048$  bytes, which is approximately 64 KB. Option A matches this calculation. The other options are larger than the actual requirement.

Q13. A processor uses a four‑level hierarchical paging scheme with each level indexing 9 bits and a 12‑bit offset. A virtual address has a first‑level index of 0x1A3. Which of the following statements is true about the translation process?

A.The first‑level entry directly gives the physical frame

B.The first‑level entry points to a second‑level table ✅

C.The offset is added to the first‑level index

D.No translation is needed because the offset is zero

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: In a multi‑level scheme, the first‑level entry never contains the final physical frame; instead, it holds a pointer to the next‑level table. The given first‑level index (0x1A3) therefore selects an entry that references a second‑level page table, which will be consulted next. Option B correctly reflects this step. Options A and C misinterpret the role of the first level, and D is false because the offset is non‑zero.

Q14. Explain why a two‑level hierarchical page table can be more space‑efficient than a single‑level page table when the virtual address space is sparsely populated, even though both use the same number of bits for indexing.

A.Because unused second‑level tables are not allocated ✅

B.Because it compresses entries

C.Because it uses larger pages

D.Because it eliminates page faults

💡 Difficulty: hard | ✅ Correct: A

📖 Explanation: A two‑level hierarchy stores only those second‑level tables that correspond to first‑level entries actually referenced by a process. If many virtual pages are unused, the associated second‑level tables are never created, saving memory. The indexing bits are identical in both designs, but the hierarchical approach avoids allocating space for entries that would remain empty. Option A captures this selective allocation; the other options describe unrelated effects.

Q15. A system has a 48‑bit virtual address space and uses a three‑level hierarchical page table. The page size is 4 KB. If the designer allocates 12 bits for the offset and distributes the remaining bits equally among the three levels, how many entries does each level’s page table contain?

2^{12}

entries ✅

2^{10}

entries

2^{16}

entries

2^{8}

entries

💡 Difficulty: hard | ✅ Correct: A

📖 Explanation: With a 48‑bit address and a 4 KB page ( $2^{12}$ offset bits), the remaining $48-12 = 36$ bits represent the virtual page number. Dividing these equally among three levels gives $36/3 = 12$ bits per level. Each level therefore requires $2^{12}=4096$ entries. Option A states this value correctly. Options B, C, and D correspond to different bit allocations and are therefore incorrect.

Q16. In a hierarchical paging system, a TLB entry can cache a complete virtual‑to‑physical translation. If a TLB miss occurs, how many memory accesses are required to translate a virtual address using a three‑level page table, assuming no second‑level tables are missing?

A.1

B.2

C.3 ✅

D.4

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: When the TLB does not contain the translation, the processor must read the first‑level entry, then the second‑level entry, and finally the third‑level entry to obtain the physical frame number. Each read is a separate memory access, totaling three accesses. Option C reflects this count. Options A and B underestimate the required steps, while D adds an extra access that is not needed in a straightforward three‑level walk.

Q17. Why does increasing the page size in a hierarchical paging scheme reduce the depth of the page‑table hierarchy needed to cover a given virtual address space?

A.Larger pages increase the number of offset bits, reducing bits needed for indexing ✅

B.Larger pages decrease the number of virtual pages, allowing fewer levels

C.Larger pages have no effect on hierarchy depth

D.Larger pages increase TLB size

💡 Difficulty: hard | ✅ Correct: A

📖 Explanation: A larger page size means the offset field occupies more bits of the virtual address, leaving fewer bits for the page‑number portion. With fewer page‑number bits, fewer bits are required at each level, so the hierarchy can be shallower while still covering the entire address space. Option A correctly explains this relationship. Option B describes a consequence but not the direct reason, and options C and D are unrelated to hierarchy depth.

Q18. What does the abbreviation 'TLB' stand for in the context of hierarchical paging?

A.Translation Lookaside Buffer ✅

B.Total Linear Base

C.Thread Lock Bit

D.Table List Block

💡 Difficulty: hard | ✅ Correct: A

📖 Explanation: TLB is short for Translation Lookaside Buffer, a small, fast cache that stores recent virtual‑to‑physical address translations to avoid repeatedly walking the page‑table hierarchy. Option A provides the correct expansion. The other options are fabricated terms that do not correspond to the established abbreviation used in memory‑management literature.

🔗 Related Topics (MCQs)

📝 Basic hardware in Main memory MCQs 📝 Address binding in Main memory MCQs 📝 Logical versus physical address space in Main memory MCQs 📝 Dynamic memory loading in Main memory MCQs 📝 Dynamic linking and shared libraries in Main memory MCQs

←Previous Topic:Shared Pages in Paging of Operating System📝 Hierarchical paging in Structure of the Page TableHashed page tables:Next Topic→