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

Operating Systems

7 topics · 119 Qs · 7.7 marks/paper · since 2011

Start mock (30 Qs)

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

Topics

Open a topic to browse, or practice it timed.

By year

Jump to the first question from that paper.

Subject guide

What does GATE test in 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. 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

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

How questions show up

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.