Answer: FIFO replaces the page that came in first, LRU replaces the page not used for the longest time, and Optimal replaces the page that will not be used for the longest time in future. For the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames they give 15, 12 and 9 page faults.
Logic
- FIFO: keep a pointer to the oldest frame; on a fault, replace that frame and move the pointer round-robin.
- LRU: store the time each frame was last used and update it on every hit and every load; on a fault, replace the frame with the smallest last-used time (empty frames have −1, so they are filled first).
- Optimal: on a fault, for each frame find when its page is next referenced; replace the one used farthest in the future (or never again).
Program (C)
#include <stdio.h>
#define MAX 50
int n, f, ref[MAX];
int findPage(int frame[], int page)
{
int j;
for (j = 0; j < f; j++)
if (frame[j] == page)
return j;
return -1;
}
int fifo()
{
int frame[MAX], i, j, next = 0, faults = 0;
for (j = 0; j < f; j++)
frame[j] = -1;
for (i = 0; i < n; i++) {
if (findPage(frame, ref[i]) == -1) {
frame[next] = ref[i]; /* replace the oldest page */
next = (next + 1) % f;
faults++;
}
}
return faults;
}
int lru()
{
int frame[MAX], lastUsed[MAX], i, j, pos, faults = 0;
for (j = 0; j < f; j++) {
frame[j] = -1;
lastUsed[j] = -1;
}
for (i = 0; i < n; i++) {
pos = findPage(frame, ref[i]);
if (pos == -1) {
pos = 0; /* empty frame, else least recently used */
for (j = 1; j < f; j++)
if (lastUsed[j] < lastUsed[pos])
pos = j;
frame[pos] = ref[i];
faults++;
}
lastUsed[pos] = i; /* update on every hit and every load */
}
return faults;
}
int optimal()
{
int frame[MAX], i, j, k, pos, farthest, nextUse, faults = 0;
for (j = 0; j < f; j++)
frame[j] = -1;
for (i = 0; i < n; i++) {
if (findPage(frame, ref[i]) != -1)
continue;
faults++;
pos = findPage(frame, -1); /* use an empty frame if any */
if (pos == -1) {
farthest = -1;
for (j = 0; j < f; j++) { /* page used farthest in future */
nextUse = n; /* n means never used again */
for (k = i + 1; k < n; k++)
if (ref[k] == frame[j]) {
nextUse = k;
break;
}
if (nextUse > farthest) {
farthest = nextUse;
pos = j;
}
}
}
frame[pos] = ref[i];
}
return faults;
}
int main()
{
int i;
printf("Enter number of pages in reference string: ");
scanf("%d", &n);
printf("Enter reference string: ");
for (i = 0; i < n; i++)
scanf("%d", &ref[i]);
printf("Enter number of frames: ");
scanf("%d", &f);
printf("\nFIFO page faults = %d\n", fifo());
printf("LRU page faults = %d\n", lru());
printf("Optimal page faults = %d\n", optimal());
return 0;
}Sample runs (gcc)
Enter number of pages in reference string: 20
Enter reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
Enter number of frames: 3
FIFO page faults = 15
LRU page faults = 12
Optimal page faults = 9
Enter number of pages in reference string: 12
Enter reference string: 1 2 3 4 1 2 5 1 2 3 4 5
Enter number of frames: 4
FIFO page faults = 10
LRU page faults = 8
Optimal page faults = 6Optimal always gives the fewest faults but needs future knowledge, so it is used only as a benchmark; LRU is the practical approximation.