##### What is the average time taken to access a virtual address?

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)

1. 1.5 ns
2. 2 ns
3. 3 ns
4. 4 ns
Sumit Verma
22 May 2017 11:58 am

There are many approaches to solve these type of questions. This is mine.
Consider each case:
1. TLB Hit + Cache Hit:
T1 = TLB Hit probability* Cache Hit probability*  access time
T1 = 0.96 * 0.9 * (1+1)  = 1.728 ns
2. TLB Hit + Cache Miss:
T2 = TLB Hit probability* Cache Miss probability*  access time (Main memoery will be accessed)
T2 = 0.96 * 0.1 * (1+1+10) = 1.152 ns
3. TLB Miss + Cache Hit:
T3 = TLB Miss probability* Cache Hit probability*  access time (2 page table will be accessed)
T3 = 0.04 * 0.9 * (1+1+10+10) = 0.792 ns
4. TLB Miss + Cache Miss:
T4 = TLB Miss probability* Cache Miss probability*  access time
T4 = 0.04 * 0.1 * (1+10+1+10+10) = 0.128 ns

Total avg. time = 3.8 ns ≅ 4ns.

Anuja Shetye
5 May 2021 11:07 am

@sumit Verma I am confused with the 3rd point. During cache hit why the 2 page tables are accessed. I will have directly the required page in cache na?