Log In
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
edited by

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

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

0 votes
1 answer
Why the formula used here is not P(10) + (1-P)(50) = 20 ?; A computer keeps its page tables in memory. The time required to read a word from the page table is 50ns. To reduce this overhead, the computer has a TLB, which holds 32 (virtual page, physical page frame) pairs and can do ... Solution: 10ns + (1 - p) 50ns = 20ns p =4/5 = .80 The TLB hit rate has to be 80% for a mean access time of 20ns.
asked Dec 3, 2018 in Operating System rahuljai 428 views
2 votes
1 answer
A computer has a 128-entry $L_1$ TLB, 1024-entry $L_2$ TLB, and uses page size of 4KB. A program reads a 1MB array, one byte at a time from start to end, 10 times. Assuming the TLBs are directly mapped and initially empty, and no other memory is accessed, find TLB hits and misses of both $L_1$ and $L_2$ TLB (array is page aligned).
asked Aug 8, 2017 in Operating System habedo007 409 views
1 vote
0 answers
Consider a memory system consists of a single external cache with an access time of 30ns and a hit rate of 0.85, and a main memory with an access time of 80ns. Now we add virtual memory to the system. The TLB is implemented internal to the processor chip and takes 4ns to do a ... the effective memory access time of the system with virtual memory?( Marks: 0.00 ) 8ns 30ns 40ns 51ns
asked Jan 17, 2017 in Operating System Neal Caffery 461 views
0 votes
3 answers
Consider a system with 2-levels of paging and a TLB with hit rate of 95% and TLB access time of 1ns. Find the effective memory access time if there’s a data cache whose hit rate is 85% and cache access time is 1ns, and main memory access time is 100ns. 100ns. 27ns ​​​​​​​ 25ns ​​​​​​​ 30ns ​​​​​​​ 20ns
asked Jan 17, 2017 in Operating System Neal Caffery 1.3k views