Skip to content
GATETECH
Official PYQ · 2003Q78Memory Management and Virtual MemoryMCQ1 mark

GATE CS 2003 Q78 — Memory Management and Virtual Memory

Explain with AI

A processor uses 2−level2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 3232 bits wide. The memory is byte addressable. For virtual to physical address translation, the 1010 most significant bits of the virtual address are used as index into the first level page table while the next 1010 bits are used as index into the second level page table. The 1212 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 44 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%\text{96\%}. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%\text{90\%}. Main memory access time is 1010 ns, cache access time is 11 ns, and TLB access time is also 11 ns.

Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.50.5 ns)

Choose one option
View worked solution

Answer: D

To find the average memory access time, we analyze the two possible scenarios based on the TLB lookup:

  1. Scenario 1: TLB Hit (Probability = 0.960.96)

    The physical address is obtained directly from the TLB. We then access the physically addressed cache:

    • Cache Hit (Probability = 0.900.90): Time taken = TTLB+TCache=1 ns+1 ns=2 nsT_{\text{TLB}} + T_{\text{Cache}} = 1\text{ ns} + 1\text{ ns} = 2\text{ ns}.
    • Cache Miss (Probability = 0.100.10): Time taken = TTLB+TCache+TMemory=1 ns+1 ns+10 ns=12 nsT_{\text{TLB}} + T_{\text{Cache}} + T_{\text{Memory}} = 1\text{ ns} + 1\text{ ns} + 10\text{ ns} = 12\text{ ns}.

    Average time for TLB Hit (ThitT_{\text{hit}}) = 0.90×2 ns+0.10×12 ns=3 ns0.90 \times 2\text{ ns} + 0.10 \times 12\text{ ns} = 3\text{ ns}.

  2. Scenario 2: TLB Miss (Probability = 0.040.04)

    We must perform a 2-level page table translation. Since both levels are stored in the main memory, we access them sequentially:

    • First-level page table access = 10 ns10\text{ ns}
    • Second-level page table access = 10 ns10\text{ ns}

    After obtaining the physical address, we access the cache/memory for the actual data:

    • Cache Hit (Probability = 0.900.90): Time taken = 1 (TLB)+10 (L1)+10 (L2)+1 (Cache)=22 ns1\text{ (TLB)} + 10\text{ (L1)} + 10\text{ (L2)} + 1\text{ (Cache)} = 22\text{ ns}.
    • Cache Miss (Probability = 0.100.10): Time taken = 1 (TLB)+10 (L1)+10 (L2)+1 (Cache)+10 (Memory)=32 ns1\text{ (TLB)} + 10\text{ (L1)} + 10\text{ (L2)} + 1\text{ (Cache)} + 10\text{ (Memory)} = 32\text{ ns}.

    Average time for TLB Miss (TmissT_{\text{miss}}) = 1+10+10+[1+0.10×10]=23 ns1 + 10 + 10 + [1 + 0.10 \times 10] = 23\text{ ns}.

Overall Average Access Time:

Tavg=(0.96×Thit)+(0.04×Tmiss)T_{\text{avg}} = (0.96 \times T_{\text{hit}}) + (0.04 \times T_{\text{miss}})Tavg=(0.96×3 ns)+(0.04×23 ns)=2.88 ns+0.92 ns=3.8 nsT_{\text{avg}} = (0.96 \times 3\text{ ns}) + (0.04 \times 23\text{ ns}) = 2.88\text{ ns} + 0.92\text{ ns} = 3.8\text{ ns}

Rounding 3.8 ns3.8\text{ ns} to the nearest 0.5 ns0.5\text{ ns} gives 4 ns4\text{ ns}.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Memory Management and Virtual Memory questions