LRU Page Replacement Algorithm in Java

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

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 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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription