Optimal Page Replacement Algorithm
- Initialize an array to keep track of when each page in memory will be referenced next (called the "future reference array" ).
- When a page fault occurs, check if there is an empty page frame. If yes, load the page into the empty frame and update the future reference array.
- If all page frames are occupied, select the page that will be referenced furthest in the future (according to the future reference array) for replacement.
- Repeat steps 2 & 3 until all page references are processed.
Example 1:
Input: Number of frames (fn) = 3
Reference String: {1, 2, 5, 4, 1, 2, 5, 1, 2, 3}
There are two memory page frames available in this updated illustration. Let's examine the result. The goal is to tally the hits (pages stored in memory) and misses (pages absent in memory).
Example 2:
Input: Number of frames (fn) = 4
The reference string consists of the following sequence: {5, 3, 2, 1, 4, 5, 2, 4, 5, 3, 1, 4}.
There are three page frames available in memory in this altered illustration, and the identical reference string pattern is employed. Let's examine the outcomes. The objective is to tally the occurrences of hits (pages present in memory) and misses (pages absent in memory).
Explanation:
In both examples, we have modified the number of page frames available in memory and the reference string. The Optimal Page Replacement Algorithm works as described earlier:
- If the referred page is already present in memory (a hit) , increment the hit count.
- If the referred page is not present in memory (a miss ), the algorithm decides which page to replace. Load the page into an empty frame in memory if one exists. If there are no empty frames, the algorithm replaces the page that will never be referred to again (if such a page exists). If no page is ever referenced in the future, the algorithm selects the page that is referenced farthest in the future for replacement.
- Load the page into an empty frame in memory if one exists.
- If there are no empty frames, the algorithm replaces the page that will never be referred to again (if such a page exists).
- If no page is ever referenced in the future, the algorithm selects the page that is referenced farthest in the future for replacement.
In these instances, the algorithm can be executed with the designated quantity of page frames and the provided reference string. The results will display the count of hits and misses, enabling you to assess the algorithm's effectiveness in reducing page faults for the provided reference string and memory capacity. The objective is to decrease misses and increase hits to enhance the efficacy of memory administration. The precise tallies will vary based on the particular reference string and memory size implemented in the simulation.
Example Code in C:
Here is a simple C program demonstrating the functionality of the Optimal Page Replacement algorithm in C:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define NUM_FRAMES 3
#define NUM_PAGES 10
// Function to find the page that will be referenced furthest in the future
int findOptimalPage(int page[], int pageFrames[], int index, int numFrames) {
int farthest = -1;
int farthestIndex = -1;
for (int i = 0; i < numFrames; i++) {
int j;
for (j = index; j < NUM_PAGES; j++) {
if (pageFrames[i] == page[j]) {
if (j > farthest) {
farthest = j;
farthestIndex = i;
}
break;
}
}
if (j == NUM_PAGES) {
return i;
}
}
if (farthestIndex == -1) {
return 0;
}
return farthestIndex;
}
int main() {
int pageReferences[NUM_PAGES] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3};
int pageFrames[NUM_FRAMES];
bool isPageInFrame[NUM_FRAMES];
int pageFaults = 0;
for (int i = 0; i < NUM_FRAMES; i++) {
pageFrames[i] = -1;
isPageInFrame[i] = false;
}
printf("Page Reference String: ");
for (int i = 0; i < NUM_PAGES; i++) {
printf("%d ", pageReferences[i]);
}
printf("\n");
for (int i = 0; i < NUM_PAGES; i++) {
int page = pageReferences[i];
if (!isPageInFrame[page]) {
int pageToReplace = findOptimalPage(pageReferences, pageFrames, i + 1, NUM_FRAMES);
pageFrames[pageToReplace] = page;
isPageInFrame[pageToReplace] = true;
pageFaults++;
printf("Page %d loaded into frame %d\n", page, pageToReplace);
}
}
printf("Total Page Faults: %d\n", pageFaults);
return 0;
}
Output:
Running the above code with the given page reference string will produce the following.
Page Reference String: 7 0 1 2 0 3 0 4 2 3
Page 7 loaded into frame 0
Page 0 loaded into frame 1
Page 1 loaded into frame 2
Page 2 loaded into frame 0
Page 3 loaded into frame 1
Page 4 loaded into frame 0
Total Page Faults: 6
This output shows the sequence of page faults and the pages loaded into frames at each step using the Optimal Page Replacement Algorithm for the given page reference string.