IAE Academy

GATE 2020 CS Q.53: solution and answer

GATE 2020 · CSQ.53 · 2 marks · NAT

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 in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ______.

See the question in the paper
GATE 2020 CS question 53Tap to open full size

Answer and solution

ANSWER

The average memory access time is 155.0 ns.

Official answer: 154.5 to 155.5Source: Official answer key, GATE 2020 CS (IIT Delhi)

  1. A TLB hit costs the TLB lookup plus one memory access: ns.

  2. A TLB miss with the page in memory costs the TLB lookup, one access to the 1-level page table in memory, and one access for the data: ns.

  3. A page that is not in memory cannot have a TLB entry, so a page fault can happen only on a TLB miss. We therefore read the 10% page fault rate as applying to TLB misses.

  4. Page fault service time: with a clean victim there is one disk transfer, ns. With a dirty victim there are two transfers (write-back, then read), ns. The average is ns. The TLB update time is negligible.

  5. Cost of a TLB miss: ns.

  7. So the average memory access time is ns.

KEY IDEA

Page faults happen only on TLB misses. Weight the hit path (120 ns) by 0.95 and the miss path (220 ns plus 0.1 times the average fault service time of 6000 ns) by 0.05.

WATCH OUT FOR

Applying the 10% fault rate to every access, or charging the fault service to TLB hits. That gives about 725 ns instead of 155 ns. Another slip is counting only one disk transfer for a dirty page, when it needs a write-back and a read.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 6 Virtual memory questions, with notes

More Virtual memory questions