Practical 15: Write a C program to simulate the following page replacement algorithm: FIFO, LRU, and Optimal.
2024, April 17
15. Page Replacement Algorithms in C
This practical aims to simulate three common page replacement algorithms: First-In-First-Out (FIFO), Least Recently Used (LRU), and Optimal Page Replacement. Each of these algorithms helps in managing how pages are loaded into memory from disk and replaced to accommodate new pages when memory is full. This simulation will be implemented using the C programming language on a Kali Linux environment.
15.A. FIFO (First-In-First-Out)
The FIFO page replacement algorithm is one of the simplest types of algorithm that manages the pages in memory. It operates on the principle that the pages that have been in memory the longest should be replaced first. This algorithm does not account for the frequency of page use after its entry into memory.
// The FIFO algorithm is implemented using the following function:
void fifo(int pages[], int n, int frameSize) {
int frame[frameSize], fcount = 0;
for (int i = 0; i < frameSize; i++)
frame[i] = -1;
for (int i = 0; i < n; i++) {
int j = 0, flag = 0;
while (j < frameSize) {
if (frame[j] == pages[i]) {
flag = 1;
break;
}
j++;
}
if (flag == 0) {
frame[fcount] = pages[i];
fcount = (fcount + 1) % frameSize;
}
for (j = 0; j < frameSize; j++)
printf("%d ", frame[j]);
printf("\\n");
}
}15.A.1. Implementation of FIFO Page Replacement Algorithm
The FIFO page replacement algorithm is implemented using the following steps:
- Initialize: Start with an empty frame and a counter set to point to the first frame.
- Check for a Page Hit: When a page is requested, check if it's already in one of the frames. If the page is found, it's a page hit, and no replacement is needed.
- Page Replacement:
- If the page is not in any frame (a page fault) and the frame is not full, load the page into the next available frame.
- If all frames are full, remove the page that was loaded first (the page at the counter position) and load the new page into that frame.
- Update Counter: After a page is replaced, move the counter to the next frame position in a circular manner.
15.A.2. Implementation of FIFO Page Replacement in C
Below is the C code that demonstrates the implementation of the FIFO Page Replacement algorithm:
#include <stdio.h>
int main()
{
int incomingStream[] = {4, 1, 2, 4, 5};
int pageFaults = 0;
int frames = 3;
int m, n, s, pages;
pages = sizeof(incomingStream) / sizeof(incomingStream[0]);
printf(" Incoming \t Frame 1 \t Frame 2 \t Frame 3 ");
int temp[frames];
for (m = 0; m < frames; m++)
{
temp[m] = -1;
}
for (m = 0; m < pages; m++)
{
s = 0;
for (n = 0; n < frames; n++)
{
if (incomingStream[m] == temp[n])
{
s++;
pageFaults--;
}
}
pageFaults++;
if ((pageFaults <= frames) && (s == 0))
{
temp[m] = incomingStream[m];
}
else if (s == 0)
{
temp[(pageFaults - 1) % frames] = incomingStream[m];
}
printf("\n");
printf("%d\t\t\t", incomingStream[m]);
for (n = 0; n < frames; n++)
{
if (temp[n] != -1)
printf(" %d\t\t\t", temp[n]);
else
printf(" - \t\t\t");
}
}
printf("\nTotal Page Faults:\t%d\n", pageFaults);
return 0;
}15.B. LRU (Least Recently Used)
The LRU algorithm keeps track of page usage over a short period of time. It replaces the page that has been in memory the longest with no recent use. This means that it favors pages that have been most recently used.
// The LRU algorithm is implemented using the following function:
void lru(int pages[], int n, int frameSize) {
int frame[frameSize], used[frameSize];
for (int i = 0; i < frameSize; i++) {
frame[i] = -1;
used[i] = 0;
}
for (int i = 0; i < n; i++) {
int j = 0, flag = 0, least = 9999, rIndex;
while (j < frameSize) {
if (frame[j] == pages[i]) {
flag = 1;
used[j] = i;
break;
}
if (used[j] < least) {
least = used[j];
rIndex = j;
}
j++;
}
if (flag == 0) {
frame[rIndex] = pages[i];
used[rIndex] = i;
}
for (j = 0; j < frameSize; j++)
printf("%d ", frame[j]);
printf("\\n");
}
}15.B.1. Implementation of LRU Page Replacement Algorithm
The LRU page replacement algorithm is implemented using the following steps:
- Initialize: Start with an empty frame and a list or another structure to keep track of the age of each page in the frame.
- Check for a Page Hit: When a page is requested, check if it's already in one of the frames. If the page is found (a page hit), move this page to the top of the age list or mark it as most recently used.
- Page Replacement:
- If the page is not in any frame (a page fault) and there is space available, load the page into a free frame and adjust its position in the age list to mark it as most recently used.
- If all frames are full and a new page needs to be loaded, remove the page that is least recently used (the one at the bottom of the age list) and replace it with the new page. Then mark the new page as most recently used.
- Update Age List: After every page reference, update the age list to ensure that the most recently accessed pages are considered 'youngest' and the least accessed are 'oldest'.
15.B.2. Implementation of LRU Page Replacement in C
Below is the C code that demonstrates the implementation of the LRU Page Replacement algorithm:
#include <stdio.h>
int main()
{
int frame, page, i, j, flag = 0, count = 0, temp, pageFault = 0, index;
printf ("LRU Page Replacement Algorithm\n");
printf ("Enter the number of frames available: ");
scanf ("%d", &frame);
printf ("Enter the number of pages available: ");
scanf ("%d", &page);
int free_frame[frame], pages[page], used_frame[frame];
for (count = 0; count < frame; count++)
free_frame[count] = -1;
printf ("Enter the page sizes: ");
for (i = 0; i < page; i++)
scanf ("%d", &pages[i]);
for (count = 0; count < page; count++)
{
flag = 0;
for (j = 0; j < frame; j++)
{
if (free_frame[j] == pages[count])
{
flag = 1;
break;
}
}
if (flag == 0)
{
for (j = 0; j < frame; j++)
used_frame[j] = 0;
for (j = 0, temp = count - 1; j < frame; j++, temp--)
{
for (i = 0; i < frame; i++)
{
if (free_frame[i] == pages[temp])
used_frame[i] = 1;
}
}
for (j = 0; j < frame; j++)
if (used_frame[j] == 0)
index = j;
free_frame[index] = pages[count];
printf ("Page Fault: ");
pageFault++;
}
for (i = 0; i < frame; i++)
printf ("%d\t", free_frame[i]);
printf ("\n");
}
printf ("The Total Page Faults are: %d\n", pageFault);
return 0;
}15.C. Optimal Page Replacement
The Optimal Page Replacement algorithm replaces the page that will not be used for the longest period of time in the future. It provides the best possible way to manage page replacements but requires future knowledge of the reference string, which is not possible in actual systems.
// The Optimal algorithm is implemented using the following function:
void optimal(int pages[], int n, int frameSize) {
int frame[frameSize];
for (int i = 0; i < frameSize; i++)
frame[i] = -1;
for (int i = 0; i < n; i++) {
int j = 0, flag = 0, max, fIndex, found[frameSize];
for (int k = 0; k < frameSize; k++)
found[k] = 0;
for (j = 0; j < frameSize; j++) {
if (frame[j] == pages[i]) {
flag = 1;
break;
}
}
if (flag == 0) {
for (j = 0; j < frameSize; j++) {
int k;
for (k = i + 1; k < n && frame[j] != pages[k]; k++);
if (k == n) found[j] = 9999;
else found[j] = k;
}
max = found[0], fIndex = 0;
for (j = 1; j < frameSize; j++) {
if (found[j] > max) {
max = found
[j];
fIndex = j;
}
}
frame[fIndex] = pages[i];
}
for (j = 0; j < frameSize; j++)
printf("%d ", frame[j]);
printf("\\n");
}
}15.C.1. Implementation of Optimal Page Replacement Algorithm
The Optimal page replacement algorithm is implemented using the following steps:
- Initialize: Start with empty frames.
- Check for a Page Hit: When a page is requested, check if it's already in one of the frames. If the page is found (a page hit), no replacement is needed.
- Page Replacement:
- If the page is not in any frame (a page fault) and there is space available, load the page into the free frame.
- If all frames are full and a new page needs to be loaded, identify the page among those currently in memory that will not be used for the longest time in the future. Replace this page with the new page.
- Forecast Future Requests: Maintain information on future requests for each page, which is often theoretical in real-world systems as future requests are not always known.
15.C.2. Implementation of Optimal Page Replacement in C
Below is the C code that demonstrates the implementation of the Optimal Page Replacement algorithm:
#include <stdio.h>
// This function checks if current strea item(key) exists in any of the frames or not
int search(int key, int frame_items[], int frame_occupied)
{
for (int i = 0; i < frame_occupied; i++)
if (frame_items[i] == key)
return 1;
return 0;
}
void printOuterStructure(int max_frames){
printf("Stream ");
for(int i = 0; i < max_frames; i++)
printf("Frame%d ", i+1);
}
void printCurrFrames(int item, int frame_items[], int frame_occupied, int max_frames){
// print current reference stream item
printf("\n%d \t\t", item);
// print frame occupants one by one
for(int i = 0; i < max_frames; i++){
if(i < frame_occupied)
printf("%d \t\t", frame_items[i]);
else
printf("- \t\t");
}
}
// This Function helps in finding frame that will not be used
// for the longest period of time in future in ref_str[0 ... refStrLen - 1]
int predict(int ref_str[], int frame_items[], int refStrLen, int index, int frame_occupied)
{
// For each current occupant in frame item
// we try to find the frame item that will not be referenced in
// for the longest in future in the upcoming reference string
int result = -1, farthest = index;
for (int i = 0; i < frame_occupied; i++) {
int j;
for (j = index; j < refStrLen; j++)
{
if (frame_items[i] == ref_str[j])
{
if (j > farthest) {
farthest = j;
result = i;
}
break;
}
}
// If we find a page that is never referenced in future,
// return it immediately as its the best
if (j == refStrLen)
return i;
}
// If none of the frame items appear in reference string
// in the future then we return 0th index. Otherwise we return result
return (result == -1) ? 0 : result;
}
void optimalPage(int ref_str[], int refStrLen, int frame_items[], int max_frames)
{
// initially none of the frames are occupied
int frame_occupied = 0;
printOuterStructure(max_frames);
// Here we traverse through reference string
// and check for miss and hit.
int hits = 0;
for (int i = 0; i < refStrLen; i++) {
// If found already in the frame items : HIT
if (search(ref_str[i], frame_items, frame_occupied)) {
hits++;
printCurrFrames(ref_str[i], frame_items, frame_occupied, max_frames);
continue;
}
// If not found in frame items : MISS
// If frames are empty then current reference string item in frame
if (frame_occupied < max_frames){
frame_items[frame_occupied] = ref_str[i];
frame_occupied++;
printCurrFrames(ref_str[i], frame_items, frame_occupied, max_frames);
}
// else we need to use optmial algorithm to find
// frame index where we need to do replacement for this
// incoming reference string item
else {
int pos = predict(ref_str, frame_items, refStrLen, i + 1, frame_occupied);
frame_items[pos] = ref_str[i];
printCurrFrames(ref_str[i], frame_items, frame_occupied, max_frames);
}
}
printf("\n\nHits: %d\n", hits);
printf("Misses: %d", refStrLen - hits);
}
// Driver Function
int main()
{
// int ref_str[] = {9, 0, 5, 1, 0, 3, 0, 4, 1, 3, 0, 3, 1, 3};
int ref_str[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
int refStrLen = sizeof(ref_str) / sizeof(ref_str[0]);
int max_frames = 3;
int frame_items[max_frames];
optimalPage(ref_str, refStrLen, frame_items, max_frames);
return 0;
}Compilation and Execution
To compile and run the simulation, use the following commands on your Kali terminal:
gcc -o page_replacement page_replacement.c
./page_replacementEnsure that the page_replacement.c file contains all the function implementations and the main function that initializes the page array and calls these algorithms. Alternatively you can use the codes seperately.