Page Eviction
| Depends on | Virtual Memory • Paging |
|---|
A page fault has just required that a memory page be evicted so that the urgently needed page can be loaded. Which page should be evicted?
With a ‘crystal ball’ (or some other paranormal means of foretelling the future) the choice is quite easy: discard a page which will never be needed again. Failing that possibility, discard the page which will only be needed in the most-distant future.
With only engineering to use things are a bit harder. We need to predict the future based on past events – probably in a way which is reasonably simple to implement.
Page replacement algorithms
Here are some possible algorithms for choosing:
- ‘Random’ - pick any page. Fairly simple and yet this works reasonably well.
- ‘First-In,First-Out(FIFO)’ - It is one of the simplest page replacement algorithm. The oldest page, which has spent the longest time in memory is chosen and replaced. This algorithm is implemented with the help of a FIFO queue to list the pages in memory. A page is inserted at the rear end of the queue and is replaced at the front of the queue.
- ‘Least Recently Used’ - the page which hasn’t been touched for the longest time. The assumption is that ‘if you haven’t used it recently you probably won’t want it again, soon’. This holds reasonably well for most software.
LRU is often cited as one of the ‘better’ means of predicting the future, but it requires some effort to keep a list of references sorted chronologically; this needs to be supported in hardware as each memory operation (load or store) may move any pave to the back-of-the-queue.
This is a far-from exhaustive list. You should be able to find several others, plus variants and hybrids, in the [1].
Here is the demonstration from the paging article again: you might like to play more with the replacement algorithms.
Sophisticated operating systems – and some modern hardware – will collect data about system operation to help make such decisions.
Note that, before eviction the page itself must be up to date; this may involve flushing the caches.
‘Pinned’ pages
There are some pages which should not be evicted – and others which are highly desirable to keep in memory – which contain code critical to the operating system. One example might be an interrupt service routine for interrupts requiring low latency (most of them!).
Another example would be the page holding the code which loads pages from the disk!
It is left to the reader to imagine the consequences of evicting the code which loads pages from disk…
Such pages are ‘permanently’ resident and are sometimes referred to as being “pinned”; they are excluded from being chosen for eviction.
Another reason for pinning a page could be some parallel operation, such as a DMA transfer being active (or pending) on that page. It is important to let a transfer complete before moving the data (again).
You can try pinning pages in the demonstration above. Note that you can’t pin all the pages – the reason should be obvious!
Paging daemon
- It is faster to evict a ‘clean’ page – i.e. one which is the same as a copy on disk.
(This could be because it has been written back to disk already.) - It is quicker to pre-sort pages in ‘quiet’ periods to make candidate selection easier when needed.
- A ‘dirty’ page can be ‘cleaned’ by copying it back, even if it is still retained.
These sort of jobs are often handled by a background task: in this case the paging daemon.
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 10.4, pages 401-413 |
|---|
