Integrating Virtual Memory, TLBs, and Caches

---

In a memory hierarchy, including a TLB and a cache, a memory reference can encounter three different types of misses: a TLB miss, a page fault, and a cache miss. The table below shows the possible combinations of events:

• Under the best of circumstances, a virtual address is translated by the TLB and sent to the cache where the appropriate data is found, retrieved, and sent back to the processor.


• In the worst case, a reference can miss in all three components.

In the table, three of these combinations are impossible, and one is possible (TLB hit, virtual memory hit, cache miss) but never detected.

TLB	Page table	Cache	Possible? If so, under what circumstance?
Hit	Hit	Miss	Possible, although the page table is never really checked if TLB hits.
Miss	Hit	Hit	TLB misses, but entry found in page table; after retry, data is found in cache.
Miss	Hit	Miss	TLB misses, but entry found in page table; after retry, data misses in cache.
Miss	Miss	Miss	TLB misses and is followed by a page fault; after retry, data must miss in cache.
Hit	Miss	Miss	Impossible: cannot have a translation in TLB if page is not present in memory.
Hit	Miss	Hit	Impossible: cannot have a translation in TLB if page is not present in memory.
Miss	Miss	Hit	Impossible: data cannot be allowed in cache if the page is not in memory.

The following table shows parameters of a virtual memory system.

Virtual address (bits)	Physical DRAM installed	Page size	PTE size (byte)
32	4 GiB	8 KiB	4

For a single page table, how many page table entries (PTE) are needed?   Check solution

Page size: 8 KiB = 213 bytes

32 – 13 = 19 bits ⇒ 219 entries

How much physical memory is needed for storing the page table?   Check solution

219 × 4 = 221 bytes = 2 MiB