What is the least recently used page replacement algorithm?

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:

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.

The first three pages, 0, 1, 2, will give rise to 3-page faults (look at the image above).
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.
This process is repeated for the entire reference string.
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.)
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.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments