FIFO Page Replacement
Goal:- Program for FIFO page replacement Method.
Method:- First in First out (Queue)
Explanation:- This is the simplest page replacement algorithm.In a page replacement algorithm we decide when a page replacement occures then which frames are to be replaced.
For evaluating an algorithm we take a particular string of memory references ,called reference string.
In FIFO page replacement algorithm- for each page we track the time when it was brought into the memory and when any replacement request comes then oldest page is chosen.
If we choose a queue to hold all pages in memory then its more easy to understand and implement rather than tracking time of all pages.
If we are using a queue in our implementation then :
1.Replacement of any page takes place at the head of the queue and
2.Insertion of pages takes place at the tail of the queue.
FIFO is easy to understand but there is no practical use of this algorithm in now-a-days because performance of FIFO is not always good.
Page Fault:- Page Fault is a interrput that occurs when a program request page that is not in real memory.Then this interrput sends signal to OS to fetch that page from Virtual memory and load it into RAM.
**Program explained here counts the no. of page fault occurs when a input reference string is implemented onto Memory according to FIFO replacement method.
Example:-
Reference string- 7,0,1,2,0,3,0,4
No. of frames: 3
Frame NO. | Reference String(Page Values) |
Initially | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 |
1 | -1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 |
2 | -1 | -1 | 0 | 0 | 0 | 0 | 3 | 3 | 3 |
3 | -1 | -1 | -1 | 1 | 1 | 1 | 1 | 0 | 0 |
When any page value already presented in frames then no page fault will occur.
Number of Page Fault occured with above string is 7 and shown in table and colored red.
Program:-
#include<stdio.h>
#include<conio.h>
int main()
{
int a[10],count=0,i,j,k,n,m;
printf("\n\tEnter No. of Pages:\n");
printf("\t");
scanf("%d",&n);
printf("\n\tEnter values of Reference String :\n");
for(i=0;i<n;i++)
{
printf("\t");
scanf("%d",&a[i]);
}
printf("\n\tEnter no. of frames:\n");
{
printf("\t");
scanf("%d",&m);
}
int count1[m];
for(i=0;i<m;i++)
count1[i]=-1;
printf("\n Displaying Distribution-----------\n");
for(i=0;i<n;i++)
{
k=0;
for(j=0;j<m;j++)
{
if(a[i]==count1[j])
{
k++;
count--;
}
}
count++;
if(count<=m && k==0)
{
count1[i]=a[i];
}
else if(k==0)
{
count1[(count-1)%m]=a[i];
}
printf("\n\t********************************\n");
for(j=0;j<m;j++)
{
printf("\t");
printf("(%d)\t",count1[j]);
}
}
printf("\n\n\tTotal Page Faults %d",count);
getch();
return 0;
}
Output:-
If you want to share more information about topic discussed above or find anything incorrect Please do comments.
0 comments:
Post a Comment