1 2 3 4 1 2 5 1 2 3 4 5: FIFO has 9 faults with 3 frames, 10 with 4
Hit ratio
hits / references = 1 − faults / references
Working-set demand
D = Σ WSSᵢ; thrashing if D > number of frames
Page faults lower bound
at least the number of distinct pages referenced (compulsory misses)
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Number of page faults for a reference string (FIFO / LRU / OPT)
Fill a frame table column by column; for OPT look ahead for the farthest next use.
★★★
Belady's anomaly: which policy can show it
FIFO yes; LRU and OPT no (stack algorithms).
★★★
Effective access time with page faults
EAT = (1 − p)m + p·s; solve for p to meet a slowdown target.
★★★
Thrashing and working-set statements
Which actions reduce thrashing (fewer processes) and which worsen it (more processes).
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
9 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
9 questions · 0 correct of 0 attempted · marks 0 / 17
Year:
GATE 2025 CS2 · Q47MSQ2 marks
Consider 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 three frames after each reference are: after 1*: (1, -, -); 2*: (1, 2, -); 3*: (1, 2, 3); 4*: (1, 4, 3); 5*: (1, 4, 5); 4: (1, 4, 5); 1: (1, 4, 5); 6*: (6, 4, 5); 4: (6, 4, 5); 5: (6, 4, 5); 1*: (6, 1, 5); 3*: (6, 1, 3); 2*: (2, 1, 3). The *-marked references cause page replacements. Which one or more of the following could be the page replacement policy/policies in use?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS1 · Q54NAT2 marks
In 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 frame to a page. A process accesses the pages in the following order of page numbers: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4. If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ______.
GATE 2022 · Q64NAT2 marks
Consider 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 decimal place) is ______.
GATE 2020 · Q53NAT2 marks
Consider a paging system that uses a 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 total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal place) is ______.
GATE 2018 · Q10MCQ1 mark
Consider 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 taken for a memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?
GATE 2017 Set 1 · Q40MCQ2 marks
Recall 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 Belady's anomaly. Which of the following is CORRECT?
GATE 2016 Set 1 · Q49NAT2 marks
Consider a computer system with ten physical page frames. The system is provided with an access sequence (a1, a2, ..., a20, a1, a2, ..., a20), where each ai is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is ______.
GATE 2014 Set 1 · Q33NAT2 marks
Assume 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 2012 Code A · Q42MCQ2 marks
Consider 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 policy. Then
Common traps
In OPT, ties (pages never used again) can be broken arbitrarily, but the fault count is the same.
LRU is a stack algorithm, so adding frames never increases its faults.
Count hits as hits: the initial loading of an empty frame is still a fault.
The dirty-bit term is only added when the victim is dirty: read the fraction in the question.