Operating Systems Assignment No. 4:
Demand Paging
Set A
i. Write the simulation program to implement demand paging and show the page scheduling and total number of page faults for the following given page reference string. Give input n as the number of memory frames.
Reference String : 12,15,12,18,6,8,11,12,19,12,6,8,12,15,19,8
1) Implement FIFO
2) Implement LRU
Program For FIFO:-
#include<stdio.h>
#define MAX 20
int frames[MAX],ref[MAX],mem[MAX][MAX],faults,sp,m,n;
void accept()
{
int i;
printf("Enter no.of frames:");
scanf("%d", &n);
printf("Enter no.of references:");
scanf("%d", &m);
printf("Enter reference string:\n");
for(i=0;i<m;i++)
{
printf("[%d]=",i);
scanf("%d",&ref[i]);
}
}
void disp()
{
int i,j;
for(i=0;i<m;i++)
printf("%3d",ref[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(mem[i][j])
printf("%3d",mem[i][j]);
else
printf(" ");
}
printf("\n");
}
printf("Total Page Faults: %d\n",faults);
}
int search(int pno)
{
int i;
for(i=0;i<n;i++)
{
if(frames[i]==pno)
return i;
}
return -1;
}
void fifo()
{
int i,j;
for(i=0;i<m;i++)
{
if(search(ref[i])==-1)
{
frames[sp] = ref[i];
sp = (sp+1)%n;
faults++;
for(j=0;j<n;j++)
mem[j][i] = frames[j];
}
}
}
int main()
{
accept();
fifo();
disp();
return 0;
}
Program For LRU:-
#include<stdio.h>
#define MAX 20
int frames[MAX],ref[MAX],mem[MAX][MAX],faults,
sp,m,n,time[MAX];
void accept()
{
int i;
printf("Enter no.of frames:");
scanf("%d", &n);
printf("Enter no.of references:");
scanf("%d", &m);
printf("Enter reference string:\n");
for(i=0;i<m;i++)
{
printf("[%d]=",i);
scanf("%d",&ref[i]);
}
}
void disp()
{
int i,j;
for(i=0;i<m;i++)
printf("%3d",ref[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(mem[i][j])
printf("%3d",mem[i][j]);
else
printf(" ");
}
printf("\n");
}
printf("Total Page Faults: %d\n",faults);
}
int search(int pno)
{
int i;
for(i=0;i<n;i++)
{
if(frames[i]==pno)
return i;
}
return -1;
}
int get_lru()
{
int i,min_i,min=9999;
for(i=0;i<n;i++)
{
if(time[i]<min)
{
min = time[i];
min_i = i;
}
}
return min_i;
}
void lru()
{
int i,j,k;
for(i=0;i<m && sp<n;i++)
{
k=search(ref[i]);
if(k==-1)
{
frames[sp]=ref[i];
time[sp]=i;
faults++;
sp++;
for(j=0;j<n;j++)
mem[j][i]=frames[j];
}
else
time[k]=i;
}
for(;i<m;i++)
{
k = search(ref[i]);
if(k==-1)
{
sp = get_lru();
frames[sp] = ref[i];
time[sp] = i;
faults++;
for(j=0;j<n;j++)
mem[j][i] = frames[j];
}
else
time[k]=i;
}
}
int main()
{
accept();
lru();
disp();
return 0;
}
Set B:
I.Write the simulation program to implement demand paging and show the page scheduling and total number of page faults for the following given page reference string. Give input n as the number of memory frames.
Reference String : 12,15,12,18,6,8,11,12,19,12,6,8,12,15,19,8
1) Implement OPT
2) Implement MFU
Program for OPT:-
#include<stdio.h>
int main()
{
int no_of_frames, no_of_pages, frames[10], pages[30], temp[10], flag1, flag2, flag3, i, j, k, pos,
max, faults = 0;
printf("Enter number of frames: ");
scanf("%d", &no_of_frames);
printf("Enter number of pages: ");
scanf("%d", &no_of_pages);
printf("Enter page reference string: ");
for(i = 0; i < no_of_pages; ++i){
scanf("%d", &pages[i]);
}
for(i = 0; i < no_of_frames; ++i){
frames[i] = -1;
}
for(i = 0; i < no_of_pages; ++i){
flag1 = flag2 = 0;
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == pages[i]){
flag1 = flag2 = 1;
break;
}
}
if(flag1 == 0){
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == -1){
faults++;
frames[j] = pages[i];
flag2 = 1;
break;
}
}
}
if(flag2 == 0){
flag3 =0;
for(j = 0; j < no_of_frames; ++j){
temp[j] = -1;
for(k = i + 1; k < no_of_pages; ++k){
if(frames[j] == pages[k]){
temp[j] = k;
break;
}
}
}
for(j = 0; j < no_of_frames; ++j){
if(temp[j] == -1){
pos = j;
flag3 = 1;
break;
}
}
if(flag3 ==0){
max = temp[0];
pos = 0;
for(j = 1; j < no_of_frames; ++j){
if(temp[j] > max){
max = temp[j];
pos = j;
}
}
}
frames[pos] = pages[i];
faults++;
}
printf("\n");
for(j = 0; j < no_of_frames; ++j){
printf("%d\t", frames[j]);
}
}
printf("\n\nTotal Page Faults = %d", faults);
return 0;
}
Program For MFU:-
#include<stdio.h>
#define MAX 20
int frames[MAX],ref[MAX],mem[MAX][MAX],faults,
sp,m,n,count[MAX];
void accept()
{
int i;
printf("Enter no.of frames:");
scanf("%d", &n);
printf("Enter no.of references:");
scanf("%d", &m);
printf("Enter reference string:\n");
for(i=0;i<m;i++)
{
printf("[%d]=",i);
scanf("%d",&ref[i]);
}
}
void disp()
{
int i,j;
for(i=0;i<m;i++)
printf("%3d",ref[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(mem[i][j])
printf("%3d",mem[i][j]);
else
printf(" ");
}
printf("\n");
}
printf("Total Page Faults: %d\n",faults);
}
int search(int pno)
{
int i;
for(i=0;i<n;i++)
{
if(frames[i]==pno)
return i;
}
return -1;
}
int get_mfu(int sp)
{
int i,max_i,max=-9999;
i=sp;
do
{
if(count[i]>max)
{
max = count[i];
max_i = i;
}
i=(i+1)%n;
}while(i!=sp);
return max_i;
}
void mfu()
{
int i,j,k;
for(i=0;i<m && sp<n;i++)
{
k=search(ref[i]);
if(k==-1)
{
frames[sp]=ref[i];
count[sp]++;
faults++;
sp++;
for(j=0;j<n;j++)
mem[j][i]=frames[j];
}
else
count[k]++;
}
sp=0;
for(;i<m;i++)
{
k = search(ref[i]);
if(k==-1)
{
sp = get_mfu(sp);
frames[sp] = ref[i];
count[sp]=1;
faults++;
sp = (sp+1)%n;
for(j=0;j<n;j++)
mem[j][i] = frames[j];
}
else
count[k]++;
}
}
int main()
{
accept();
mfu();
disp();
return 0;
}
Set C:
I. Write the simulation program to implement demand paging and show the page scheduling and total number of page faults for the following given page reference string. Give input n as the number of memory frames.
Reference String: 2,5,2,8,5,4,1,2,3,2,6,1,2,5,9,8
1) Implement MRU
2) Implement Second Chance Page Replacement.
3) Least Frequently Used
#include <stdio.h>
#define MAX 100
int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3,
0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
int totalPages = 20;
/* ------------------------------------------------
Display Frames
------------------------------------------------ */
void displayFrames(int frames[], int n)
{
int i;
printf("[ ");
for (i = 0; i < n; i++)
{
if (frames[i] == -1)
printf("- ");
else
printf("%d ", frames[i]);
}
printf("]");
}
/* ------------------------------------------------
FIFO Page Replacement
------------------------------------------------ */
int FIFO(int n)
{
int frames[MAX];
int i, j, pointer = 0;
int pageFaults = 0;
int found;
for (i = 0; i < n; i++)
frames[i] = -1;
printf("\n\n========== FIFO ==========\n");
printf("Page\tFrames\t\tStatus\n");
for (i = 0; i < totalPages; i++)
{
found = 0;
for (j = 0; j < n; j++)
{
if (frames[j] == pages[i])
{
found = 1;
break;
}
}
if (!found)
{
frames[pointer] = pages[i];
pointer = (pointer + 1) % n;
pageFaults++;
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tPage Fault\n");
}
else
{
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tHit\n");
}
}
printf("Total FIFO Page Faults = %d\n", pageFaults);
return pageFaults;
}
/* ------------------------------------------------
LRU Page Replacement
------------------------------------------------ */
int LRU(int n)
{
int frames[MAX];
int recent[MAX];
int i, j;
int pageFaults = 0;
int found, pos, lruIndex;
for (i = 0; i < n; i++)
{
frames[i] = -1;
recent[i] = -1;
}
printf("\n\n========== LRU ==========\n");
printf("Page\tFrames\t\tStatus\n");
for (i = 0; i < totalPages; i++)
{
found = 0;
for (j = 0; j < n; j++)
{
if (frames[j] == pages[i])
{
found = 1;
pos = j;
break;
}
}
if (found)
{
/* Update recent usage */
recent[pos] = i;
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tHit\n");
}
else
{
pageFaults++;
/* Empty frame available */
pos = -1;
for (j = 0; j < n; j++)
{
if (frames[j] == -1)
{
pos = j;
break;
}
}
/* Find least recently used page */
if (pos == -1)
{
lruIndex = 0;
for (j = 1; j < n; j++)
{
if (recent[j] < recent[lruIndex])
lruIndex = j;
}
pos = lruIndex;
}
frames[pos] = pages[i];
recent[pos] = i;
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tPage Fault\n");
}
}
printf("Total LRU Page Faults = %d\n", pageFaults);
return pageFaults;
}
/* ------------------------------------------------
MFU Page Replacement
------------------------------------------------ */
int MFU(int n)
{
int frames[MAX];
int frequency[MAX];
int lastUsed[MAX];
int i, j;
int pageFaults = 0;
int found, pos;
int mfuIndex;
for (i = 0; i < n; i++)
{
frames[i] = -1;
frequency[i] = 0;
lastUsed[i] = -1;
}
printf("\n\n========== MFU ==========\n");
printf("Page\tFrames\t\tStatus\n");
for (i = 0; i < totalPages; i++)
{
found = 0;
/* Check whether page is already present */
for (j = 0; j < n; j++)
{
if (frames[j] == pages[i])
{
found = 1;
frequency[j]++;
lastUsed[j] = i;
break;
}
}
if (found)
{
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tHit\n");
}
else
{
pageFaults++;
/* Find empty frame */
pos = -1;
for (j = 0; j < n; j++)
{
if (frames[j] == -1)
{
pos = j;
break;
}
}
/* If no empty frame, find MFU page */
if (pos == -1)
{
mfuIndex = 0;
for (j = 1; j < n; j++)
{
if (frequency[j] > frequency[mfuIndex])
{
mfuIndex = j;
}
else if (frequency[j] == frequency[mfuIndex] &&
lastUsed[j] < lastUsed[mfuIndex])
{
/*
* If frequencies are equal,
* replace the least recently used one.
*/
mfuIndex = j;
}
}
pos = mfuIndex;
}
frames[pos] = pages[i];
frequency[pos] = 1;
lastUsed[pos] = i;
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tPage Fault\n");
}
}
printf("Total MFU Page Faults = %d\n", pageFaults);
return pageFaults;
}
/* ------------------------------------------------
OPTIMAL Page Replacement
------------------------------------------------ */
int OPT(int n)
{
int frames[MAX];
int i, j, k;
int pageFaults = 0;
int found, pos;
int farthest, nextUse;
int replaceIndex;
for (i = 0; i < n; i++)
frames[i] = -1;
printf("\n\n========== OPTIMAL ==========\n");
printf("Page\tFrames\t\tStatus\n");
for (i = 0; i < totalPages; i++)
{
found = 0;
/* Check if page is already in memory */
for (j = 0; j < n; j++)
{
if (frames[j] == pages[i])
{
found = 1;
break;
}
}
if (found)
{
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tHit\n");
continue;
}
pageFaults++;
/* Find empty frame */
pos = -1;
for (j = 0; j < n; j++)
{
if (frames[j] == -1)
{
pos = j;
break;
}
}
/* If memory is full */
if (pos == -1)
{
farthest = -1;
replaceIndex = -1;
for (j = 0; j < n; j++)
{
nextUse = -1;
/* Search for next occurrence */
for (k = i + 1; k < totalPages; k++)
{
if (frames[j] == pages[k])
{
nextUse = k;
break;
}
}
/*
* If page will never be used again,
* replace it immediately.
*/
if (nextUse == -1)
{
replaceIndex = j;
break;
}
/* Select page used farthest in future */
if (nextUse > farthest)
{
farthest = nextUse;
replaceIndex = j;
}
}
pos = replaceIndex;
}
frames[pos] = pages[i];
printf("%d\t", pages[i]);
displayFrames(frames, n);
printf("\tPage Fault\n");
}
printf("Total OPT Page Faults = %d\n", pageFaults);
return pageFaults;
}
/* ------------------------------------------------
Main Function
------------------------------------------------ */
int main()
{
int n;
int fifoFaults, lruFaults, mfuFaults, optFaults;
int minimum;
printf("============================================\n");
printf(" PAGE REPLACEMENT ALGORITHM SIMULATION\n");
printf("============================================\n");
printf("\nReference String:\n");
for (int i = 0; i < totalPages; i++)
{
printf("%d", pages[i]);
if (i < totalPages - 1)
printf(", ");
}
printf("\n\nEnter number of memory frames: ");
scanf("%d", &n);
if (n <= 0 || n > MAX)
{
printf("Invalid number of frames!\n");
return 1;
}
/* Run all algorithms */
fifoFaults = FIFO(n);
lruFaults = LRU(n);
mfuFaults = MFU(n);
optFaults = OPT(n);
/* Comparative Analysis */
printf("\n\n============================================\n");
printf(" COMPARATIVE ANALYSIS\n");
printf("============================================\n");
printf("\nAlgorithm\tPage Faults\n");
printf("--------------------------------------------\n");
printf("FIFO\t\t%d\n", fifoFaults);
printf("LRU\t\t%d\n", lruFaults);
printf("MFU\t\t%d\n", mfuFaults);
printf("OPT\t\t%d\n", optFaults);
minimum = fifoFaults;
if (lruFaults < minimum)
minimum = lruFaults;
if (mfuFaults < minimum)
minimum = mfuFaults;
if (optFaults < minimum)
minimum = optFaults;
printf("\nMinimum Page Faults = %d\n", minimum);
printf("Best Performing Algorithm(s): ");
if (fifoFaults == minimum)
printf("FIFO ");
if (lruFaults == minimum)
printf("LRU ");
if (mfuFaults == minimum)
printf("MFU ");
if (optFaults == minimum)
printf("OPT ");
printf("\n");
return 0;
}
No comments:
Post a Comment