The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+53 votes

Consider a system with a two-level paging scheme in which a regular memory access takes $150$ $nanoseconds$, and servicing a page fault takes $8$ $milliseconds$. An average instruction takes $100$ nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is $90$%, and the page fault rate is one in every $10,000$ instructions. What is the effective average instruction execution time?

  1. $645$ $nanoseconds$
  2. $1050$ $nanoseconds$
  3. $1215$ $nanoseconds$
  4. $1230$ $nanoseconds$
asked in CO & Architecture by Boss (18.1k points)
edited by | 12.4k views
@Bikram Sir please explain
indeed a nice question
@Arjun sir, Is it possible that for a memory address translation there can be more than one page fault(only for more than one page table)?

as we know page fault is accessing a page that is marked invalid in page table.and suppose there are two page tables and when we try to access page of $PT1$ which is marked invalid and after restoring this page there is again a page fault for $PT2$. Is it possible?
I think access will be like this

Find page in Page Table 1 , if not found , then search it in Page Table2, if not found then only bought it from main memory
but @srestha if a page is not present in page table $1$, then How will you know which page to acess at inner level bcz from only outer level pages will have entries for those pages.OR it is possible that those page which have entries at outer level page may not be present at inner levels?

But I have one doubt here --if we have page fault at level-1 then what is the techniqe for storing the pages.

 we store only that page or along with it we also restore all those page to which this outer level page is referring to.If it is latter case then only at level-1 can cause page fault and subsequent access to page tables can not lead to page fault otherwise we can get multiple level of page faults for  the same address translation.

6 Answers

+79 votes
Best answer
Average Instruction execution time

 = Average CPU execution time + Average time for getting data(instruction operands from memory for each instruction)

 =   Average CPU execution time
   + Average address translation time for each instruction
   + Average memory fetch time for each instruction
   + Average page fault time for each instruction

 = $100+2\Big(0.9 (0) + 0.1 (2 \times 150)\Big) + 2\times 150 + \dfrac{1}{10000} \times 8 \times 10^6$

(Page Fault Rate per 10,000 instruction is directly given in question.Two memory accesses per instruction and  hence we need 2 $\times$ address translation time for average instruction execution time)

[ TLB access time assumed as 0 and 2 page tables need to be accessed in case of TLB miss as the   system uses two-level paging ]

= $100 + 60 + 300 + 800$

= $1260 ns$
answered by Veteran (355k points)
edited by
@ Srestha (2+1) because after 2-page page table access, the translated physical address finally retrieves data from that location in memory.


Page_hit( TLB_hit(c+ m) + TLB_miss(c + (n+1)*m) ) + Page_miss( Service time)

I think this formula is not valid here because page_hit or page_miss ratio depends on no. of instructions and not on memory accesses.


For n level paging we use:-

 TLB_hit(c+ m) + TLB_miss(c + (n+1)*m) 

@Tuhin Dutta may you please explain me where this formula fits in Arjun sir's explanation.


The formula can be written in this way:

TLB_hit*c + TLB_hit*m + TLB_miss*c + TLB_miss*n*m + TLB_miss*1*m

Now as per question,

n = no of page table levels; TLB access time(c) = 0; Mem Access(m) = 150 

On putting the values,

= 0.9*0 + 0.9*150 + 0.1*0 + 0.1*2*150 + 0.1*1*150 

= 0.9*0 + 0.1*2*150 + 0.9*150 + 0.1*150 

= 0.1*2*150 + 0.9*150 + 0.1*150

= 0.1*2*150 + 1*150

This bold portion should be multiplied by 2 since each instruction does 2 mem. accesses which is actually done by Arjun sir separately.

Summary of the given solution:

Instruction: Add R1, M[1000], M[2000]

All instructions are in this format, each instruction needs 100ns CPU time, two memory access to fetch both the operands. Address translation will be done for both the operands.

Avg execution time = 100ns (cpu time) + .9*2(0)(Add translation time for both the operands TLB Hit) + .1*2*(150+150)(TLB miss for both the operands Add translation time) + 2*150(both operands are fetched from the memory) + (1/10000)*8ms ( avg page fault service time)

$= 100ns + 0 + 60ns + 300ns + 800ns = 1260ns$
Shouldn't the last part i.e. page fault service time be multiplied by 2 as page fault can happen in both operand fetch from memory?
@swati page fault is given per instruction but not per memory address


100 + 2*150 + 2*(0.9*0 + 0.1*2*150) + 800 = 1260

