|
Ex. No. :9(iii)
|
MEMORY MANAGEMENT SCHEME II
- LRU
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
LRU:
“Replace the page that had not been
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 sting is brought into the memory. The operating
system keeps track of all pages in the memory, thereby keeping track of the
page that had not been used for longer sequence of time. If the page in the
page reference string is not in memory, the page fault is incremented and the
page that had not been 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 next page. 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 pages are referred and calculate the page fault for all those pages
in the page references string for the number of available frames.
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: Read the reference
string character by character.
Step5: Compare the character
with the frames. If the character is already present move to the next page
number. If not replace the frame that has not be used for the longer time.
Step6: Display the frames
Step7: Display the page fault
Step7: Terminate the program
Program
#include<stdio.h>
#include<ctype.h>
#include<conio.h>
int find(char [], int
[],int,int);
void main()
{
int
frame[10],fn,i=0,j,k=0,flag,page,fault=0,m,len;
char refstr[25],pr[5][20];
clrscr();
printf("\tLRU page replacement
algorithm\n");
printf("\t--------------------------------\n");
printf("\t Total No.of
frames:");
scanf("%d",&fn);
printf("\n\treference string:");
scanf("%s",refstr);
len=strlen(refstr);
for(j=0;j<fn;j++)
{
frame[j]=-1;
for(m=0;m<len;m++)
pr[j][m]=' ';
}
do
{
flag=0;
for(j=0;j<fn;j++)
if(frame[j]==refstr[i])
{
flag=1;
break;
}
if(flag == 1)
i++;
else
{
if(i>fn-1)
{
page=find(refstr,frame,fn,i-1);
for(j=0;j<fn;j++)
if(frame[j] == page)
{
frame[j]=refstr[i++];
fault++;
}
}
else
{
frame[k++]=refstr[i++];
fault++;
}
for(j=0;j<fn;j++)
pr[j][i-1]=frame[j];
}
}while(refstr[i] != '\0');
printf("\n\t\tpage faults for the
given reference string are\n");
printf("\t---------------------------------------------\n\n");
for(i=0;i<len;i++)
printf(" %c ",refstr[i]);
printf("\n\nThe allotted frames
are\n");
printf("----------------------------\n");
printf("\n");
for(j=0;j<fn;j++)
{
for(m=0;m<len;m++)
printf(" %c
",pr[j][m]);
printf("\n\n");
}
printf("No.of page
faults:%d\n",fault);
getch();
}
int find(char refstr[],int frame[],int
fn,int index)
{
int temp[10],i,j,c=0;
for(i=0;i<fn;i++)
temp[i]=frame[i];
for(;;)
{
for(i=0;i<fn;i++)
if(refstr[index] == temp[i])
{
temp[i]=-1;
c++;
}
index--;
if(index == 0 || c == fn)
break;
}
if(index == 0)
return refstr[index];
else
return
refstr[index+1];
}
OUTPUT
[anandh@localhost ~]$ ./a.out
LRU page replacement algorithm
-----------------------------------------
Total No.of
frames:3
reference
string:125624512412
page faults for the given reference string are
-------------------------------------------------------
1 2 5
6 2 4
5 1 2
4 1 2
The allotted frames are
----------------------------
1 1 1
6 6 5
5 5 4
2
2 2 2
2 1 1
1
5
5 4 4
4 2 2
No.of page faults:9
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