Page replacement algorithms (FIFO, LRU, Optimal) in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding FIFO Page Replacement

Consider a system using the FIFO (First-In-First-Out) page replacement algorithm with 3 page frames. Given the page reference string: 7, 0, 1, 2, 0, 3, 0, 4, how many page faults will occur?

A 7

B 5

C 6

D 4

💡 Hint

Remember, FIFO replaces the oldest loaded page first.

With 3 frames, the pages loaded and replaced in order cause 7 page faults for the given string.

🔍 Analysis

intermediate

LRU Page Replacement Behavior

Using the LRU (Least Recently Used) algorithm with 4 page frames, analyze the page reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. How many page faults will occur?

A 10

B 9

C 8

D 7

💡 Hint

LRU replaces the page that was least recently used when a replacement is needed.

Tracking the pages shows 9 page faults for the given reference string with 4 frames under LRU.

❓ Comparison

advanced

Optimal vs FIFO Page Replacement

Given the page reference string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 and 3 page frames, which algorithm results in fewer page faults: FIFO or Optimal?

A FIFO results in fewer page faults

B Cannot determine without frame size

C Optimal results in fewer page faults

D Both have the same number of page faults

💡 Hint

Optimal algorithm replaces the page that will not be used for the longest time in the future.

Optimal always results in the least number of page faults compared to FIFO for the same reference string and frame size.

❓ Reasoning

advanced

Identifying Page Faults in LRU

With 2 page frames and the reference string 1, 2, 3, 2, 1, 4, 5, which pages cause page faults under the LRU algorithm?

A 1, 2, 3, 4, 5

B 1, 2, 3, 5

C 1, 2, 3, 4

D 1, 3, 4, 5

💡 Hint

Page faults occur when a page is not in any frame at the time of reference.

Pages 1, 2, 3, 4, and 5 cause faults; 2 and 1 are hits on second references.

📋 Factual

expert

Optimal Page Replacement Algorithm Property

Which statement correctly describes the Optimal page replacement algorithm?

A It replaces the page that was loaded first in memory

B It replaces the page that has the highest frequency of use

C It replaces the page that was least recently used

D It replaces the page that will not be used for the longest time in the future

💡 Hint

Think about how Optimal predicts future page references.

Optimal replaces the page that will not be needed for the longest time in the future, minimizing page faults.