Menu
I'm trying to understand the FIFO page replacement algorithm, but all the information I can find amounts to what's below. Can you explain how you use a reference string to evaluate a page replacement algorithm, using the particular example of FIFO?
When a page must be replaced, the oldest page is chosen.
In all our examples, the reference string is
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 frame (9 page faults) 4 frame (10 page faults)
908
First In First Out (FIFO): This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the 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.
The page replacement algorithm decides which memory page is to be replaced. The process of replacement is sometimes called swap out or write to disk. Page replacement is done when the requested page is not found in the main memory (page fault).
FIFO is an abbreviation for first in, first out. It is a method for handling data structures where the first element is processed first and the newest element is processed last.
Case-2: If the system has 4 frames, the given reference string using the FIFO page replacement algorithm yields a total of 10 page faults.
A page fault is when a page is not present in a frame of memory so a trap has to be sent to the OS and the page has to be added to a frame. If there is no room then something needs to be removed. FIFO is one method to determine what page will get removed.
The concept is that whatever page got added first to the frame will get removed first. This is what FIFO stands for. Using your first example. I will go down the reference string list and show you what the memory will look like.
1: 1 +1 fault
2: 1,2 +1 fault
3: 1,2,3 +1 fault
4: 2,3,4 +1 fault - 1 gets removed because it was the first added
1: 3,4,1 +1 fault - 2 gets removed because it was the first on the list
2: 4,1,2 +1 fault - 3 got removed..
5: 1,2,5 +1 fault - 4 got removed..
1: 1,2,5 No change - 1 is already present so no page fault was required
2: 1,2,5 No change - 2 is already present in the frame
3: 2,5,3 +1 fault - 1 was removed because it is first
4: 5,3,4 +1 fault - Now 2 got removed
5: 5,3,4 No change - No change because 5 is present in one of the frames.
This gives the total of 9 faults.
You can also think of it as the oldest page gets removed.
Hopefully I made no mistakes :D
198
------------ * FIRST IN FIRST OUT * -------------
Page no. 1 | 1 +1
Page no. 2 | 1 2 +1
Page no. 3 | 1 2 3 +1
Page no. 4 | 1 2 3 4 +1
Page no. 1 |
Page no. 2 |
Page no. 5 | 2 3 4 5 +1
Page no. 1 | 3 4 5 1 +1
Page no. 2 | 4 5 1 2 +1
Page no. 3 | 5 1 2 3 +1
Page no. 4 | 1 2 3 4 +1
Page no. 5 | 2 3 4 5 +1
Page Faults = 10
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
