Least Recently Used (LRU) Page Replacement Algorithm

LRU stands for Least Recently Used Algorithm 

In the least recently used algorithm when a page fault generates, we choose the page that was used very less in the past. In other words, the optimal algorithm checks forward reference while LRU checks backward reference in the page reference string.

The page table entry records the time when the page was last referenced and it is modified every time when the page is referenced. It basically works on the assumption that if a page is not used frequently in the past then chances are there that it might not be required in the future also.

Example String For LRU

PAGE FAULT ::  9  PAGE HIT :: 6

Program in Python:

pages,q=[],[]  
t,pf=0,0  
capacity=int(input("Enter the capacity of main memory"))  
str1=input("enter requiderd page string")  
n=len(str1)  
for i in range(0,n):
    pages.append(int(str1[i]))  
q=[-1]*capacity  
print("req.page main memory")   
for i in range(0,n):  
    if (pages[i] not in q):
        q.pop(0)  
        q.append(pages[i])  
        pf=pf+1  
        t=t+1  
    else:  
        q.remove(pages[i])  
        q.append(pages[i])  
        t=t+1  
    print(str(pages[i])+"  "+str(q))   
print("Page Fault :: "+str(pf),"\n"+"Page Hit :: "+str(n-pf))   

Expected Output From Algorithm:

Output Of LRU

DOWNLOAD SOURCE CODE