GATE CSE 2020 | Question: 53

Question

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 ___________

Comments

So the general convention in standard books is to include pf only when there is a tlb miss? unless it is specifically given that page fault rate given is for each memory access?

---

Well page fault rate being not w.r.t memory access -- I have seen only in that one standard book. You can post this question in stack exchange where you might get a better clarity regarding the confusion.

---

I found this way easy may be it wil also help you , if you not understood formula by best answer just look this solution ( if understood then ignore this comment )

https://gateoverflow.in/333178/gate-cse-2020-question-53?show=420032#a420032

Answer 1

Memory Access Time = 100 ns

TLB look up = 20 ns

no.of levels in paging = 1

page fault rate=10%

 

AMAT = evaluate Memory Address + Access Memory Address

evaluate Memory Address = $0.95*20 + 0.05 (20+ 1 * 100 )$ = 19+6=25 ns

Access Memory Address = Page fault rate * Pagefault service Time + (1-page fault rate) * Memory Acess time.

 

Page fault service time = dirty read + non-dirty read

= 0.2*(5000 + 5000+100) + 0.8* (5000+100) = 2020+4080=6100 ns

Dirty read --- 5000 for writing back to the page, 5000 for fetching new required page and 100 for accessing it.

 

Access Memory Address = 0.1 * 6100 + 0.9 * 100 = 610 + 90 = 700 ns

 

AMAT = 25 + 700 = 725 ns

Comments

In the question page transfer time is given and not the page service time. So i think we have to add the time to access memory again on page fault

yes, i missed that.

---

God @shashin, will you challenge this one, since official key differs?

---

Congratulations @Shaik Masthan for your GATE 2020 rank. Your answers and comments helped a great deal while preparing for this exam.

Answer 2

@Arjun sir, This should be the logical flow..Could you please check..

Comments

You can check in Galvin. Once page fault happens, after page is filled in, memory access is reinitiated.

---

@Arjun Sir, we have 10% of memory access as Page Faults.

So, for these 10% we will need to perform address resolution once again, but memory will be accessed only once.So we need to add (0.1 x 25) ns = 2.5 ns.
In your answer we have (0.1 x (25 + 100)) = 12.5 ns extra, where you have considered memory access after Page Fault.

If we go by Galvin also, we need to perform only address resolution again.

---

No. It'll be another memory access but for the same virtual address. It is due to this complication, most books use "page fault service time" instead of "page transfer time". Also, "page fault mechanism" can vary as per the implementation. Answer to this question will definitely be a range one.

Answer 3

The answer can be divided into parts:
= Time to convert VA to PA + Access word
= [tlb_access_time + tlb_miss_rate * k_levels_paging * memory_access_time]
  +  
[memory_access_time + page_fault_rate (page_fault_service_time + dirty_page_rate * write_back_time) ]
= [20 + 0.05 * 1 * 100]
   +
   [100 + 0.1*(5000 + 0.2 * 5000)]

= [25] + [100 + 600]
= 25 + 700
= 725

Answer 4

95%tlb hit*(tlb access time + 20% of 10% dirty page + 80% of 10% simple page fault + 90% no page fault) +  5%TLB miss*(tlb access time + paging time + same story)

effective memory access time =

0.95{20 + 0.1*0.2*(100+5000+5000) + 0.1*0.8*(100+5000)+0.9*(100)} + 0.05{20 + 100 + 0.1*0.2*(100+5000+5000) + 0.1*0.8*(100+5000)+0.9*(100)}

= 0.95*720 + 0.05*820

= 684 + 41

=725 ns