PAGE REPLACEMENT EXAMPLES
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.
Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3-page frames. Find the number of
page faults using FIFO Page Replacement Algorithm.
FIFO – Page Replacement
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. 6 comes, it is also not available in
memory, so it replaces the oldest page slot i.e 3 —> 1 Page Fault. Finally, when 3 come it is not
available, so it replaces 0 1-page fault.
Least Recently Used
In this algorithm, page will be replaced which is least recently used.
Example Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frames.
Find number of page faults using LRU Page Replacement Algorithm.
Least Recently Used – Page Replacement
Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
0 is already there so —> 0 Page fault. when 3 came it will take the place of 7 because it is least
recently used —> 1 Page fault
0 is already in memory so —> 0 Page fault.
4 will takes place of 1 —> 1 Page Fault
Now for the further page reference string —> 0 Page fault because they are already available in the
memory.