Least Recently Used or LRU caching is one of the operating systems’ most commonly used algorithms for page replacement. It is used in operating systems to optimize performance and allocation of memory resources among processes.
It is also used in operating systems to implement virtual memory. Here, you will learn what LRU replacement is, how it works, and how it is used in operating systems to implement virtual memory. So, let us start by discussing the LRU algorithm and how it works.
Least Recently Used (LRU) Page Replacement
It uses recent past pages loaded in memory as a reference for the near future to select a victim frame that has not been used for the longest time. LRU replacement associates the time of last use with each page.
LRU caching works on the assumption that the most recently used page in the memory is most likely to be reaccessed. Therefore, it tries to keep the most recently used page in memory, and whenever a page is to be replaced, LRU will choose the page that has not been used for the longest time.
The LRU Cache Implementation
Consider we have eight pages for a process numbered 0 to 7 and only 3 locations in memory (also known as frames) to load these pages. Let’s assume that the process needs the pages in the following order.
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
We use the LRU page replacement algorithm to deal with page faults during the program execution. Also, assume that no pages are loaded into the main memory at the start. Then our main memory will look like this
In the above example, a fault will occur when the page required by the program is not loaded in any of the three frames. At the start, all three frames are empty. Hence, a page fault occurs when the program tries to access page 7.
Similarly, a page fault occurs when pages 0 and 1 are accessed. When page 2 is accessed, the memory contains pages 7, 0, and 1. Since page 2 is not in any frame, a page fault occurs here as well. Now, when the program tries to access page 0 again, the memory contains pages 2, 0, and 1 in frames.
As page 0 is already in frame 2, a page fault does not occur. Now that we know how LRU works, let us see how it is used in operating systems to accomplish virtual memory. Let’s start with a brief overview of virtual memory.
Virtual Memory
Virtual memory is a concept used in operating systems that allows users to run programs that require more memory than is available on the system. To achieve this task, the operating system divides the program into fixed-length units known as Pages.
These pages are loaded into the main memory in the form of frames. A frame is a fixed-size block in the main memory. The size of a frame is similar to the size of a page. A page is a logical address that is mapped to a physical frame in the main memory.
The information related to all the page mapping is kept in the page table by the OS. The operating system then uses Demand Paging and LRU page replacement (or some other page-replacement algorithm) to execute the program page by page.
Demand Paging
In demand paging, the process resides on the secondary storage devices (disk drives), using the Lazy Swapper to execute the program. The Lazy Swapper loads the program into the main memory page by page but only loads a page when required.
It allows the OS (operating system) to load only those parts of a program currently in execution and helps it save memory for other processes.
A page fault trap is generated when the system tries to execute a page that is not yet loaded in the main memory. Here, the operating system does the following tasks.
- Interrupts the process.
- Saves the current state of the process.
- Selects which page is required to be loaded in the main memory.
- Looks for a free frame in the main memory.
- If a free frame exists, it loads the page.
- If no free frame is available, it uses LRU (or some other) page replacement algorithm to select a victim frame.
- Loads the page into the victim frame.
- Loads the saved state of the process and continues execution.
Therefore, by using LRU for page replacements in demand paging, operating systems can implement virtual memory, which improves performance, better utilizes memory resources, and allows the system to run programs that require more memory than available.
What does Lazy Swapper do?
Lazy Swapper is a process to load the program into the main memory page by page but only when needed. It allows the OS to load only those parts of a program currently in execution and helps it save memory for other processes.
