ENVS 1800 Lecture 4: ENVS 1800 Tutorial 4 Notes
14 May 2018
School
Department
Course
Professor
ENVS 1800 Tutorial 4 Notes – Second chance page replacement algorithms
Introduction
• Least desirable will be a page that has been recently referenced and modified.
• This is a commonly used algorithm.
• One difficulty with this algorithm is that gradually all the used bits fill up, making
selection difficult or impossible.
• There are a number of variations on this algorithm that solve this problem by selectively
resetting used bits at regular intervals or each time a page replacement occurs.
• The most common approach pictures the process pages as numerals on a clock.
• When a page replacement must be found, the clock hand moves until it finds an unset
used bit and the corresponding page is replaced.
• Pages with set used bits that the hand passes over are reset.
• The hand remains at the found replacement page awaiting the next replacement
requirement.
• This variation on NUR is called the clock page replacement algorithm.
• One second chance algorithm uses an interesting variation on FIFO, using a referenced
bit similar to that of NUR.
• When the oldest page is selected for replacement, its referenced bit is checked.
• If the referenced bit is set, the bit is reset, and the time is upgraded, as though the page
had just entered memory.
• This gives the page a second pass through the list of pages.
• If the referenced bit is not set, then the page is replaced
• Since it is safe to assume that it has not been referenced in some time.
• Another second chance algorithm keeps a small pool of free pages that are not assigned.
• When a page is replaced, it is not removed from memory
• Instead, is moved into the free pool.
• The oldest page in the free pool is removed to make room.
find more resources at oneclass.com
find more resources at oneclass.com
