What are common examiner traps in Operating Systems?

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).

GATE CSE Operating Systems (OS) PYQs

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

Start mock · 30 Qs

Topics: 7
Questions: 119
Marks / paper: 7.7
Asked: since 2011

These are the 119 GATE CSE Operating Systems PYQs (since 2011), grouped topic-wise with solutions. See all GATE CSE PYQs or GATE CSE question papers by year.

Topics

Open a topic to browse its questions, or practice it as a timed test.

By year

Jump to the first question from each year’s paper.

What GATE tests in Operating Systems

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. CPU and I/O scheduling in GATE CS is predominantly an algorithmic and numerical topic focusing on precise Gantt chart simulation, turnaround/waiting time computation, and comparative metric evaluation. Concurrency and Synchronization is consistently evaluated through rigorous interleaving analysis, semaphore tracing, and correctness verification of mutual exclusion algorithms.

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

How questions show up

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.

High-yield formulas

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.

Examiner traps in Operating Systems

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).

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