Basic Page Replacement
Basic Page Replacement takes the following approach:-
If no frame is free, then we find one that is not currently being used and free it. We can free a frame by writing its content to swap space.
We modify the page fault service routine :-
i ) Find the location of desired page on the disk.
ii) Find a free frame.
a) If there is a free frame then use it.
b) If there is no free frame then use a page replacement algorithm to select a victim frame.
c) Write the victim frame to the disk.
iii) Read the desired page.
iv) Restart the process.
When no frames are free
This situation doubles the page fault service time. To reduce this we use the Modify bit or Dirty bit.
i) When this scheme is used, each page or frame has a modify bit associated with it in the hardware.
ii) Whenever any word or byte in the page has to be written into then the modify bit for a page is set by hardware. It indicates that the page has been modified.
iii) If bit is set - page has been modified since it has read in from the disk.
If bit is not set - Page has not been modified since it was read into memory.
iv) It is applicable to read only pages. Such pages cannot be modified.
v) It reduces the Input/Output (I/O) time by one half if the page has not been modified. For example :- If a user process 20 pages then we can execute 20 pages in 10 frames.
Page Replacement Algorithms
There are variety of Page replacement algorithms. Some of the most common and important Page Replacement Algorithms are :-
1) FIFO Page Replacement Algorithm
2) Second Chance Page Replacement Algorithm
3) Optimal Page Replacement Algorithm
4) Least Recently Used (LRU) Page Replacement Algorithm
5) LRU Approximation Page Replacement Algorithm
6) Counting Based Page Replacement Algorithm
1. FIFO Page Replacement Algorithm
It is the simplest page-replacement algorithm. As the name represents , when the page has to be replaced then the oldest page is chosen. The page is replaced at the Head of the queue and inserted at the Tail of the queue. The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm and it requires very little book-keeping on the part of the operating system.
Advantages of FIFO Page Replacement Algorithm:-
i) Easy to understand and execute.
Disadvantages of of FIFO Page Replacement Algorithm:-
i) It is not very effective.
ii) System needs to keep track of each frame
iii) Sometimes it behaves abnormally. This behaviour is called Belady’s anomaly.
iv) Bad replacement choice increases the page fault rate and slow process execution.
2. Second Chance Page Replacement Algorithm
It is the modified form of the FIFO page replacement algorithm. One way to implement is to have a circular queue. If the value is equal to 0, then we proceed to replace the page. But if the reference bit is equal to 1, then we give the page second chance. When the page get second chance, its reference bit is cleared. Second-chance Chance Page Replacement Algorithm gives every page a second-chance.
3. Optimal Page Replacement Algorithm
This algorithm has the lowest page fault. It has been called OPT or MIN. In this algorithm, replace the page that will not be used for the longest period of time. It involves future knowledge.
It is better than FIFO and it is twice as good as FIFO.
Advantages of Optimal Page Replacement Algorithm :-
i) Lowest page fault rate.
ii) Never suffers from Belady’s anomaly.
iii) Twice as good as FIFO Page Replacement Algorithm.
Disadvantages Optimal Page Replacement Algorithm :-
i) Difficult to implement.
ii) It needs forecast i.e. Future knowledge.
4. Least Recently Used (LRU) Page Replacement Algorithm
In this algorithm , the page that has not been used for the longest period of time has to be replaced.
Advantages of LRU Page Replacement Algorithm :-
i) It is amenable to full statistical analysis.
ii) Never suffers from Belady’s anomaly.
5. LRU Approximation Page Replacement Algorithm
This algorithm use the reference bit. Reference bit is associated with each entry in the page table. Initially bits are cleared to 0 by the operating system. User process executes, the bit associated is set to 1 by the hardware. After sometimes, we can determine which pages have been used and which have not been used by loamining the reference bit, although we don’t know the order.
6. Counting Based Page Replacement Algorithm
In this algorithm, we keep the counter of the number of reference that have been made to each page. In this 2 schemes are used :-
i) Least Frequency Used (LFU) Page Replacement Algorithm
It requires that the page with smallest count to be replaced.
ii) Most Frequency (MFU) Used Page Replacement Algorithm
It is based on the argument that the page with the smallest count was probably just brought in and has yet to be used.