Page replacement algorithms using Java

 

1. FIFO (First In, First Out):

  • select the page that has been in main memory the longest
  • use a queue (data structure)
  • problem: although a page has been present for a long time, it may be really useful
  • Windows NT and Windows 2000 use this algorithm, as a local page replacement algorithm (described separately), with the pool method (described in more detail separately)
    • create a pool of the pages that have been marked for removal
    • manage the pool in the same way as the rest of the pages
    • if a new page is needed, take a page from the pool
    • if a page in the pool is referenced again before being replaced in memory, it is simply reactivated
    • this is relatively efficient

2. LRU (Least Recently Used):

  • choose the page that was last referenced the longest time ago
  • assumes recent behavior is a good predictor of the near future
  • can manage LRU with a list called the LRU stack or the paging stack (data structure)
  • in the LRU stack, the first entry describes the page referenced least recently, the last entry describes to the last page referenced.
  • if a page is referenced, move it to the end of the list
  • problem: requires updating on every page referenced
  • too slow to be used in practice for managing the page table, but many systems use approximations to LRU

3. NRU (Not Recently Used):

  • as an approximation to LRU, select one of the pages that has not been used recently (as opposed to identifying exactly which one has not been used for the longest amount of time)
  • keep one bit called the “used bit” or “reference bit”, where 1 => used recently and 0 => not used recently
  • variants of this scheme are used in many operating systems, including UNIX and MacIntosh
  • most variations use a scan pointer and go through the page frames one by one, in some order, looking for a page that has not been used recently.

Using above Three procedure we implements  Page replacement algorithms Page replacement algorithms using Java.


package Paging;

/**
 *
 * @author Hizbul Bahar
 */
import java.io.*;
import javax.swing.JOptionPane;

public class Main
{
 int n, page[], f, frames[], faults, count;
 double rate;

 public Main() throws IOException
 {
 n=Integer.parseInt(JOptionPane.showInputDialog("Enter number of pages"));
 page=new int[100];
 f=Integer.parseInt(JOptionPane.showInputDialog("Enter number of page frames"));
 frames=new int[f];
 count=1;
 }

void reset()
 {
 int j;
 for(j=0;j<f;j++)
 frames[j]=0;
 faults=0;
 count=1;
 }
 void read() throws IOException
 {
 int i;
 // System.out.println("Enter the pages");

for(i=0;i<n;i++)
 {
 page[i]=Integer.parseInt(JOptionPane.showInputDialog("Enter page number " +(i+1)+ ":"));
 }

for(i=0;i<f;i++)
 frames[i]=-1;
 }

 void fifo()
 {
 int i,j,m=0,k=0;
 reset();

for(i=0;i<n;i++)
 {
 if(i < f)
 {
 for (j = 0; j < f; j++)
 {
 j = i;
 frames[j] = page[i];
 j = f;
 faults++;
 }
 }
 if (i >= f)
 {
 for (j = 0; j < f; j++)
 {
 if (page[i] != frames[j])
 m++;
 }
 if (m == f)
 {
 if (k == f)
 k = 0;
 j = k;
 frames[j] = page[i];
 k=j+1;
 faults++;
 }
 m = 0;
 }
 display();
 }
 System.out.println("Number of Page Faults: "+faults);
 }
 void lru()
 {
 int i,j,duration[],max;
 reset();

duration=new int[f];
 boolean found=false;

for(i=0;i<n;i++)
 {
 if(i<f)
 {
 for(j=0;j<f;j++)
 {
 j=i;
 frames[j]=page[i];
 j=f;
 faults++;
 }
 }
 else if(i>=f)
 {

for(j=0;j<f;j++)
 duration[j]++;
 for(j=0;j<f;j++)
 {
 if(page[i]==frames[j])
 {
 found=true;
 duration[j]=0;
 }
 }
 if(found==false)
 {
 max=0;
 for(j=0;j<f;j++)
 {
 if(duration[j]>duration[max])
 max=j;
 }
 frames[max]=page[i];
 duration[max]=0;
 faults++;
 }
 }
 display();
 found=false;
 }
 System.out.println("Number of Page Faults = "+faults);
 //System.out.println("Fault rate = "+(faults*1.0/n));
 }

void display()
 {
 int i;
 System.out.print("Page frame "+count+" :");

for(i=0;i<f;i++)
 {
 if(frames[i]==-1)
 System.out.print(" -");
 else
 System.out.print(" "+frames[i]);
 }
 System.out.print("\n");
 count++;
 }
 public static void main(String[] args) throws IOException
 {
 int option;
 String choice;

Main p=new Main();
 p.read();

BufferedReader input=new BufferedReader(new InputStreamReader(System.in));

 do
 {
 System.out.println("Menu");
 System.out.println("1. FIFO");
 System.out.println("2. LRU");
 System.out.println("Enter option");

option=Integer.parseInt(JOptionPane.showInputDialog(""));
 switch(option)
 {
 case 1: p.fifo();
 break;
 case 2: p.lru();
 break;
 default: System.out.println("Invalid input");
 }

System.out.println("Press Y to continue");
 choice=input.readLine();

}while(choice.compareToIgnoreCase("y")==0);
 }
}

Advertisements

Software Engineer at The Jaxara IT Ltd , Dhaka , Bangladesh

Tagged with: , ,
Posted in JAVA

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: