📝 Hashed page tables (9 MCQs)

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

←Previous Topic:Hierarchical paging in Structure of the Page Table📝 Hashed page tablesInverted page tables:Next Topic→

What is Hashed page tables?

Definition:
Hashed page tables use hash function on virtual page number to index into collision-chained table providing O(1) average lookup for very large address spaces.

Example:
VPN $v$ hashed via $h(v) = v \mod N$ locates bucket; chain traversed until matching VPN found or null reached handling collisions gracefully.

Reason:
Hashing scales efficiently for 64-bit systems where hierarchical tables become too deep offering constant-time translation independent of address space size.

Easy

Medium

Hard

📝 All Hashed page tables MCQs

Q1. What is the primary purpose of a hashed page table in a virtual memory system?

A.To store page tables in a linked list

B.To provide a direct mapping from virtual page numbers to frame numbers using a hash function ✅

C.To eliminate the need for page replacement

D.To increase the size of physical memory

💡 Difficulty: easy | ✅ Correct: B

📖 Explanation: A hashed page table applies a hash function to a virtual page number to produce an index that points to the frame number, enabling fast address translation. Option B captures this direct mapping. Option A mentions a possible data structure but not the main goal. Option C is false because page replacement is still needed. Option D is unrelated; hashing does not alter physical memory size. This explanation links the concept to real OS implementations.

Q2. Why does a hashed page table typically use a chaining mechanism to resolve collisions rather than open addressing?

A.Because chaining allows variable‑length chains without rehashing ✅

B.Because open addressing requires more memory

C.Because chaining is faster to search

D.Because open addressing cannot handle more than 50% load factor

💡 Difficulty: medium | ✅ Correct: A

📖 Explanation: Chaining stores all entries that hash to the same bucket in a linked list, so the table can grow without moving existing entries or recomputing hashes. This flexibility makes it preferable for page tables where the number of entries can change dynamically. Option A correctly describes this benefit. Option B is misleading; open addressing does not necessarily need extra memory. Option C is inaccurate because search time can be longer with long chains. Option D is an oversimplification; open addressing can handle higher loads but with degraded performance.

Q3. How does the load factor of a hashed page table affect its average lookup time, and what trade‑off does increasing the number of buckets introduce?

A.Higher load factor reduces lookup time but increases memory usage

B.Higher load factor increases lookup time linearly, while more buckets increase memory overhead ✅

C.Load factor does not affect lookup time

D.More buckets always improve performance without cost

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: The load factor is the ratio of stored entries to bucket count; as it rises, more entries share each bucket, causing longer chain traversals and higher average lookup time, roughly proportional to the load factor. Adding more buckets spreads entries thinner, reducing chain length but requiring additional memory for the bucket array. Option B captures both effects. Option A reverses the relationship. Option C ignores the well‑known impact of load factor. Option D is false because more buckets consume extra memory and may not yield proportional gains.

Q4. In what way does a hashed page table improve memory utilization compared to a multi‑level page table for sparse address spaces?

A.It stores only entries for allocated pages ✅

B.It pre‑allocates entries for all possible pages

C.It uses fixed‑size arrays for each level

D.It requires twice the memory of a multi‑level table

💡 Difficulty: medium | ✅ Correct: A

📖 Explanation: A hashed page table creates an entry only when a virtual page is actually mapped, so unused regions of the address space consume no space. This contrasts with multi‑level tables, which may allocate intermediate tables even for empty regions, wasting memory. Option A correctly states the benefit. Option B describes the opposite of what hashing does. Option C is a property of hierarchical tables, not hashing. Option D exaggerates the memory cost of hashing.

Q5. Given a virtual page number 0x0F2 and a hash function h(vpn)=vpn mod 256, what bucket index will the page be placed in?

A.242 ✅

B.15

C.256

D.0

💡 Difficulty: easy | ✅ Correct: A

📖 Explanation: Convert 0x0F2 from hexadecimal to decimal: 0x0F2 = 242. Applying the hash function h(vpn)=vpn mod 256 gives 242 mod 256 = 242, so the page maps to bucket 242. Option A matches this calculation. Options B, C, and D are incorrect results of mis‑calculations or misuse of the modulus. Understanding the conversion and modulus operation is essential for implementing hashed page tables in real systems.

Q6. A hashed page table uses chaining. Bucket 16 already contains entries for vpn=0x10 and vpn=0x210. A new virtual page has vpn=0x310. Using h(vpn)=vpn mod 256, what action should the system take?

A.Bucket 48, no collision, insert new entry

B.Bucket 48, collision, add to chain ✅

C.Bucket 16, collision, add to chain

D.Bucket 16, no collision

💡 Difficulty: medium | ✅ Correct: B

📖 Explanation: First convert the virtual page numbers to decimal: 0x310 = 784, 784 mod 256 = 16, so the new entry belongs to bucket 16. The existing entries (0x10 = 16, 0x210 = 528, both also map to bucket 16) mean a collision occurs, and chaining dictates that the new entry be appended to the existing chain. Option B correctly describes this process. Options A and C use the wrong bucket number, and option D ignores the collision.

Q7. Using the hash function h(vpn) = (vpn xor (vpn >> 10)) mod 1024, what bucket index is produced for vpn = 0x1000?

A.0

B.4 ✅

C.1024

D.256

💡 Difficulty: hard | ✅ Correct: B

📖 Explanation: Convert vpn = 0x1000 to decimal (4096). Shift right by 10 bits: 4096 >> 10 = 4. XOR the two values: 4096 xor 4 = 4100. Apply the modulus: 4100 mod 1024 = 4. Therefore the bucket index is 4. Option B matches this result. Options A, C, and D are incorrect because they either ignore the XOR step or misuse the modulus operation. This calculation mirrors the exact steps an OS would perform when indexing a hashed page table.

Q8. Which characteristic of hashed page tables makes them more suitable than inverted page tables for systems with a high degree of process concurrency?

A.They store one entry per physical frame

B.They allow multiple entries per bucket

C.They enable direct lookup of a virtual page without scanning all processes ✅

D.They require less memory than inverted tables

💡 Difficulty: hard | ✅ Correct: C

📖 Explanation: In a hashed page table, the hash directly maps a virtual page number to a bucket, allowing the OS to locate the translation without iterating over every process’s pages, which is necessary in an inverted table. This direct lookup scales well with many concurrent processes. Option C captures this advantage. Option A describes inverted tables. Option B is true but not the key scalability factor. Option D is inaccurate; memory usage depends on design choices.

Q9. A system’s hashed page table lookup costs an average of 3 memory accesses. If the TLB hit rate is 80% and a TLB miss incurs a full hashed lookup, what is the overall average memory accesses per address translation?

A.1.6 ✅

B.2

C.2.2

D.2.8

💡 Difficulty: medium | ✅ Correct: A

📖 Explanation: When the TLB hits (80% of the time), only one memory access is needed for the instruction or data fetch. When it misses (20% of the time), the system performs the 3‑access hashed lookup in addition to the normal fetch, totaling 4 accesses. The weighted average is 0.8 × 1 + 0.2 × 4 = 0.8 + 0.8 = 1.6 accesses per translation. Option A reflects this calculation. Options B, C, and D result from incorrect weighting or omission of the base fetch cost. This shows how TLB performance directly influences overall memory traffic in a system using hashed page tables.

🔗 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:Hierarchical paging in Structure of the Page Table📝 Hashed page tablesInverted page tables:Next Topic→