The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes

First read this whole thing what I am writing below:

Case 1: If we have to access unit address in memory using TLB and we assume that no page fault occurs then,

EMAT=p( T+M )+( 1-p ) (T+M+M)

T=TLB access time, M=memory access time(page table access time is included), p= TLB hit. EMAT : estimated memory access time.

case 2: As case 1 , But here page fault occurs.

QUESTION: Now how will we calculate EMAT?
Does the following calculated EMAT affect or contributes to the solution of my question?
EMAT= X(S+M)+(1-X)(M)
X=page fault occurring ratio, S=page fault service time
Note: Here we are not using any TLB. This is for normal virtual memory concept without TLB

Now my main question is: when we calculate EMAT using TLB and if there page fault occurs then how does the last calculated EMAT here affects the first Estimated memory access time which we have calculated using TLB?

in Operating System by Junior (559 points)
edited by | 367 views

1 Answer

+1 vote

EMAT= X(S+M)+(1-X)(M)

just add one more M for page table access at the beginning and it will be correct:

EMAT= M + X(S+M)+ (1-X)(M)

In paging and cache concepts always go step by step, i.e., hierarchically. EMAT with TLB and Page Fault both in picture:

If TLB is updated asap(use this for numericals):

EMAT = t ( tat + m ) + (1-t) ( tat + m + pf(pfst+m) + (1-pf)m ) 

If TLB hasn't been update when we looked up for a page in it(helpful in interviews just to give a point):

EMAT = t ( tat + pf(pfst+m) + (1-pf)m ) + (1-t) ( tat + m + pf(pfst+m) + (1-pf)m ) 

where t=TLB hit probability, tat=TLB access time, pf=Page Fault probability, pfst=Page Fault service time and m=memory access time.


check with TLB
if found in TLB
        go to memory
else not in TLB
        go to page table in memory 
            go to memory
                if page fault occurs
                    service page fault then acess memory
                    access memory

by Loyal (5.2k points)
edited by
Sorry, I forgot to mention that in M i have included the page table access time. Thnks
Your welcome. Including page table access time in M will make your equation in Case 1 incorrect.

Thus, EMAT=p( T+M )+( 1-p ) (T+M+M)

becomes: EMAT=p( T+M )+( 1-p ) (T+M)

Now, one can not differentiate between first part when only memory is accessed for a specific page and second part when both page table and memory(for a page) is accessed.

That's why, you should not include page table access and memory access together for simplification purposes.

Akhilesh Singla I'm not able to understand this part of equation  t ( tat + pf(pfst+m) + (1-pf)m ) . 

if there's a tlb hit means that is page is already loaded in memory than why are you taking page fault rate and page fault service time in this case.

shouldn't it be like t(tat+m) ?

Hmm, you are right. I included it for cases when TLB hasn't been updated about a page which has left the memory. I should have mentioned that. And the standard approach doesn't include my assumption. I will edit it now. Thanks for pointing it out.

EMAT = t + m + (1-Ht)( p * PS  + (1-p) * m )

t= tlb access time

m= memory access time

Ht= hit rate of tlb

p= page fault rate

PS= pagefault service time

Can't we use this formula as t + m is access whether is TLB hit or TLB miss. Please help on this topic I'm confused. How tlb and page fault rate formula is changed when cache is also introduced.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,376 questions
55,812 answers
91,176 users