edited by
46,776 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

4 votes
4 votes

Both TLB and CACHE Memory is a type of Cache. But you can understand in this way that TLB is somehow related to accessing  the page table  and CACHE is related to accessing the element of the main memory

Whenever TLB and CACHE MEMORY  are involved simply do in this way.

Since CPU always generates the logical address.

Effective Memory Access Time =

Time  taken to convert Logical access to physical address  + Main memory access time

EMAT  { TLB ACCESS TIME  +  Ptm (k* Main memory access  time) }  +  Cache access time  +  Pcm ( main memory access time + (Pf * Page fault service time ) )

k : no of level of page table

Ptm : TLB MISS RATE

Pcm :CACHE MISS RATE

Pf     :  PAGE FAULT RATE.

Whatever written in { } Curley braces is time to convert logical address to physical address.

According to the question, you can put the value and get your answer. for this question, no page fault is given so you can assume Pf = 0

 

4 votes
4 votes

Only for virtually addressed cache-

AMAT= cache hit ratio * cache access time + cache miss ratio*( VA->PA + memory word access)

=( cache hit ratio * cache access time + cache miss ratio*( tlb time+ tlb miss*(2*memory access)+ memory word access))

= 0.9*1+0.1*(1+.04*20+10)= 2.08 ns

2 votes
2 votes

So the question asks 'average time take to access virtual address'. This will comprise of two parts. First, we will use TLB/Page Table to find out which frame we need to access in main memory. Secondly, with calculated frame number, we will try to access byte/data/word which can be in cache or main memory.

The logical address is used to fetch frame number from TLB or Page Table (depending on TLB hit or miss). With TLB hit, we will not need any memory access to fetch desired frame number because we will find the required frame number from TLB. But with TLB miss, we will need one memory access to go to memory and read frame number from page table.

We now calculate the time it takes to get our desired frame number:

According to question,

TLB access time = 1 ns; Main Memory access time = 10 ns; TLB hit ratio = 0.96; TLB miss ratio = 0.04

Average time to get desired frame number = 0.96*1 + 0.04*10 = 0.96 + 0.4 = 1.36 ns

 

For each frame number, whether it was found in TLB or Page Table, we need to access data/byte. This byte could be found in Cache in case of Cache Hit and in Main memory in case of a Cache Miss.

According to question,

Cache Access Time = 1 ns; Main Memory access time = 10 ns; Cache hit ratio = 0.90; Cache Miss ratio = 0.10

Thus, average time to read the frame from memory = 1.36*0.9*1 + 1.36*0.1*10 = 1.22 + 1.36 = 2.58 ns

 

Thus, overall time taken to read a logical address = Avg. time to get frame number +Avg. time to get data

                                                                               = 1.36 + 2.58 = 3.94 = 4 ns

 

 

2 votes
2 votes

i tried from my side to make solution easier,after reading all the answers.

Answer:

Related questions

55 votes
55 votes
7 answers
3
go_editor asked Apr 24, 2016
14,672 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...