Consider a paging system that uses 1-level page table residing in 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%, 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 ________.

Correct Answer:

155

Solution:

Given:
Main memory access time (Tm) = 100ns
TLB lookup time (Tt) = 20ns
TLB hit ratio (Ht) = 95%
Page fault rate (Pf) = 10%
Page service time (PST) = time to transfer to/from disk = 5000 ns

For 20% of total page faults, a dirty page has to be written back to the disk.
Dirty page Rate (P) = 20%

Now, Effective memory access time (EMAT) = Access time in TLB Hit + Access time in TLB Miss

EMAT = Ht (Tt + Tm) +   //TLB Hit 
       (1 - Ht){        //TLB Miss
          (1 - Pf) (Tt + Tm + Tm) +  // No Page Fault 
          Pf [                       // Page Fault
             P (Tt + Tm + PST + PST + Tm) +     // Dirty Page write back
             (1 - P)(Tt + Tm + PST + Tm)        // No Dirty Page write back
          ]
        }
EMAT = 0.95 (20 + 100) + 
       0.05 (0.9 (20 + 100 + 100) + 
             0.1 (0.2 (20 + 100 + 5000 + 5000 + 100) + 
                  0.8(20 +100 + 5000 + 100)
             )
       )
EMAT = 114 + 0.05(198 + 0.1(2044 + 4176))
     = 114 + 0.05(198 + 622)
     = 114 + 41
     = 155ns

Complete Explanation:

In TLB Hit,
⇒ Ht (Tt + Tm)
⇒ 0.95 (20 + 100) = 114  .... (1)

In TLB Miss,
(1 - Ht) (Access time If no page fault occur + Access time if page fault occur) .... (2)

Access time if no page fault occur,
⇒ (1 - Pf) (Tt + Tm + Tm)
⇒ (1 - 0.10)(20 + 100 + 100) = 198 .... (3)

Access time if page fault occur,
⇒ Pf (Access time if dirty page + Access time if no dirty page) .... (4)

Access time if dirty page,
⇒ P (Tt + Tm + PST + PST + Tm)
⇒ 0.20 (20 +100 +5000 + 5000 + 100) = 2044 .... (5)

Access time no if dirty page,
⇒ (1 - P)(Tt + Tm + PST + Tm)
⇒ 0.80 (20 +100 + 5000 + 100) = 4176 .... (6)

Put (5) & (6) in (4)
Access time if page fault occur,
⇒ 0.10 (2044 + 4176) = 622 .... (7)

Put (3) & (7) in (2)
In TLB Miss,
⇒ 0.05 (198 + 622) = 40.7

Now, EMAT = 114 + 40.7 = 155.0 ns