Least Recently Used (LRU) in Python

January 20, 2023

LRU in Operating System

Least Recently Used (LRU) Algorithm

The operating system uses a set of instructions to execute different programs. These instructions are present in blocks of data called pages. The operating system uses these pages to fetch data and instructions. In most of the cases, it is said that pages that have been heavily used during information processing, will again be used in the next few instructions.

Therefore, the operating system removes the unused pages from the main memory and sends them to the secondary memory. The concept behind this is, the pages that have not been used in the processing, will not be used in the next few instructions.

The operating system implements the page fault mechanism through an algorithm. This algorithm maintains a linked list of all the pages in the memory. The most recently used pages are kept in the front, while the pages which are not used are placed at the rear position.

Read Also – LRU in C

Program in Python

The program uses cache to store the (key, value) mapping and lru and other variable tm to track the access history.



    def __initialize__(s, c):


        s.c = c


        s.tm = 0


        s.cache = {}


        s.lru = {}


        # The method takes two variables self and key, compares them and sets priority


        def getdata(self, key):


        if key in s.cache:


         s.lru[key] = s.tm


         s.tm += 1


         return s.cache[key]


        return -1


        # The method setdata takes three values for comparison and replacement in the stack.


    def setdata(self, key, value):


        if len(self.cache) >= self.c:


        # find the LRU entry


        old_key = min(self.lru.keys(), key=lambda k:self.lru[k])


        s.cache.pop(old_key)


        s.lru.pop(old_key)


        s.cache[key] = value


        s.lru[key] = self.tm


        s.tm += 1