ENVS 1800 Lecture 2: ENVS 1800 Tutorial 2 Notes
14 May 2018
School
Department
Course
Professor
ENVS 1800 Tutorial 2 Notes – Least recently used page replacement
Introduction
• FIFO does not take into account usage of the page.
• Logically, a page that has been in memory for a long period of time is probably there
because it is heavily used.
• The page being removed may be in current use, which would result in a second page
fault and force the system to reload the page almost immediately.
• FIFO has a second, interesting deficiency.
• You would assume that increasing the number of pages available to a process would
reduce the number of page faults for that process.
• However, it has been shown that under certain conditions, use of the FIFO page
replacement algorithm results in more page faults with an increased number of pages,
instead of fewer.
• This oditio is kow as Belad’s aoal.
• If ou are iterested, eaples of Belad’s aoal a e foud i the referees
Deitel [DEIT03] and Silberschatz et al. [SILB08].
• For these reasons, FIFO is not considered a good page replacement algorithm.
• The least recently used (LRU) algorithm replaces the page that has not been used for the
longest time, on the assumption that the page probably will not be needed again.
• This algorithm performs fairly well, but requires a considerable amount of overhead.
• To implement the LRU algorithm, the page tables must record the time every time the
page is referenced.
• Then, when page replacement is required, every page must be checked to find the page
with the oldest recorded time.
• If the number of pages is large, this can take a considerable amount of time.
• Intuitively, this algorithm has appeal, since it would seem that a page not used much is
more replaceable than one that has received a lot of use.
find more resources at oneclass.com
find more resources at oneclass.com
