GATE CSE 2003 | Question: 78

Question

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 $\text{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 $\text{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

Comments

Those who have still do not understood go here ->https://www.youtube.com/watch?v=7NoRhQC_XgI&t=384s

---

Great explanation @palashbehera5 !!!

---

It is divided in two parts at first change VA->PA then access the MM.

Case 1: Hit in TLB -> 1ns

Case 2: Miss in TLB -> Miss rate of TLB*(no. of levels *MM access time)

                                          0.04*(2*10)=0.8ns

Case 3: Hit in cache -> 1ns

Case 4: Miss in cache ->Miss rate of cache *(MM access time)

                                        0.1*10=1ns

Average Memory access time=1+0.8+1+1=>3.8ns

Answer 1

My approach is best as I have studied it from Galvin and Tannenbaum and also took help from IIT B professor in solving such a question

See my approach

Answer 2

TLB hit: 0.96 → This Means we have LA with us.

TLB miss: 0.04 → We now look for LA in 2-level PT.

---

Cache-hit: 0.90 → Respective frame found.

Cache-miss: 0.10 → Now try to find the page frame in MM

---

MM access time: 10ns

Cache access time: 1ns

TLB access time: 1ns

---

 0.96 * [1 + 0.9*(1) + 0.10*(1+10) ] + 0.04 * [1 + 2*10 + 0.9*(1) + 0.10*(1+10) ] = 3.5 ≈ 4 (answer)

---

If you understand these below lines then, I think this question is over for you.

TLB → hit : now we have LA, check the cache for respective frame :  → hit : 1ns

                                                                                                                  → miss : 1ns + 10ns (checking MM)

       → miss : check 2-level PT & get LA, now check the cache for respective frame :  → hit : 1ns

                                                                                                                                            → miss : 1ns + 10ns (checking MM)

Answer 3

The average time taken to access a virtual address is approximately 2.5 ns. This is because the TLB has a hit rate of 96% so the probability of a TLB hit is 0.96, and the probability of a TLB miss is 0.04. For a TLB hit, the average access time is 1 ns (TLB access time) For a TLB miss, the processor needs to access the page table in main memory, which takes 10 ns. Then it needs to check the cache which takes 1 ns on average (90% hit rate) So the average access time is (0.96 * 1) + (0.04 * (10 + 1)) = 2.5 ns.