A processor uses 2-level page tables for virtual to physical address…
2003
A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns. Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)
- A.
1.5 ns
- B.
2 ns
- C.
3 ns
- D.
4 ns
Attempted by 8 students.
Show answer & explanation
Correct answer: D
Solution: compute the average access time by considering TLB hit/miss and cache hit/miss.
Given: TLB hit rate = 0.96, TLB access = 1 ns; cache hit rate = 0.90, cache access = 1 ns; main memory = 10 ns. No page faults.
On a TLB hit (probability 0.96): you pay 1 ns for the TLB, then access the physically addressed cache. If cache hits (0.9) add 1 ns → total 2 ns. If cache misses (0.1) add cache check 1 ns + memory 10 ns → total 12 ns. Expected time on TLB hit = 0.9*2 + 0.1*12 = 3.0 ns.
On a TLB miss (probability 0.04): you pay 1 ns for the TLB miss check, then perform a two-level page-table walk in main memory (2 × 10 ns = 20 ns). After obtaining the physical frame, access cache: if cache hits (0.9) add 1 ns → 22 ns total; if cache misses (0.1) add 1+10 =11 ns → 32 ns total. Expected time on TLB miss = 0.9*22 + 0.1*32 = 23.0 ns.
Overall average = 0.96*3.0 + 0.04*23.0 = 2.88 + 0.92 = 3.8 ns ≈ 4.0 ns.
Answer: 4.0 ns (to the nearest 0.5 ns).