The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+54 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 (18k points)
edited by | 8k 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.


4 Answers

+57 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 (18k points)
edited by
Sir, in second case where you have included the case where Page Tables are searched in cache also, there in cache miss why haven't you taken miss as 0.1*(10 + 1) rather than what you have taken 0.1*(10) ?
In case if cache is virtually addressed:

Why we need not count the cache access time in case of cache miss? How without accessing cache we can know whether its cache miss?

You have also not used TLB access time in case of TLB miss but @mayank has considered it. Which one is correct?
@Debashish where is it written in the question that page tables aren't cached? do we have to assume it?

@Arjun sir evrything is fine but I have a doubt here..
in case of TLB, first we search the TLb,if page is present then we access it otherwise we go for page table.

but here TLB access time is given not the TLB search or/Lookup time. So,in case of miss we wont access the TLB then why we are adding it in case of miss.

as here lookup time is given so we add it

That is wrong-- you should not decide the usage of a time based on access/search/look up. Only when TLB is looked we can know a miss -- the only other alternative is if TLB and page tabkes are looed-up simultaneously. But this is not common as given in standard books.

@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
+18 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.2k 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
+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 (22k 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.
+2 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 (10.7k 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 ??

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

37,117 questions
44,701 answers
43,765 users