Page Replacement · Operating Systems

Page Replacement Lab

CSC-264 · Semester IV · Operating Systems

intermediate30 minAvailable

Page Replacement

Walk a reference string through FIFO, LRU and Optimal.

Reference string

Number of frames: 3

Reference sequence

70120304230321201701

Page faults

Fault rate

75.0%

Step 1 of 20 — accessing page 7

Frame 17

Frame 2—

Frame 3—

Page fault — 7 not in memory. Filled an empty frame.

Lab brief

Objective

Simulate FIFO, LRU and Optimal page replacement on the same reference string and compare their page-fault behaviour.

Theory & concepts

When a referenced page is not in memory, a page fault occurs and the OS must bring the page in — often evicting another. FIFO evicts the oldest-loaded page, LRU evicts the least recently used, and Optimal evicts the page that will be used farthest in the future (a theoretical yardstick).

Rendering diagram…

Handling a page fault and choosing a victim page

Algorithm	Evicts	Strengths	Weaknesses
FIFO	oldest loaded	simple	Belady's anomaly
LRU	least recently used	good locality tracking	needs timestamps
Optimal	used farthest in future	minimum faults	not implementable

Prerequisites

Lesson: Paging and demand paging
Lesson: Page replacement algorithms

Instructions

1Use the provided reference string or type your own.
2Choose a frame size (for example 3).
3Run FIFO and count the page faults.
4Repeat with LRU and Optimal on the same string.
5Vary the frame count and observe how faults change.

Tasks

Run FIFO
Trace the reference string in 3 frames and count faults.
Run LRU
Repeat and explain which page was chosen for eviction.
Compare with Optimal
Show that Optimal gives the fewest faults.
Belady's anomaly
Try FIFO with 3 and 4 frames and see if faults increase.

Self-check

Hand-traced results match the simulation.
The choice of victim page is justified for each algorithm.
The student explains Belady's anomaly for FIFO.

Environment

reference string editorframe visualizationfault countermultiple algorithms