For TLB access, is it because we are considering two addresses so that's why 2 is multiplied?

 what, if it is an instruction with indirect addressing(operand of the instruction gives the location where the address of the actual operand is stored) then do we need to access TLB twice? 

100 + 2*150 + 0.9*0 + 0.1*2*150 + 800 = 1230

@ arjun sir

why .0001*8ms is not multiplied by 2
why you havent multiplied 800 by 2???
+14 votes

(gate 2004 qus)

EAIET=[CPU execution time]+(TLB Hit*2*Memory access time +TLB miss ratio(page table access time+2*memory access time ))+{page fault probability*page fault service time}
That is 100ns+(0.9*2*150+0.1(150+150+2*150))+800ns.....[800ns herecomes from 0.0001*8*10^6]


answered by Active (2k points)
0.1(150+150+2*150) can u please explain why did you do 150 +150  why is it not just 150
this part 0.1(150+150+2*150) is not correct when there is a  miss in the TLB then both operands need 2*(150+150)ns time for address translation. and further 2*150ns for actual operands fetch from the memory.
+12 votes

I think this problem has two parts---

1st:- We have to calculate Instruction execution time when Instruction is in Memory.

        Execution Time in this case is---

                     TLB hit(time to execute instruction)+TLB miss(PageTable access + time to execute instruction)

                   =TLB hit(time to execute instruction)+TLB miss(2*MemoryAccessTime + time to execute instruction)

                  =TLB hit(CPU time+2*MemoryAccessTime)+TLB miss(2*MemoryAccessTime + (CPU time+2*MemoryAccessTime))


                 =430 ns

2nd-      Now we also have to include the fact that Instruction may not be in Mainmemory.Then we have to service page fault first             then we execute instruction like above case

           So overall effective average instruction execution time would be

                      =P*(PageFaultServiceTime+InstructionExceTime when in memory)+(1-P)(InstructionExceTime when in memory)


Please let me knw if there is any issue.

answered by Loyal (6.5k points)
In second case, why are you not taking the time for address translation?

2nd case is not about address translation.It is about whether instruction is in mainmemory or not.depending on that we have two cases where you see we have InstructionExceTime when in memory which include full instruction execution along with translation(as calculated in case 1)

should not we consider page fault when there is tlb miss why we are considering it to be separate
chk once more

here page fault is calculated when tlb miss

but thing I notice, it is only calculating when the instruction not in main memory.rt?
yes page fault will be calculated when instruction will not be in main memory instead of tlb miss.

In the above answer,

 =TLB hit(CPU time+2*MemoryAccessTime)+TLB miss(2*MemoryAccessTime + (CPU time+2*MemoryAccessTime))

When a  mis occur then we access two page tables,after that we got physical address,now we should do one more memory reference to read that memory and then we should add + (CPU time+2*MemoryAccessTime))

Can some one clarify on this?


@ rahul sharma 5

this answer is not correct. Chk selected ans

+6 votes

Average instruction execution time $= (100+0.9(2*150)+0.1(4*150)+\frac{8*10^{6}}{10^{4}})$ns

$\Rightarrow 1230$ns.

Explainations -

  • $2$ memory accesses if page is found in TLB.
  • $4$ memory accesses if page is not found in TLB. Additional $2$ memory accesses just because of 2 level page. 2 Memory accesses for 2 page tables would be there on TLB miss.

Answer is D.

answered by (81 points)
edited by
+2 votes

Given  - 
memory access time (MA)= 150ns
TLB HIT Rate (ht) = 90%
No. Of Levels in paging scheme (k) = 2
Page Fault Service Time (Pf) = 8 milli sec
Page Fault Rate (Pr)= 1/10000

TLB search time= negligible = 0

page fault service time when pagefault  Pf*Pr = 800ns

Instruction Access time (IAT)= 100ns +2*(MA) = 400ns

(hierarchical way )

EAIT = TLB search time  + (TLB MISS * 2 level memory access time) + (page fault service time when pagefault) + Instruction Access time

EAIT= t + (1 - ht) (k*MA) + IAT + (Pr*Pf)
         = 0 + (1-0.9)(2*150) + 400 + (800)

       = 0 + (0.1)(2*150) + 400 + (800) = 30 + 400 + 800

          = 1230 ns

answered by Active (2.3k points)
edited by
where have u taken tlb hit?

TLB search time is time when page is found in Tlb

0 votes

T(memory access avg) = .90(150) + .1(150+150+150) = 180 (150- level1, 150-level2 and 150-memory) 
T effective = 100+ 2* 180 + 1/10000* 8* 10^6 = 1260. 

answered by Active (2k 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

38,017 questions
45,509 answers
48,736 users