Practical-13
Title : Simulate the behavior of FIFO,LFU, LRU page -replacement algorithms on the reference string, and compare their performances using the number of page faults generated for each algorithm.
—------------------------------------------------------------------------------------------------------------------
To simulate and compare the behavior of FIFO (First-In-First-Out), LFU (Least Frequently Used), and LRU (Least Recently Used) page replacement algorithms, we need to follow these steps:
Simulate Each Algorithm:
FIFO: Maintain a queue of pages. Replace the oldest page when a page fault occurs.
LFU: Track the frequency of page access. Replace the least frequently used page when a page fault occurs.
LRU: Track the most recently used page. Replace the least recently used page when a page fault occurs.
Use a Reference String: This is a sequence of page accesses. We'll simulate each algorithm using this string.
Compare the Number of Page Faults: Count and compare the number of page faults for each algorithm.
Example Reference String and Page Frames
Reference String: [1, 2, 3, 4, 2, 1, 5, 2, 1, 4, 5]
Number of Page Frames: 3
1. FIFO (First-In-First-Out) Algorithm
Purpose: Replace the oldest page in memory when a page fault occurs.
Algorithm:
Initialize:
Create a queue to store the pages.
Set the number of page faults to 0.
Initialize the page frame (memory) to empty.
Process Each Page Request:
For each page request in the reference string:
Check if Page is in Memory:
If the page is in the memory, no page fault occurs.
Continue to the next page request.
If Page Fault Occurs:
If the memory is not full:
Add the new page to the memory.
If the memory is full:
Remove the oldest page from the memory (from the front of the queue).
Add the new page to the memory.
Increment the page fault count.
Output:
Print the state of the page frames after processing each page request.
Print the total number of page faults.
2. LFU (Least Frequently Used) Algorithm
Purpose: Replace the page with the lowest frequency of access when a page fault occurs.
Algorithm:
Initialize:
Create an array to store the pages.
Create an array to store the frequency of each page.
Set the number of page faults to 0.
Initialize the page frame (memory) to empty.
Process Each Page Request:
For each page request in the reference string:
Check if Page is in Memory:
If the page is in the memory:
Update the page’s frequency count.
No page fault occurs.
Continue to the next page request.
If Page Fault Occurs:
If the memory is not full:
Add the new page to the memory.
Set its frequency to 1.
If the memory is full:
Find the page with the minimum frequency.
Remove the page with the lowest frequency from the memory.
Add the new page to the memory and set its frequency to 1.
Increment the page fault count.
Output:
Print the state of the page frames after processing each page request.
Print the total number of page faults.
3. LRU (Least Recently Used) Algorithm
Purpose: Replace the page that has not been used for the longest time when a page fault occurs.
Algorithm:
Initialize:
Create an array to store the pages.
Create an array to store the last used time for each page.
Set the number of page faults to 0.
Initialize the page frame (memory) to empty.
Process Each Page Request:
For each page request in the reference string:
Check if Page is in Memory:
If the page is in the memory:
Update its last used time.
No page fault occurs.
Continue to the next page request.
If Page Fault Occurs:
If the memory is not full:
Add the new page to the memory.
Set its last used time to the current time.
If the memory is full:
Find the page with the oldest last used time.
Remove the page with the oldest last used time from the memory.
Add the new page to the memory and set its last used time to the current time.
Increment the page fault count.
Output:
Print the state of the page frames after processing each page request.
Print the total number of page faults.
Code-
#include <stdio.h>
#include <stdbool.h>
#define PAGE_FRAMES 3
#define REFERENCE_LENGTH 11
// Function prototypes
void FIFO(int reference[], int length, int frames);
void LFU(int reference[], int length, int frames);
void LRU(int reference[], int length, int frames);
int main() {
int reference[REFERENCE_LENGTH] = {1, 2, 3, 4, 2, 1, 5, 2, 1, 4, 5};
printf("FIFO Page Replacement:\n");
FIFO(reference, REFERENCE_LENGTH, PAGE_FRAMES);
printf("\nLFU Page Replacement:\n");
LFU(reference, REFERENCE_LENGTH, PAGE_FRAMES);
printf("\nLRU Page Replacement:\n");
LRU(reference, REFERENCE_LENGTH, PAGE_FRAMES);
return 0;
}
void FIFO(int reference[], int length, int frames) {
int page[frames];
int front = 0, rear = -1, page_faults = 0;
bool found;
// Initialize page frames
for (int i = 0; i < frames; i++) {
page[i] = -1;
}
for (int i = 0; i < length; i++) {
found = false;
// Check if page is already in the frame
for (int j = 0; j < frames; j++) {
if (page[j] == reference[i]) {
found = true;
break;
}
}
if (!found) {
// Page fault occurred
page_faults++;
front = (front + 1) % frames;
page[front] = reference[i];
}
printf("Page %d: ", reference[i]);
for (int j = 0; j < frames; j++) {
if (page[j] != -1) {
printf("%d ", page[j]);
}
}
printf("\n");
}
printf("Total Page Faults: %d\n", page_faults);
}
void LFU(int reference[], int length, int frames) {
int page[frames];
int frequency[frames];
int page_faults = 0;
bool found;
// Initialize page frames and frequencies
for (int i = 0; i < frames; i++) {
page[i] = -1;
frequency[i] = 0;
}
for (int i = 0; i < length; i++) {
found = false;
// Check if page is already in the frame
for (int j = 0; j < frames; j++) {
if (page[j] == reference[i]) {
found = true;
frequency[j]++;
break;
}
}
if (!found) {
// Page fault occurred
page_faults++;
// Find the least frequently used page
int min_freq = frequency[0];
int min_index = 0;
for (int j = 1; j < frames; j++) {
if (frequency[j] < min_freq) {
min_freq = frequency[j];
min_index = j;
}
}
page[min_index] = reference[i];
frequency[min_index] = 1;
}
printf("Page %d: ", reference[i]);
for (int j = 0; j < frames; j++) {
if (page[j] != -1) {
printf("%d ", page[j]);
}
}
printf("\n");
}
printf("Total Page Faults: %d\n", page_faults);
}
void LRU(int reference[], int length, int frames) {
int page[frames];
int last_used[frames];
int page_faults = 0;
bool found;
// Initialize page frames and last used timestamps
for (int i = 0; i < frames; i++) {
page[i] = -1;
last_used[i] = -1;
}
for (int i = 0; i < length; i++) {
found = false;
// Check if page is already in the frame
for (int j = 0; j < frames; j++) {
if (page[j] == reference[i]) {
found = true;
last_used[j] = i;
break;
}
}
if (!found) {
// Page fault occurred
page_faults++;
// Find the least recently used page
int min_last_used = last_used[0];
int min_index = 0;
for (int j = 1; j < frames; j++) {
if (last_used[j] < min_last_used) {
min_last_used = last_used[j];
min_index = j;
}
}
page[min_index] = reference[i];
last_used[min_index] = i;
}
printf("Page %d: ", reference[i]);
for (int j = 0; j < frames; j++) {
if (page[j] != -1) {
printf("%d ", page[j]);
}
}
printf("\n");
}
printf("Total Page Faults: %d\n", page_faults);
}
No comments:
Post a Comment