FIFO PAGE REPLACEMENT
In this "FIFO PAGE REPLACEMENT ALGORITHM" covers FIFO page replacement technique with example and FIFO page replacement Program with Input-Output.
In Memory Management, Paging is a technique by which a computer can store and retrieve data from secondary storage for use in main memory. To do page replacement there are some page replacement algorithms.
Page replacement algorithms are able to decide which page needed to be replaced when new page comes in. Whenever a new page is referred and not present in memory, page fault occurs and Operating System replaces one of the existing pages with newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorithms is to reduce number of page faults.
First In First Out (FIFO) Page Replacement Algorithm –
In this simplest page replacement algorithm, operating system keeps track of all pages in the memory in a queue, oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
In FCFS scheduling, Where which process comes first can execute first. Similar to this, FIFO page replacement select the first page for removal when new page is entered.
A process can be divided into several pages, when CPU requires a page that is not in the Main Memory, Some page replacement algorithms is used to load that page in Main Memory. During checking, Weather the page is found or not, it is generally described as,
Page Hit – If CPU tries to retrieve the needed page from main memory, and that page is existed in the main memory (RAM), then it is known as “PAGE HIT”. Otherwise, If not exist in main memory, then it is known as "PAGE FAULT or PAGE MISS".
If any page fault occurs then new page must be loaded from Secondary storage to Main Memory.
ALGORITHM:
1- Start traversing the pages.
i) If set holds less pages than capacity.
a) Insert page into the set one by one until the size of set reaches capacity or all page requests are processed.
b) Simultaneously maintain the pages in the queue to perform FIFO.
c) Increment page fault
ii) Else
If current page is present in set, do nothing.
Else
a) Remove the first page from the queue as it was the first to be entered in the memory
b) Replace the first page in the queue with the current page in the string.
c) Store current page in the queue.
d) Increment page faults.
2. Return page faults.
Example -1. Consider page reference string 1, 3, 0, 3, 5, 6 and 3 page slots.
Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3
Page Faults.
when 3 comes, it is already in memory so —> 0 Page Faults.
Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e 1. —>1
Page Fault.
Finally 6 comes, it is also not available in memory so it replaces the oldest page slot
i.e 3 —>1 Page Fault.
So total page faults = 5.
Example -2. Consider the following reference string: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1 with 4
frames.
Using FIFO page replacement algorithm –
So, total number of page faults = 9.
Given memory capacity (as number of pages it can hold)
C PROGRAM:
#include<stdio.h>
int main()
{
int i,j,n,a[50],frame[10],no,k,avail,count=0;
printf("\n ENTER THE NUMBER OF PAGES: ");
scanf("%d",&n);
printf("\n ENTER THE PAGE NUMBERS: ");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("\n ENTER THE NUMBER OF FRAMES :");
scanf("%d",&no);
for(i=0;i<no;i++)
frame[i]= -1;
j=0;
printf("ref string\t page frames\n");
for(i=1;i<=n;i++)
{
printf("%d\t",a[i]);
avail=0;
for(k=0;k<no;k++)
if(frame[k]==a[i])
avail=1;
if (avail==0)
{
frame[j]=a[i];
j=(j+1)%no;
count++;
for(k=0;k<no;k++)
printf("%d ",frame[k]);
}
printf("\n");
}
printf("Total Page Fault is: %d",count);
return 0;
}INPUT-OUTPUT:
ENTER THE NUMBER OF PAGES: 12
ENTER THE PAGE NUMBERS:0 2 1 6 4 0 1 0 3 1 2 1
ENTER THE NUMBER OF FRAMES :4
Ref string page frames
0 0 -1 -1 -1
2 0 2 -1 -1
1 0 2 1 -1
6 0 2 1 6
4 4 2 1 6
0 4 0 1 6
1
0
3 4 0 3 6
1 4 0 3 1
2 2 0 3 1
1
Total Page Fault is: 9
Here, -1 represents empty page frames. You can see blanks here whenever there are no page fault occurs, or no new page replaced with the new. At the end, the Total page fault is 9. In order to count no of times new page enters in the queue.
YOU MIGHT LIKE :
Comments
Post a Comment