5.4.11 · D5Memory Hierarchy & Caches
Question bank — Virtual memory and paging
This bank drills the boundaries: signs of "not in RAM", the difference between illusion and hardware, and the places where the neat page-arithmetic almost-but-not-quite breaks. For the mechanics behind any answer, see Multi-level page tables, Page replacement algorithms, and Locality of reference.
True or false — justify
Every answer explains why, because "true/false" alone teaches nothing.
True or false: The offset part of a virtual address is translated by the page table.
False — only the VPN is translated. Moving a page into a frame is a rigid shift, so byte of the page stays byte of the frame; the offset is copied unchanged.
True or false: A page fault always means the program has a bug.
False — a page fault is a normal event meaning the page is currently on disk or not-yet-allocated. The OS loads it and resumes the instruction. Only an access to a genuinely invalid address is a crash (segfault).
True or false: Virtual address 0x4000 in process A and process B refer to the same physical RAM byte.
False — each process has its own page table, so the same VA maps to different frames. That separateness is the isolation virtual memory promises.
True or false: The TLB stores actual data from memory.
False — the TLB stores translations (VPN → PFN), not data. Data caching is the job of the CPU caches; the two are separate structures serving different lookups.
True or false: Bigger pages are strictly better because the page table shrinks.
False — larger pages mean fewer entries but more internal fragmentation (a 1-byte need still burns a whole page) and heavier per-fault disk I/O. It is a trade-off, not a free win.
True or false: With a 100% TLB hit ratio, no page-table walk ever happens.
True in the steady state — but the very first access to each page (a compulsory miss) must still walk the table to populate the TLB, so a real 100% is asymptotic, never from the first instruction.
True or false: Virtual memory requires a disk (swap space) to function at all.
False — the translation and isolation benefits work purely in RAM. Disk is only needed for the "pretend RAM is bigger" benefit; a system with swap disabled still uses paging for protection.
True or false: The page size is chosen by the programmer for each process.
False — page size is a fixed hardware/OS property (e.g. 4 KiB). A process cannot pick its own; at most the OS may offer huge pages as a separate opt-in mechanism.
Spot the error
Each statement below contains a subtle mistake — name it.
"To translate, the MMU multiplies the whole virtual address by the frame number."
Wrong — the MMU translates only the VPN via a table lookup, then does . There is no multiplication of the whole address, and the frame number comes from a table, not arithmetic on the VA.
"A single-level page table for a 48-bit address space is fine; it's only a few thousand entries."
Wrong — entries , so with that is entries (billions), which is why Multi-level page tables exist to allocate only the used portions.
"The TLB helps because it makes memory itself faster."
Wrong — the TLB doesn't speed up RAM. It removes the extra memory access needed to read the page table, exploiting locality so translation is nearly free.
"If a page is in RAM, accessing it can still cause a page fault."
Wrong in general — if the page is present and permissions allow the access, no fault fires. (A protection fault is a different trap, triggered by a permission violation, not by absence.)
"On a TLB miss the CPU immediately gives up and raises a page fault."
Wrong — a TLB miss just triggers a page-table walk. A page fault only occurs if that walk finds the page is not resident. Miss ≠ fault.
"Because each process has its own page table, sharing memory between two processes is impossible."
Wrong — two page tables can map different VPNs (or the same VPN) to the same physical frame, giving shared memory while keeping separate tables.
Why questions
Why is memory split into fixed-size pages instead of arbitrary-length regions?
Fixed sizes let any page drop into any frame (no external fragmentation) and reduce translation to a simple shift/mask instead of storing a start+length per region.
Why are the low bits of the address never translated?
They index a byte inside a page, and a page keeps its internal layout when moved to a frame. Only which page (the base) changes, so only the high bits (the VPN) get mapped.
Why does the effective access time formula add only rather than a huge penalty?
Because the miss penalty of one extra table-walk access is weighted by the small miss probability ; with high locality most accesses skip the walk entirely, so the average extra cost is tiny.
Why can two processes both "start at address 0" without colliding?
Address 0 is a virtual address, and each process's page table maps its virtual 0 to a different physical frame — the numbers coincide but the real locations do not.
Why is a page fault sometimes deliberately triggered by the OS (lazy allocation)?
The OS can mark a page not-present so that the first touch traps in, letting it allocate/zero the frame only when actually used — saving RAM for pages a program never reads.
Edge cases
What happens when a virtual address offset equals 0 (the very first byte of a page)?
Nothing special — offset means the VA lands on the frame's base byte after translation. The arithmetic still holds; it is not a degenerate or forbidden case.
What if the requested VPN has no valid page-table entry at all?
The lookup finds an invalid (not-present-and-not-swapped) entry, so the OS treats it as an illegal access — a segfault — rather than a recoverable page fault.
What happens if physical RAM is completely full when a new page must be loaded?
The OS must evict a resident page using a replacement policy, writing it to disk if dirty, before the incoming page can occupy the freed frame.
Degenerate case: page size equal to the whole virtual address space (one page).
Then the VPN has bits and everything is offset — there is nothing to translate, so paging collapses into direct addressing. This is the limiting boundary showing paging only pays off with many pages.
What about an address that lies exactly on a page boundary, and an access that spans two pages?
A single byte at a boundary is fine, but a multi-byte access crossing the boundary touches two VPNs, each translated separately — so one half can be resident while the other faults.
If the TLB and page table disagree (stale TLB entry after the OS remaps a page), what breaks?
The CPU would translate using the stale frame and read wrong memory; this is why the OS must flush/invalidate the affected TLB entry whenever it changes a mapping.
Zero-size process (no pages mapped yet): what does its page table look like?
All entries are invalid/not-present. Any access faults immediately — perfectly consistent, since a brand-new process's mappings are created lazily on first touch.
Recall Quick self-test — cover the answers
- Is a TLB miss the same as a page fault? ⟶ No; a miss triggers a walk, a fault only if the page is absent.
- Does the offset get translated? ⟶ No; only the VPN.
- Can two processes share a frame? ⟶ Yes; their tables can both point to it.
- Why flush the TLB on remap? ⟶ To avoid using a stale, now-wrong translation.