Page replacement algorithms (FIFO, LRU, Optimal) in Operating Systems - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the page replacement algorithm that removes the oldest page first.

Operating Systems

algorithm = "[1]"  # This algorithm replaces the oldest page in memory first.

Drag options to blanks, or click blank then click option'

ARandom

BLRU

CFIFO

DOptimal

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing FIFO with LRU which removes least recently used pages.

Choosing Optimal which requires future knowledge.

FIFO stands for First-In-First-Out. It replaces the oldest page in memory first, regardless of how often or recently it was used.

2fill in blank

medium

Complete the code to identify the algorithm that replaces the page which will not be used for the longest time in the future.

Operating Systems

algorithm = "[1]"  # This algorithm requires future knowledge of page references.

Drag options to blanks, or click blank then click option'

AOptimal

BFIFO

CLRU

DClock

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing LRU which uses past usage, not future.

Confusing with FIFO which uses arrival order.

Optimal page replacement algorithm replaces the page that will not be used for the longest time in the future. It is theoretical and requires future knowledge.

3fill in blank

hard

Fix the error in the description of the algorithm that replaces the least recently used page.

Operating Systems

algorithm = "[1]"  # This algorithm replaces the page that was used the longest time ago.

Drag options to blanks, or click blank then click option'

AFIFO

BLRU

COptimal

DRandom

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing LRU with FIFO which removes oldest loaded page.

Choosing Optimal which requires future knowledge.

LRU stands for Least Recently Used. It replaces the page that has not been used for the longest time.

4fill in blank

hard

Fill both blanks to complete the sentence describing FIFO and LRU algorithms.

Operating Systems

The [1] algorithm replaces pages in the order they were loaded, while the [2] algorithm replaces pages based on least recent usage.

Drag options to blanks, or click blank then click option'

AFIFO

BOptimal

CLRU

DClock

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up FIFO and LRU in the sentence.

Choosing Optimal which is not described here.

FIFO replaces pages in the order they were loaded (oldest first). LRU replaces pages based on least recent usage.

5fill in blank

hard

Fill all three blanks to complete the dictionary that maps algorithm names to their key characteristics.

Operating Systems

algorithms = {"FIFO": "[1]", "LRU": "[2]", "Optimal": "[3]"}

Drag options to blanks, or click blank then click option'

Aremoves oldest page

Bremoves least recently used page

Cremoves page not used for longest future time

Dremoves random page

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up the descriptions of LRU and Optimal.

Choosing random page removal which is not part of these algorithms.

This dictionary maps each algorithm to its main page replacement strategy: FIFO removes the oldest page, LRU removes the least recently used page, and Optimal removes the page not used for the longest time in the future.

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