Page Replacement Algorithm:-
The page replacement is a mechanism that loads a page from disc to memory when a page of memory needs to be allocated. Page replacement can be described as follows:
- Find the location of the desired page on the disk.
- Find a free frame:
- If there is a free frame, use it.
- If there is no free frame, use a page-replacement algorithm to select a victim frame.
- Write the victim page to the disk; change the page and frame tables accordingly.
- Read the desired page into the (newly) free frame; change the page and frame tables.
- Restart the user process.
(Diagram of Page replacement)
Page Replacement Algorithms: The page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. We evaluate an algorithm by running it on a particular string of memory references and computing the number of page faults. The string of memory references is called a reference string.
The different page replacement algorithms are described as follows:
- First-In-First-Out (FIFO) Algorithm:
A FIFO replacement algorithm associates with each page the time when that page was brought into memory. When a page must be replaced, the oldest page is chosen to swap out. We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory, we insert it at the tail of the queue.
(FIFO page-replacement algorithm)
Note: For some page-replacement algorithms, the page fault rate may increase as the number of allocated frames increases. This most unexpected result is known as Belady’s anomaly.
- Optimal Page Replacement algorithm:-
One result of the discovery of Belady’s anomaly was the search for an optimal page replacement algorithm. An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms, and will never suffer from Belady’s anomaly. Such an algorithm does exist and has been called OPT or MIN.
It is simply “Replace the page that will not be used for the longest period of time”. Use of this page-replacement algorithm guarantees the lowest possible page fault rate for a fixed number of frames.
- LRU Page Replacement Algorithm:-
If we use the recent past as an approximation of the near future, then we will replace the page that has not been used for the longest period of time. This approach is the least-recently-used (LRU) algorithm.
LRU replacement associates with each page the time of that page’s last use. When a page must be replaced, LRU chooses that page that has not been used for the longest period of time.
(LRU page-replacement algorithm)
The major problem is how to implement LRU replacement. An LRU page-replacement algorithm may require substantial hardware assistance. The problem is to determine an order for the frames defined by the time of last use. Two implementations are feasible:
Counters: We associate with each page-table entry a time-of-use field, and add to the CPU a logical clock or counter. The clock is incremented for every memory reference. Whenever a reference to a page is made, the contents of the clock register are copied to the time-of-use field in the page-table entry for that page. We replace the page with the smallest time value. This scheme requires a search of the page table to find the LRU page and a write to memory (to the time-of-use field in the page table) for each memory access. The times must also be maintained when page tables are changed (due to CPU scheduling).
Stack: Another approach to implementing LRU replacement is to keep a stack of page numbers. Whenever a page is referenced, it is removed from the stack and put on the top. In this way, the top of the stack is always the most recently used page and the bottom is the LRU page. Because entries must be removed from the middle of the stack, it is best implemented by a doubly linked list, with a head and tail pointer. Each update is a little more expensive, but there is no search for a replacement; the tail pointer points to the bottom of the stack, which is the LRU page. This approach is particularly appropriate for software or microcode implementations of LRU replacement.
(Use of a stack to record the most recent page references)
- LRU Approximation Page Replacement Algorithm
In this algorithm, Reference bits are associated with each entry in the page table. Initially, all bits are cleared (to 0) by the operating system. As a user process executes, the bit associated with each page referenced is set (to 1) by the hardware. After some time, we can determine which pages have been used and which have not been used by examining the reference bits.
This algorithm can be classified into different categories as follows:
- Additional-Reference-Bits Algorithm: It can keep an 8-bit(1 byte) for each page in a page table in memory. At regular intervals, a timer interrupts transfers control to the operating system. The operating system shifts the reference bit for each page into the high-order bit of its 8-bit, shifting the other bits right over 1-bit position, discarding the low-order bit. These 8 bits shift registers contain the history of page use for the last eight time periods.
If we interpret these 8-bits as unsigned integers, the page with the lowest number is the LRU page, and it can be replaced.
- Second-Chance Algorithm: The basic algorithm of second-chance replacement is a FIFO replacement algorithm. When a page has been selected, we inspect its reference bit. If the value is 0, we proceed to replace this page. If the reference bit is set to 1, we give that page a second chance and move on to select the next FIFO page. When a page gets a second chance, its reference bit is cleared and its arrival time is reset to the current time. Thus, a page that is given a second chance will not be replaced until all other pages are replaced.
- Counting-Based Page Replacement:-We could keep a counter of the number of references that have been made to each page, and develop the following two schemes.
- LFU page replacement algorithm: The least frequently used (LFU) page-replacement algorithm requires that the page with the smallest count be replaced. The reason for this selection is that an actively used page should have a large reference count.
- MFU page-replacement algorithm: The most frequently used (MFU) page replacement algorithm is based on the argument that the page with the largest count is replaced.