Describe page tables, multi-level paging, and inverted page tables, and explain why each is used.

• A. Page tables map virtual pages to physical frames; multi-level paging reduces memory for page tables; inverted page tables map physical frames to virtual pages, reducing memory usage but requiring faster lookup.
• B. Multi-level paging increases memory usage; inverted tables map virtual pages to processes.
• C. Inverted page tables are a type of CPU cache.
• D. Multi-level paging eliminates the need for a TLB.

Answer: (A)

The main idea here is how the system translates a virtual address into a physical location and the trade‑offs between different page‑table schemes.

A page table is the straightforward mapping from each virtual page to the physical frame that holds its data, along with status bits such as valid/invalid, permissions, and dirty flags. This makes address translation fast when the needed table entries are in memory, but if the virtual address space is large, a single‑level page table can become huge and wasteful because many entries may never be used.

To save memory, multi‑level paging organizes the mapping in layers. The virtual address is split into several parts: indices into a top‑level directory and then into one or more secondary page tables, ultimately giving the offset within the final page. Only the parts of the page tables that are actually needed are allocated in memory, which dramatically reduces the memory required for page tables in large or sparse address spaces. Translation still happens quickly, especially when aided by a TLB that caches recent mappings, but it may involve multiple memory lookups to walk the level(s) of the hierarchy.

An inverted page table takes a different approach by reversing the mapping: each physical frame has an entry describing which virtual page (and which process) is currently stored there. This lowers the memory needed for the page table because there is one entry per physical frame rather than one per virtual page. The trade‑off is that finding which frame holds a given virtual page requires a lookup that can be slower unless you have fast associative lookup, hashing, or hardware support like a TLB to speed translations.

So, page tables provide direct mappings from virtual pages to physical frames; multi‑level paging saves memory by organizing the table hierarchically; and inverted page tables save memory by mapping frames to virtual pages, at the expense of lookup speed unless fast lookups are available. The other options misstate these relationships—they don’t accurately describe how multi‑level paging reduces memory, what inverted tables are, or how these schemes relate to speed and translation hardware.