/* 
 * PagingAlgorithm.java (Implements Paging Algorithm System for all type of
 *                       page replacement algorithms.).
 *
 * Written by : Nitin  Motgi (nmotgi@cs.ucf.edu)
 *
 * Portions copyright(c) 2001 to School of Electrical Engineering and 
 * Computer Science, UCF, Orlando.                   
 *                                    
 * Use and distribution of this source code are strictly governed by 
 * terms and conditions set by the authors.
 * 
 * $Id : PagingAlgorithm.java, v1.0.0 03/01/2001. $
 *
 * ASSUMPTION : If the page that it is trying to read is "FREE", then
 *              it will report "overwriting -1" in the output.
 *
 * Revision History:
 *
 * 1. Created basic structure           Nitin,        v1.0.0  03/01/2001.
 * 2. Added Documentation.              Nitin,        v1.0.1  03/01/2001.
*/

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


abstract public class PagingAlgorithm{
 public Vector FrameList;           /* Contains the frame list that are in
				       Memory.*/
 public Vector ProgramList;         /* Keeps Pages tables and other 
				       information for currently loaded
				       program.*/
 public int    nNoOfFrames;         /* Gives the total number of frames.*/
 public int    nCurrentPrograms;    /* Count of no of programs in memory.*/    
 public int    nCurrentPagesInMem;  /* Number of Pages that are in the     
				       frames.*/ 
 public boolean bDebug;             /* Tells whether Debug is on/off.*/    
 public int    nPageFault;          /* Counts number of page faults.*/
 public int nGlobalCount;           /* Used for LRU.*/
 

 /* This function is used from the derived class that 
    implements this. This is made so that derived class
    can change the implementation of this function but,
    the base behaviour of the system remains same.*/
 abstract public int getVictim(int nProgName);

 /* This function is called from the Derived class to construct
    this object completely in it's constructor.*/
 public void Create(){
  FrameList = new Vector();         /* Create a new Vector List.*/    
  ProgramList = new Vector();       /* Create a new Program List.*/
  nCurrentPrograms = 0;             /* # of pg. in memory is RESET.*/
  nPageFault = 0;                   /* # of page faults is reset.*/    
  nCurrentPagesInMem = 0;           /* current loaded programs.*/    
  nGlobalCount = 0;
  __CreateFrameStructure();         /* Create all the frames in mem.*/
 }/* End of Constructor.*/

 /* This function creates frame objects as many specified in nNoOfFrames
    and updates it in FrameList.*/
 private void __CreateFrameStructure(){
  
  for(int nIndex=0; nIndex < nNoOfFrames; nIndex++){
   Frame newFrame = new Frame(); 
   FrameList.insertElementAt(newFrame,nIndex);
  }/* End of for.*/

 }/* End of __CreateFrameStructure.*/


 /* Execute "Load" Instruction. When load instruction is called a 
    Program structure is created and added to Program list. It will
    stay in list till it is not unloaded from the memory.*/
 public void load(int nProgName, int nProgSize,int nPageSize){
  int nPages;
  ProgramStruct newProg = new ProgramStruct(nProgName,nProgSize,nPageSize);
  ProgramStruct tempProg;

  /* Before adding check if the program is already in the memory.
     If so, print an error message indicating that reload not
     possible of the program structures.*/
  for(int nIndex=0; nIndex < nCurrentPrograms; nIndex++) {
   tempProg = (ProgramStruct)ProgramList.elementAt(nIndex);   
   if(tempProg.nProgName == nProgName){
    System.out.println("Loading failed : Program already in memory.");
    return;
   }/* End if.*/
  }/* End for.*/

  ProgramList.insertElementAt(newProg,nCurrentPrograms);
  nCurrentPrograms++;
  int nPageInFrame = (int)((nNoOfFrames - nCurrentPagesInMem) * 0.15);
  if(nPageInFrame == 0) nPageInFrame = 1;
  if(nPageInFrame > (int)(nProgSize/nPageSize))
   nPageInFrame = (int)(nProgSize/nPageSize);

  /* Will load as many pages as 10% of current frames are going to be.*/
  if(nProgSize/1000 == 0){
   if(bDebug)
    System.out.println("Loading P"+nProgName+":"+nPageInFrame+" pages in working set,"+
			nProgSize+ " of memory space.");
  }/* End if.*/
  else   
   if(bDebug)
    System.out.println("Loading P"+nProgName+":"+nPageInFrame+" pages in working set,"+
			nProgSize/1000 + "k of memory space.");
  
  int nFrameIndex;
  for(int nIndex=0; nIndex < nPageInFrame; nIndex++){

   /* Write to working set.*/
   __WriteWorkingSet(nProgName,nIndex);

   /* Get the victim page and based on it's interpretation form a opinion.*/
   nFrameIndex = getVictim(nIndex);

   /* Get the current frame status.*/
   Frame actFrame = new Frame();
   actFrame = (Frame)FrameList.elementAt(nFrameIndex);

   /* Add the page to the Dirty List.*/
   if(actFrame.bFrameStatus == true){
    if(actFrame.bDirtyBit == true){
     /* Save the Page in DirtySet for this program.*/
     __SavePage(nProgName,nFrameIndex);
     __DelFromWorkingSet(nProgName,nFrameIndex);
    }/* End if.*/
   }/* End if.*/

   /* Add the page to the Frame List.*/
   actFrame.nProgHolding = nProgName;
   actFrame.nPageHolding = nIndex;
   actFrame.bFrameStatus = true;
   actFrame.bDirtyBit = false;
   actFrame.nAccessFreq = 0;
   actFrame.lTimeStamp = nGlobalCount;
   nCurrentPagesInMem++;
  }/* End for.*/
  nGlobalCount++;
 }/* End of load.*/

