In this assignment, you will write a program that simulates a simple virtual mem
ID: 3575655 • Letter: I
Question
In this assignment, you will write a program that simulates a simple virtual memory system with two page replacements policies: First-In First Out (FIFO) and Least Recently Used (LRU). Your program reads an input file named “input.txt” containing a sequence of page requests (page numbers) and generates an output file named “output.txt” that shows how the input pages are mapped into physical frames.
The first line in the input file has three integers. The first integer is the number of pages, the second integer is the number of frames, and the third integer is the number of page access requests. The remaining lines in the input file are page access requests (page numbers), with each page request appearing on a separate line. In an interesting input, the number of frames will be less than the number of pages; otherwise, the problem will be trivial. Furthermore, in an interesting input, some pages will be requested multiple times (the same page number appears multiple times in the sequence). Because the number of frames is typically smaller than the number of pages, the same page may be mapped to a different frame each time it is requested.
In your simulation, assume demand paging, that is, pages are loaded into physical frames only when they are needed. So, initially, no pages are loaded, and all frames are available. If the number of frames is x, the first x pages accessed will be trivially mapped to the x frames without having to unload (replace) any pages. When a request to access the (x+1)th page arrives, your program must unload one of the x pages that have been loaded into physical frames and replace it with the new page. The selection of the page to be unloaded (replaced) depends on the page replacement policy.
Your program will implement two replacement policies: FIFO and LRU. In the FIFO policy, the first page loaded into a physical frame will be selected for unloading (replacement). In the LRU policy, the page that has not been accessed for the longest time will be selected for unloading (replacement). The latter policy may be implemented by associating with each page-table entry a time stamp indicating the latest time at which the page was accessed. The page with the smallest time stamp will then be replaced.
The output file will have one line for each page request, indicating how that page request was handled. As shown in the example below, the output file format is self- explanatory. Write your implementation in JAVA without using java swing/GUI.
Example
Here is an example input file and the corresponding output file. The input has 8 pages, 4 frames and 12 page requests.
Input:
8 4 12
4
3
4
6
1
6
4
5
2
4
6
1
Output:
FIFO
Page 4 loaded into Frame 0
Page 3 loaded into Frame 1
Page 4 already in Frame 0
Page 6 loaded into Frame 2
Page 1 loaded into Frame 3
Page 6 already in Frame 2
Page 4 already in Frame 0
Page 4 unloaded from Frame 0, Page 5 loaded into Frame 0
Page 3 unloaded from Frame 1, Page 2 loaded into Frame 1
Page 6 unloaded from Frame 2, Page 4 loaded into Frame 2
Page 1 unloaded from Frame 3, Page 6 loaded into Frame 3
Page 5 unloaded from Frame 0, Page 1 loaded into Frame 0
LRU
Page 4 loaded into Frame 0
Page 3 loaded into Frame 1
Page 4 already in Frame 0
Page 6 loaded into Frame 2
Page 1 loaded into Frame 3
Page 6 already in Frame 2
Page 4 already in Frame 0
Page 3 unloaded from Frame 1, Page 5 loaded into Frame 1
Page 1 unloaded from Frame 3, Page 2 loaded into Frame 3
Page 4 already in Frame 0
Page 6 loaded in Frame 2
Page 5 unloaded from Frame 1, Page 1 loaded into Frame 1
Explanation / Answer
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
import javax.swing.JFileChooser;
public class pgReplace {
public static void main(String[] args) throws IOException {
ArrayList<Integer> ref = new ArrayList<Integer>();
try {
Scanner filein = new Scanner(getInputFileNameFromUser());
while(filein.hasNext()) {
String frame = filein.next();
int frm = Integer.parseInt(frame);
ref.add(frm);
}
filein.close();
} catch (FileNotFoundException e) {
System.err.println("FileNotFoundException: " + e.getMessage());
}
if(!ref.isEmpty()){
int size = ref.size();
System.out.println("The length of the Reference String is: " + size);
}
Iterator<Integer> iter = ref.iterator();
while (iter.hasNext())
System.out.print(iter.next() +" ");
Integer frame[] = new Integer[ref.size()];
frame = ref.toArray(frame);
System.out.printf(" Select the Page Replacement Algorithm: ");
System.out.printf(" 1.FIFO 2.LRU ? ");
Scanner sc = new Scanner(System.in);
while (!sc.hasNextInt()) {
sc.next();
}
int ch = sc.nextInt();
switch(ch){
case 1: fifo(frame,ref.size());
break;
case 2: lru(frame,ref.size());
break;
default: System.out.printf(" Invlaid Choice");
}
}
/**Simulates LRU page replacement for given reference string
@throws IOException */
public static void lru(Integer[] page, int n) throws IOException {
int [] frame = new int[10];
int []used = new int[10];
int index = 0;
int i,j,k,temp;
int flag=0,pf=0;
BufferedWriter write = new BufferedWriter(new FileWriter("file.txt"));
PrintWriter out = new PrintWriter(write);
System.out.printf(" LRU Page Replacement");
System.out.printf(" Enter number of Frames: ");
Scanner sc = new Scanner(System.in);
while (!sc.hasNextInt()) {
sc.next(); // discard next token, which isn't a valid int
}
int nf = sc.nextInt();
for(i=0;i<nf;i++)
frame[i]= -1;
for(i=0;i<n;i++){
flag=0;
for(j=0;j<nf;j++){
if(frame[j]==page[i]){//no fault
System.out.printf(" %d: ", page[i]);
out.printf(" %d: ", page[i]);
flag=1;
break;
}
}
if(flag==0){//fault occurs
for(j=0;j<nf;j++)
used[j]=0;//all unused initially
try{
for(j = 0,temp= i-1;j < nf-1;j++,temp--){
for(k = 0;k < nf;k++){
if(frame[k]==page[temp])
used[k]=1;
}
}
}
catch(ArrayIndexOutOfBoundsException e){
}
for(j=0;j<nf;j++)
if(used[j]==0)
index=j;
frame[index]=page[i];
System.out.printf(" %d: ", page[i]);
System.out.printf("--->F ");
out.printf(" %d: ", page[i]);
out.printf("--->F ");
pf++;//no of page faults
}
for(k= nf-1;k>=0;k--)
if(frame[k] != -1){
System.out.printf(" %d",frame[k]);//print frames
out.printf(" %d",frame[k]);
}
}
System.out.printf(" Number of page faults is: %d ",pf);
out.printf(" Number of page faults is: %d ",pf);
out.close();
write.close();
}
/**Simulates FIFO page replacement for given reference string
@throws IOException */
public static void fifo(Integer[] pages, int pg) throws IOException {
int [] frame = new int[25];
int i,k,avail,count=0;
BufferedWriter write = new BufferedWriter(new FileWriter("file.txt"));
PrintWriter out = new PrintWriter(write);
System.out.printf(" FIFO Page Replacement");
System.out.printf(" Enter number of Frames: ");
Scanner sc = new Scanner(System.in);
while (!sc.hasNextInt()) {
sc.next(); // discard next token, which isn't a valid int
}
int nof = sc.nextInt();
for(i=0;i<nof;i++)
frame[i]= -1;
int j=0;
System.out.printf(" ");
out.printf(" ");
for(i=0;i<pg;i++){
System.out.printf("%d ",pages[i]);
out.printf("%d ",pages[i]);
avail=0;
for(k=0;k<nof;k++)
if(frame[k]==pages[i])
avail=1;
if (avail==0){
frame[j]=pages[i];
j=(j+1) % nof;
count++;
for(k=0;k<nof;k++)
if(frame[k]!=-1){
System.out.printf("%d",frame[k]);
out.printf("%d",frame[k]);
}
System.out.printf("-->F");
out.printf("-->F");
}
if(avail==1){
for(k=0;k<nof;k++)
if(frame[k]!=-1){
System.out.printf("%d",frame[k]);
out.printf("%d",frame[k]);
}
}
System.out.printf(" ");
out.printf(" ");
}
System.out.printf(" No of Faults: %d",count);
out.printf(" No of Faults: %d",count);
out.close();
write.close();
}
static File getInputFileNameFromUser() {
JFileChooser fileDialog = new JFileChooser();
fileDialog.setDialogTitle("Select File for Input");
int option = fileDialog.showOpenDialog(null);
if (option != JFileChooser.APPROVE_OPTION)
return null;
else
return fileDialog.getSelectedFile();
}
}