GATE CSE 2004 | Question: 47

Question

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?

• A. $\text{645 nanoseconds}$
• B. $\text{1050 nanoseconds}$
• C. $\text{1215 nanoseconds}$
• D. $\text{1230 nanoseconds}$

Comments

@anurags228

bro how u got 450 ?

---

Everyone is giving different answers. Literally confused. Someone pls say which one is the correct solution to this question.

---

Instead of 2*( Effective average Instruction execution time )

if i take 100  + 1*( Effective average Instruction execution time )

then im getting 1215 ns sec as my answer

and that is even matching with options too.

Answer 1

A simple approach to this question:

1. TLB hit:

      1.1 no page fault : access the instruction

      1.2 page fault : service the page fault

 

2. TLB miss:

 Access 2 levels of paging and then:

     2.1 no page fault : access the instruction

      2.2 page fault : service the page fault

so, average instruction execution time =

$0.9[0 + 0.0001(8*10^6) + 0.9999(400)] + 0.1[0 + 300 + 0.0001(8*10^6) + 0.9999(400)] = 1229.96 ns$

instruction execution time = 100ns + 2[150ns] = 400ns

Answer 2

Answer is 1260.

How?

see first the CPU will fetch the instruction:
Here arises 2 cases.
Case I:The instruction is  present in the main memory.
Here for instruction memory accesses will be perforrmed.

for 1 memory access avg access time:

X=TLB hit(TLB access time+memory access time for the word)+TLB miss(TLB access time+memory access for first level of page table+memory access for 2nd level of page table+memory access for the word)

X=0.9(0+150)+0.1(0+150+150+150)=135+45=180ns.
we require 2 memory access/instruction  there fore for each instruction 2X=360ns necessary for memory access.

Case II:The instruction is  not present in the main memory.

then we need

Y=page fault service time +time to access memory 2 times=8 *10^6+2X
 

finally.......

the time required:
The CPU time required per instruction+0.9999(time taken when instruction is present in the memory)+0.0001(time taken when instruction is not persent in the memory).

100ns+0.9999(2X)+0.0001(8 *10^6+2X)=1260ns

 

 

 

 

 

Answer 3

I was also confused by this question and was not able to understand as per the concepts that I have understood so far, after struggling it with some time (a-lot of time) I was able to break it down to pieces and was able to come to logical explanation, hope it will be helpful to fellow aspirant.

 

Please refer the the snapshot attached.

 

 

 

Answer 4

I was also confused by this question and was not able to understand as per the concepts that I have understood so far, after struggling it with some time (a-lot of time) I was able to break it down to pieces and was able to come to logical explanation, hope it will be helpful to fellow aspirant.

 

Please refer the the snapshot attached.