Skip to main content

LRU page replacement algorithm

In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault occurs and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.
When the page that was selected for replacement and paged out is referenced again it has to be paged in (read in from disk), and this involves waiting for I/O completion. This determines the quality of the page replacement algorithm: the less time waiting for page-ins, the better the algorithm. A page replacement algorithm looks at the limited information about accesses to the pages provided by hardware, and tries to guess which pages should be replaced to minimize the total number of page misses, while balancing this with the costs (primary storage and processor time) of the algorithm itself.
The page replacing problem is a typical online problem from the competitive analysis perspective in the sense that the optimal deterministic algorithm is known.

/*
 * LRU.java (Implements Paging Algorithm Least Recently Used for
 *           replacing pages from frame system)  
 *
 * Written by : Abdul Mugeesh
 *
 * 1. Created basic structure          
 * 2. Added Documentation.            
 * 3. Final Documentation Check.      
 * 4. Final Variable Name Check.            
 * 5. Final Functionality Check.              
*/

/* Import some of the libraries.*/
import java.lang.*;
import java.util.*;
import java.io.*;


class LRU extends PagingAlgorithm{
 String[][] szRequest;
 int nPageSize;
 int nNoOfRequest;

 public LRU(String[][] szRequest,int nNoOfRequest,
   int nNoOfFrames, int nPageSize,boolean bDebug){
  this.szRequest = szRequest;
  this.nNoOfRequest = nNoOfRequest;
  this.nPageSize = nPageSize;
  super.nNoOfFrames = nNoOfFrames;
  super.bDebug = bDebug;
  super.Create();
 }/* End of constructor.*/

 public void read(int nProgName, int nPageIndex,int nAddress){
   super.read(nProgName, nPageIndex, nAddress);
 }/* End of read.*/

 public void load(int nProgName, int nProgSize){
  super.load(nProgName, nProgSize, nPageSize);
 }/* End of read.*/

 public void write(int nProgName, int nPageIndex,int nAddress){
  super.write(nProgName, nPageIndex, nAddress);
 }/* End of read.*/

 public void unload(int nProgName){
  super.unload( nProgName);
 }/* End of read.*/

 public void Start(){
  System.out.println("Using LRU ...");
  for(int nIndex=2; nIndex < nNoOfRequest; nIndex++){
   if(szRequest[nIndex][0].equals("load"))
      load(Integer.parseInt(szRequest[nIndex][1]),
  Integer.parseInt(szRequest[nIndex][2]));
 
   if(szRequest[nIndex][0].equals("read"))
      read(Integer.parseInt(szRequest[nIndex][1]),
  (int)Integer.parseInt(szRequest[nIndex][2])/nPageSize,
  Integer.parseInt(szRequest[nIndex][2]));

   if(szRequest[nIndex][0].equals("write"))
      write(Integer.parseInt(szRequest[nIndex][1]),
   (int)Integer.parseInt(szRequest[nIndex][2])/nPageSize,
   Integer.parseInt(szRequest[nIndex][2]));

   if(szRequest[nIndex][0].equals("unload"))
      unload(Integer.parseInt(szRequest[nIndex][1]));

  }/* End for.*/
  System.out.println("Number of page faults for LRU:"+super.nPageFault);
 }/* End of Start.*/

 public int getVictim(int nProgName){
  Frame newFrame;
  int nEmptyIndex=-1;
  long lTimeStamp = 99999999;
  int nLRUIndex=-1;

  for(int nIndex=0; nIndex < super.nNoOfFrames; nIndex++){
   newFrame = (Frame)super.FrameList.elementAt(nIndex);
   if(newFrame.bFrameStatus == false) return nIndex;
   else{
    if(lTimeStamp >= newFrame.lTimeStamp){
     nLRUIndex = nIndex;
     lTimeStamp = newFrame.lTimeStamp;
    }/* End if.*/
   }/* End if.*/
  }/* End for.*/
  return nLRUIndex;
 }/* End of getVicitim.*/
}/* End of LRU.*/

Comments

Post a Comment

Popular posts from this blog

Login and Registration Example in JSP with Session

Those who want to start with jsp and MySQL, this is an excellent example for themselves. Here you can learn how to insert data to MySQL using JSP. Also you can learn about session handling in jsp. 1 2 3 4 5 6 7 8 9 10 CREATE TABLE `members` (    `id` int (10) unsigned NOT NULL auto_increment,    `first_name` varchar (45) NOT NULL ,    `last_name` varchar (45) NOT NULL ,    `email` varchar (45) NOT NULL ,    `uname` varchar (45) NOT NULL ,    `pass` varchar (45) NOT NULL ,    `regdate` date NOT NULL ,    PRIMARY KEY   (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=latin1; index.jsp 1 2 3 4 5 6 ...
Post a Comment
Read more

Timer funcitons in JavaScript: Reminder Script

Timers are used in web pages and we will discuss how to setup one and how to use one with an example. The function setTimeout() in function is used and here is its general syntax. mytime = setTimeout(expression, msec); mytime  is the identifier used to identify the current timeout function.  expression  is the statement that is to be executed after the specified time has ticked off.  msec  is the duration of time in milliseconds after which the expression will be executed.  You can see by using setTimeout function we can execute any function or object after a set of time. For example if msec is set 5000 then the expression will be executed after 5 seconds or 5000 milliseconds.  We will try one example where we will have four period buttons and each button will set a different time for another function to execute and display a alert button. We will call it as a reminder script and we will get one alert box based on the period button we click...
Post a Comment
Read more

Binary Addition

/* File Name : BinAdd.java */    import java.util.*; public class BinAdd    {  public static String addBit(String a, String b, String c)  { String r=""; if(a.equals("1") && b.equals("0") || a.equals("0") && b.equals("1")) { if( c.equals("0")) r="1"; else { r="0"; c="1"; } } else if( a.equals("0") && b.equals("0") ) { if(c.equals("0")) r="0"; else r="1"; } else if( a.equals("1") && b.equals("1") ) { if(c.equals("0")){ r="0"; c="1"; } else { r="1"; c="1"; } } return c+r; }   public static String add(String a, String b)   { String r=""; int len=a.length(); String carry="0"; for(int i=len-1;i...
Post a Comment
Read more

Real time changing Clock showing date and time

We can display a clock which will be showing the local time of the client computer by using JavaScript. Note that this time displayed is taken from user computer and not from the server.  We have seen in our  date object example how to display current date and time   where the current date and time is displayed once. Here we will try to display changing clock or real time change in date and time by using  setTimeout function . This setTimeout function we have used to trigger the time display function in a refresh rate of 1000 mill seconds ( 1 Sec ). This refresh rate can be changed to any other value. By changing the value to 5000 the clock will refresh and show the exact time once in every 5 seconds.  Here is the demo of this script and code is given below that.  Sat Apr 23 2016 08:27:22 GMT+0530 (IST)   Here is the code <html> <head> <title>(Type a title for your page here)</title> <script type="text/javascript...
Post a Comment
Read more