WRITE A PROGRAM THAT IMPLEMENTS THE FIFO AND LRU PAGE REPLACEMENT ALGORITHMS. Yo
ID: 3774520 • Letter: W
Question
WRITE A PROGRAM THAT IMPLEMENTS THE FIFO AND LRU PAGE REPLACEMENT ALGORITHMS.
You may use any of the following languages for your program: C, C++, Java.
Write a program that implements the FIFO and LRU page-replacement
algorithms presented in this chapter. First, generate a random page reference
string where page numbers range from 0 to 9. Apply the
random page-reference string to each algorithm, and record the number
of page faults incurred by each algorithm. Implement the replacement
algorithms so that the number of page frames can vary as well. Assume
that demand paging is used.
Design and implement two classes—LRU and FIFO—that extend
ReplacementAlgorithm. Each of these classes will implement the
insert() method, one class using the LRU page-replacement algorithm
and the other using the FIFO algorithm.
The random page-reference string should consist of at least 10000 numbers.Using the same reference string, obtain the number of faults for each algorithm (Optimaland LRU) for each of the following number of page frames:1, 2, 3, 4, 5, 6, 7, 8.
Plot a graph of page fault frequency (y-axis) versus number of page frames (x-axis).
Draw both plots on the same graph.
Label each plot by the algorithm identifier (Optimal, LRU).Note: it is not expected that your program will produce the plot; rather, a separate application can be used to make the plot.
NEED TO HAVE-
program listing.
-table of results.
-graph
Explanation / Answer
Solution:
Code:
package replacement;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;
// Class Replacement
public class Replacement {
// Read input
static Scanner sc=new Scanner(System.in);
int no_pages, page[], no_frames, frames[], faults, count;
double rate;
// Constructor
public Replacement() throws IOException
{
// read number of pages
System.out.println("Enter number of pages");
no_pages=sc.nextInt();
page=new int[no_pages];
// read number of frames
System.out.println("Enter number of frames");
no_frames=sc.nextInt();
frames=new int[no_frames];
count=1;
}
// Function to reset the frame array
void frame_reset()
{
int j;
for(j=0;j<no_frames;j++)
frames[j]=0;
faults=0;
count=1;
}
// Page reference randomly generating
void page_reference() throws IOException
{
int i;
// Rabdomly generating the string
for(i=0;i<no_pages;i++)
{
page[i]=0 + (int)(Math.random() * ((9 - 0) + 1));
}
System.out.println("The reference string is");
// Printing the string
for(i=0;i<no_pages;i++)
{
System.out.print(page[i]);
}
System.out.println();
for(i=0;i<no_frames;i++)
frames[i]=-1;
}
// FIFO replacement
void FIFO_repacement()
{
int i,j,k=0;
// Reset the frame set
frame_reset();
boolean found=false;
for(i=0;i<no_pages;i++)
{
for(j=0;j<no_frames;j++)
{
if(page[i]==frames[j])
found=true;
}
if(found==false)
{
frames[k]=page[i];
if(k==no_frames-1)
k=0;
else
k++;
faults++;
}
display();
found=false;
}
System.out.println("Number of page faults = "+faults);
System.out.println("Fault rate = "+(faults/no_pages));
}
// LRU replacement
void LRU_replacement()
{
int i,j,dur[],max;
frame_reset();
dur=new int[no_frames];
boolean found=false;
for(i=0;i<no_pages;i++)
{
for(j=0;j<no_frames;j++)
dur[j]++;
for(j=0;j<no_frames;j++)
{
if(page[i]==frames[j])
{
found=true;
dur[j]=0;
}
}
if(found==false)
{
max=0;
for(j=0;j<no_frames;j++)
{
if(dur[j]>dur[max])
max=j;
}
frames[max]=page[i];
dur[max]=0;
faults++;
}
display();
found=false;
}
System.out.println("Number of page faults = "+faults);
System.out.println("Fault rate = "+(faults/no_pages));
}
// Disply function
void display()
{
int i;
System.out.print("Page frame "+count+" :");
for(i=0;i<no_frames;i++)
{
if(frames[i]==-1)
System.out.print(" -");
else
System.out.print(" "+frames[i]);
}
System.out.print(" o_pages");
count++;
}
public static void main(String[] args) throws IOException{
int me;
String ch;
Replacement p=new Replacement();
p.page_reference();
do
{
System.out.println("1. FIFO");
System.out.println("2. LRU");
System.out.println("Enter option");
me=sc.nextInt();
switch(me)
{
case 1: p.FIFO_repacement();
break;
case 2: p.LRU_replacement();
break;
default: System.out.println("Invalid input");
}
System.out.println("Enter Y to continue");
sc.nextLine();
ch=sc.nextLine();
}
while(ch.compareToIgnoreCase("y")==0);
}
}
Output:
run:
Enter number of pages
20
Enter number of frames
5
The reference string is
96193674245746318669
1. FIFO
2. LRU
Enter option
1
Page frame 1 : 9 0 0 0 0
o_pagesPage frame 2 : 9 6 0 0 0
o_pagesPage frame 3 : 9 6 1 0 0
o_pagesPage frame 4 : 9 6 1 0 0
o_pagesPage frame 5 : 9 6 1 3 0
o_pagesPage frame 6 : 9 6 1 3 0
o_pagesPage frame 7 : 9 6 1 3 7
o_pagesPage frame 8 : 4 6 1 3 7
o_pagesPage frame 9 : 4 2 1 3 7
o_pagesPage frame 10 : 4 2 1 3 7
o_pagesPage frame 11 : 4 2 5 3 7
o_pagesPage frame 12 : 4 2 5 3 7
o_pagesPage frame 13 : 4 2 5 3 7
o_pagesPage frame 14 : 4 2 5 6 7
o_pagesPage frame 15 : 4 2 5 6 3
o_pagesPage frame 16 : 1 2 5 6 3
o_pagesPage frame 17 : 1 8 5 6 3
o_pagesPage frame 18 : 1 8 5 6 3
o_pagesPage frame 19 : 1 8 5 6 3
o_pagesPage frame 20 : 1 8 9 6 3
o_pagesNumber of page faults = 13
Fault rate = 0
Enter Y to continue
Y
1. FIFO
2. LRU
Enter option
2
Page frame 1 : 9 0 0 0 0
o_pagesPage frame 2 : 9 6 0 0 0
o_pagesPage frame 3 : 9 6 1 0 0
o_pagesPage frame 4 : 9 6 1 0 0
o_pagesPage frame 5 : 9 6 1 3 0
o_pagesPage frame 6 : 9 6 1 3 0
o_pagesPage frame 7 : 9 6 1 3 7
o_pagesPage frame 8 : 9 6 4 3 7
o_pagesPage frame 9 : 2 6 4 3 7
o_pagesPage frame 10 : 2 6 4 3 7
o_pagesPage frame 11 : 2 6 4 5 7
o_pagesPage frame 12 : 2 6 4 5 7
o_pagesPage frame 13 : 2 6 4 5 7
o_pagesPage frame 14 : 2 6 4 5 7
o_pagesPage frame 15 : 3 6 4 5 7
o_pagesPage frame 16 : 3 6 4 1 7
o_pagesPage frame 17 : 3 6 4 1 8
o_pagesPage frame 18 : 3 6 4 1 8
o_pagesPage frame 19 : 3 6 4 1 8
o_pagesPage frame 20 : 3 6 9 1 8
o_pagesNumber of page faults = 12
Fault rate = 0
Enter Y to continue
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.