Page replacement algorithms (FIFO, LRU, Optimal) in Operating Systems - Mini Project: Build & Apply

Understanding Page Replacement Algorithms: FIFO, LRU, and Optimal

📖 Scenario: You are learning how operating systems manage memory using page replacement algorithms. These algorithms decide which memory pages to remove when new pages need space.Imagine a small computer memory that can hold only a few pages at a time. When a new page is requested and memory is full, the system must replace one page using a specific strategy.

🎯 Goal: Build a simple step-by-step example showing how three page replacement algorithms (FIFO, LRU, Optimal) decide which page to replace when a new page is requested.You will create data structures to hold page requests, set up memory size, apply each algorithm's logic, and show the final memory state after processing requests.

📋 What You'll Learn

Create a list of page requests with exact values

Define the memory frame size as a variable

Implement the FIFO page replacement logic

Implement the LRU page replacement logic

Implement the Optimal page replacement logic

Show the final memory frames after processing all requests for each algorithm

💡 Why This Matters

🌍 Real World

Operating systems use page replacement algorithms to manage limited memory efficiently, improving computer performance.

💼 Career

Understanding these algorithms is important for roles in system programming, software development, and IT infrastructure management.

1

Set up the page request sequence

Create a list called page_requests with these exact page numbers in order: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Operating Systems

# Create the list of page requests
# Your code here

Hint

Use square brackets and commas to create the list with the exact numbers.

2

Define the memory frame size

Create a variable called frame_size and set it to the integer 3 to represent the number of pages memory can hold at once.

Operating Systems

page_requests = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
# Define the memory frame size
# Your code here

Hint

Use a simple assignment to set frame_size to 3.

3

Implement FIFO page replacement logic

Write code to simulate the FIFO page replacement algorithm using the page_requests list and frame_size. Use a list called fifo_frames to hold pages in memory. For each page request, if the page is not in fifo_frames and memory is full, remove the oldest page (first in list) and add the new page at the end. If memory is not full, just add the new page. Use a for loop with variable page to process page_requests.

Operating Systems

page_requests = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
frame_size = 3
# Implement FIFO page replacement
# Your code here

Hint

Use a list to hold frames and a loop to check each page. Remove the first page if full, then add the new page.

4

Implement LRU and Optimal page replacement logic and show final frames

Add code to simulate the LRU and Optimal page replacement algorithms using the same page_requests and frame_size. Create lists lru_frames and optimal_frames to hold pages. For LRU, replace the page that was least recently used when memory is full. For Optimal, replace the page that will not be used for the longest time in the future. Use for loops with variable i to track current position in page_requests. After processing all requests, the lists fifo_frames, lru_frames, and optimal_frames should show the final pages in memory for each algorithm.

Operating Systems

page_requests = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
frame_size = 3
fifo_frames = []
for page in page_requests:
    if page not in fifo_frames:
        if len(fifo_frames) == frame_size:
            fifo_frames.pop(0)
        fifo_frames.append(page)
# Implement LRU and Optimal page replacement
# Your code here

Hint

For LRU, move recently used pages to the end of the list. For Optimal, check future requests to decide which page to replace.

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