### FIFO Page replacement algorithm

Prob. How many page faults will occur with a reference string 0,1,7,2,3,2,7,1,0,3?
There are four frames which are initially empty.
Use
1. FIFO Page replacement algorithm
Sol.

FIFO Page replacement algorithm:

FIFO stands for First in first out.
In FIFO Page replacement algorithm problem is, it may replace heavily used pages.

 0 1 7 2 3 2 7 1 0 3

Above table is an example of page frame, which is empty initially. And first page is 0.

So 0 will get added here, but there will be a page fault.

What is a page fault?
The page which is requested by the program is not present in the RAM, that means there is a page fault.

0 was not present in the page frame so there was a page fault.

 0 1 7 2 3 2 7 1 0 3 0 F

The next page is 1 and there is space for two more pages.So 0 will remain there and 1 will get added there.And again there will be a page fault.

 0 1 7 2 3 2 7 1 0 3 0 0 1 F F

The next page is 7, which is not in the page frame, but there is place for one more page, so 0 and 1 will remain there and 7 will get added. And there will be a page fault.

 0 1 7 2 3 2 7 1 0 3 0 0 0 1 1 7 F F F
The next page is 2, which is not in the page frame, but there is place for one more page, so 0, 1 and 7 will remain there and 2 will get added. And there will be a page fault.

 0 1 7 2 3 2 7 1 0 3 0 0 0 0 1 1 1 7 7 2 F F F F

I have given red color when there is a page fault, and black color for rest of the pages, and green color for page hits.

Now the page frame is full, and the next page is 3 which is not there in the page frame. So we need to remove one page from the page frame, so we can add 3 there.

Now see in the table below,

Page 0 came first than 1 than 7 than 2, so page 0 will get removed, and 3 will get added there. And there will be a page fault because 3 was not present in the page frame. And 1, 7, and 2 will remain there.

 0 1 7 2 3 2 7 1 0 3 0 0 0 0 3 1 1 1 1 7 7 7 2 2 F F F F F

The next page is 2, which is already present in the page frame. This is known as page hit.

What is page hit ?
The page which is requested by the program is already present in the RAM/page frame is known as page hit.

 0 1 7 2 3 2 7 1 0 3 0 0 0 0 3 3 1 1 1 1 1 7 7 7 7 2 2 2 F F F F F H

The next page is 7, which is already present in the page frame. This is known as page hit.

 0 1 7 2 3 2 7 1 0 3 0 0 0 0 3 3 3 1 1 1 1 1 1 7 7 7 7 7 2 2 2 2 F F F F F H H

The next page is 1, which is already present in the page frame. This is known as page hit.

 0 1 7 2 3 2 7 1 0 3 0 0 0 0 3 3 3 3 1 1 1 1 1 1 1 7 7 7 7 7 7 2 2 2 2 2 F F F F F H H H

The page frame is full, and the next page is 0 which is not there in the page frame. So we need to remove one page from the page frame, so we can add 0 there.

Now see in the table below,

Page 1 came first than 7 than 2 than 3, so page 1 will get removed, and 0 will get added there. And there will be a page fault because 0 was not present in the page frame. And 3, 7, and 2 will remain there.

The next page is 3, which is already present in the page frame. This is known as page hit.
Now see in the table below,

 0 1 7 2 3 2 7 1 0 3 0 0 0 0 3 3 3 3 3 3 1 1 1 1 1 1 1 0 0 7 7 7 7 7 7 7 7 2 2 2 2 2 2 2 F F F F F H H H F H

Total pages present in the pages = 10.
 0 1 7 2 3 2 7 1 0 3

Total page faults = 06.
 F F F F F F

Total page hits= 04
 H H H H