GATE CS 2004 Q47 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

The effective average instruction execution time consists of three components: CPU execution time, memory access time, and page fault service overhead.

1. Page Fault Overhead:
The page fault rate is $1$ in every $10,000$ instructions ($10^{-4}$ per instruction).
$$\text{Page Fault Overhead} = 10^{-4} \times 8\text{ ms} = 10^{-4} \times (8 \times 10^6\text{ ns}) = 800\text{ ns}$$

2. Effective Memory Access Time (EMAT):
Each instruction requires $2$ memory accesses. For each memory access, the TLB hit ratio is $90\%$ ($0.9$).

• On a TLB hit (probability $0.9$): Only $1$ memory access is needed to fetch the data/instruction. Time taken = $150\text{ ns}$.
• On a TLB miss (probability $0.1$):
  • Official GATE key assumption: A TLB miss requires $1$ page table access + $1$ physical memory access (total $2$ accesses). Time taken = $2 \times 150\text{ ns} = 300\text{ ns}$.
  • Strict two-level paging interpretation: A TLB miss requires $2$ page table accesses + $1$ physical memory access (total $3$ accesses). Time taken = $3 \times 150\text{ ns} = 450\text{ ns}$.

Calculating EMAT for both cases:

• Case 1 (Official Key Assumption):$$\text{EMAT} = (0.9 \times 150\text{ ns}) + (0.1 \times 300\text{ ns}) = 135\text{ ns} + 30\text{ ns} = 165\text{ ns}$$Memory access time for $2$ accesses = $2 \times 165\text{ ns} = 330\text{ ns}$.
  $$\text{Total Time} = \text{CPU Time} + \text{Memory Access Time} + \text{Page Fault Overhead}$$$$\text{Total Time} = 100\text{ ns} + 330\text{ ns} + 800\text{ ns} = 1230\text{ ns}$$
• Case 2 (Strict Two-Level Paging):$$\text{EMAT} = (0.9 \times 150\text{ ns}) + (0.1 \times 450\text{ ns}) = 135\text{ ns} + 45\text{ ns} = 180\text{ ns}$$Memory access time for $2$ accesses = $2 \times 180\text{ ns} = 360\text{ ns}$.
  $$\text{Total Time} = 100\text{ ns} + 360\text{ ns} + 800\text{ ns} = 1260\text{ ns}$$

Since $1260\text{ ns}$ is not among the options, Case 1 represents the intended solution.