FIFO
The First In, First Out (FIFO) algorithm is a classic method used by operating systems to manage the pages in memory when there isn't enough space to keep all the needed pages in RAM at once. It is one of the simplest forms of page replacement algorithms and operates exactly as its name suggests: the first page loaded into memory is also the first to be removed when space is needed.
How FIFO Works
To understand how FIFO functions, imagine memory as a limited set of slots where each slot can hold one page. When a program starts, these slots are empty, and pages are loaded into them as the program accesses different parts of its code or data. Here’s what happens step-by-step in a system using FIFO:
-
Loading Pages: As the program runs, it loads new pages into the available empty slots in memory.
-
Checking Full Memory: If a page fault occurs and all memory slots are full, the FIFO algorithm looks at the page that has been in memory the longest.
- Replacing the Oldest Page: This oldest page is then removed to make space for the new page that the program needs to access.
Implementation in C
Implementing FIFO in C requires managing a queue where the index of the pages in memory is stored. Here's a basic structure of how you might write this:
C
#include <stdio.h>
#include <stdlib.h>
#define MAX_FRAMES 3 // Number of frames in memory
int frames[MAX_FRAMES];
int front = 0; // Start of the queue
int rear = -1; // End of the queue
void insert(int page) {
if (rear == MAX_FRAMES - 1) {
// Memory is full, remove the first page
for (int i = 0; i < rear; i++) {
frames[i] = frames[i + 1];
}
frames[rear] = page; // Add new page at the end
} else {
// Add new page to the queue
frames[++rear] = page;
}
}
void display() {
for (int i = 0; i <= rear; i++) {
printf("%d ", frames[i]);
}
printf("\n");
}
int main() {
// Example usage
insert(1);
insert(2);
insert(3);
display(); // Output: 1 2 3
insert(4);
display(); // Output: 2 3 4 (1 is replaced)
return 0;
}
You can also try this code with Online C Compiler
Output
1 2 3
2 3 4
This simple program illustrates how FIFO manages memory. When the memory reaches its limit, the oldest page is replaced by the new page. The queue maintains the order of pages just as they were inserted.
Implementation
Implementing the FIFO page replacement algorithm in C programming involves creating a straightforward simulation that mimics how an operating system might handle memory pages when only a limited number of them can be kept in RAM. The goal is to show how the FIFO algorithm decides which page to evict when a new page needs to be loaded but memory is full.
Step-by-Step Implementation
The following steps outline the process to simulate the FIFO page replacement algorithm in a clear and concise way, using basic C programming techniques:
Initialize Memory Structure
We start by setting up an array to represent the frames available in memory. Each element of the array will hold a page number.
Simulate Page Requests
As the program runs, it simulates requests for pages. These requests are represented by an array of integers where each integer is a page number that the program needs to access.
Process Each Page Request
For each page requested, the program checks if the page is already in one of the memory frames.
-
If the page is already in memory, it's a 'hit', and no page replacement is needed.
-
If the page is not in memory and there is an empty frame, the page is loaded into the free frame.
- If there are no free frames (i.e., memory is full), the algorithm removes the page that was loaded first (the one at the front of the queue) and loads the new page into that frame.
Track Page Faults
A 'page fault' occurs whenever a page needs to be loaded into memory from disk (either into an empty frame or replacing an existing page). The simulation keeps a count of these page faults to measure the effectiveness of the FIFO strategy.
Example Code
C
#include <stdio.h>
#define FRAME_SIZE 3
int frames[FRAME_SIZE];
int front = 0;
int rear = 0;
int pageFaults = 0;
void displayFrames() {
for (int i = 0; i < FRAME_SIZE; i++) {
printf("%d ", frames[i]);
}
printf("\n");
}
void insertPage(int page) {
int i;
for (i = 0; i < rear; i++) {
if (frames[i] == page) {
printf("Page %d already in frame.\n", page);
displayFrames();
return;
}
}
if (rear < FRAME_SIZE) {
frames[rear++] = page;
} else {
for (i = 0; i < FRAME_SIZE - 1; i++) {
frames[i] = frames[i + 1];
}
frames[i] = page;
}
pageFaults++;
printf("Page %d inserted:\n", page);
displayFrames();
}
int main() {
int requests[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
int n = sizeof(requests) / sizeof(requests[0]);
for (int i = 0; i < n; i++) {
insertPage(requests[i]);
}
printf("Total page faults: %d\n", pageFaults);
return 0;
}
You can also try this code with Online C Compiler
Output
Page 1 inserted:
1 0 0
Page 2 inserted:
1 2 0
Page 3 inserted:
1 2 3
Page 4 inserted:
2 3 4
Page 1 inserted:
3 4 1
Page 2 inserted:
4 1 2
Page 5 inserted:
1 2 5
Page 1 already in frame.
1 2 5
Page 2 already in frame.
1 2 5
Page 3 inserted:
2 5 3
Page 4 inserted:
5 3 4
Page 5 already in frame.
5 3 4
Total page faults: 9
This program efficiently demonstrates how FIFO handles page requests & manages memory. It includes functions to insert pages into frames and display the current state of memory, making it easy to track what's happening at each step.
Frequently Asked Questions
What is FIFO in C programming?
FIFO (First In, First Out) is a queue data structure in C where elements are processed in the order they were added, removing the oldest first.
What is FIFO policy for page replacement?
FIFO page replacement algorithm swaps out the oldest page in memory when a new page needs to be loaded and memory is full.
How do you use FIFO page replacement algorithm?
In FIFO, maintain a queue to track pages in memory. Replace the oldest page (front of the queue) when a new page is referenced.
Conclusion
In this article, we have learned about the FIFO page replacement algorithm and its implementation in C programming. We discussed how FIFO handles memory pages, its simplicity, and scenarios where it may not be the most efficient due to Belady’s Anomaly. The example provided a clear demonstration of how FIFO processes page requests and manages memory in a limited frame environment, along with tracking page faults to assess its performance.
You can refer to our guided paths on the Code360. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.
26+ registered 
