Page replacement algorithm
In a computer operating system which utilises paging for memory management, page replacement algorithms are used to decide what pages to swap out when a page needs to be swapped in.
The Theoratically Optimal Page Replacement Algorithm
The theoratically optimal page replacement algorithms is an algorithm which works as follows: when a page needs to be swapped in, the operating system looks at all the pages currently in memory, and sees how long it is before that page will be used. Then, the operating system swaps out the page which will be used only after the largest number of instructions has passed (i.e. the longest time before the page is used). A page that is not going to be used until 6 million instructions have executed will be swapped out over a page which is going to be used after 4 thousand instructions have executed.
However, this algorithm is ideal and cannot be implemented, simply because it is not possible or feasible for the operating system to compute how long it is before a page is going to used. In spite of this, there exists algorithms which can offer near-optimal performance - on the first run of a program, the operating system keeps track of all the pages which it references, and by using this data, it decides what pages to swap in and out on the second run. This algorithm can offer near-optimal performance, but only on the second run, and only for programs which have been run at least once before.
Not Recently Used
The not recently used (NRU) page replacement algorithm is an algorithm which favours keeping pages which have been recently used. This algorithm works on the following principle: when a page is referenced, a referenced bit will be set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit will be set. The setting of the bits is usually done by the hardware, although it is possible to do so on the software level as well.
At a certain fixedtime interval, the clock interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current clock interval are marked with a referenced bit. When a page needs to be replaced, the operating system divides the pages into four categories:
- Category 0: not referenced, not modified
- Category 1: not referenced, modified
- Category 2: referenced, not modified
- Category 3: referenced, modified
Although it does not seem possible for a page to be not referenced yet modified, this happens when a category 3 page has its referenced bit cleared by the clock interrupt. The NRU algorithm simply picks a random page from the lowest category for removal. Note that this algorithm implies that a refernced page is more important than a modified page.
First-In First-Out
The first-in first-out (FIFO) page replacement algorithm is another low-overhead algorithm which requires little bookkeeping on the part of the operating system. The idea is obvious from the name - the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the earliest arrival in front. When a page needs to be replaced, the page at the front of the queue is selected, as it will be the oldest page. While FIFO is cheap and intuitive, it performs relatively badly in practical application. Thus, it is rarely used in its unmodified form.
Second-Chance
A modified form of the FIFO page replacement algorithm, known as the second chance page replacement algorithm, fares relatively better than FIFO at little cost for the improvement. It works by looking at the front of the queue as FIFO does, but instead of immediately swapping out that page, it checks to see if its referenced bit is set. If it is not set, the page is swapped out. Otherwise, the referenced bit is cleared, and