OS Notes
HubFunctions of Operating SystemsHistory of Operating SystemsObjectives of Operating SystemsTypes of Operating Systems — Operating SystemsWhat is an Operating SystemThe Booting ProcessThe KernelOperating System ServicesOperating System StructureSystem CallsUser Mode vs Kernel ModeContext SwitchingInterprocess Communication (IPC)MultithreadingProcess Control Block (PCB)Introduction to ProcessesProcess SchedulingProcess StatesThreadsCritical Section ProblemDining Philosophers ProblemMonitorsMutex LocksProducer-Consumer ProblemReaders-Writers ProblemSemaphoresIntroduction to Process SynchronizationBanker\Deadlock AvoidanceDeadlock DetectionIntroduction to DeadlocksDeadlock PreventionDeadlock RecoveryNecessary Conditions for DeadlockResource Allocation GraphContiguous Memory AllocationDemand PagingMemory Management IntroductionPage Replacement AlgorithmsPagingSegmentationThrashingVirtual Memory — Operating SystemsDisk Scheduling - I/O OptimizationDisk Structure - Physical OrganizationRAID - Redundant Array of Independent DisksSecondary Storage - Persistent StorageStorage Virtualization - Abstract StorageSwap Space Management - Virtual MemoryDirectory StructureFile Allocation MethodsFile ConceptsFile ProtectionFile System ImplementationFile System IntroductionFree Space ManagementDevice DriversDisk Scheduling AlgorithmsDMA - Direct Memory AccessInterruptsI/O HardwareI/O SoftwareCPU Scheduling Interview QuestionsLinux Interview QuestionsMemory Management Interview QuestionsOperating System CheatsheetOperating System Interview Questions — Operating SystemsAndroid Operating System — Operating SystemsEmbedded OS Case StudyiOS Operating System — Operating SystemsLinux ArchitectureWindows ArchitectureGlossary of Terms — Operating SystemsImportant Formulas — Operating SystemsQuick Revision Notes — Operating SystemsRecommended Books — Operating SystemsFCFS Scheduling - First Come First ServedMultilevel Feedback Queue SchedulingMultilevel Queue SchedulingPriority SchedulingRound Robin SchedulingScheduling Algorithm ComparisonCPU Scheduling ConceptsSJF Scheduling - Shortest Job FirstCloud Operating Systems - Architecture and ImplementationDistributed Operating Systems - Design and ConceptsEmbedded Operating Systems - Real-time and Resource-ConstrainedMobile Operating Systems - Android, iOS, and WindowsNetwork Operating Systems - NOS ArchitectureReal-Time Operating SystemsVirtualization - Containers and Virtual MachinesAdvanced Virtualization - Full and Para-virtualizationBasic Linux Commands - Command Line UsageLinux File System - ext4 and othersLinux Introduction - OS OverviewPermissions and Security - Linux SecurityProcess Management in Linux - Process ControlShell Scripting - Bash ProgrammingUser Management - Users and GroupsBankerCPU Scheduling Simulator ProjectMini Operating System ProjectPage Replacement SimulatorShell Scripting ProjectsAccess Control - Permission ModelsAuthentication - User VerificationAuthorization - Access ControlMalware and Threats - Security ThreatsOS Security Basics - Threats and ControlsProtection Mechanisms - Security ImplementationSecurity Best Practices - OS Hardening
Build a page replacement algorithm simulator — implement FIFO, LRU, Optimal, and Clock algorithms with visualization of page faults, hit ratios, and Belady
Project Overview
When physical memory is full and a new page needs to be loaded, the operating system must decide which existing page to evict. This decision is made by page replacement algorithms. In this project, you will build a simulator that accepts a reference string and number of frames, then runs multiple algorithms and compares their performance — visualizing page faults, hit ratios, and demonstrating phenomena like Belady's Anomaly.
Why This Project Matters
Page replacement is not just academic theory. Every operating system uses some variant of these algorithms constantly. Your web browser, database server, and even your phone's apps all trigger page replacements. Understanding the trade-offs between algorithms helps you understand why systems sometimes feel slow (thrashing) and how kernel developers optimize memory performance.
Data Structures
Example
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_FRAMES 20
#define MAX_REFERENCES 100
typedef struct {
int frames[MAX_FRAMES];
int num_frames;
int page_faults;
int page_hits;
} SimulationState;
int reference_string[MAX_REFERENCES];
int ref_length;
Algorithm Implementations
FIFO (First-In, First-Out)
Replace the page that has been in memory the longest. Simple but suffers from Belady's Anomaly.
Example
int simulate_fifo(int num_frames) {
int frames[MAX_FRAMES];
int front = 0; // circular queue pointer
int page_faults = 0;
int current_size = 0;
for (int i = 0; i < num_frames; i++)
frames[i] = -1;
for (int i = 0; i < ref_length; i++) {
int page = reference_string[i];
bool found = false;
// Check if page already in frames
for (int j = 0; j < current_size; j++) {
if (frames[j] == page) {
found = true;
break;
}
}
if (!found) {
// Page fault — replace using FIFO order
frames[front] = page;
front = (front + 1) % num_frames;
if (current_size < num_frames) current_size++;
page_faults++;
}
// Print current frame state
printf("Page %d: [", page);
for (int j = 0; j < current_size; j++)
printf("%d%s", frames[j], j < current_size-1 ? ", " : "");
printf("] %s\n", found ? "HIT" : "FAULT");
}
return page_faults;
}
LRU (Least Recently Used)
Replace the page that has not been used for the longest time. No Belady's Anomaly but harder to implement.
Example
int simulate_lru(int num_frames) {
int frames[MAX_FRAMES];
int last_used[MAX_FRAMES]; // timestamp of last access
int page_faults = 0;
int current_size = 0;
for (int i = 0; i < num_frames; i++) {
frames[i] = -1;
last_used[i] = -1;
}
for (int i = 0; i < ref_length; i++) {
int page = reference_string[i];
bool found = false;
int found_idx = -1;
for (int j = 0; j < current_size; j++) {
if (frames[j] == page) {
found = true;
found_idx = j;
break;
}
}
if (found) {
last_used[found_idx] = i; // update access time
} else {
page_faults++;
if (current_size < num_frames) {
frames[current_size] = page;
last_used[current_size] = i;
current_size++;
} else {
// Find least recently used frame
int lru_idx = 0;
for (int j = 1; j < num_frames; j++)
if (last_used[j] < last_used[lru_idx])
lru_idx = j;
frames[lru_idx] = page;
last_used[lru_idx] = i;
}
}
}
return page_faults;
}
Optimal (OPT)
Replace the page that will not be used for the longest time in the future. Theoretically best but requires future knowledge.
Example
int simulate_optimal(int num_frames) {
int frames[MAX_FRAMES];
int page_faults = 0;
int current_size = 0;
for (int i = 0; i < num_frames; i++)
frames[i] = -1;
for (int i = 0; i < ref_length; i++) {
int page = reference_string[i];
bool found = false;
for (int j = 0; j < current_size; j++)
if (frames[j] == page) { found = true; break; }
if (!found) {
page_faults++;
if (current_size < num_frames) {
frames[current_size++] = page;
} else {
// Find page used farthest in future
int farthest = -1, replace_idx = 0;
for (int j = 0; j < num_frames; j++) {
int next_use = INT_MAX;
for (int k = i + 1; k < ref_length; k++) {
if (reference_string[k] == frames[j]) {
next_use = k;
break;
}
}
if (next_use > farthest) {
farthest = next_use;
replace_idx = j;
}
}
frames[replace_idx] = page;
}
}
}
return page_faults;
}
Clock (Second Chance) Algorithm
A practical approximation of LRU using a reference bit and circular queue:
Example
int simulate_clock(int num_frames) {
int frames[MAX_FRAMES];
bool ref_bit[MAX_FRAMES];
int hand = 0;
int page_faults = 0;
int current_size = 0;
for (int i = 0; i < num_frames; i++) {
frames[i] = -1;
ref_bit[i] = false;
}
for (int i = 0; i < ref_length; i++) {
int page = reference_string[i];
bool found = false;
for (int j = 0; j < current_size; j++) {
if (frames[j] == page) {
ref_bit[j] = true; // give second chance
found = true;
break;
}
}
if (!found) {
page_faults++;
while (ref_bit[hand]) {
ref_bit[hand] = false; // clear second chance
hand = (hand + 1) % num_frames;
}
frames[hand] = page;
ref_bit[hand] = true;
hand = (hand + 1) % num_frames;
if (current_size < num_frames) current_size++;
}
}
return page_faults;
}
Main Program — Comparison Mode
Example
int main() {
printf("Enter reference string length: ");
scanf("%d", &ref_length);
printf("Enter reference string: ");
for (int i = 0; i < ref_length; i++)
scanf("%d", &reference_string[i]);
int num_frames;
printf("Enter number of frames: ");
scanf("%d", &num_frames);
printf("\n=== Results ===\n");
printf("FIFO: %d page faults\n", simulate_fifo(num_frames));
printf("LRU: %d page faults\n", simulate_lru(num_frames));
printf("Optimal: %d page faults\n", simulate_optimal(num_frames));
printf("Clock: %d page faults\n", simulate_clock(num_frames));
// Demonstrate Belady's Anomaly for FIFO
printf("\n=== Belady's Anomaly Check (FIFO) ===\n");
for (int f = 1; f <= 7; f++)
printf("Frames=%d: %d faults\n", f, simulate_fifo(f));
return 0;
}
Sample Test Case
Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 Frames: 3
Expected Results:
- FIFO: 15 page faults
- LRU: 12 page faults
- Optimal: 9 page faults
Project Extensions
- Graphical visualization — show frame contents at each step as a table
- Belady's Anomaly detector — automatically find reference strings where more frames cause more faults in FIFO
- Random reference string generator — test with locality of reference patterns
- Performance charts — plot page faults vs. number of frames for each algorithm
- Working Set simulation — implement working set model with window parameter
Key Takeaways
- Optimal is a theoretical benchmark — useful for comparison but not implementable
- LRU is near-optimal but expensive (needs hardware support or approximation)
- Clock algorithm provides the best practical trade-off in real operating systems
- FIFO is simple but can perform poorly due to Belady's Anomaly
- More frames generally means fewer faults, except with Belady's Anomaly in FIFO
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Page Replacement Simulator.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.
Search Terms
operating-systems, operating systems, operating, systems, practicals, and, projects, page
Related Operating Systems Topics
Continue learning this concept
Practicals And ProjectsCPU Scheduling Simulator ProjectBuild a CPU scheduling simulator implementing FCFS, SJF, SRTF, Priority, and Round Robin algorithms with Gantt chart generation, performance metrics, and comparison analysis.Practicals And ProjectsBankerComplete implementation project for BankerPracticals And ProjectsMini Operating System ProjectBuild a mini operating system simulation — implement process scheduling, memory management, file system, and shell interface in C to understand OS internals through hands-on coding.Practicals And ProjectsShell Scripting ProjectsPractical shell scripting projects for OS labs — system monitoring scripts, automated backup, log analyzer, process manager, and user administration tools with complete Bash implementations.Memory ManagementPage Replacement AlgorithmsComplete guide to page replacement algorithms — FIFO, Optimal, LRU, LRU approximations, clock algorithm, and Belady\Distributed And Modern OsCloud Operating Systems - Architecture and ImplementationComprehensive guide to cloud operating systems including virtualization, multi-tenancy, resource allocation, and cloud kernel architecture. Learn about hypervisors, containerization, auto-scaling, and cloud computing concepts for BCA students with real-world examples.