retagged by
44,945 views
51 votes
51 votes
Consider a paging system that uses $1$-level page table residing in main memory and a $\textsf{TLB}$ for address translation. Each main memory access takes $100$ ns and $\textsf{TLB}$ lookup takes $20$ ns. Each page transfer to/from the disk takes $5000$ ns. Assume that the $\textsf{TLB}$ hit ratio is $95 \%$, page fault rate is $10 \%$. Assume that for $20 \%$ of the total page faults, a dirty page has to be written back to disk before the required page is read from disk. $\textsf{TLB}$ update time is negligible. The average memory access time in ns (round off to $1$ decimal places) is ___________
retagged by

10 Answers

Best answer
110 votes
110 votes

Given,

  1. Main Memory access time: $100$ ns
  2. TLB lookup time: $20$ ns
  3. Time to transfer one page to/from disk: $5000$ ns
  4. TLB hit ratio: $0.95$
  5. Page fault rate: $0.10$
  6. $20$ % of page faults needs to be written back to disk

Hence, effective memory access time =

$0.95(20+100) + 0.05\{0.90(20+100+100) + 0.10[0.80(20+100+5000+100) + 0.20(20+100+5000+5000+100)]\}$
$=155.0$ ns

Explanation:

If there is a TLB hit, you just need to access the memory. If there is a miss 1 TLB lookup was wasted,

  1. You need to lookup the page table for the entry and then access the required location, requiring 2 memory accesses - Assuming No Page fault occurs.
  2. If there is a page fault, Then 1 memory access was wasted (you can only know that the page is not present in memory by  checking the corresponding page entry in the page table). $80$ % of the time, you'll only be fetching a page from secondary storage which takes $5000$ ns, $20$% of the time, you'll need to write a dirty page back to disk and bring the page (which caused the page fault) back to main memory, requiring $5000+5000$ ns 
selected by
37 votes
37 votes
  • For all memory accesses in a system with virtual memory we need Virtual Address to  Physical Address translation and this goes through TLB.
  • On TLB hit, we get the physical address.
  • On TLB miss, we have to do page table access which always resides in physical memory (no page fault possible here).
  • In the question it is given $1-$ level page table is used. So, TLB miss will need one physical memory access to get the physical address.
  • Question mentions page fault rate as $10\%$ and this should default to $10$ page faults every $100$ memory accesses. (Since TLB miss rate is $5\%$ and for normal program run a TLB hit and page fault cannot happen for a memory access (can happen for invalid memory accesses), it is also possible to consider page fault rate as $10\%$ of all TLB misses. See the last part of the answer for this.


In the question page transfer time is given. This is different from page fault service time which includes the page transfer time + the memory access time as once the page is filled, a new memory access is initiated.

So, $\text{Average Memory Access Time}  = \text{Address Translation Time} + \text{Data Retrieval Time}$
$\qquad = \text{TLB access time} + \text{TLB Miss ratio} \times {\text{Page Table Access time}} + \text{Main memory access time} + \text{Page fault rate} \times (\text{Page fill Time} + \text{Address Translation Time} + \text{Main memory access time}) + \text {Dirty Page Rate} \times \text{Page Write Time} $
$\qquad = 20 + 0.05 \times 100 + 100 + 0.1 \times (5000 + 20+ 0.05\times 100+ 100) + 0.1 \times 0.2 \times 5000$
$\qquad = 20 + 5 + 100 + 512.5 + 100$
$\qquad = 737.5 \; ns$

PS: If the question had given page fault service time also as $5000$ answer will be
$20 + 0.05 \times 100 + 0.9 \times 100 + 0.1 \times 5000  + 0.1 \times 0.2 \times 5000 = 25 +90 + 500 + 100 = 715\; ns$


"Assume that the TLB hit ratio is 95%, page fault rate is 10%"

If this statement is changed to 

"Assume that the TLB hit ratio is 95%, and when TLB miss happens page fault rate is 10%"

$\text{Average Memory Access Time}  = \text{Address Translation Time} + \text{Data Retrieval Time}$
$\qquad = \text{TLB access time} + \text{TLB Miss ratio} \times {\text{Page Table Access time}} + \text{Main memory access time} + \text{Page fault rate} \times (\text{Page fill Time} + \text{Address Translation Time} + \text{Main memory access time}) + \text {Dirty Page Rate} \times \text{Page Write Time} $
$\qquad = 20 + 0.05 \times 100 + 100 + 0.05 \times 0.1 \times (5000 + 20+ 0.05\times 100+ 100) + 0.05 \times 0.1 \times 0.2 \times 5000$
$\qquad = 20 + 5 + 100 + 25.625 + 5$
$\qquad = 155.625 \; ns$

If "memory access being restarted" is ignored for page fault, this will be 

$\qquad = 20 + 0.05 \times 100 + 100 + 0.05 \times 0.1 \times (5000) + 0.05 \times 0.1 \times 0.2 \times 5000$
$\qquad = 20 + 5 + 100 + 25 + 5$
$\qquad = 155\; ns$


Ideally the answer key should be $715 - 738$ due to the confusion in the meaning of page transfer time as most standard resources use page fault service time instead.

If we assume page fault rate is given "only when TLB miss happens" answer should be  $155-155.7$

A previous year question where page fault rate "per instruction" is clearly mentioned in question: https://gateoverflow.in/318/gate2004-47. This GATE2020 question is VERY POORLY framed and must be challenged.

Another similar question where TLB miss is taken as per memory access is given below (See the equation used in 3-e)

https://gateoverflow.in/?qa=blob&qa_blobid=5047954265438465988

edited by
13 votes
13 votes
TLB_HIT(tlb_access

                 + memory

                + %page_fault(

                                        %dirty(disk_access + disk_access) + %No_dirty(disk_access)

                                        )

               )

+

TLB_MISS(tlb_access

                   + (memory[for pagetable]

                   + memory

                   + %page_fault(

                                           %dirty(disk_access + disk_access) + %No_dirty(disk_access)

                                           )

                  )

 

Substituting the values:

0.95(20+100+ 0.1[ 0.2(5000+5000) + 0.8(5000) ])

+0.05(20+100+100+ 0.1[ 0.2(5000+5000) + 0.8(5000) ])

 

= 684 + 41 = 725.
12 votes
12 votes

Given,

  1. Main Memory access time: 100 ns
  2. TLB lookup time: 20 ns
  3. Time to transfer one page to/from disk: 5000 ns
  4. TLB hit ratio: 0.95
  5. Page fault rate: 0.10
  6. 20 % of page faults need to be written back to disk

 

Hence, effective memory access time =

0.95*(20+100) + 0.05*(20+100+100) + 0.1*5000 + 0.1*0.2*5000

=725.0 ns

When finding effective memory access time in TLB with page faults, first find TLB lookup time in case of TLB hit and TLB miss, then the time due to page fault. Here 20% of the page faults are causing dirty pages so we have to also consider that.

Answer:

Related questions

28 votes
28 votes
8 answers
2
Arjun asked Feb 12, 2020
16,296 views
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ______.