edited by
47,109 views
121 votes
121 votes

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)

  1. $1.5$ ns
  2. $2$ ns
  3. $3$ ns
  4. $4$ ns
edited by

15 Answers

1 votes
1 votes
Answer to this question boils down to

You will look cache

you will definately look TLB

and you will look main memory once when you wont find in Cache

and you will look k times in Main memory when you wont find in TLB

 

t+c+ ((1-h1)k + 1-h2)m is the formula

1 + 1 + (0.04*2 + 0.1)10

2 + 0.18(10) = 3.8ns
1 votes
1 votes

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 $

edited by
Answer:

Related questions

55 votes
55 votes
7 answers
3
go_editor asked Apr 24, 2016
14,695 views
Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ is shown below.$$\begin{ar...