Page replacement algorithms
|
|
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. That happens when a page fault occurs.
| Contents |
The Theoretically Optimal Page Replacement Algorithm
The theoretically optimal page replacement algorithm 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 be used. In spite of this, there exist 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 referenced 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 the page is inserted at the back of the queue, as if it were a new page, and this process is repeated. If all the pages have their referenced bit set, on the second encounter of the first page in the list, that page will be swapped out, as it now has its referenced bit cleared.
Essentially, what second-chance does is, as its name suggests, giving every page a "second-chance" - an old page which has been referenced is probably in use, and should not be swapped out over a new page which has not been referenced.
Least Recently Used
The least recently used page (LRU) replacement algorithm, though similar in name to NRU, differs in the fact that LRU keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval. LRU works on the idea that the pages which have been most heavily used in the past few instructions will be used heavily in the next few instructions too. While LRU can provide near-optimal performance in theory, it is rather expensive to implement in practice. There are a few implementation methods for this algorithm which try to reduce the cost yet keep as much of the performance as possible.
The most expensive method is the linked list method, whereby there is a linked list containing all the pages in memory. At the back of this list is the least recently used page, and at the front is the most recently used page. The cost of this implementation lies in the fact that items in the list will have to be moved about every memory reference, which is a very time-consuming process.
Another way, which requires hardware support is as follows: suppose the hardware has a 64-bit counter which is incremented at every instruction. Whenever a page is accessed, it gains a value equal to the counter at the time of page access. Whenever a page needs to be replaced, the operating system simply picks out the page which has the lowest counter, and swaps it out. This is not feasible in present hardware as there exists no such hardware counters.
Because of these implementation costs, one may consider algorithms, such as those which follow, which are similar to LRU, but which offer cheaper implementations.
Not Frequently Used
The not frequently used (NFU) page replacement algorithm also requires a counter, but every page has one counter of its own, which is initially zero. At each clock interval, all pages which have been referenced within that interval will have their counter incremented by 1. In effect, the counters keep track of how frequently a page has been used. Thus, the page with the lowest counter can be swapped out when necessary.
The main problem with NFU is that it keeps track of the frequency of use without regard to the time span of use. Thus, in a multi-pass compiler, pages which were heavily used during the first pass, but are not needed in the second pass will be favoured over pages which are comparably lightly used in the second pass, as they have higher frequency counters. This results in poor performance. Thankfully, a similar and better algorithm exists, and its description follows.
Aging
The aging algorithm is a descendant of the NFU algorithm, with modifications to make it aware of the time span of use. Instead of just incrementing the counters of pages referenced, putting equal emphasis on page references regardless of the time, the reference counter on a page is first shifted right (divided by 2), before adding the referenced bit to the left of that binary number. For instance, if a page has referenced bits 1,0,0,1,1,0 in the past 6 clock ticks, its referenced counter will look like this: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100. As you can see, page references closer to the present have more impact than page references a long time ago in the past. This ensures that pages referenced more recently, though less frequently referenced, will have higher priority over pages more frequently referenced in the past. Thus, when a page needs to be swapped out, the page with the lowest counter will be chosen.
Note that aging differs from LRU in the sense that aging can only keep track of the references in the latest 16/32 (depending on the bit size of the processor's integers) time intervals. Consequently, two pages may have referenced counters of 00000000, even though one page was referenced 9 intervals ago and the other 1000 intervals ago. Generally speaking, knowing the usage within the past 16 intervals is sufficient for making a good decision as to which page to swap out. Thus, aging can offer near-optimal performance for a moderate price.
References
- Tanenbaum, Andrew S. Operating Systems: Design and Implementation (Second Edition). New Jersey: Prentice-Hall 1997.