What are common examiner traps in Memory Management and Virtual Memory?

Forgetting that TLB search happens first, or double-counting TLB lookup when access is parallel/sequential. On a TLB miss without page fault, forgetting the extra memory access needed to fetch the Page Table Entry before accessing the data itself. In multi-level inner page table count calculation, omitting the root/outer page directory table from the total page count. Row-major vs Column-major traversal in C arrays causing stride-induced thrashing when row size exceeds page frame capacity. Assuming stack algorithms like LRU or OPT can suffer from Belady's anomaly (only non-stack algorithms like FIFO, Random suffer). Assuming a Cache hit is possible when a Page Table miss (page fault) occurs in a physically addressed cache. Confusing units between milliseconds (ms) and nanoseconds (ns) in EMAT formulas (1 ms = 106 ns). Treating 1 KB as 1000 bytes instead of 1024 bytes (e.g., taking 2 KB = 2000 instead of 2048). Applying translation/mapping to the offset rather than keeping offset invariant between virtual and physical address. Confusing Page Number with Frame Number during final address computation. Off-by-one errors when base indexing starts from 0 versus 1. Failing to update the recency order/timestamp when a page hit occurs, which leads to incorrect victim eviction in subsequent steps. Neglecting cold/compulsory misses during initial frame loading. Confusing the Least Recently Used (backward-looking) policy with Optimal/MIN (forward-looking) or FIFO (insertion-order) policies. Miscounting total page hits instead of total page faults when asked for page faults.

GATE CSE Memory Management and Virtual Memory PYQs

Medium yield28.6% of Operating Systems

Memory management and virtual memory is a high-yield, computation-heavy topic in GATE CS, frequently carrying 2-mark NAT and MCQ/MSQ questions. The exam heavily… Read the guide

Take topic test

Questions: 32
Asked: since 2011
Total marks: 55
Marks / paper: 2.2

32 GATE CSE Memory Management and Virtual Memory PYQs with solutions, from Operating Systems. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Memory Management and Virtual Memory

Concepts, patterns, formulas and traps distilled from past papers.

Memory management and virtual memory is a high-yield, computation-heavy topic in GATE CS, frequently carrying 2-mark NAT and MCQ/MSQ questions. The exam heavily emphasizes multi-level page table sizing, hierarchical bit-splitting, page replacement algorithm simulation (FIFO, LRU, OPTIMAL, MRU, LIFO), and Effective Memory Access Time (EMAT) calculations involving TLBs and disk transfers. Recent years have introduced variants such as bounded lookahead optimal replacement, code-based loop/array access patterns, and TLB reach sizing.

Core concepts

Hierarchical / Multi-level Paging and Page Table Sizing
Translation Lookaside Buffer (TLB) hit/miss and TLB Reach
Demand Paging, Page Fault Handler, and Dirty / Modified Bit Writeback
Page Replacement Algorithms (FIFO, LRU, OPTIMAL, MRU, LIFO, LFU/MFU)
Belady's Anomaly and Stack Algorithms Inclusion Property
MMU hardware responsibilities vs OS kernel memory management duties
Interaction between TLB, Page Table, Main Memory, and Physically Tagged Caches
Dynamic Memory Partitioning (First-Fit, Best-Fit, Worst-Fit) and Internal/External Fragmentation
Inverted and Hashed Page Tables
Paging and Address Translation
Page Size conversion (1 KB = 1024 bytes)
Virtual Page Number (VPN) and Offset extraction
Page Table Frame Mapping
Physical Address composition
Demand Paging
Page Faults and Cold/Compulsory Misses
Least Recently Used (LRU) Page Replacement
Page Frame State Tracking and Recency Stack Updates
Page Hits vs Page Faults

Recurring question patterns

