FOR FREE CONTENT

GATE 2020 Question on EMAT, TLB, and Page Fault rate

Question: GATE 2020 on Effective Memory Access Time 

Consider a paging system that uses 1-level page table residing in the main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, the 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. TLB update time is negligible.

The average memory access time in ns (round off to 1 decimal places) is ________ .

Note – This question was Numerical Type.

(A) 154.5

(B) 155

(C) 755

(D) 725

You should know:

Before seeing the solution please follow the previous chapter:  Effective Access Time using Hit ratio and Miss ratio, Effective Memory Access Time (EMAT) with Page Fault rate, Number of information at page entry

Solution: 

It looks like a complex question but if you understand the concept it will be easy. 

Concept of the given question (Algorithm to calculate Effective Memory Access Time)

A TLB Hit:

1. It is a paging system where we first search the page entry of the required page is present at TLB or not.

2. If it present at TLB then access TLB, get page entry and corresponding frame number. Then access memory to get the required byte using this frame number. In this case, only one memory reference is used.

B TLB Miss:

1. Page Fault Miss (Page fault not occurred) 

If the page entry of the required page is not present at TLB, then go to the page table which resides at the memory and get the page entry and corresponding frame number. Then access main memory to get the required byte using frame number. So, here we access the main memory two times. 

2. Page Fault Hit (Page Fault Occurred) 

Page entry of required page not present at TLB, even when we go to main memory for page table, this particular page (page entry) is not present at the memory, which is page fault. Then we go to disk and bring up the page to main memory. 

When page fault occurred, it has also two situations: 

a.No page replacement: The memory frame is free where we load the page from disk to main memory, so, no page replacement is required. Here we use one memory access and one disk access.

b.Page replacement: Main memory is not empty, no free frame, we have no space to load a new page, and then we have to replace an existing page from memory to disk. And load a new page from disk to recently free space at main memory. Here we use one memory access but two disk access. 

Dirty Page: Sometimes replaced page is modified (dirty page), so it has to take backup of all modified data when it places to main memory to disk. 

Now, here given some hit rates and miss rates as per the hit rate of TLB, page fault and page fault with modified (dirty) page Effective Memory Access Time will be calculated.

Now, try to calculate a generalized formula:

Where, TLB hit ratio = h, Page fault hit rate = p and page fault with dirty page hit rate = dr, TLB access time = t , memory access time = m and disk access time = d.

1.  No dirty page: No dirty page or no page replacement (with Dirty page miss rate).

2.  Dirty page: Page replacement with the dirty page (with Dirty page hit rate).

We hope you understand the concept of the question and formula of EMAT.

Here, 

TLB hit ratio (h) = 95% (0.95), Page fault hit rate (p) = 10% (0.1)and page fault with dirty page rate (dr) = 20% (0.2), TLB access time (t)= 20 ns , memory access time (m)=100 ns and disk access time (d) = 5000 ns.

EMAT = 154.5 ns

So, option (A) is correct.