A reference string is the sequence of page numbers referenced by an executing program during a given time interval. Reference strings are used to compare different page replacement algorithms by counting the number of page faults generated.
Since page faults are time consuming, the optimal page replacement algorithm selects the page that will not be referenced for the longest time in the future. Thus the requirement to copy data back into memory is lessened.
The FIFO page replacement algorithm selects the page that has been resident in memory for the longest time. This uses a simple queue to determine which to swap out. Very easy to implement, but no guarantee of efficiency.
The least-recently-used page replacement algorithm (LRU) selects the page that has not been referenced for the longest time. The theory is if it hasn’t been used in a while, it may not be needed for a while more.
The LRU can be instantiated with a queue as well, however, every time a page is referenced, it gets moved to the back of the queue, no matter where it’s previous location was.
Approximations of the LRU Algorithm
While the LRU would be more efficient for memory management, the fact that it requires the queue of pages to be modified at each memory reference – it makes the algorithm too inefficient in practice.
Several algorithms exist that approximate LRU and can be implemented efficiently.
The aging page replacement algorithm has a hardware bit set whenever the page is accessed. A register is bit shifted toward a smaller number unless it is updated. So after a given set of time, it can me marked for removal if necessary.
The second-chance page replacement algorithm is a coarse-grain approximation of LRU. The algorithm uses the r-bit to divide all pages into only two categories: recently referenced and not recently referenced. This makes is faster since its not moving data around quite so often.
The third-chance page replacement algorithm (also known as a not-recently-used page replacement algorithm (NRU) is a further refinement of the aging page replacement and second-chance algorithms. It uses both bit methods (aging (r) and modified (m)) since replacing a modified page takes longer.
Thus it allows a modified page to stay active a little bit longer than if it wasn’t modified, even if it hasn’t been accessed as recently.
It creates an instance where each page is allowed one of four values.
- Recently used/Modified – least likely to be removed
- Recently used/Not Modified
- Not Recently used/Modified
- Not Recently used/Not Modified – most likely to be removed
Page Replacement with Fixed # of Frames was originally found on Access 2 Learn