 /* Saves the Dirty Page in Dirty Set for the program.*/
 private void __SavePage(int nProgName, int nPageIndex){
  ProgramStruct pgStruct = new ProgramStruct();
  boolean bFound = false;
  int nIndex;

  for(nIndex=0; nIndex < nCurrentPrograms; nIndex++){
   pgStruct = (ProgramStruct)ProgramList.elementAt(nIndex);
   if(pgStruct.nProgName == nProgName) break;
  }/* End of for.*/

  for(nIndex=0; nIndex < pgStruct.nDirtySetCount; nIndex++)
   if(pgStruct.nDirtySet[nIndex] == nPageIndex){ 
    bFound = true;
    break;
   }/* End if.*/

  if(bFound == true) return;
  pgStruct.nDirtySet[pgStruct.nDirtySetCount++] = nPageIndex;
  
 }/* End of __SavePage.*/

 /* Writes to working set. If it is not present in the working set
    it will write else it will leave it as it is.*/
 private void __WriteWorkingSet(int nProgName, int nPageIndex){
  ProgramStruct pgStruct = new ProgramStruct();
  boolean bFound = false;
  int nIndex;

  for(nIndex=0; nIndex < nCurrentPrograms; nIndex++){
   pgStruct = (ProgramStruct)ProgramList.elementAt(nIndex);
   if(pgStruct.nProgName == nProgName) break;
  }/* End of for.*/

  for(nIndex=0; nIndex < pgStruct.nWorkingSetCount; nIndex++){
   if(pgStruct.WorkingSet[nIndex] == nPageIndex){ 
    bFound = true;
    break;
   }/* End if.*/
  }/* End for.*/

  if(bFound == true) return;
  pgStruct.WorkingSet[pgStruct.nWorkingSetCount] = nPageIndex;
  pgStruct.nWorkingSetCount++;
 }/* End of __WriteWorkingSet.*/

 /* This function deletes a page for from the working set for the
    given program structure.*/
 private void __DelFromWorkingSet(int nProgName, int nPageIndex){
  ProgramStruct pgStruct = new ProgramStruct();
  boolean bFound = false;
  int nIndex;

  for(nIndex=0; nIndex < nCurrentPrograms; nIndex++){
   pgStruct = (ProgramStruct)ProgramList.elementAt(nIndex);
   if(pgStruct.nProgName == nProgName) break;
  }/* End of for.*/

  for(nIndex=0; nIndex < pgStruct.nWorkingSetCount; nIndex++)
   if(pgStruct.WorkingSet[nIndex] == nPageIndex){ 
    bFound = true;
    break;
   }/* End if.*/

  if(bFound == false) return;
  for(;nIndex < pgStruct.nWorkingSetCount-1; nIndex++){
   pgStruct.WorkingSet[nIndex] = pgStruct.WorkingSet[nIndex+1];
  }/* End for.*/
  pgStruct.nWorkingSetCount--;
 }/* End of __DelFromWorkingSet.*/



