Understanding FIFO
Page Replacement
This presentation explores the First-In, First-Out (FIFO) page replacement
algorithm. It is a fundamental concept in operating systems for memory
management. We will cover its mechanism, benefits, and limitations.
by Shreya More
Page Replacement
Algorithms Overview
Minimize Page Diverse Varying
Faults Algorithms Performance
The primary goal is to Options include FIFO, LRU, Each algorithm offers
reduce interruptions for Optimal, LFU, and MFU. unique efficiency
better performance. characteristics.
System Efficiency
Algorithm choice directly
impacts overall system
efficiency.
How FIFO Works
Queue Behavior
Memory operates like a simple queue structure.
Oldest Replaced
On a page fault, the oldest page is removed.
Circular Buffer
Implementation is straightforward using a circular buffer.
Example Sequence
Consider page requests: 1, 2, 3, 4, 1, 2, 5.
Pros and Cons of FIFO
Pros Cons
• Simple to implement. • Suffers from Belady's anomaly.
• Low computational overhead. • Ignores page usage frequency.
• Good for initial understanding. • Not efficient for all workloads.
Next Steps
1 Explore LRU
Investigate Least Recently Used algorithm for better
performance.
2 Study Optimal
Understand the theoretical "Optimal" algorithm for
comparison.
3 Analyze Workloads
Evaluate how different workloads affect algorithm
efficiency.
Coding : -
#include <stdio.h>// I/Ofunctionalities
#include <stdlib.h>// general purposr funtion
int main() {// entry point of code
int i = 0, j = 0, k = 0, i1 = 0, m, n;
int rs[30], flag = 1, p[30];// rs store the pages and p is used to display the pages
printf("FIFO page replacement algorithm....\n");
printf("Enter the number of frames: ");
scanf("%d", &n);
printf("Enter the reference string (end with -1):\n");
while (1) {
scanf("%d", &rs[i]);
if (rs[i] == -1) // -1 to end input
break;
i++;
}
m = i;
// initialize page frames
for (j = 0; j < n; j++)
p[j] = -1; // Initialize frames with -1(to indicate they are empty)
for (i = 0; i < m; i++) {//outerloop to go through each page
flag = 1;
//inner loop to check page is already in frame
for (j = 0; j < n; j++) {
if (p[j] == rs[i]) {
printf("Page %d already in frame.\n", rs[i]);
flag = 0;
break;
}
}
//page replacement
if (flag == 1) {//page fault
p[i1] = rs[i];//new page is inserted
i1++;
k++; // Page fault
if (i1 == n)//start replacing from the beginning
i1 = 0;
//prints the current state of all frames after inserting
printf("Frames after inserting page %d:\n", rs[i]);
for (j = 0; j < n; j++) {
printf("Page %d: %d", j + 1, p[j]);
if (p[j] == rs[i])
printf(" *");
printf("\n");
}
printf("\n");
}
}
printf("Total number of page faults = %d\n", k);
return 0;
}
OUTPUT :-
Conclusion
Basic but Flawed Learning Tool
FIFO provides a simple introduction to replacement It's excellent for understanding foundational principles.
concepts.
Better Alternatives Workload Matters
LRU and Optimal algorithms typically outperform FIFO. Algorithm choice depends on the specific system
workload.