LRU Page Replacement Algorithm in Java

June 30, 2023

LRU Page Replacement Algorithm in Java

In memory management, page replacement algorithms play a very vital part of keeping the main memory filled with fresh pages. One of the algorithms called Least Recently Used (LRU) page replacement algorithm works on the concept that it replaces those pages first which are the oldest and have been least referred.
On this page,you will find LRU Page Replacement Algorithm in Java in detail.

LRU Page Replacement Algorithm in Java

LRU Page Replacement Algorithm in Java

To implement this, a counter called an “age bit” is maintained, which keeps track of which page is to be referred and when it is to be referred. It ensures that the page which was least recently used is discarded to make space for the new page. When the page requested by the user is not present in the RAM, then a page fault occurs. When the page requested by the user is already present in the RAM, then page hit occurs.

Let us understand LRU Algorithm in Java with an example.

LRU Page Replacement Algorithm in OS
OS dekstop gif
OS mobile gif

Priority Scheduling

CPU Scheduling

FCFS Scheduling

Preemptive Scheduling

LRU Program in Java (Method-1)

Run 
import java.util.Arrays;
public class Main 
{
    static boolean checkHit(int incomingPage, int[] queue, int occupied) 
    {
        for (int i = 0; i < occupied; i++) 
        {
            if (incomingPage == queue[i])
                return true;
        }
        return false;
    }

    static void printFrame(int[] queue, int occupied) 
    {
        for (int i = 0; i < occupied; i++)
            System.out.print(queue[i] + "\t\t\t");
    }

    public static void main(String[] args) 
    {

        int[] incomingStream = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3};
        int n = incomingStream.length;
        int frames = 3;
        int[] queue = new int[frames];
        int[] distance = new int[frames];
        int occupied = 0;
        int pagefault = 0;

        System.out.println("Page\t Frame1 \t Frame2 \t Frame3");

        for (int i = 0; i < n; i++) {
            System.out.print(incomingStream[i] + ": \t\t");

            if (checkHit(incomingStream[i], queue, occupied)) 
            {
                printFrame(queue, occupied);
            } else if (occupied < frames) 
            {
                queue[occupied] = incomingStream[i];
                pagefault++;
                occupied++;
                printFrame(queue, occupied);
            } else 
            {
                int max = Integer.MIN_VALUE;
                int index = -1;
                for (int j = 0; j < frames; j++) 
                {
                    distance[j] = 0;
                    for (int k = i - 1; k >= 0; k--) 
                    {
                        ++distance[j];
                        if (queue[j] == incomingStream[k])
                            break;
                    }
                    if (distance[j] > max) 
                    {
                        max = distance[j];
                        index = j;
                    }
                }
                queue[index] = incomingStream[i];
                printFrame(queue, occupied);
                pagefault++;
            }
            System.out.println();
        }
        System.out.println("Page Fault: " + pagefault);
    }
}

Output


Page	 Frame1 	 Frame2 	 Frame3
1:  		1			
2:  		1			2			
3:  		1			2			3			
2:  		1			2			3			
1:  		1			2			3			
5:  		1			2			5			
2:  		1			2			5			
1:  		1			2			5			
6:  		1			2			6			
2:  		1			2			6			
5:  		5			2			6			
6:  		5			2			6			
3:  		5			3			6			
1:  		1			3			6			
3:  		1			3			6	
		
Page Fault: 8

LRU Program in Java (Method-2)

Run 
import java.util.Arrays;
public class Main 
{
    public static void main(String[] args) 
    {
        int m, n, position = 0, k, l;
        int a = 0, b = 0, page_fault = 0;

        int total_frames = 3;
        int[] frames = new int[total_frames];
        int[] temp = new int[total_frames];
        int[] pages = { 1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3, 6, 1, 2, 4, 3 };
        int total_pages = pages.length;

        Arrays.fill(frames, -1);

        for (n = 0; n < total_pages; n++) 
        {
            System.out.print(pages[n] + ": ");
            a = 0;
            b = 0;
            for (m = 0; m < total_frames; m++) 
            {
                if (frames[m] == pages[n]) 
                {
                    a = 1;
                    b = 1;
                    break;
                }
            }
            if (a == 0) 
            {
                for (m = 0; m < total_frames; m++) 
                {
                    if (frames[m] == -1) 
                    {
                        frames[m] = pages[n];
                        b = 1;
                        page_fault++;
                        break;
                    }
                }
            }
            if (b == 0) 
            {
                Arrays.fill(temp, 0);
                for (k = n - 1, l = 1; l <= total_frames - 1; l++, k--) 
                {
                    for (m = 0; m < total_frames; m++) 
                    {
                        if (frames[m] == pages[k]) 
                        {
                            temp[m] = 1;
                        }
                    }
                }
                for (m = 0; m < total_frames; m++) 
                {
                    if (temp[m] == 0)
                        position = m;
                }
                frames[position] = pages[n];
                page_fault++;
            }

            for (m = 0; m < total_frames; m++) 
            {
                System.out.print(frames[m] + "\t");
            }
            System.out.println();
        }
        System.out.println("\nTotal Number of Page Faults:\t" + page_fault);
    }
}

Output

1: 1	-1	-1	
2: 1	2	-1	
3: 1	2	3	
2: 1	2	3	
1: 1	2	3	
5: 1	2	5	
2: 1	2	5	
1: 1	2	5	
6: 1	2	6	
2: 1	2	6	
5: 5	2	6	
6: 5	2	6	
3: 5	3	6	
1: 1	3	6	
3: 1	3	6	
6: 1	3	6	
1: 1	3	6	
2: 1	2	6	
4: 1	2	4	
3: 3	2	4	

Total Number of Page Faults:	11

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
OS dekstop banner

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout
Operating systems Memory

      Read More

  1. Memory Management Introduction
  2. Partition Allocation Method
    1. First Fit in OS
      1. Program in C | C++ | Java | Python
    2. Best fit
      1. Program in C | C++ | Java | Python
    3. Worst fit
      1. Program in C | C++ | Java | Python
    4. Next fit
      1. Program in C | C++ | Java | Python
    5. First fit best fit worst fit in OS Example
  3. Buddy- System Allocator
  4. Paging
    1. Types of Paging
  5. Fragmentation
    1. internal fragmentation
    2. external fragmentation
    3. internal fragmentation vs external fragmentation
  6. Mapping Virtual address to Physical Address.
  7. Virtual Memory 
  8. Demand Paging
  9. Implementation of Demand paging and page fault
  10. Segmentation
  11. Page Replacement Algorithms
    1. LRU
    2. FIFO
    3. Optimal Page Replacement algorithm
  12. Thrashing
  13. Belady’s Anomaly
  14. Static vs Dynamic Loading
  15. Static vs Dynamic Linking
  16. Swapping
  17. Translational Look Aside Buffer
  18. Process Address Space
  19. Difference between Segmentation and Paging
Go to Operating System Tutorials Main Page