FIFO (First-In-First-Out) Page Replacement Algorithm
steps:
● Initialize an empty frame array.
● Loop through the page requests.
● Check if the page is already in the frame.
● If not, replace the oldest page in the frame.
● Print the current state of the frame.
Program:
#include <stdio.h>
void FIFO(int pages[], int n, int capacity) {
int frame[capacity];
for (int i = 0; i < capacity; i++)
frame[i] = -1;
int index = 0, page_faults = 0;
for (int i = 0; i < n; i++) {
int flag = 0;
// Check if the page is already in the frame
for (int j = 0; j < capacity; j++) {
if (frame[j] == pages[i]) {
flag = 1;
break;
}
}
// If the page is not in the frame, add it
if (flag == 0) {
frame[index] = pages[i];
index = (index + 1) % capacity;
page_faults++;
}
// Print the current frame
for (int j = 0; j < capacity; j++) {
if (frame[j] != -1)
printf("%d ", frame[j]);
else
printf("- ");
}
printf("\n");
}
printf("Total Page Faults: %d\n", page_faults);
}
int main() {
int pages[] = {1, 3, 0, 3, 5, 6, 3};
int n = sizeof(pages) / sizeof(pages[0]);
int capacity = 3;
FIFO(pages, n, capacity);
return 0;
}
Result:
LRU (Least Recently Used) Page Replacement Algorithm
Steps:
● Initialize an empty frame array and a counter array to track the usage
of pages.
● Loop through the page requests.
● Check if the page is already in the frame and update its counter.
● If not, replace the least recently used page.
● Print the current state of the frame.
Program:
#include <stdio.h>
void LRU(int pages[], int n, int capacity) {
int frame[capacity], counter[capacity];
for (int i = 0; i < capacity; i++) {
frame[i] = -1;
counter[i] = 0;
}
int page_faults = 0, time = 0;
for (int i = 0; i < n; i++) {
int flag = 0, least = time, pos = 0;
// Check if the page is already in the frame
for (int j = 0; j < capacity; j++) {
if (frame[j] == pages[i]) {
counter[j] = ++time;
flag = 1;
break;
}
}
// If the page is not in the frame, replace the least recently used page
if (flag == 0) {
for (int j = 0; j < capacity; j++) {
if (frame[j] == -1) {
pos = j;
break;
} else if (counter[j] < least) {
least = counter[j];
pos = j;
}
}
frame[pos] = pages[i];
counter[pos] = ++time;
page_faults++;
}
// Print the current frame
for (int j = 0; j < capacity; j++) {
if (frame[j] != -1)
printf("%d ", frame[j]);
else
printf("- ");
}
printf("\n");
}
printf("Total Page Faults: %d\n", page_faults);
}
int main() {
int pages[] = {1, 3, 0, 3, 5, 6, 3};
int n = sizeof(pages) / sizeof(pages[0]);
int capacity = 3;
LRU(pages, n, capacity);
return 0;
}
Result:
Optimal Page Replacement Algorithm
Steps:
● Initialize an empty frame array.
● Loop through the page requests.
● Check if the page is already in the frame.
● If not, replace the page that will not be used for the longest time in the
future.
● Print the current state of the frame.
Program:
#include <stdio.h>
int predict(int pages[], int frame[], int n, int index, int capacity) {
int res = -1, farthest = index;
for (int i = 0; i < capacity; i++) {
int j;
for (j = index; j < n; j++) {
if (frame[i] == pages[j]) {
if (j > farthest) {
farthest = j;
res = i;
}
break;
}
}
if (j == n) {
return i;
}
}
return (res == -1) ? 0 : res;
}
void Optimal(int pages[], int n, int capacity) {
int frame[capacity];
for (int i = 0; i < capacity; i++)
frame[i] = -1;
int page_faults = 0;
for (int i = 0; i < n; i++) {
int flag = 0;
// Check if the page is already in the frame
for (int j = 0; j < capacity; j++) {
if (frame[j] == pages[i]) {
flag = 1;
break;
}
}
// If the page is not in the frame, replace the optimal page
if (flag == 0) {
if (i >= capacity) {
int j = predict(pages, frame, n, i + 1, capacity);
frame[j] = pages[i];
} else {
frame[i] = pages[i];
}
page_faults++;
}
// Print the current frame
for (int j = 0; j < capacity; j++) {
if (frame[j] != -1)
printf("%d ", frame[j]);
else
printf("- ");
}
printf("\n");
}
printf("Total Page Faults: %d\n", page_faults);
}
int main() {
int pages[] = {1, 3, 0, 3, 5, 6, 3};
int n = sizeof(pages) / sizeof(pages[0]);
int capacity = 3;
Optimal(pages, n, capacity);
return 0;
}
Result:
