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

If you too are a machine, ridiculed by people for not having emotions and understand pseudo codes for every concept:

try {
    PHYSICAL_ADDRESS = searchTLB(page#);  //TLBHit! get physical address  Htlb(Ttlb
    try{ 
        FINAL_PAGE = searchCM(PHYSICAL_ADDRESS); //CMHit! search CM using physical address 
    } catch (CMMissException) {   // and get desired page  + Hcm(Tcm)
        FINAL_PAGE = getPageFromMM(PHYSICAL_ADDRESS);//CMMiss 1MM access to get page from phy address
    }    //        +(1-Hcm)(Tcm+Tmm))
} catch (TLBMissException) {       //TLBMiss
    PHYSICAL_ADDRESS = searchMM(LOGICAL_ADDRESS, levels=2); //2MM access to get phy add of page
    try{  //  (1-Htlb)(Ttlb+2Tmm
        FINAL_PAGE = searchCM(PHYSICAL_ADDRESS); //search in CM quickly if the page is cached + Hcm(Tcm)
    } catch (CMMissException) {
        FINAL_PAGE = getPageFromMM(PHYSICAL_ADDRESS);//CMMiss! Page wasn’t cached   +(1-Hcm)(Tcm+Tmm))
    }
}
return FINAL_PAGE;

 

Final expression:

$Htlb(Ttlb+Hcm(Tcm)+(1-Hcm)(Tcm+Tmm)) $
$+  (1-Htlb)(Ttlb+2Tmm+Hcm(Tcm)+(1-Hcm)(Tcm+Tmm)) $

$= 0.96(1+0.9(1)+(0.1)(1+10)) + (0.04)(1+2(10)+0.9(1)+(0.1)(1+10))$
$= 3.8ns $

Answer 2

https://documentcloud.adobe.com/link/track?uri=urn:aaid:scds:US:0c36b08d-25e7-4892-af15-784372cfc9b5#pageNum=1

See this

Answer 3

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 4

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)