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

EAIT = CPU time + 2*(EMAT)

EMAT= (VA addr to PA addr) + (Access the byte from PA)

          = TLB access time + (1-TLB hit rate)(2*memory access time) + memory access time + (page fault rate * page servicing time)

         = 0 + 0.1(2*150) + 150 + (1/1000)(8 msec)

         = ( 30+150+800 ) n sec

         = 980 nsec

   EAIT = 100 + 2(980)

            = 2060 nsec (final answer)

Comments

A/Q:
PAGE FAULT IS OCCURRING ON THE BASIS OF INSTRUCTIONS AND NOT ON THE BASIS OF MEMORY ACCESS.
[the page fault rate is one in every 10,000 instructions.]

[BRIEF INTERPRETATION]

WE NEED TWO MEMORY ACCESS TO FETCH AN INSTRUCTION BUT FOR THE SECOND MEMORY ACCESS PAGE FAULT WILL NOT HAPPEN. 


DETAILED EXPLANATION AND INTERPRETATION OF THE PROBLEM:

Remember, the time that we are calculating is "per instruction" or for One single instruction.
Page fault means the process page that CPU wants to access is not present in the main memory and thus needs to be copied into main memory from SECONDARY MEMORY.
Now, when the memory was accessed for the first time, [A/Q:  An average instruction takes 100 nanoseconds of CPU time, and two memory accesses.] at that time only Page fault was resolved and the required instruction was brought in the main memory. So, even if we need two memory access for one instruction, the page fault service needs to be included ONLY ONCE as for the second memory access the same instruction is being accessed which is deemed to be present in the memory on second access.
You have taken the Page fault service time twice. It needs a correction, So subtract 800 from your answer to get 2060-800= 1260.


 

Answer 2

Effective average Execution Time is =

Average Cpu execution Time +

Avg Address Translation time +

Avg Memory Access Time + Page Fault Service for each instruction

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

=100 +60+300+800

= 1260 ns

None of the above

Comments

I think Page service (800) should also be multiply with 2 .

as one average memory access also include page service time .and for every memory access it should be included and your answer include it once  for two memory access.

Answer should be 2060ns

---

conclusion is that page service has already been done once and will be done after 10000 instruction that['s why answer include it once

Answer 3

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 4

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