edited by
62,877 views
129 votes
129 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. $\text{645 nanoseconds}$
  2. $\text{1050 nanoseconds}$
  3. $\text{1215 nanoseconds}$
  4. $\text{1230 nanoseconds}$
edited by

19 Answers

Best answer
161 votes
161 votes
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

 $=\underbrace{100}_{\text{Average CPU execution time}}+\underbrace{2\left(0.9 (0) + 0.1 (2 \times 150)\right)}_{\text{Average address translation time for each instruction}} + \underbrace{2\times 150}_{\text{Average memory fetch time for each instruction}} + \underbrace{\dfrac{1}{10000} \times 8 \times 10^6}_{\text{Average page fault time for each instruction}}$

(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 \textsf{ ns}$

PS: GATE question might have missed the time for second address translation in their calculation which might have made them give 1230 in option D instead of 1260.
edited by
113 votes
113 votes

I think here we are overcomplicating things and question is simple but we need to understand it carefully.

 page fault rate is one in every 10,000 instructions.

 

 Page fault service time=8ms.

So, on an average time lost due to page fault per instruction=$\frac{8ms}{10000}=800ns$

Now, to this compute Memory access time using TLB.

$EMAT=0.9(150)+0.1(3*150)=180ns$

Since, 2 Memory References are made, Hence total time=$360ns$

To this, $100ns$ of cpu time.

effective average instruction execution time=$800+360+100=1260ns$

31 votes
31 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))

                 =0.9(400)+0.1(700)

                 =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)

                     =(1/10000)(8*106+430)+(9999/10000)(430)=1230ns

Please let me knw if there is any issue.

19 votes
19 votes

effective average instruction execution time = CPU TIME + 2 (effective memory access time )

effective memory access time= logical address To physical address + fetch the bye from memory 

                                                =  t+(1-pt)(km)+m+pf(ps) (t =tlb access time ,pt =tlb hit, k= paging level, m= memory access time ,pf page fault,ps= page service )

                                    =   0+(1-0.9)*(2*150ns)+150ns+(1/10000)(8ms)

                                     =30ns+150ns+800ns=980ns 

effective average instruction execution time= 100+2(980)=2060ns .. so ans is none of this ...

reshown by
Answer:

Related questions

66 votes
66 votes
9 answers
1
Kathleen asked Sep 18, 2014
23,663 views
The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined bythe instruction set architecturepage sizenum...
59 votes
59 votes
4 answers
2
go_editor asked Apr 24, 2016
19,515 views
Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$\begin{array}{|l|l|c|} \hline \text {Instruction} & \text...
35 votes
35 votes
3 answers
3
52 votes
52 votes
10 answers
4