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).
When a page fault occurs, the operating system has to choose a page to remove from memory to make room for the page that has to be brought in. The page replacement is done by swapping the required pages from backup storage to main memory and vice-versa. If the page to be removed has been modified while in memory, it must be rewritten to the disk to bring the disk copy up to date. If, however, the page has not been changed (e.g., it contains program text), the disk copy is already up to date, so no rewrite is needed. The page to be read in just overwrites the page being evicted. A page replacement algorithm is evaluated by running the particular algorithm on a string of memory references and compute the page faults.Referenced string is a sequence of pages being referenced. Page fault is not an error. Contrary to what their name might suggest, page faults are not errors and are common and necessary to increase the amount of memory available to programs in any operating system that utilizes virtual memory, including Microsoft Windows, Mac OS X, Linux and Unix.
Each operating system uses different page replacement algorithms. To select the particular algorithm, the algorithm with lowest page fault rate is considered.
1.First-In First-Out page replacement (FIFO)
2.Least recently used page replacement (LRU)
3.Optimal page replacement algorithm
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 : Consider page reference string 1, 3, 0, 3, 5, 6 with 3 page frames. Find number of page faults.
In the Least Recently Used (LRU) page replacement policy, the page that is used least recently will be replaced.
>> Example : Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 4 page frames.Find number of page faults.
In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.
>> Example : Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, with 4 page frame. Find number of page fault.
NOTE : Optimal page replacement is perfect, but not possible in practice as the operating system cannot know future requests. The use of Optimal Page replacement is to set up a benchmark so that other replacement algorithms can be analyzed against it.
Belady’s Anomaly is the phenomenon of increasing the number of page faults on increasing the number of frames in main memory.
LRU Page Replacement Algorithm and Optimal Page Replacement Algorithm are stack based algorithms. Hence, they do not suffer from Belady’s Anomaly.
>> Example : For Optimal Page Replacement Algorithm, Consider the reference string 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.
Case-1 : When frame size = 3
Number of page faults = 7
Case-2 : When frame size = 4
Number of page faults = 6
So, from this above example you understood that Optimal Page Replacement Algorithm doesn't suffer Belady's Anomaly Algorithm.
>> Example : For LRU Page Replacement Algorithm, Consider the reference string 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.
Case-1 : When frame size = 3
Number of page faults = 10
Case-2 : When frame size = 4
Number of page faults = 8
So, from this above example you understood that LRU Page Replacement Algorithm doesn't suffer Belady's Anomaly Algorithm.
>> Example : For FIFO Page Replacement Algorithm, Consider the reference string 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.
Case-1 : When frame size = 3
Number of page faults = 9
Case-2 : When frame size = 4
Number of page faults = 10