 /* This function performs read operation on the memory, if there
    is page fault it will use the method to find a victim in the page
    and continue reading.
    ASSUMPTION : If the page that it is trying to read is "FREE", then
		 it will report "overwriting -1" in the output.
    */
 public void read(int nProgName, int nPageIndex,int nAddress){
  ProgramStruct pgStruct = new ProgramStruct();
  boolean bFound = false;
  int nIndex;

  nGlobalCount++;
  for(nIndex=0; nIndex < nCurrentPrograms; nIndex++){
   pgStruct = (ProgramStruct)ProgramList.elementAt(nIndex);
   if(pgStruct.nProgName == nProgName){ 
    bFound = true;
    break;
   }/* End if.*/
  }/* End of for.*/

  boolean bDirty = false;

  if(bFound == false){
   if(bDebug)
    System.out.println("Access Violation P"+nProgName);
   return;
  }/* End if.*/

  /* Check if it is access violation.*/
  if(nAddress > pgStruct.nTotSize){
   if(bDebug)
    System.out.println("Access violation P"+nProgName);
   return;
  }/* End if.*/

  Frame thisFrame;
  if(__SearchInWorkingSet(pgStruct,nPageIndex) == false){
   nPageFault++;
   if(__SearchInDirtySet(pgStruct,nPageIndex) == true) bDirty = true;
    __WriteWorkingSet(nProgName,nPageIndex);
    int nFrameIndex = getVictim(nPageIndex);
    thisFrame = (Frame)FrameList.elementAt(nFrameIndex);

    if(thisFrame.bDirtyBit == true){
     /* Save the Page in DirtySet for this program.*/
     __SavePage(nProgName,nFrameIndex);
     if(bDebug)
     System.out.println("Page fault P"+nProgName+", saving page " + 
			 thisFrame.nPageHolding);
    }else{
     /* If the page is not dirty, then we need not save it.*/
     if(bDirty == false){
       if(bDebug == true)
	System.out.println("Page Fault P"+nProgName+", overwriting page " +
			   thisFrame.nPageHolding);
     }else{
      if(bDebug)
       System.out.println("Page Fault P"+nProgName+", reloading page " +
			   nPageIndex);
     }/* End if.*/
    }/* End else.*/
    __DelFromWorkingSet(thisFrame.nProgHolding,thisFrame.nPageHolding); 
    thisFrame.nProgHolding = nProgName;
    thisFrame.nPageHolding = nPageIndex;
    thisFrame.nAccessFreq  = 0;
    thisFrame.lTimeStamp = nGlobalCount;
    thisFrame.bFrameStatus = true;
    thisFrame.bDirtyBit = false;
   }/* End if.*/
   else
    /* This section only performs "hit".*/
   __UpdatePage(nProgName,nPageIndex,false);
 }/* End of read.*/

 /* Search for a page in the Working set for a given program.*/
 /* Return true if found else false.*/
 private boolean __SearchInWorkingSet(ProgramStruct pgStruct, int nPageIndex){
  for(int nIndex=0; nIndex < pgStruct.nWorkingSetCount; nIndex++){
   if(pgStruct.WorkingSet[nIndex] == nPageIndex) return true;
  }/* End of for.*/
  return false;
 }/* End of __SearchInWorkingSet.*/

 /* Search for a page in the DirtySet for a given program.*/
 /* Return true if found else false.*/
 private boolean __SearchInDirtySet(ProgramStruct pgStruct, int nPageIndex){
  for(int nIndex=0; nIndex < pgStruct.nDirtySetCount; nIndex++){
   if(pgStruct.nDirtySet[nIndex] == nPageIndex) return true;
  }/* End of for.*/
  return false;
 }/* End of __SearchInDirtySet.*/

 /* Updates the page with necessary data. If the bStat is true then it
    will update the dirty bit or else leave it as it is.*/
 private void __UpdatePage(int nProgName, int nPageIndex,boolean bStat){
  Frame thisFrame = new Frame();
  for(int nIndex=0; nIndex < nNoOfFrames; nIndex++){
   thisFrame = (Frame)FrameList.elementAt(nIndex);
   if(thisFrame.nProgHolding == nProgName && 
      thisFrame.nPageHolding == nPageIndex &&
      thisFrame.bFrameStatus == true){
      thisFrame.nAccessFreq++;
      thisFrame.lTimeStamp = nGlobalCount;
      if(bStat == true) thisFrame.bDirtyBit = true;
      else thisFrame.bDirtyBit = false;
      break;
   }/* End if.*/
  }/* End for.*/
 }/* End of __UpdatePage.*/

