Design and implement a Demand Paging virtual memory simulator! It must be a text
ID: 3913351 • Letter: D
Question
Design and implement a Demand Paging virtual memory simulator! It must be a text based application (NOT a GUI based one). You can use the C/C++ or Java programming language. The following algorithms must be implemented: FIFO, OPT, LRU and LFU. The application must simulate the execution of each of these algorithms on a hypothetical computer having only N physical frames (numbered from 0 to N-1, N<8), assuming that the single process that is running has a virtual memory of ten frames (numbered from 0 to 9). The number N should be a number provided in the command line as an argument. The algorithms will be simulated based on a reference string (a sequence of pages that are to be accessed) that will be either read from the keyboard or randomly generated.
THE SIMULATION MUST FOLLOW THE ANIMATED EXAMPLES FROM THE ONLINE MODULE 3 AS CLOSE AS POSSIBLE IN ALL ASPECTS !!!
The program should be menu-based and the menu will keep the user in a loop containing the following options:
0 – Exit Will exit the program
1 – Read reference string A reference string will be read from the keyboard and stored in a buffer. Each value of the reference string will be verified and validated (or rejected). Using option 1 again will result in overwriting the old reference string.
2 – Generate reference string A reference string will be randomly generated; the length of the reference string will be given by the user interactively. The string will be stored in a buffer. Using option 2 more than once will result in overwriting the old reference string.
3 – Display current reference string Will display the stored reference string; if there is no reference string stored yet, an error message will be displayed.
4 – Simulate FIFO Will simulate the step by step execution of the FIFO algorithm using the stored reference string; if there is no reference string stored yet, an error message must be displayed. The user will press a key after each step of the simulation to continue the simulation. The total number of faults will be displayed at the end of the simulation.
5 – Simulate OPT Will simulate the step by step execution of the OPT algorithm using the stored reference string; if there is no reference string stored yet, an error message must be displayed. The user will press a key after each step of the simulation to continue the simulation. The total number of faults will be displayed at the end of the simulation.
6 – Simulate LRU Will simulate the step by step execution of the LRU algorithm using the stored reference string; if there is no reference string stored yet, an error message must be displayed. The user will press a key after each step of the simulation to continue the simulation. The total number of faults will be displayed at the end of the simulation.
7 – Simulate LFU Will simulate the step by step execution of the LFU algorithm using the stored reference string; if there is no reference string stored yet, an error message must be displayed. The user will press a key after each step of the simulation to continue the simulation. The total number of faults will be displayed at the end of the simulation.
Selecting a different option will result in an error message but the user will NOT exit the loop!
Deliverables:
1. The source code of the project
2. A report document (report.doc/report.pdf/…) containing an introduction and an overview of the project, then a comprehensive description of the design and the implementation of your project.
3. A test document (test1.doc/ test1.pdf/ …) containing screensots that show the execution of the 4 algorithms using the inputs from HW6. Three screenshots are required for each algorithm: one that shows the beginning of the simulation, one in the middle of the simulation and one showing the end of the simulation.
4. A test document (test2.doc/ test2.pdf/ …) containing screensots that show the execution of the 4 algorithms using the following inputs: N=5, ref. string is: 0 1 2 3 4 5 6 7 8 9 0 9 1 8 2 7 3 6 4 5 Three screenshots are required for each algorithm: one that shows the beginning of the simulation, one in the middle of the simulation and one showing the end of the simulation.
Explanation / Answer
import java.util.ArrayList;
// Class PageReplacementPager definition
public class PageReplacementPager
{
// For frame of [0-3]
private int pFrames = 4;
// For virtual frame [0-7]
private int vFrames = 8;
// Sequence of pages to be read
private String sequenceReferenceString;
// For types 0 = FIFO, 1 = OPT, 2 = LRU
private int pagingType;
// For number of available frames
private int totalAvaiableFrames = 4;
// To store number of page fault
private int totalPageFaults = 0;
// Constructor to set the reference string and algorithm type
public PageReplacementPager(String refString, int pType)
{
sequenceReferenceString = refString;
pagingType = pType;
this.describe();
}// End of constructor
// Method to describe - mostly for debugging
private void describe()
{
System.out.println("START: type " + pagingType + "/Paging on " + this.sequenceReferenceString);
}// End of method
// Method to execute the solution
public void executeSimulation()
{
// Checks the type of replacement
switch (this.pagingType)
{
// FIFO
case 0:
// Calls the method for First in First out page replacement
FIFO(this.sequenceReferenceString);
break;
// OPT
case 1:
// Calls the method for Optimal page replacement
OPT(this.sequenceReferenceString);
break;
// LRU
case 2:
// Calls the method for List Recently Used page replacement
LRU(this.sequenceReferenceString);
break;
default:
System.out.println("Invalid type!");
}// End of switch
// Displays the result
System.out.println("**************************** FINAL RESULTS ********************************************");
System.out.println(" " + "Processing completed: " + this.sequenceReferenceString.length() + " pages processed.");
System.out.println(" " + "Total faults: " + this.totalPageFaults);
System.out.println("*********************************************************************************");
}// End of method
// First In First Out algorithm using the stored reference
void FIFO(String rsData)
{
// Set up array for physical frames of type integer
ArrayList <Integer>physicalFrames = new ArrayList<Integer>();
// Adds -1
physicalFrames.add(-1);
physicalFrames.add(-1);
physicalFrames.add(-1);
physicalFrames.add(-1);
int loopFaultNo;
int victimFrameNo;
// Loops each vFrame (character in string) referenced to process
for (int counter = 0; counter < this.sequenceReferenceString.length(); counter++)
{
loopFaultNo = 0;
victimFrameNo = -1;
// Convert current reference to integer
int currentPage = Integer.parseInt(Character.toString(this.sequenceReferenceString.charAt(counter)));
Integer integerCurrentPage = new Integer(currentPage);
// Displays the information
System.out.println("Processing frame " + currentPage + " (frame " + counter + " of " + this.sequenceReferenceString.length() + ")");
// Checks if there are null pFrames add to that (also make sure it isn't already in there)
if (this.totalAvaiableFrames > 0 && (!physicalFrames.contains(integerCurrentPage)))
{
// adds the item to physical frame push simulate
physicalFrames.set(3, physicalFrames.get(2));
physicalFrames.set(2, physicalFrames.get(1));
physicalFrames.set(1, physicalFrames.get(0));
physicalFrames.set(0, currentPage);
loopFaultNo = 1;
// Increase the number of page fault by one
this.totalPageFaults++;
// Decrease the number of available frame by one
this.totalAvaiableFrames--;
}// End of if condition
// Otherwise
else
{
// Checks if physical frame index of current page is less than zero
if (physicalFrames.indexOf(currentPage) < 0)
{
// or No Match, time to make a victim and page fault
victimFrameNo = Integer.parseInt(physicalFrames.get(3).toString());
physicalFrames.set(3, physicalFrames.get(2));
physicalFrames.set(2, physicalFrames.get(1));
physicalFrames.set(1, physicalFrames.get(0));
physicalFrames.set(0, currentPage);
loopFaultNo = 1;
// Increase the number of page faults by one
this.totalPageFaults++;
}// End of if condition
}// End of else
// Display the information
System.out.print("Reference String Page: " + currentPage + " |" + physicalFrames.toString().replaceAll("-1", "-"));
// Checks if the loop fault is one display page fault
if (loopFaultNo == 1)
System.out.print(" PAGE FAULT ");
// Checks if victim frame is not -1 then display the victim frame
if (victimFrameNo != -1)
System.out.print(" VICTIM " + victimFrameNo);
System.out.print(" Press enter to continue. ");
// Try block begins
try
{
System.in.read();
}// End of try block
catch (Exception e)
{
};
} // end for each loop
} //End of method FIFO
// Optimal Page Replacement algorithm using the stored reference string
void OPT(String rsData)
{
// Set up array for physical frames
ArrayList physicalFrames = new ArrayList();
// Initializes each index position to zero
int[] futureUse = new int[4];
futureUse[0] = 0;
futureUse[1] = 0;
futureUse[2] = 0;
futureUse[3] = 0;
int loopFaultNo;
int victimFrameNo;
// Loops for each vFrame (character in string) referenced to process
for (int counter = 0; counter < this.sequenceReferenceString.length(); counter++)
{
loopFaultNo = 0;
victimFrameNo = -1;
// Convert current reference to integer
int currentPage = Integer.parseInt(Character.toString(this.sequenceReferenceString.charAt(counter)));
Integer integerCurrentPage = new Integer(currentPage);
// Displays information
System.out.println("Processing frame " + currentPage + " (frame " + counter + " of " + this.sequenceReferenceString.length() + ")"); //info
// Checks if there are null pFrames add to that (also make sure it isn't already in there)
if (this.totalAvaiableFrames > 0 && (!physicalFrames.contains(integerCurrentPage)))
{
// Loops till physical frame size
for (int c = 0; c < physicalFrames.size(); c++)
{
if (Integer.parseInt(physicalFrames.get(c).toString()) >= 0)
{
//sinceUseBit[c]+=1;
}// End of if condition
}// End of for loop
// Adds the current page to physical frame
physicalFrames.add(currentPage);
int addedat = physicalFrames.indexOf(currentPage);
loopFaultNo = 1;
// Increase the number of page fault by one
this.totalPageFaults++;
// Decrease the number of available frame by one
this.totalAvaiableFrames--;
}// End of if condition
// Otherwise
else
{
// Either do nothing if there is a match
// Determine number of future uses for each item in "physical frame" - pFrame
for (int pCounter = 0; pCounter < physicalFrames.size(); pCounter++)
{
int numOfFutureUses = 0;
// Loops till the length of the reference string
for (int rCounter = counter; rCounter < this.sequenceReferenceString.length(); rCounter++)
{
// Checks for equality
if (Integer.parseInt(physicalFrames.get(pCounter).toString())
== Integer.parseInt(Character.toString(this.sequenceReferenceString.charAt(rCounter))))
// Increase the number of future uses by one
numOfFutureUses += 1;
}// End of for loop
futureUse[pCounter] = numOfFutureUses;
}// End of for loop
// Checks if the physical frame current page is less than zero
if (physicalFrames.indexOf(currentPage) < 0)
{
// No Match, time to make a victim and page fault
int leastUsefulElement = 0;
int smallest = 7;
// Loops till physical frame size
for (int c = 0; c < physicalFrames.size(); c++)
{
// Checks if the future bits fs index position data is less than earlier smallest
if (futureUse[c] < smallest)
{
leastUsefulElement = c;
smallest = futureUse[c];
} // End of if condition
}// End of for loop
victimFrameNo = Integer.parseInt(physicalFrames.get(leastUsefulElement).toString());
physicalFrames.set(leastUsefulElement, currentPage);
loopFaultNo = 1; //for display processing
this.totalPageFaults++;
}// End of if condition
}// End of else
// Display information
System.out.print("Reference String Page: " + currentPage + " |" + physicalFrames.toString().replaceAll("-1", "-"));
// Checks if loop fault is one display page fault
if (loopFaultNo == 1)
System.out.print(" PAGE FAULT ");
// Checks if loop fault is not minus one display victim frame
if (victimFrameNo != -1)
System.out.print(" VICTIM " + victimFrameNo);
System.out.print(" Press ENTER to continue. ");
// try block
try
{
System.in.read();
}
catch (Exception e)
{
};
} // End of for each
} // End of method OPT
// List Frequently Used algorithm using the stored reference string
void LRU(String rs)
{
// Set up array for physical frames of type Integer
ArrayList <Integer>physicalFrames = new ArrayList<Integer>();
int[] sinceUse = new int[4];
// Initializes each index position to zero
sinceUse[0] = 0;
sinceUse[1] = 0;
sinceUse[2] = 0;
sinceUse[3] = 0;
int loopFaultNo;
int victimFrameNo;
// For each vFrame (character in string) referenced to process
for (int counter = 0; counter < this.sequenceReferenceString.length(); counter++)
{
loopFaultNo = 0;
victimFrameNo = -1;
// Convert current reference to integer
int currentPage = Integer.parseInt(Character.toString(this.sequenceReferenceString.charAt(counter)));
Integer integerCurrentPage = new Integer(currentPage);
// Displays information
System.out.println("Processing frame " + currentPage + " (frame " + counter + " of " + this.sequenceReferenceString.length() + ")");
// Checks if there are null pFrames add to that (also make sure it isn't already in there)
if (this.totalAvaiableFrames > 0 && (!physicalFrames.contains(integerCurrentPage)))
{
// Adds the current page to physical frame
physicalFrames.add(currentPage);
int addedat = physicalFrames.indexOf(currentPage);
sinceUse[addedat] += 1;
loopFaultNo = 1;
// Increase the page fault by one
this.totalPageFaults++;
// Decrease the number of available frame by one
this.totalAvaiableFrames--;
} // End of if
// Otherwise
else
{
// Either do nothing if there is a match
int addedat = physicalFrames.indexOf(currentPage);
// Try begins
try
{
// Increase the since user bit array addedat index position by one
sinceUse[addedat] += 1;
} // End of try
catch (Exception e)
{
}
// Checks if physical frames current page value is less than zero
if (physicalFrames.indexOf(currentPage) < 0)
{
// or No Match, time to make a victim and page fault
int leastFrequentElement = 0;
int small = 7;
// Loops till physical frame size
for (int cur = 0; cur < physicalFrames.size(); cur++)
{
// Checks since use bit current index position is less than earlier small
if (sinceUse[cur] < small)
// Update the least frequent element to cur minus one value
leastFrequentElement = cur - 1;
}// End of for loop
victimFrameNo = Integer.parseInt(physicalFrames.get(leastFrequentElement).toString());
physicalFrames.set(leastFrequentElement, currentPage);
sinceUse[leastFrequentElement] = 0;
loopFaultNo = 1;
// Increase the number of page fault by one
this.totalPageFaults++;
}// End of if condition
}// End of else
// Display information
System.out.print("Reference String Page: " + currentPage + " |" + physicalFrames.toString().replaceAll("-1", "-"));
// Checks if loop fault is one then display page fault
if (loopFaultNo == 1)
System.out.print(" PAGE FAULT ");
// Checks if victim frame is not -1 then display victim frame
if (victimFrameNo != -1)
System.out.print(" VICTIM " + victimFrameNo);
System.out.print(" Press ENTER to continue. ");
// try block
try
{
System.in.read();
}
catch (Exception e)
{
};
} // End for each
} // End of LRU
}// End of class
Sample Output:
************************ Memory Paging Menu ************************
0 – Exit
1 – Accept reference string
2 – Generate reference string
3 – Toggle display of current reference string
4 – FIFO
5 – OPT
6 – LFU
> 2
Enter how many frames to process (0 for default string):
4
-----------------------------------------------
************************ Memory Paging Menu ************************
0 – Exit
1 – Accept reference string
2 – Generate reference string
3 – Toggle display of current reference string
4 – FIFO
5 – OPT
6 – LFU
> 4
START: type 0/Paging on 7147
Processing frame 7 (frame 0 of 4)
Reference String Page: 7 |[7, -, -, -] PAGE FAULT
Press enter to continue.
Processing frame 1 (frame 1 of 4)
Reference String Page: 1 |[1, 7, -, -] PAGE FAULT
Press enter to continue.
Processing frame 4 (frame 2 of 4)
Reference String Page: 4 |[4, 1, 7, -] PAGE FAULT
Press enter to continue.
Processing frame 7 (frame 3 of 4)
Reference String Page: 7 |[4, 1, 7, -]
Press enter to continue.
**************************** FINAL RESULTS ********************************************
Processing completed: 4 pages processed.
Total faults: 3
*********************************************************************************
-----------------------------------------------
************************ Memory Paging Menu ************************
0 – Exit
1 – Accept reference string
2 – Generate reference string
3 – Toggle display of current reference string
4 – FIFO
5 – OPT
6 – LFU
> 5
START: type 1/Paging on 7147
Processing frame 7 (frame 0 of 4)
Reference String Page: 7 |[7] PAGE FAULT
Press ENTER to continue.
Processing frame 1 (frame 1 of 4)
Reference String Page: 1 |[7, 1] PAGE FAULT
Press ENTER to continue.
Processing frame 4 (frame 2 of 4)
Reference String Page: 4 |[7, 1, 4] PAGE FAULT
Press ENTER to continue.
Processing frame 7 (frame 3 of 4)
Reference String Page: 7 |[7, 1, 4]
Press ENTER to continue.
**************************** FINAL RESULTS ********************************************
Processing completed: 4 pages processed.
Total faults: 3
*********************************************************************************
-----------------------------------------------
************************ Memory Paging Menu ************************
0 – Exit
1 – Accept reference string
2 – Generate reference string
3 – Toggle display of current reference string
4 – FIFO
5 – OPT
6 – LFU
> 6
START: type 2/Paging on 7147
Processing frame 7 (frame 0 of 4)
Reference String Page: 7 |[7] PAGE FAULT
Press ENTER to continue.
Processing frame 1 (frame 1 of 4)
Reference String Page: 1 |[7, 1] PAGE FAULT
Press ENTER to continue.
Processing frame 4 (frame 2 of 4)
Reference String Page: 4 |[7, 1, 4] PAGE FAULT
Press ENTER to continue.
Processing frame 7 (frame 3 of 4)
Reference String Page: 7 |[7, 1, 4]
Press ENTER to continue.
**************************** FINAL RESULTS ********************************************
Processing completed: 4 pages processed.
Total faults: 3
*********************************************************************************
-----------------------------------------------
************************ Memory Paging Menu ************************
0 – Exit
1 – Accept reference string
2 – Generate reference string
3 – Toggle display of current reference string
4 – FIFO
5 – OPT
6 – LFU
>
0
Thanks!
-----------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.