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.

Memory Management and Virtual Memory

32 Qs · since 2011 · 55 marks · 2.2 marks/paperMedium yield

Take topic test

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-le… Guide

Type

GATE CSE 2026 Set 1Q54MSQ2 marksMediumConsider a system that has a cache memory unit and a memory management unit (MMU). The address input to the cache memory is a physical address. The MMU has a translation lookaside buffer (TLB). Assume that when a page is evicted from the main memory, the corresponding blocks in the cache are marked as invalid. For a…
GATE CSE 2026 Set 2Q54NAT2 marksMediumA system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB. TLB reach is defined as the total amount of physical memory that can be accessed through the TLB entries. The paging system uses pages of size 4 KB. The virtual address space is 64 GB and physical address space is 1 GB. If each TLB entry…
GATE CSE 2026 Set 2Q55NAT2 marksEasyConsider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order,…
GATE CSE 2025 Set 1Q14MCQ1 markEasyConsider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
GATE CSE 2025 Set 1Q54NAT2 marksMediumIn optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows: *The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a…
GATE CSE 2025 Set 2Q47MSQ2 marksMediumDiagramConsider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right): The *-marked references cause page replacements. Which one or more of the following could be the…
GATE CSE 2025 Set 2Q58NAT2 marksMediumA computer system supports a logical address space of $2^{32}$ bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a $b$ -bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry…
GATE CSE 2024 Set 1Q62NAT2 marksEasyConsider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in…
GATE CSE 2024 Set 2Q24MSQ1 markMediumWhich of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?
GATE CSE 2024 Set 2Q64NAT2 marksMediumConsider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = $2^{10}$ bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon…
GATE CSE 2023Q57NAT2 marksMediumConsider the following two-dimensional array $D$ in the C programming language, which is stored in row-major order: int D[128][128]; Demand paging is used for allocating memory and each physical page frame holds 512 elements of the array $D$ . The Least Recently Used (LRU) page-replacement policy is…
GATE CSE 2023Q58NAT2 marksMediumConsider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with $L$ levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes. The value of $L$ is ________.
GATE CSE 2022Q38MCQ2 marksMediumWhich one of the following statements is FALSE?
GATE CSE 2022Q64NAT2 marksMediumConsider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string $7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1$ the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one…
GATE CSE 2021 Set 1Q11MSQ1 markEasyIn the context of operating systems, which of the following statements is/are correct with respect to paging?
GATE CSE 2021 Set 2Q48NAT2 marksMediumDiagramConsider a three-level page table to translate a 39-bit virtual address to a physical address as shown below. The page size is 4KB (1KB = $2^{10}$ bytes) and page table entry size at every level is 8 bytes. A process $P$ is currently using 2GB (1GB = $2^{30}$ bytes) virtual memory which is mapped to 2GB of…
GATE CSE 2020Q11MCQ1 markMediumConsider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?
GATE CSE 2020Q53NAT2 marksMediumConsider 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…
GATE CSE 2018Q10MCQ1 markEasyConsider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is $M$ units if the corresponding memory page is available in memory, and $D$ units if the memory access causes a page fault. It has been experimentally measured that the average time…
GATE CSE 2017 Set 1Q40MCQ2 marksMediumRecall that Belady's anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements: S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady's anomaly S2: LRU page replacement algorithm suffers from…
GATE CSE 2016 Set 1Q47NAT2 marksMediumConsider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is ________ megabytes.
GATE CSE 2016 Set 1Q49NAT2 marksHardConsider a computer system with ten physical page frames. The system is provided with an access sequence $(a_1, a_2, \ldots, a_{20}, a_1, a_2, \ldots, a_{20})$ , where each $a_i$ is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and…
GATE CSE 2016 Set 2Q20MCQ1 markEasyIn which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?
GATE CSE 2015 Set 1Q12NAT1 markEasyConsider a system with byte-addressable memory, 32-bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in megabytes is ________.
GATE CSE 2015 Set 1Q47MCQ2 marksMediumConsider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies First In First Out (FIFO) and Least Recently Used (LRU)?
GATE CSE 2014 Set 1Q33NAT2 marksEasyAssume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the *optimal replacement policy* is _________.
GATE CSE 2014 Set 2Q33MCQ2 marksMediumA computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, ..., 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page…
GATE CSE 2014 Set 3Q20NAT1 markMediumA system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? 4, 7, 6, 1, 7, 6, 1,…
GATE CSE 2014 Set 3Q33NAT2 marksEasyConsider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is ________.
GATE CSE 2013Q52MCQ2 marksMediumStatement for Linked Answer Questions 52 and 53: A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table ( $T_1$ ), which occupies exactly one page. Each entry of $T_1$ stores the…
GATE CSE 2012Q42MCQ2 marksMediumConsider the virtual page reference string $1, 2, 3, 2, 4, 1, 3, 2, 4, 1$ on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement…
GATE CSE 2011Q20MCQ1 markMediumLet the page fault service time be $10\text{ ms}$ in a computer with average memory access time being $20\text{ ns}$ . If one page fault is generated for every $10^6$ memory accesses, what is the effective access time for the memory?

Topic guide

What does GATE test in Memory Management and Virtual Memory?

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
common · NAT · 2 marks · 2025, 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
common · NAT · 2 marks · 2025, 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
common · mixed · 2 marks · 2020, 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
occasional · NAT · 2 marks · 2026
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
occasional · MSQ · 2 marks · 2026, 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
rare · NAT · 2 marks · 2026
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
common · NAT · 2 marks · 2024
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
common · NAT · 1 marks · 2014
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.