1,905 views

Page tables are stored in memory , which has access time of 100 ns. The TLB holding 8 page table entries, has an access time of 10 ns. Using execution of process , it is found that 85 % of the time, a required page table entry exist in TLB and only 2 % of the total references causes page fault. Page replacement time is 2 ms . Calculate the effective memory access time , assuming page memory access requires 2 memory accesses and TLB requires one memory access.

A) 38120 ns B) 40000 ns C) 40120 ns D) None

1 comment

what if page fault occured in case of TLB hit also. Should we not consider that in this?

Subscribe to GO Classes for GATE CSE 2022

Page table access time=$100 ns$

TLB has 8 PTE and access time of a PTE is $10 ns$, that means TLB access time $10 ns$

Page Table are in TLB i.e. TLB  hit time$=85$%

Page Fault is for $=2$%

TLB miss time $=13$%

For TLB hit =$1$ memory access

For TLB miss=$2$ memory access

So, Effective Memory Access Time$=0.85\left (100+10 \right )+0.13\left ( 100+100 \right )+\frac{2}{100}\times 2000000$

$=40119.50ns\simeq 40120ns.$

Ans $C)$

https://www.inf.ed.ac.uk/teaching/courses/os/slides/10-paging16.pdf

Similar ques from book https://gateoverflow.in/211302/operating-system-by-harris

by

@srestha maam why did you take tlb miss rate as 13%? shouldnt the tlb miss rate be 15%???
any reference?
shouldnt we evaluate in this approach?

EMAT= 0.02(10+100+2000000)+0.98(0.85(10+100)+0.15(10+100+100))??
no....
I am not getting your approach..:( maam can you please explain...

chk this type of gate ques, u get the idea

for example can see this https://gateoverflow.in/2122/gate2011-20-ugcnet-june2013-ii-48

edited
@srestha ma'am, thanks ma'am.. Finally got it :)

but ma'am don't we need to add tlb access time and page table access time in case of page fault?
dont relate TLB hit or miss with page fault ,so i think answer explain by you is wrong
@Gurdeep Saini we need to consider page fault only in case of a tlb miss. So here it is mentioned that of the total page references 2% of them are page faults.

Consider you have total 100 page references.out of these 100, 85 page references result in tlb hit and 15 of them result in tlb miss. Now it is already said that 2% is the page fault rate. So out of 15tlb misses,  13 are tlb miss with page table hit and 2 of them are both tlb miss as well as page table miss.

as per my knowledge,

let it is 1-level paging only for simplicity,

first search in TLB, if hit, directly goto the Memory address, and fetch it

if miss, then one time for page table and one time for fetching

EMAT = TLBhit(TLBaccess time + Page_Fetch) + TLBmiss ( TLBaccess time + Page table Fetch + Page_Fetch )

= ( TLBaccess time ) + TLBmiss ( Page table Fetch ) + Page_Fetch

Now, assume Page fault, Every Page Fault requires Page service

Effective Page_Fetch =  ( Page_Fault ( Page_service + Page_Fetch ) + ( (1-Page_Fault) * Page_Fetch ) )

=  Page_Fault ( Page_service ) + ( Page_Fetch )

∴ EMAT = ( TLBaccess time ) + TLBmiss ( Page table Fetch ) + Page_Fault ( Page_service ) + ( Page_Fetch )

edited by

from my concept ,

EMAT  = (Time taken to convert virtual address to physical address VA -> PA) + Time taken to access the byte  /word from memory

= TLB access time +  TLB miss (No_of_page_table * Memory access) + Memory access + Ppage-fault  * Page_fault_service_time

= 10 + 0.15 * 100 + 100 + 0.02 * 2 * 2 x 106

= 40125 ns

@magma

10 + 0.15 * 100 + 100 + 0.02 * 2 * 2 x 106

typo in this line please correct it you have write 2 two times but your approach is correct

@Magma only for 13% of the times it is a tlb miss and a page table hit. For 2% of the time it is a tlb miss and a page table miss also, i.e. a page fault occurs.

Is this concept is right ??? Somoshree Datta 5

@Magma, no..it is mentioned in the question that 2% of the total references are page fault and not 2% of the tlb misses are page fault. So from 100 pages, 2 pages have caused page fault. So  85 pages are tlb hit and 13 pages are tlb miss but page table hit.
GOt it !

btw very confusing  :3
Exactly! :(
when TLB hit also, it should goto Main Memory, then Page fault may occurs.

Note that it is TLB, used for direct access of memory by avoiding pagetables.

If it is cache, then as you said Main Memory Access skipped at that time.
@Shaik how can a page fault occur on a tlb hit?? tlb hit itself means that the particular is present in the main memory. If this wasnt the case then it would have been a tlb miss.

@somoshree check this u will get ur answer

https://gateoverflow.in/73973/%23operating-system

@Srestha ,Shaik yes a page fault might occur on a tlb hit..but will the answer differ because of this??We never consider page fault with tlb hit while attempting numericals..if there is a page fault in case of tlb hit, then it should be explicitly mentioned in the question..I dont think in any of the sums asked in GATE they considered tlb hit and page fault together..
I havenot considered it also :)
edited by

@Shaik

EMAT = ( TLBaccess time ) + TLBmiss ( Page table Fetch ) + Page_Fault ( Page_service ) + ( Page_Fetch )

how tlb hit not require any main memory  access? It needs 1 access, explicitely given in question too

how page table not require any main memory  access?

i considered it when TLB miss, Read my comment clearly mam

in case of tlb miss we must add tlb access time also.. 0.85(100+10)+.13(100+100+10)+ .02×2 milliseconds

D

0.85(10+110)+0.15(13/15(10+100+100)+2/15(10+100+2000000+100)=40125

85% time there will be a TLB hit so it will take (10+100) ns.

15% of the time two things can happen:

• X% of the time page fault will occur that is it will take (10+100+2000000+100) ns.
• (1-X)% of the time no page fault so it will take (10+100+100) ns.

Page fault occurs 2% of the total memory accesses so X% of 15 should be equal to 2.

i.e. 15 * X/100 = 2        X=200/15.

@Viral Kapoor

how 13/15 comes in your equation?

can u explain how you got those accesses time and what all are your considerations?