Multi-Level Hierarchical Paging Bit-Splitting and Sizing
CommonNAT2 marks2025, 2024, 2023, 2021
Given virtual address size, physical address size, page size, and PTE size, determine the number of levels $L$ , index bit widths per level, total page table overhead, or min/max memory frames allocated dynamically across levels.
Page Replacement Simulation and Fault Counting
CommonNAT2 marks2025, 2023, 2022, 2016
Simulate page replacement policies (FIFO, LRU, OPTIMAL, MRU, LIFO, or constrained lookahead OPT) on a given reference string or nested loop array access pattern to find total faults, hit ratios, or identify policy from trace tables.
Effective Memory Access Time (EMAT) with TLB and Faults
Commonmixed2 marks2020, 2018, 2014, 2011
Calculate EMAT / EAT given TLB search time, hit ratio, memory access latency, page fault service time, dirty page writeback probabilities, or solve algebraically for the page fault rate.
TLB Hardware Sizing and Reach
OccasionalNAT2 marks2026
Compute the total TLB size in bytes given TLB reach, page size, ASID/PID bits, VPN bits, PFN bits, and control bits.
Conceptual MSQ / Event Sequence Feasibility
OccasionalMSQ2 marks2026, 2024, 2022, 2021
Identify valid/invalid concurrent hardware sequences across TLB, Page Table, and physically tagged Cache, or determine responsibilities of MMU vs OS and properties like Belady's anomaly.
Dynamic Memory Allocation Partitioning
RareNAT2 marks2026
Trace process memory requests through free holes using allocation policies (Best-Fit, First-Fit, Worst-Fit) and count remaining holes under size thresholds or find external fragmentation.
Virtual Address to Physical Address Translation
CommonNAT2 marks2024
Given page size, virtual-to-physical frame mapping, and a decimal virtual address, calculate the corresponding physical address in decimal by extracting page number and offset.
Reference String Simulation for Page Fault Calculation
CommonNAT1 marks2014
Given an initially empty set of physical memory page frames (e.g., 3 frames) and a chronological page reference string, the candidate traces memory accesses step-by-step using a replacement policy like LRU to calculate the total number of page faults.

Formulas GATE uses

Page Offset and VPN Bits

p = \log_2(\text{Page Size}), \quad \text{VPN bits} = \text{VA bits} - p

Used in logical address decomposition and multi-level index splitting.

Page Table Entry Indexing Capacity per Page

\text{Entries per page} = \frac{\text{Page Size}}{\text{PTE Size}} = 2^k \implies k \text{ bits per level}

Used when determining the number of levels $L = \lceil \text{VPN bits} / k \rceil$ .

Effective Memory Access Time (TLB only)

\text{EMAT} = t_{\text{TLB}} + h \cdot t_m + (1 - h) \cdot (N \cdot t_m + t_m)

Used for $N$ -level paging with TLB hit ratio $h$ , TLB access time $t_{\text{TLB}}$ , and main memory latency $t_m$ .

Effective Memory Access Time with Demand Paging and Dirty Eviction

\text{EMAT} = t_{\text{TLB}} + h(t_m) + (1 - h)\left[ t_m + (1 - p)t_m + p(S + t_m) \right]

Used when incorporating TLB misses, page fault probability $p$ , and fault service time $S = (1 - d)T_{\text{read}} + d(T_{\text{read}} + T_{\text{write}})$ .

TLB Reach

\text{TLB Reach} = (\text{Number of TLB Entries}) \times (\text{Page Size})

Used to find the count of entries in the TLB from reach and page size.

Total TLB Storage Size

\text{TLB Size} = \text{Entries} \times (\text{PID bits} + \text{VPN bits} + \text{PFN bits} + \text{Control bits})

Used to calculate full hardware storage requirement of the associative TLB.

Virtual Page Number (VPN)

\text{VPN} = \lfloor \frac{\text{Virtual Address}}{\text{Page Size}} \rfloor

Used to find which page index a given linear virtual address belongs to.

Page Offset

\text{Offset} = \text{Virtual Address} \bmod \text{Page Size}

Used to calculate the displacement within the page/frame.

Physical Address Calculation

\text{Physical Address} = (\text{Frame Number} \times \text{Page Size}) + \text{Offset}

Used to construct the final physical memory address after looking up the frame number from the page table.

Page Fault Indicator

