Page replacement algorithms
Not Recently Used
This uses the accessed and dirty bits in the PTE. It uses these as a crude
measure of whether a page should be eviced from memory. In order to 'forget'
occasionally, a background process in the OS sweeps round all the pages
in memory every few clock ticks and sets their accessed bit to false. This
means that 'not recently' accessed pages will be considered more likely
for eviction. (The dirty bit---whether a page has been written to---is
not cleared, since this is needed to determine whether a page has been
modified and must be written back to disk.)
The accessed and dirty bits are used as follows:
| accessed |
dirty |
priority |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
2 |
| 1 |
1 |
3 |
The pages with the lowest priority are evicted first, with some algorithm
choosing randomly between them.
This algorithm is easy to understand, efficient, and though not as good
as LRU, is often adequate.
last updated 6 March 1998