Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

lru
os

What is the least recently used page replacement algorithm?

Sarvech Qadir

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Page replacement is a widely used approach in memory management. The idea is simple: the main memory cannot hold all the referred pages in memory. So whenever a new page is referenced, an existing page is replaced by the page that was newly called. The goal of any page replacement mechanism is to minimize the number of page faults.

Least Recently Used (LRU) algorithm is a page replacement technique used for memory management. According to this method, the page which is least recently used is replaced. Therefore, in memory, any page that has been unused for a longer period of time than the others is replaced.

This idea is somewhat based on locality of reference, that any page that has been unused for a great amount of time is more likely to remain unused. Therefore, it is better to replace that page.

Algorithm Example

Let’s look at an example:

widget

Given a reference string: 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 and given that there are a total of 3 memory locations available.

  1. The first three pages, 0, 1, 2, will give rise to 3-page faults (look at the image above).

  2. Now that the table is filled and the next page, 3, is not present in the table, a page must be replaced. Since 0 is the least recently used page, page 3 will replace 0. This will result in a 1 page fault.

  3. This process is repeated for the entire reference string.

  4. When a number from the reference string already exists in the table, there is no page fault and no effort is required to replace the page. In that case, the reference page will become the recently used page (like when 0 is referenced when the page frames contain 4, 0 and 1.)

  5. Make sure you look at whether or not a given page is recently used from the reference string.

Code

Let’s look at a relevant coding example for calculating page faults with LRU:

# LRU code
# defining the table size
table_size = 3
reference_string = [0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4]
# the list which stores the current pages in memory
# and where page replacement is executed.
pages = []
# page faults
faults = 0
# iterating through the ref string
for page in reference_string:
# check if page already exists in the list,
# if yes, we just remove the page and append it
# to the end of the list (last index).
if page in pages:
# removing
pages.remove(page)
# appending
pages.append(page)
# if page is not there
else:
# we first check length of page list.
# if still spots left in the list, we first fill it
if(len(pages) < table_size):
pages.append(page)
else:
# if the page list is filled. We remove the
# first page.
pages.remove(pages[0])
# and then we append page to the end of list.
pages.append(page)
# Increment 1 in Page faults
faults +=1
print("total page faults = ", faults)

In the code, we will go with the approach that the first page in the table will always be least recently used and is always removed. The new page does not replace the first page, but is always appended at the end of the list. For example, if the list is [0, 1, 2] and a new page 3 is entered, the list changes to become [1,2,3]. 0, being the first page, is removed and page 3 is appended at the end of the list.

For a page that already exists in the page table, we will just remove the page of that value and append it to the end. For example, if the list is [0, 1, 2] and a new page 1 is entered, the list changes to become [0,2,1].

The total number of page faults are returned which is the same as the number of columns in the illustration provided above.

RELATED TAGS

lru
os

CONTRIBUTOR

Sarvech Qadir
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring