The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+60 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
asked in Operating System by Boss (18.2k points)
edited by | 11.5k views
Anyone please summarize this thing.It's very difficult to understand for beginner !
Some important lines in this question -->

Page tables for both levels are stored in the main memory.

Physically addressed cache.
3.8 is wrong ?

i am not understanding why it should be 3.152
its coming 3.8 questn it is said to round off the value upto nearest o.5 ns so nearest is 4 ns and thus the answer...
but to get 3.152 arjun sir has used a different approach

am asking regarding that

look at the best answer

There is no point of confusion in this question. Firstly we should know the access sequence of TLB, Cache, page tables and MM. The following figure depicts this clearly:

Now coming to our question following sequence will be followed:

1. TLB will be accessed

     1.1 TLB Hit

         cache access....if cache Hit...word will be accessed from cache....If cache MISS word will be accessed from MM(no page fault)

    1.2 TLB Miss

         2 Page tables will be accessed(it is given page tables are in MM, so 2 MM access)....then cache will be accessed.....if cache Hit, word will be accessed from cache....if cache miss word will be accessed from MM...

So following the above sequence, AMAT is as following:


         =4ns (round off to the nearest 0.5ns)

(it is given page tables are in MM, so 2 MM access)  why?

hem chandra joshi, bcoz there are two level page access one table, one MM access.

I know Processor can simultaneously look in multiple blocks of TLB, but in case of main memory we need multiple access to main memory for accessing page table depending on levels ? Can someone clear this?
in this question there is no any page fault .consider a situation in which there is page fault having page fault rate is 10% then what will be expression for it.
Thank you for such a good explanation

9 Answers

+67 votes
Best answer

78. It's given cache is physically addressed. So, address translation is needed for all memory accesses. (I assume page table lookup happens after TLB is missed, and main memory lookup after cache is missed)

Average access time = Average address translation time + Average memory access time
= 1ns 
(TLB is accessed for all accesses)
+ 2*10*0.04 
(2 page tables accessed from main memory in case of TLB miss)
+ Average memory access time
= 1.8ns + Cache access time + Average main memory access time
= 1.8ns + 1 * 0.9 (90% cache hit) 
+ 0.1 * (10+1) (main memory is accessed for cache misses only)
= 1.8ns + 0.9 + 1.1
= 3.8ns

We assumed that page table is in main memory and not cached. This is given in question also, though they do not explicitly say that page tables are not cached. But in practice this is common as given here. So, in such a system, 

Average address translation time 
= 1ns (TLB is accessed for all accesses) 
+ 2*0.04 * [0.9 * 1 + 0.1 * 10] 
(2 page tables accessed in case of TLB miss and they go through cache)

$= 1 \ ns + 1.9 \times .08$

$= 1.152 \ ns $

and average memory access time $= 1.152 \ ns + 2 \ ns = 3.152  \ ns$

If the same thing is repeated now probably you would get marks for both. 2003 is a long way back -- then page table caching never existed as given in the SE answers. Since it exists now, IIT profs will make this clear in question itself.

answered by Boss (18.2k points)
edited by

@Arjun sir

In case when TLB is cached then

Average address translation time 
= 1ns (TLB is accessed for all accesses) 
+ 2*0.04 * [0.9 * 1 + 0.1 * 10] 
(2 page tables accessed in case of TLB miss and they go through cache)

I think it should be 1+10 =11

Why? Because,

If cache hit then access cache  i.e. 0.9*1 

In case of cache miss ..Access main memory for page table and if we follow hierarchical memory access scheme (as is being followed for page access here) then that page table is transferred to cache memory and thus cache access time should be added. i.e. 0.1 * (1+10) where 1ns is cache access time.

In question it's given that both page tables are stored in the main memory.  So how can we consider that they are in cache memory... Hence when TLB miss then main memory is accessed for page tables.
@VS ,you are correct.

@Arjun sir.Please add the edit suggested by @VS. I took me 30 mins to get the same answer.I could have seen her comment earlier:(

Prerna Chauhan in second line 

 Page tables for both levels are stored in the main memory.

@Arjun sir can you verify @VS answer

I think it is correct
How can TLB be cahed? TLB is itself is buffer storing subset of page table entry.
Physically addressed cache means physical frames containing virtual page are cached in cache am I correct
Can anyone please tell why the 2 ns is added to obtain the average memory access time in the answer (3.152 ns) ? I mean, where is the 2 ns coming from ??

in TLB caching @Arjun sir why have u not taken hierarchical approach?


Average address translation time 
= 1ns (TLB is accessed for all accesses) 
+ 2*0.04 * [0.9 * 1 + 0.1 * (10+1)] = 1.16 ns 
(2 page tables accessed in case of TLB miss and they go through cache)

So final answer should be 3.16 ns



how is page table caching done? I am unable to understand? For 2 level paging why is cache also accessed twice in page table caching?

+21 votes

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

answered by Active (2.3k points)
I am not understanding 2*(10) ? Please explain.
@eyeamgl Because when you miss the TLB then you have to look into the page table for physical address conversion and page table is in main memory so total twice memory time will be there and here memory access time given is 10 so 2*10(twice of memory access time as i said )
ok thanks
Compare this explanation with Debashish Deka's lovely diagram, you'll get a clear picture. Thanks
@eyeamgl We multiply by 2 because this is 2 level paging. We have to calculate the physical address by visiting two level of pages.
+11 votes

Effective memory access time 4 ns (aprox )

Eff Memory Acces Time $=X_{TLB}\begin{pmatrix} C_{TLB}+X_{PAC} [C_{PAC}]+(1-X_{PAC} ) [C_{PAC}+M] \end{pmatrix} +(1- X_{TLB})\begin{pmatrix} C_{TLB}+2M+X_{PAC} [C_{PAC}]+(1-X_{PAC} ) [C_{PAC}+M] \end{pmatrix}$

$=0.96\begin{pmatrix} 1+0.9 [1]+(1-0.9 ) [1+10] \end{pmatrix} +(1- 0.96)\begin{pmatrix} 1+2\times 20+0.9 [1]+(1-0.9 ) [1+10] \end{pmatrix}$

=3.8 ns

answered by Boss (22.6k points)
edited by
@arjun sir , pls check this one
i think thet will be 2*10 instead of 2*20, though,

Why is everyone taking TLB Access Time as 1 ns and why not 10 ns.


,and TLB Access Time is also 10 ns. !!!

@pc you substituted CTLB = 1 NS ??

.Let S1= ∑nr/2r (r=0 to logn-1) .S2= ∑r2r (r=0 to logn-1) .

s1 and s2 after expension?
Its 1ns given in the question for TLB access time.
+6 votes
Average time taken to access virtual address

= ( Virtual address to physical address ) + (fetch the word from process or main memory )

= t+ ( 1- $p_{t}$)(k*m) + C +(1-$p_{c}$) *m          [K= # of levels] [m = main memory access time]

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

= 3.8 ns
answered by Boss (12.2k points)
edited by

(fetch the word from process )

*fetch the frame from cache/physical memory? 

Now see ... clear (y) ??
it is actually frame. we get frame number by accessing page table entry. a frame is bigger than a word.
What is the purpose of framing or paging ??? to fetch the word from main memory ...  so wats wrong in that statement ??
+2 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




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


answered by (287 points)
+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



answered by (253 points)
+2 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

answered by Boss (17k points)
+1 vote
3.8ns is correct answer..
answered by (367 points)
+1 vote
answered by (89 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,068 questions
53,206 answers
70,419 users