Page replacement algorithms (FIFO, LRU, Optimal) in Operating Systems - Step-by-Step Execution

Concept Flow - Page replacement algorithms (FIFO, LRU, Optimal)

Page Request

↓

Is page in memory?

Yes→Use page, no replacement

No↓

Is free frame available?

Yes→Load page into free frame

No↓

Select page to replace

↓

FIFO: Replace oldest page

↓

LRU: Replace least recently used page

↓

Optimal: Replace page not used for longest future time

↓

Replace page

↓

Continue processing next page request

When a page is requested, if it's not in memory and no free frame exists, the algorithm selects a page to replace based on FIFO, LRU, or Optimal strategy.

Execution Sample

Operating Systems

Frames = 3
Pages = [7, 0, 1, 2, 0, 3, 0, 4]
Algorithm = FIFO
For each page in Pages:
  If page in Frames: continue
  Else if free frame: add page
  Else replace page by FIFO rule

Simulates page requests with 3 frames using FIFO page replacement.

Analysis Table

Step	Page Requested	Frames Before	Page Hit?	Action	Frames After
1	7	[]	No	Load page 7 into free frame	[7]
2	0	[7]	No	Load page 0 into free frame	[7, 0]
3	1	[7, 0]	No	Load page 1 into free frame	[7, 0, 1]
4	2	[7, 0, 1]	No	Replace oldest page (7) with 2	[2, 0, 1]
5	0	[2, 0, 1]	Yes	Page hit, no replacement	[2, 0, 1]
6	3	[2, 0, 1]	No	Replace oldest page (0) with 3	[2, 3, 1]
7	0	[2, 3, 1]	No	Replace oldest page (1) with 0	[2, 3, 0]
8	4	[2, 3, 0]	No	Replace oldest page (2) with 4	[4, 3, 0]
Exit	-	[4, 3, 0]	-	All pages processed	[4, 3, 0]

💡 All pages processed; simulation ends.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
Frames	[]	[7]	[7, 0]	[7, 0, 1]	[2, 0, 1]	[2, 0, 1]	[2, 3, 1]	[2, 3, 0]	[4, 3, 0]	[4, 3, 0]
Page Requested	-	7	0	1	2	0	3	0	4	-
Page Hit	-	No	No	No	No	Yes	No	No	No	-

Key Insights - 3 Insights

Why does the FIFO algorithm replace the oldest page instead of the least recently used?

FIFO replaces the page that came into memory first, regardless of recent use. This is shown in execution_table rows 4, 6, 7, and 8 where the oldest page is replaced, not necessarily the least recently used.

Why is there no replacement when the page is already in frames?

When a page is found in memory (page hit), no replacement is needed. This is shown in step 5 where page 0 is already in frames, so no change occurs.

How does the algorithm decide when to load a page into a free frame?

If there is space in frames (less than capacity), the page is loaded without replacement. This happens in steps 1, 2, and 3 where frames are not full yet.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. Which page is replaced and why?

A Page 7, because it is the oldest page in frames

B Page 0, because it is least recently used

C Page 1, because it is the largest number

D Page 2, because it is not in frames

💡 Hint

Check the 'Action' and 'Frames Before' columns at step 4 in execution_table.

At which step does the first page hit occur according to the execution_table?

A Step 3

B Step 5

C Step 6

D Step 8

💡 Hint

Look at the 'Page Hit?' column in execution_table to find the first 'Yes'.

If the number of frames was increased to 4, how would the frames after step 4 change?

A [7, 0, 1, 2] because no replacement needed yet

B [2, 0, 1] same as before

C [7, 0, 1] no page 2 loaded

D [0, 1, 2, 3] pages replaced earlier

💡 Hint

Refer to variable_tracker and consider when replacement happens based on frame capacity.

Concept Snapshot

Page replacement algorithms decide which page to remove when memory is full.
FIFO removes the oldest page loaded.
LRU removes the least recently used page.
Optimal removes the page not needed for longest future time.
They help manage limited memory efficiently.

Full Transcript

Page replacement algorithms manage memory by deciding which page to remove when a new page is needed but memory is full. The FIFO algorithm replaces the oldest page loaded into memory, ignoring recent usage. LRU replaces the page that was used least recently, tracking usage history. Optimal replaces the page that will not be used for the longest time in the future, which is ideal but requires future knowledge. The execution example shows FIFO with 3 frames and a sequence of page requests. Pages are loaded into free frames until full, then the oldest page is replaced on a miss. Hits occur when the requested page is already in memory, requiring no replacement. This process continues until all pages are processed.

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