Page replacement algorithms (FIFO, LRU, Optimal) in Operating Systems - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the FIFO page replacement algorithm?

FIFO (First-In, First-Out) replaces the oldest page in memory first. It removes pages in the order they were loaded, like a queue.

beginner

How does the LRU page replacement algorithm decide which page to remove?

LRU (Least Recently Used) removes the page that has not been used for the longest time. It assumes pages used recently will be used again soon.

intermediate

What is the Optimal page replacement algorithm?

The Optimal algorithm replaces the page that will not be used for the longest time in the future. It gives the best performance but needs future knowledge.

beginner

Which page replacement algorithm is easiest to implement but may cause more page faults?

FIFO is the easiest to implement because it only tracks the order pages arrived. However, it can cause more page faults because it ignores usage patterns.

intermediate

Why is the Optimal page replacement algorithm not used in real systems?

Because it requires knowing the future sequence of page requests, which is impossible in real time. It is mainly used as a benchmark.

Which page replacement algorithm removes the oldest page in memory first?

A Optimal

B FIFO

C LRU

D Random

FIFO removes pages in the order they were loaded, so the oldest page is replaced first.

LRU stands for:

A Least Frequently Used

B Last Recently Used

C Least Recently Used

D Longest Running User

LRU means Least Recently Used, which replaces the page not used for the longest time.

Which algorithm requires knowledge of future page requests?

A Optimal

B LRU

C Clock

D FIFO

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

Which algorithm is easiest to implement?

A Optimal

B Second Chance

C LRU

D FIFO

FIFO is simple because it only tracks the order pages arrived, no complex tracking needed.

Why might FIFO cause more page faults than LRU?

A Because it ignores how often pages are used

B Because it removes the most recently used page

C Because it predicts future page use

D Because it uses a random selection

FIFO ignores usage patterns and removes pages just based on arrival order, which can cause more faults.

Explain how FIFO, LRU, and Optimal page replacement algorithms decide which page to remove.

Think about the order of page usage and future knowledge.

Discuss the advantages and disadvantages of FIFO and LRU algorithms.

Consider ease of implementation and fault rates.

Practice

1. Which page replacement algorithm removes the page that has been in memory the longest, regardless of usage?

easy

A. FIFO (First In First Out)

B. LRU (Least Recently Used)

C. Optimal

D. Random

Solution

1. Step 1: Understand FIFO behavior

   FIFO removes the oldest page loaded into memory first, ignoring how often it is used.

2. Step 2: Compare with other algorithms

   LRU removes the least recently used page, Optimal removes the page not needed for the longest future time, Random removes any page randomly.

3. Final Answer:

   FIFO (First In First Out) -> Option A

4. Quick Check:

   Oldest page removed = FIFO [OK]

Hint: Oldest page out means FIFO [OK]

Common Mistakes:

• Confusing FIFO with LRU
• Thinking Optimal removes oldest page
• Assuming Random is FIFO

2. Which of the following is the correct description of the LRU page replacement algorithm?

easy

A. Removes the page that will not be used for the longest time in the future

B. Removes the least recently used page

C. Removes the oldest page loaded into memory

D. Removes a random page

Solution

1. Step 1: Recall LRU definition

   LRU removes the page that has not been used for the longest time recently.

2. Step 2: Match options with definitions

   Removes the page that will not be used for the longest time in the future describes Optimal, C describes FIFO, B is random removal.

3. Final Answer:

   Removes the least recently used page -> Option B

4. Quick Check:

   Least recently used = LRU [OK]

Hint: Least recent use means LRU [OK]

Common Mistakes:

• Mixing LRU with Optimal
• Confusing LRU with FIFO
• Choosing random removal as LRU

3. Given the page reference string 7, 0, 1, 2, 0, 3, 0, 4 and 3 page frames, how many page faults occur using the FIFO algorithm?

medium

A. 6

B. 5

C. 7

D. 4

Solution

1. Step 1: Simulate FIFO with 3 frames

   Load pages in order: 7 (fault), 0 (fault), 1 (fault), then 2 replaces 7 (fault), 0 is in memory (no fault), 3 replaces 0 (fault), 0 replaces 1 (fault), 4 replaces 2 (fault).

2. Step 2: Count total faults

   Faults occur at 7,0,1,2,3,0,4 = 7 faults, but 0 at position 6 is already in memory, so no fault there. Total faults = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count page faults in FIFO = 6 [OK]

Hint: Count faults when page not in frames FIFO order [OK]

Common Mistakes:

• Counting repeated pages as faults
• Mixing FIFO with LRU results
• Forgetting to replace oldest page

4. Identify the error in this LRU page replacement simulation with 2 frames and reference string 1, 2, 3, 2, 1, 4: The algorithm replaces page 1 first instead of page 3.

medium

A. Algorithm should replace page 2 first

B. Algorithm should replace oldest page, which is page 1

C. Algorithm should replace least recently used page, which is page 3

D. Algorithm should replace a random page

Solution

1. Step 1: Simulate LRU up to replacement point

   1(fault)[1], 2(fault)[1,2], 3 replaces LRU=1 [2,3], 2(hit) updates LRU=3 MRU=2 [3,2]. Next 1 should replace LRU=3.

2. Step 2: Check replacement choice

   The error is replacing page 1 instead of the least recently used page 3.

3. Final Answer:

   Algorithm should replace least recently used page, which is page 3 -> Option C

4. Quick Check:

   LRU replaces least recently used page [OK]

Hint: Replace least recently used page in LRU [OK]

Common Mistakes:

• Replacing oldest page instead of least used
• Confusing LRU with FIFO
• Replacing wrong page due to usage order

5. You have 4 page frames and the reference string 1, 2, 3, 4, 2, 1, 5, 1, 2, 3, 4, 5. Using the Optimal page replacement algorithm, how many page faults will occur?

hard

A. 7

B. 8

C. 9

D. 6

Solution

1. Step 1: Simulate Optimal with 4 frames

   1,2,3,4 (4 faults). 2 hit, 1 hit. 5 replaces 4 (farthest next at pos11, fault 5). 1 hit, 2 hit, 3 hit. 4 replaces 1 (no future use, fault 6). 5 hit.

2. Step 2: Count total faults

   Total faults = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Optimal page faults counted = 6 [OK]

Hint: Replace page not needed longest in future [OK]

Common Mistakes:

• Counting repeated pages as faults
• Using FIFO or LRU logic instead of Optimal
• Forgetting to check future references