Deitel et al. (2004) states that in a virtual memory system with paging, all of the page frames might be occupied when a process references a nonresident page. In this situation, the system does not only bring in a new memory page from the secondary page, it also must first decide which page in main memory that should be replaced, that is either the page in main memory will be removed or overwritten to make room for the incoming page. The decision making can be overcome by using the page-replacement algorithm. There are few strategies of page-replacement; the main purpose of page-replacement is to reduce the number of page faults a process experiences as it runs from the beginning to the end, and hopefully decrease the process's execution time.
The optimal page replacement or OPT is one of the page-replacement strategies. It works when a page requires to be exchanged in or the system needs a new memory page, the operating system or (OS) exchange out the page which will be referenced farthest in the future. For example, a page that will not be referenced in the next 5 seconds will be exchanged out over a page that is going to be referenced within 0.3 seconds. However, this strategy could be implemented because the OS could not calculate how long before a page is going to be referenced next. In spite of that, if a program is running on a simulator and keeping an eye on all page references, it will be possible to implement OPT on the second run by using the page reference data that was compiled during the first run. By doing this, the OS can use the data compiled during first run and will be able to decide which pages that needs to be swapped in or out. This means that only programs that have memory reference pattern which is consistent for every runs.
Another page-replacement strategy is the Random page-replacement or RAND. This strategy is easy to implement and it has lower overhead. An overhead are bit sequences or series in one data transmission other than the actual end user data. In this strategy, any page in the main memory can be a candidate for replacement of a new incoming page. However, RAND has a disadvantage of accidentally replacing a page that will be reference to the next page, which is nevertheless, the worse page to be replaced. In spite of this, the benefit of using this strategy is that it makes the OS to decide quicker and fairer on selecting which page to replace for the new incoming page.
Next, in the First in First Out page-replacement or FIFO strategy, the OS will replace the page that has been in the system the longest. In this strategy, the system keeps an eye on the order in which pages that enters the main memory. This strategy is appealing because it is reasonable, that is, the page which is in the system the longest has had its chance and it will be the time to give a new page a chance. However, the FIFO page replacement strategy can replace a heavily used page. An example of this is that on large timesharing systems, it is normal for several users to share a program to edit or correct programs. The FIFO page replacement strategy in this kind of system, it might decide to replace a heavily used program. It is a bad choice, because the page would have to be recalled to main memory instantly, which results an increased rate of page fault.
Deitel et al. (2004) have stated that the FIFO page replacement strategy's problem of replacing heavily used page that is in the system for a long time can be avoided by implementing FIFO with a referenced bit for each page and replacing a page only if its referenced bit is set to zero or 0. This modified FIFO page replacement is known as Second-Chance. This second-chance of FIFO will inspect the referenced bit of the oldest page and if the bit is off or zero, it will then instantly selects that page for replacement. However, if the referenced bit is on or 1, the page is moved to the tail of the FIFO queue. In due course, the page that was moved to the tail of the queue will slowly move to the head of the queue. When it reaches at the head of the queue, and if the referenced bit is off or 0, it will then be selected for replacement.
Moreover, active pages will be sent to back to the tail of the queue, because their referenced bit will be set, thus will still remain in the main memory. As for a modified page, it is written or flushed to the auxiliary storage before the system selects it as replacement, even though its referenced bit is set off or 0, it will remain temporarily irreplaceable until the system completes its transfer. Assuming a process references this page before it is flushed completely, it is then recaptured, which will save an expensive page-in operation from auxiliary storage.
The clock page replacement strategy, produces basically the same results as the second chance strategy, but arranges the pages in a circular queue instead of a linear queue. Whenever there's a page fault occurs, a list pointer will move around the circular queue which moves like the hand of a clock rotates. If a page's referenced bit is off or 0, the pointer is moved to the next element of the queue. In the clock page replacement strategy, if the first page referenced bit is set to off or 0, it will then be the replacement for the new incoming page.
Next, another strategy for page replacement is the Least-Recently-Used or LRU page replacement strategy. This strategy uses a process's recent past behavior as a good indicator of the process near future pattern. If the system needs to replace a page for the new incoming page, LRU strategy will replace the page that has been in the memory the longest without being referenced. Even though LRU perform better than FIFO strategy, the advantage of this strategy comes at the cost of system overhead. The LRU strategy works when a page frame is referenced, the system then places the page's entry to the head of the queue, which indicates that the page has recently referenced. While the older entries will be send towards the tail of the queue. If an existing page needs to be replaced to make room for new incoming page, the system will replace the page at the end of the queue. It is a good strategy, but it acquires substantial overhead due to the system needs to update the list every time a page is referenced.
The Least-Frequently-Used or LFU strategy is another strategy in page replacement in the system. It makes the system decide on how completely the page is being used. In this strategy, the system replace the page which is least frequently used or least referenced. The strategy focus on the idea that if a page is not intensively or completely referenced is probably not likely to be referenced in the future. However, this strategy has some setbacks that is, using ample of overhead because it needs to update the system from time to time and the system can easily select the wrong pages for replacement.
Another strategy used for page replacement is the Not-Used-Recently or NUR page replacement strategy. This strategy uses two hardware bits per page entry. Its referenced bit is set to 0 if the page is not referenced and set to one if it has been referenced, and modified is set to 0 if the page has not yet been modified and set to 1 if it is modified. This strategy works by initially setting all the pages referenced bit to 0. So when a page is referenced it will then set to 1. If the system needs to replace a page, NUR will attempt to find a page that is still set to 0 or has not been referenced. However, if no such page exists, it will then replace a referenced page.
In the Far page replacement, it uses graphs of predictable patterns of reference functions and data to make decision on which page can be replace in the main memory. This strategy has shown mathematically to perform at near optimal levels. The replacement algorithm of this strategy works in phases which are similar to the clock algorithm. The far page replacement strategy firstly marks all vertices in the access graph as not yet referenced. If the process access a page, the algorithm will then mark it as referenced the vertex that it corresponds that page. When the system needs to select a page to be replaced, it will choose an unreferenced page that is furthest away from any referenced page in the access graph. The focus of this strategy is that the unreferenced page which is furthest away from any referenced page is probably be used or referenced furthest in the future. The setbacks of this strategy is that it is complex and incurs significant execution-time overhead, it still has not been implemented in real system.
In conclusion, there are many different strategies present for page replacement, each of the strategies has their own benefits and setbacks which occurs when it is used, and some of the strategies are nearly impossible to be implemented.