 /* This function tries to execute write for program and page specified.*/
 public void write(int nProgName, int nPageIndex,int nAddress){
  ProgramStruct pgStruct = new ProgramStruct();
  boolean bFound = false;
  int nIndex;

  nGlobalCount++;
  for(nIndex=0; nIndex < nCurrentPrograms; nIndex++){
   pgStruct = (ProgramStruct)ProgramList.elementAt(nIndex);
   if(pgStruct.nProgName == nProgName){ 
    bFound = true;
    break;
   }/* End if.*/
  }/* End of for.*/

  boolean bDirty = false;
  if(bFound == true){ 
   /* Check if it is access violation.*/
   if(nAddress > pgStruct.nTotSize){
    if(bDebug)
    System.out.println("Access violation P"+nProgName);
    return;
   }/* End if.*/

   if(__SearchInWorkingSet(pgStruct,nPageIndex) == false){
    nPageFault++;
    if(__SearchInDirtySet(pgStruct,nPageIndex) == true) bDirty = true;
    __WriteWorkingSet(nProgName,nPageIndex);
    int nFrameIndex = getVictim(nPageIndex);
    Frame thisFrame = new Frame();
    thisFrame = (Frame)FrameList.elementAt(nFrameIndex);
    __DelFromWorkingSet(thisFrame.nProgHolding,thisFrame.nPageHolding);
    if(thisFrame.bDirtyBit == true){
     /* Save the Page in DirtySet for this program.*/
     __SavePage(nProgName,nFrameIndex);
     if(bDebug)
     System.out.println("Page fault P"+nProgName+", saving page " +
			 thisFrame.nPageHolding);

    }else{
     if(bDirty == false){
       if(bDebug)
       System.out.println("Page Fault P"+nProgName+", overwriting page " +
			    thisFrame.nPageHolding);
     }else{
       if(bDebug)
       System.out.println("Page Fault P"+nProgName+", reloading page " +
			   nPageIndex);
     }/* End if.*/
    }/* End if.*/
    thisFrame.nProgHolding = nProgName;
    thisFrame.nPageHolding = nPageIndex;
    thisFrame.nAccessFreq  = 0;
    thisFrame.lTimeStamp = nGlobalCount;
    thisFrame.bFrameStatus = true;
    thisFrame.bDirtyBit = true;
   }/* End if.*/
    else
    /* This section only performs "hit".*/
    __UpdatePage(nProgName,nPageIndex,false);
  }else{
   if(bDebug)
    System.out.println("Access Violation P"+nProgName);
  }/* End if.*/
 }/* End of write.*/

 /* Unloads the program from the memory.It also frees all the frames
    that it was holding in the memory.*/
 public void unload(int nProgName){
  ProgramStruct pgStruct;
  Frame         thisFrame;
  boolean bStat = false;

  for(int nIndex=0; nIndex < nCurrentPrograms; nIndex++){
   pgStruct = (ProgramStruct)ProgramList.elementAt(nIndex);
   if(pgStruct.nProgName == nProgName){
    bStat = true;
    for(int nIndexi=0; nIndexi < pgStruct.nWorkingSetCount; nIndexi++){
     for(int nIndexj=0; nIndexj < nNoOfFrames; nIndexj++){
      thisFrame = (Frame)FrameList.elementAt(nIndexj);      
      if(thisFrame.nProgHolding == nProgName &&
	 thisFrame.nPageHolding == pgStruct.WorkingSet[nIndexi] &&
	 thisFrame.bFrameStatus == true){
	 thisFrame.bFrameStatus = false;
	 thisFrame.nProgHolding = -1;
	 thisFrame.bDirtyBit    = false;
	 thisFrame.nPageHolding = -1;
	 thisFrame.nAccessFreq  = 0;
	 thisFrame.lTimeStamp   = 0;
      }/* End if.*/
     }/* End for.*/
     __DelFromWorkingSet(nProgName,pgStruct.WorkingSet[nIndexi]);
    }/* End for.*/
    if(bDebug)
     System.out.println("P"+nProgName+" terminated.");
    ProgramList.removeElementAt(nIndex);
    nCurrentPrograms--;
    return;
   }/* End if.*/
  }/* End for.*/
  if(bStat == false)
   if(bDebug)
   System.out.println("P"+nProgName+" cannot be terminated.");
 }/* End of unload.*/
}/* End of PagingAlgorithm.*/