160 views
FIFO Page Replacement Algorithm in C
The First-In-First-Out (FIFO) page replacement algorithm is a simple page replacement policy used in operating systems to decide which page to replace when a new page needs to be brought into memory, and the memory is already full. The FIFO algorithm replaces the oldest page in memory, i.e., the page that has been in memory for the longest time.
Here’s a C program that simulates the FIFO page replacement algorithm:
C
#include <stdio.h>
int main() {
int n; // Number of frames in memory
printf("Enter the number of frames: ");
scanf("%d", &n);
int frames[n]; // Array to store the page frames
int pageQueue[n]; // Array to store the pages in the order they are loaded
// Initialize the frames and pageQueue arrays to -1, indicating empty frames
for (int i = 0; i < n; i++) {
frames[i] = -1;
pageQueue[i] = -1;
}
int numPages; // Number of pages in the input sequence
printf("Enter the number of pages: ");
scanf("%d", &numPages);
printf("Enter the page reference sequence: ");
for (int i = 0; i < numPages; i++) {
int page;
scanf("%d", &page);
// Check if the page is already in memory
int inMemory = 0;
for (int j = 0; j < n; j++) {
if (frames[j] == page) {
inMemory = 1;
break;
}
}
if (!inMemory) {
// Page fault: replace the oldest page with the new page
int oldestIndex = 0;
for (int j = 1; j < n; j++) {
if (pageQueue[j] < pageQueue[oldestIndex]) {
oldestIndex = j;
}
}
frames[oldestIndex] = page;
pageQueue[oldestIndex] = i + 1; // Update the page loading time
}
// Update the page loading order
for (int j = 0; j < n; j++) {
if (pageQueue[j] != -1) {
pageQueue[j]++;
}
}
// Print the current state of memory
printf("Memory: ");
for (int j = 0; j < n; j++) {
if (frames[j] != -1) {
printf("%d ", frames[j]);
} else {
printf("- ");
}
}
printf("\n");
}
return 0;
}In this program:
- The user is prompted to enter the number of frames in memory (
n), the number of pages in the input sequence (numPages), and the page reference sequence. - The
framesarray simulates the memory frames, and thepageQueuearray keeps track of the pages in the order they were loaded into memory. - The program iterates through the page reference sequence and checks if each page is already in memory. If not, it finds the oldest page in memory (according to the loading order) and replaces it with the new page.
- After each page reference, the program prints the current state of memory.
You can run this program with different inputs to observe how the FIFO page replacement algorithm works.