PYQs / GATE CS / 2016 / Set 1 / Q59 GATE CS 2016 Set 1 — Question 59 Go beyond PYQs with Success Tracker AI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply. NAT +2 / -0 Hard Page Replacement Algorithms Memory Management Operating System
Operating System → Memory Management → Page Replacement Algorithms
Last updated 5 September 2026
Question Consider a computer system with ten physical page frames. The system is provided with an access sequence
( a 1 , a 2 , … , a 20 , a 1 , a 2 , … , a 20 ) (a_1, a_2, \dots, a_{20}, a_1, a_2, \dots, a_{20}) ( a 1 , a 2 , … , a 20 , a 1 , a 2 , … , a 20 ) , where each
a i a_i 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 the optimal page replacement policy is
________ .
Solution Given:
Number of frames F = 10 F = 10 F = 10 Access sequence S = ( a 1 , … , a 20 , a 1 , … , a 20 ) S = (a_1, \dots, a_{20}, a_1, \dots, a_{20}) S = ( a 1 , … , a 20 , a 1 , … , a 20 ) Total requests = 40 a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
1. LIFO Policy: LIFO replaces the page that was brought into memory most recently.
Pass 1 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 10 a_1, \dots, a_{10} a 1 , … , a 10 { a 1 , … , a 10 } \{a_1, \dots, a_{10}\} { a 1 , … , a 10 } a 10 a_{10} a 10 a 11 a_{11} a 11 a 10 a_{10} a 10 { a 1 , … , a 9 , a 11 } \{a_1, \dots, a_9, a_{11}\} { a 1 , … , a 9 , a 11 } a 11 a_{11} a 11 a 12 a_{12} a 12 a 11 a_{11} a 11 { a 1 , … , a 9 , a 12 } \{a_1, \dots, a_9, a_{12}\} { a 1 , … , a 9 , a 12 } a 12 a_{12} a 12 ... a 20 a_{20} a 20 a 19 a_{19} a 19 { a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } a 20 a_{20} a 20 Total faults in Pass 1 =
10 + 10 = 20 10 + 10 = 20 10 + 10 = 20 .
Memory state:
{ a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } .
Pass 2 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 9 a_1, \dots, a_9 a 1 , … , a 9 a 10 a_{10} a 10 a 20 a_{20} a 20 { a 1 , … , a 9 , a 10 } \{a_1, \dots, a_9, a_{10}\} { a 1 , … , a 9 , a 10 } a 10 a_{10} a 10 a 11 a_{11} a 11 a 10 a_{10} a 10 { a 1 , … , a 9 , a 11 } \{a_1, \dots, a_9, a_{11}\} { a 1 , … , a 9 , a 11 } a 11 a_{11} a 11 ... a 20 a_{20} a 20 a 19 a_{19} a 19 { a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } a 20 a_{20} a 20 Total faults in Pass 2 =
11 11 11 (for
a 10 … a 20 a_{10} \dots a_{20} a 10 … a 20 ).
Total LIFO faults =
20 + 11 = 31 20 + 11 = 31 20 + 11 = 31 .
2. Optimal Policy: Replace the page that will not be used for the longest time.
Pass 1 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 10 a_1, \dots, a_{10} a 1 , … , a 10 { a 1 , … , a 10 } \{a_1, \dots, a_{10}\} { a 1 , … , a 10 } a 11 a_{11} a 11 a 12 … a 20 , a 1 … a 10 a_{12} \dots a_{20}, a_1 \dots a_{10} a 12 … a 20 , a 1 … a 10 a 1 … a 9 a_1 \dots a_9 a 1 … a 9 a 10 a_{10} a 10 a 10 a_{10} a 10 a 10 a_{10} a 10 { a 1 , … , a 9 , a 11 } \{a_1, \dots, a_9, a_{11}\} { a 1 , … , a 9 , a 11 } a 12 a_{12} a 12 a 13 … a 20 , a 1 … a 9 , a 11 a_{13} \dots a_{20}, a_1 \dots a_9, a_{11} a 13 … a 20 , a 1 … a 9 , a 11 a 11 a_{11} a 11 a 1 … a 9 a_1 \dots a_9 a 1 … a 9 Replace a 11 a_{11} a 11 { a 1 , … , a 9 , a 12 } \{a_1, \dots, a_9, a_{12}\} { a 1 , … , a 9 , a 12 } ... a 20 a_{20} a 20 a 19 a_{19} a 19 { a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } Total faults in Pass 1 =
10 + 10 = 20 10 + 10 = 20 10 + 10 = 20 .
Memory state:
{ a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } .
Pass 2 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 9 a_1, \dots, a_9 a 1 , … , a 9 a 10 a_{10} a 10 a 11 … a 20 a_{11} \dots a_{20} a 11 … a 20 a 20 a_{20} a 20 a 1 … a 9 a_1 \dots a_9 a 1 … a 9 Replace any of a 1 … a 9 a_1 \dots a_9 a 1 … a 9 a 1 a_1 a 1 { a 10 , a 2 , … , a 9 , a 20 } \{a_{10}, a_2, \dots, a_9, a_{20}\} { a 10 , a 2 , … , a 9 , a 20 } a 11 a_{11} a 11 a 2 a_2 a 2 { a 10 , a 11 , a 3 , … , a 9 , a 20 } \{a_{10}, a_{11}, a_3, \dots, a_9, a_{20}\} { a 10 , a 11 , a 3 , … , a 9 , a 20 } ... a 19 a_{19} a 19 a 10 a_{10} a 10 a 10 a_{10} a 10 a 20 a_{20} a 20 { a 19 , a 11 , … , a 18 , a 20 } \{a_{19}, a_{11}, \dots, a_{18}, a_{20}\} { a 19 , a 11 , … , a 18 , a 20 } a 20 a_{20} a 20 Total faults in Pass 2 =
10 10 10 (for
a 10 … a 19 a_{10} \dots a_{19} a 10 … a 19 ).
Total Optimal faults =
20 + 10 = 30 20 + 10 = 30 20 + 10 = 30 .
Difference: 31 − 30 = 1 31 - 30 = 1 31 − 30 = 1 .
Turn this into a strength. Explore AI-powered practice and doubt support with Success Tracker. Review answer and solution without JavaScript Interactive answer checking needs JavaScript. The published solution is available below.
Solution Given:
Number of frames F = 10 F = 10 F = 10 Access sequence S = ( a 1 , … , a 20 , a 1 , … , a 20 ) S = (a_1, \dots, a_{20}, a_1, \dots, a_{20}) S = ( a 1 , … , a 20 , a 1 , … , a 20 ) Total requests = 40 a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
1. LIFO Policy: LIFO replaces the page that was brought into memory most recently.
Pass 1 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 10 a_1, \dots, a_{10} a 1 , … , a 10 { a 1 , … , a 10 } \{a_1, \dots, a_{10}\} { a 1 , … , a 10 } a 10 a_{10} a 10 a 11 a_{11} a 11 a 10 a_{10} a 10 { a 1 , … , a 9 , a 11 } \{a_1, \dots, a_9, a_{11}\} { a 1 , … , a 9 , a 11 } a 11 a_{11} a 11 a 12 a_{12} a 12 a 11 a_{11} a 11 { a 1 , … , a 9 , a 12 } \{a_1, \dots, a_9, a_{12}\} { a 1 , … , a 9 , a 12 } a 12 a_{12} a 12 ... a 20 a_{20} a 20 a 19 a_{19} a 19 { a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } a 20 a_{20} a 20 Total faults in Pass 1 =
10 + 10 = 20 10 + 10 = 20 10 + 10 = 20 .
Memory state:
{ a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } .
Pass 2 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 9 a_1, \dots, a_9 a 1 , … , a 9 a 10 a_{10} a 10 a 20 a_{20} a 20 { a 1 , … , a 9 , a 10 } \{a_1, \dots, a_9, a_{10}\} { a 1 , … , a 9 , a 10 } a 10 a_{10} a 10 a 11 a_{11} a 11 a 10 a_{10} a 10 { a 1 , … , a 9 , a 11 } \{a_1, \dots, a_9, a_{11}\} { a 1 , … , a 9 , a 11 } a 11 a_{11} a 11 ... a 20 a_{20} a 20 a 19 a_{19} a 19 { a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } a 20 a_{20} a 20 Total faults in Pass 2 =
11 11 11 (for
a 10 … a 20 a_{10} \dots a_{20} a 10 … a 20 ).
Total LIFO faults =
20 + 11 = 31 20 + 11 = 31 20 + 11 = 31 .
2. Optimal Policy: Replace the page that will not be used for the longest time.
Pass 1 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 10 a_1, \dots, a_{10} a 1 , … , a 10 { a 1 , … , a 10 } \{a_1, \dots, a_{10}\} { a 1 , … , a 10 } a 11 a_{11} a 11 a 12 … a 20 , a 1 … a 10 a_{12} \dots a_{20}, a_1 \dots a_{10} a 12 … a 20 , a 1 … a 10 a 1 … a 9 a_1 \dots a_9 a 1 … a 9 a 10 a_{10} a 10 a 10 a_{10} a 10 a 10 a_{10} a 10 { a 1 , … , a 9 , a 11 } \{a_1, \dots, a_9, a_{11}\} { a 1 , … , a 9 , a 11 } a 12 a_{12} a 12 a 13 … a 20 , a 1 … a 9 , a 11 a_{13} \dots a_{20}, a_1 \dots a_9, a_{11} a 13 … a 20 , a 1 … a 9 , a 11 a 11 a_{11} a 11 a 1 … a 9 a_1 \dots a_9 a 1 … a 9 Replace a 11 a_{11} a 11 { a 1 , … , a 9 , a 12 } \{a_1, \dots, a_9, a_{12}\} { a 1 , … , a 9 , a 12 } ... a 20 a_{20} a 20 a 19 a_{19} a 19 { a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } Total faults in Pass 1 =
10 + 10 = 20 10 + 10 = 20 10 + 10 = 20 .
Memory state:
{ a 1 , … , a 9 , a 20 } \{a_1, \dots, a_9, a_{20}\} { a 1 , … , a 9 , a 20 } .
Pass 2 (a 1 , … , a 20 a_1, \dots, a_{20} a 1 , … , a 20
a 1 , … , a 9 a_1, \dots, a_9 a 1 , … , a 9 a 10 a_{10} a 10 a 11 … a 20 a_{11} \dots a_{20} a 11 … a 20 a 20 a_{20} a 20 a 1 … a 9 a_1 \dots a_9 a 1 … a 9 Replace any of a 1 … a 9 a_1 \dots a_9 a 1 … a 9 a 1 a_1 a 1 { a 10 , a 2 , … , a 9 , a 20 } \{a_{10}, a_2, \dots, a_9, a_{20}\} { a 10 , a 2 , … , a 9 , a 20 } a 11 a_{11} a 11 a 2 a_2 a 2 { a 10 , a 11 , a 3 , … , a 9 , a 20 } \{a_{10}, a_{11}, a_3, \dots, a_9, a_{20}\} { a 10 , a 11 , a 3 , … , a 9 , a 20 } ... a 19 a_{19} a 19 a 10 a_{10} a 10 a 10 a_{10} a 10 a 20 a_{20} a 20 { a 19 , a 11 , … , a 18 , a 20 } \{a_{19}, a_{11}, \dots, a_{18}, a_{20}\} { a 19 , a 11 , … , a 18 , a 20 } a 20 a_{20} a 20 Total faults in Pass 2 =
10 10 10 (for
a 10 … a 19 a_{10} \dots a_{19} a 10 … a 19 ).
Total Optimal faults =
20 + 10 = 30 20 + 10 = 30 20 + 10 = 30 .
Difference: 31 − 30 = 1 31 - 30 = 1 31 − 30 = 1 .
Understand the concept, then try another question Revisit Operating System with concept notes, common mistakes and an original worked example before your next attempt.
More questions on Memory Management ← Q58 Full paper Q60 → 