\text{Fault}(t) = \begin{cases} 1 & \text{if } r_t \notin \text{Frames}_{t-1} \\ 0 & \text{if } r_t \in \text{Frames}_{t-1} \end{cases}

Used at each time step $t$ for reference $r_t$ to determine if a page fault occurs and increment the total fault counter.

LRU Victim Selection Rule

\text{Victim} = \arg\min_{p \in \text{Frames}} (\text{Last Access Time}(p))

Used when a page fault occurs and all allocated page frames are full, to select the page unreferenced for the longest time for eviction.

Examiner traps in Memory Management and Virtual Memory

Forgetting that TLB search happens first, or double-counting TLB lookup when access is parallel/sequential.
On a TLB miss without page fault, forgetting the extra memory access needed to fetch the Page Table Entry before accessing the data itself.
In multi-level inner page table count calculation, omitting the root/outer page directory table from the total page count.
Row-major vs Column-major traversal in C arrays causing stride-induced thrashing when row size exceeds page frame capacity.
Assuming stack algorithms like LRU or OPT can suffer from Belady's anomaly (only non-stack algorithms like FIFO, Random suffer).
Assuming a Cache hit is possible when a Page Table miss (page fault) occurs in a physically addressed cache.
Confusing units between milliseconds (ms) and nanoseconds (ns) in EMAT formulas (1 ms = 106 ns).
Treating 1 KB as 1000 bytes instead of 1024 bytes (e.g., taking 2 KB = 2000 instead of 2048).
Applying translation/mapping to the offset rather than keeping offset invariant between virtual and physical address.
Confusing Page Number with Frame Number during final address computation.
Off-by-one errors when base indexing starts from 0 versus 1.
Failing to update the recency order/timestamp when a page hit occurs, which leads to incorrect victim eviction in subsequent steps.
Neglecting cold/compulsory misses during initial frame loading.
Confusing the Least Recently Used (backward-looking) policy with Optimal/MIN (forward-looking) or FIFO (insertion-order) policies.
Miscounting total page hits instead of total page faults when asked for page faults.

How questions are asked

Multi-level page table level count L and outer index bit-width derivation
NAT calculating minimum and maximum allocated page table frames for a sparse address space
Simulation trace of page replacements across fixed frames to compute fault count or fault rate
EMAT calculation with hierarchical memory, TLB, and dirty page writeback latency
2D array loop iteration page fault count under row/column traversal
MSQ identifying invalid event sequences across MMU, TLB, Page Table, and Cache
NAT computing TLB capacity in bytes from TLB reach and field bit widths
Memory hole tracking after Best-Fit/First-Fit process allocations
Direct decimal address translation given page table mapping
Trace page reference string on fixed-size frame pool and compute total page faults (NAT)

Paper trends

Shift from simple 1-level page table lookups to complex multi-level hierarchy sizing, number of levels $L$ , and dynamic inner page allocation bounds (min/max X+Y).
2025, 2024, 2023, 2021, 2016, 2013
Transition of page replacement questions from simple manual string simulations to programmatic loop-based matrix access and modified algorithmic models (e.g. 4-step lookahead OPT).
2025, 2023, 2022
Rise of multi-select questions (MSQ) focusing on MMU hardware vs OS software roles and impossible event combinations across TLB, Page Table, and Cache.
2026, 2024, 2021
Recent papers feature direct numerical answer (NAT) questions assessing the basic mathematical foundations of virtual-to-physical address translation without multi-level page table complications.
2024
Testing focuses on step-by-step trace accuracy presented as a Numerical Answer Type (NAT) question requiring exact integer computation without multiple-choice cues.
2014

Difficulty notes

Easy questions (1 mark) test single-level page table sizing, basic EMAT formulas, or definition-level properties of Belady's anomaly. Medium questions (2 marks) require detailed simulation of page replacement algorithms (10-15 references), multi-level bit-splitting equations, array traversal analysis, or compound EMAT calculations. Hard questions (2 marks) involve subtle mathematical reasoning about worst/best-case page distribution across multi-level directory trees, trace deductions under non-standard constraints, or multi-component hardware cache-TLB invalidation semantics.