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.