|
Ex. No. :9(ii)
|
MEMORY MANAGEMENT SCHEME II
-
OPTIMAL PAGE REPLACEMENT
ALGORITHMS
|
AIM:
To write a program in C to implement
page replacement algorithm FIFO
PROBLEM DESCRIPTION:
Page replacement algorithms are used
to decide what pages to page out when a page needs to be allocated. This
happens when a page fault occurs and free page cannot be used to satisfy
allocation
OPTIMAL:
“Replace the page, which will not be
used for a longer sequence of time”. The frames are empty in the beginning
and initially no page fault occurs so it is set to zero. When a page fault
occurs the page reference string is brought into the memory. The operating
system keeps track of all the pages in memory, thereby keeping track of most
recently arrived and page there will not be used for a longer sequence of time
is replaced. If the page in the page reference string is not in memory, the
page fault is incremented and the one that will not be used for a longer
sequence of time is replaced. If the page in the page reference string is in
the memory, take the next page without calculating the page fault. Take the
next page in the page reference string and check if the page is already present
in the memory or not. Repeat the process until all the pages are referred and
calculate page fault for all those pages in the page reference string for the
number of available frames.
Algorithm
Algorithm
Step1: Start the program
Step2: Declare the required
variables and initialize it.
Step3; Get the frame size and
reference string from the user
Step4: Keep track of entered data elements
Step5:Accommodate a new
element look for the element that is not likely to be used in future replace.
Step6: Count the number of
page fault and display the value
Step7: Terminate the program
Program: //Program for optimal page
replacement algorithm
#include<stdio.h>
int frames[10] =
{-1,-1,-1,-1,-1,-1,-1,-1,-1};
int
nf,pf=0,pageno[50],np=0,location[10];
int search(int i);
void replace(int i);
void print(int i);
int main()
{
int i=0;
printf("Optimal
Page Replacement Algorithm :\n");
printf("-----------------------------------\n\n");
printf("Enter
the number of frames : ");
scanf("%d",&nf);
printf("Enter
the page numbers one by one.");
printf("Enter
-1 when finished : \n");
do
{
scanf("%d",&pageno[i]);
np++;
i++;
}
while(pageno[i-1] != -1);
i=0;np--;
printf("\nInput Frame Status\n");
printf("------------------------\n");
while(pageno[i] != -1)
{
if(!search(i))
{
replace(i);
pf++;
print(i);
}
else
{
print(i);
}
i++;
}
printf("\n\nPage faults : %d",pf);
}
int search(int i)
{
int j;
for(j=0;j<nf;j++)
{
if(frames[j] == pageno[i])
return 1;
}
return 0;
}
void replace(int i)
{
int j,k,max;
for(j=0;j<nf;j++)
{
if(frames[j] ==
-1)
{
frames[j] =
pageno[i];
return 0;
}
}
for(j=0;j<nf;j++)
{
for(k=i+1;k<np;k++)
{
location[j] =
np+1;
if(pageno[k] ==
frames[j])
{
location[j] =
k;
break;
}
}
}
max = 0;
for(j=0;j<nf;j++)
{
if(location[j]
> location[max])
max = j;
}
frames[max] =
pageno[i];
}
void print(int i)
{
int j;
printf("\n %d
- ",pageno[i]);
for(j=0;j<nf;j++)
printf("
%2d",frames[j]);
}
"opt.c" 97L, 1499C written
[anandh@localhost ~]$ cc opt.c
[anandh@localhost ~]$
./a.out
Optimal Page Replacement Algoritm :
-----------------------------------
Enter the number of frames : 3
Enter the page numbers one by one.Enter -1 when finished :
1
2
5
6
2
4
5
1
2
4
1
2
-1
Input Frame
Status
------------------------
1 -
1 -1 -1
2 -
1 2 -1
5 -
1 2 5
6 - 6 2 5
2 -
6 2 5
4 -
4 2 5
5 -
4 2 5
1 -
4 2 1
2 -
4 2 1
4 -
4 2 1
1 -
4 2 1
2 -
4 2 1
Page faults : 6
RESULT:
Thus the C programs to implement the Page Replacement
algorithms namely FIFO algorithms were written and executed. The obtained
outputs were verified.
No comments:
Post a Comment