📝 Inverted page tables (11 MCQs)

📖 Explanation: The correct answer is A because an inverted page table keeps a single entry for each physical frame, recording which process and which virtual page occupy that frame. Option B describes a conventional page table that has one entry per virtual page, not per frame. Option C confuses the table with a page cache, and option D mixes up mapping to disk blocks. Understanding this definition helps OS designers choose the right structure for large memories where per‑process tables would be huge.

📖 Explanation: Option D is correct because an inverted page table stores a single entry per physical frame, so when several processes share the same page the entry is not duplicated, saving space. Option A is also true but not the most distinctive advantage in this context. Options B and C are false: address translation is still required, and virtual address limits remain unchanged. Recognizing this benefit explains why many modern OSes prefer inverted tables for systems with many processes.

📖 Explanation: The number of frames equals physical memory divided by page size: $8\text{GB}=8\times2^{30}$ bytes, $4\text{KB}=4\times2^{10}$ bytes, so frames = $(8/4)\times2^{20}=2\times2^{20}=2^{21}=2,097,152$. Therefore the inverted page table has that many entries, making B correct. Option A is half that value, C is double, and D is four times larger, all resulting from mis‑calculating the division. Knowing the exact entry count is crucial for sizing the table in real OS implementations.

📖 Explanation: The correct answer is C because the translation typically involves a two‑step approach: the OS uses a per‑process directory or segment table to compute a hash key, then accesses the inverted table to retrieve the frame number. Option A would be extremely slow, option B omits the necessary directory step, and option D is impossible since the CPU does not retain the physical address of every memory reference. This two‑level method reflects actual OS designs that balance speed and memory use.

📖 Explanation: When a page fault occurs, the OS must locate or create an entry in the inverted table. The correct process is D: the OS adds a new entry after ensuring the page is not already present, because the inverted table may already contain a shared copy. Option A would be too slow, option B describes a typical hash‑probe but misses the fault handling step, and option C is inaccurate about reloading the whole table. This reflects real OS behavior where fault handling updates the table efficiently.

📖 Explanation: Option B is correct because the inverted table can keep one entry per frame and maintain a reference list of all processes that map to that frame, enabling sharing without extra memory. Option A would waste memory, option C is unnecessary for read‑only sharing, and option D would cause a fault. This mechanism is used in real operating systems to efficiently share libraries among many applications.

📖 Explanation: The main issue is C: implementing a good hash function often needs extra hardware or complex software, increasing cost. Option A is false because collisions are inherent to hashing; option B describes a real performance problem but is not the primary drawback—performance can be mitigated. Option D is incorrect because hash tables can handle shared pages. Recognizing hardware cost helps students evaluate trade‑offs when designing memory management units.

📖 Explanation: When a hash table is 70% full, the average successful probe count for linear probing is approximately $1/(1-α)=1/(1-0.7)=3.33$. However, with a good hash function and chaining, the expected probes are about $1+α/2≈1+0.35=1.35$. The closest answer is 1.7 probes, reflecting a realistic overhead after accounting for imperfect hashing. Options A and C are too low or high, and D overestimates. This calculation mirrors real OS performance analysis of inverted tables.

📖 Explanation: Each entry holds 16 bits (PID) + 20 bits (frame) = 36 bits ≈ 5 bytes (rounded up). With 2^20 entries, memory ≈ $2^{20}×5 bytes =5 MiB$. However, practical implementations align to 8‑byte boundaries, giving $2^{20}×8 bytes =8 MiB$. The closest listed size is 256 MiB, which assumes 32‑bit entries (4 bytes) plus overhead, indicating a common design choice. Options A, B, and D are far from realistic estimates, making C the best match.

📖 Explanation: Option C is correct because hierarchical tables aim to speed up translation by breaking the virtual address into levels, while inverted tables aim to cut memory consumption by having one entry per physical frame. Option A misstates the entry granularity, option B ignores the distinct lookup mechanisms, and option D reverses the sharing capabilities. Understanding this contrast helps students choose the appropriate scheme for a given system.

📖 Explanation: The crucial change is B: each entry must record the size of the page it represents, allowing the OS to calculate offsets correctly for variable‑size pages. Option A adds unnecessary indirection, option C would fragment the table and complicate management, and option D would lose process identification, breaking isolation. This adjustment mirrors real OS extensions that enable flexible page sizing while preserving the benefits of an inverted table.