50,364 views

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}$

Thank you :) @anurags228
thank you:) @anurags228
@anurags228

bro how u got 450 ?

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.
by

Which IIT released the GATE solution for 2004?

it is a 2 level paging so it will need 3 memory access 1st will give entry in 2nd page table and second time it will give actual address so processor need to access memory 3rd time also so so you need to multiply it by 3 instead of 2 so ultimate answer will be 1290 ns … please correct me if i am wrong.

https://gateoverflow.in/333178/gate-2020-cse-question-53

sir if take a look on your answer for gate 2020 question then if will find that answer for this gate 2004 question is 1230.

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$

This is by far the best explanation!!

@Jhaiyam (3*150) because once we have TLB miss, we would go to the outer page table which is located in the main memory, hence one memory access, after that, we move to the inner page table (which is also in the main memory), hence second memory access. Now we have done our V to P translation so we would access the required page from the frame number we’ve got from the inner PT, hence the third memory access.

The most important point is, we need to consider only one page fault per instruction, rather than considering page fault for each memory access (i.e in EMAT).

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.

edited by
yes page fault will be calculated when instruction will not be in main memory instead of tlb miss. That's why page fault will be with respect to instruction not with respect to memory access

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

this answer is not correct. Chk selected ans

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 ...

by

should we not get page fault only when there is TLB  miss?
This solution is absolutely right.... and none of the options are  correct...
memory access time should include page fault right?

1
19,264 views