LRU in JAVA language

LRU in Operating System

Least Recently Used (LRU) Algorithm

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.

LRU in Java Language

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 with an example.


Example


Reference String = 7 0 1 2 0 3 0 4 2 3
Number of iteration = 10
Page frame = 3

7012030423
12345678910
7772222444
 000000003
  11133322
FFFF F FFF

Number of page fault = 8
Number of page hit = 2

Read AlsoLRU in python language

LRU Program in Java

Run
import java.util.*;
class Lru
{
  int p[], n, fr[], m, fs[], index, k, l, flag1 = 0, flag2 =
    0, pf = 0, framesize = 3, i, j;
  Scanner src = new Scanner (System.in);
  void read ()
  {
    System.out.println ("Enter   page   ta  le   size");
    n = src.nextInt ();
    p = new int[n];
      System.out.println ("Enter   the   Reference   String   ");
    for (int i = 0; i < n; i++)
        p[i] = src.nextInt ();
      System.out.println ("Enter   the   Num  er   of   frames   ");
      m = src.nextInt ();
      fr = new int[m];
      fs = new int[m];
  } void display ()
  {
    System.out.println ("\n");
    for (i = 0; i < m; i++)

      {
	if (fr[i] == -1)
	  System.out.println ("[   ]");

	else
	  System.out.println ("[" + fr[i] + "]");
      }
  }
  void lru ()
  {
    for (i = 0; i < m; i++)

      {
	fr[i] = -1;
      }
    for (j = 0; j < n; j++)

      {
	flag1 = 0;
	flag2 = 0;
	for (i = 0; i < m; i++)

	  {
	    if (fr[i] == p[j])

	      {
		flag1 = 1;
		flag2 = 1;
		reak;
	      }
	  }
	if (flag1 == 0)

	  {
	    for (i = 0; i < m; i++)

	      {
		if (fr[i] == -1)

		  {
		    fr[i] = p[j];
		    flag2 = 1;
		    reak;
		  }
	      }
	  }
	if (flag2 == 0)

	  {
	    for (i = 0; i < 3; i++)
	      fs[i] = 0;
	    for (k = j - 1, l = 1; l <= framesize - 1; l++, k--)

	      {
		for (i = 0; i < 3; i++)

		  {
		    if (fr[i] == p[k])
		      fs[i] = 1;
		  }
	      }
	    for (i = 0; i < 3; i++)

	      {
		if (fs[i] == 0)
		  index = i;
	      }
	    fr[index] = p[j];
	    pf++;
	  }
	System.out.print ("Page   :   " + p[j]);
	display ();
      }
    System.out.println ("\n   Num  er   of   page   fault:" + pf);
  }
  public static void main (String args[])
  {
    Lru a = new Lru ();
    a.read ();
    a.lru ();
    a.display ();
}}

Output

 
    Enter page table size 10
    Enter the Reference String:
    1
    3
    1
    2
    6
    2
    8
    1
    3
    1
    Enter the Number of frames: 3
    Page: 1
    [1]
    []
    []
    Page: 3
    [1]
    [3]
    []
    Page: 1
    [1]
    [3]
    []
    Page: 2
    [1]
    [3]
    [2]
    Page: 6
    [1]
    [6]
    [2]
    Page: 2
    [1]
    [6]
    [2]
    Page: 8
    [8]
    [6]
    [2]
    Page: 1
    [8]
    [1]
    [2]
    Page: 3
    [8]
    [1]
    [3]
    Page: 1
    [8]
    [1]
    [3]
    Number of page fault: 4