Objective: To implement page-replacement algorithms used by the operating system
ID: 3702025 • Letter: O
Question
Objective: To implement page-replacement algorithms used by the operating system.
Background: If total memory requirements exceed the physical (main) memory, then it is necessary to replace pages from memory to free frames for new pages. Various page-replacement algorithms exist. Three common algorithms are First-In-First-Out (FIFO), Optimal (OPT), and Least-Recently-Used (LRU).
Project Task: Write a program (in Java) that implements the FIFO, OPT and LRU page-replacement algorithms. Use the following page-reference string:
0, 1, 2, 3, 2, 4, 5, 2, 4, 1, 6, 3, 7, 8, 3, 8, 4, 9, 7, 8, 1, 2, 9, 6, 4, 5, 0, 2, 5, 1, 9
where page numbers range from 0 to 9. Assume that the number of page frames is 4. Implement these three replacement algorithms, and record the number of page faults incurred by each algorithm. Assume that demand paging is used, i.e., all page frames are initially free. To ensure that your program produces correct output, you can calculate the numbers of page faults by hand and compare them with the outputs.
Explanation / Answer
FIFO
The Simplest page replacement algorithm is First In First Out (FIFO) .A First In First Out replacement algorithm (FIFO) associated with each page the time when that page was brought into memory.When a page must be replaced ,the oldest page is chosen.We can create First In First Out (FIFO) queue to hold all pages in memory.The First In First Out page replacement algorithm (FIFO) is easy to understand and program.
................................................................................................................
import java.io.*;
class FIFO
{
public static void main(String args[]) throws IOException
{
int fifo[]=new int[3];
int n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter the number of inputs :”);
n=Integer.parseInt(br.readLine());
int inp[]=new int[n];
System.out.println(“Enter the inputs:”);
for(int i=0;i<n;i++)
inp[i]=Integer.parseInt(br.readLine());
System.out.println(“—————“);
for(int i=0;i<3;i++)
fifo[i]=-1;
int Hit=0;
int Fault=0;
int j=0;
boolean check;
for(int i=0;i<n;i++)
{
check=false;
for(int k=0;k<3;k++)
if(fifo[k]==inp[i])
{
check=true;
Hit=Hit+1;
}
if(check==false)
{
fifo[j]=inp[i];
j++;
if(j>=3)
j=0;
Fault=Fault+1;
}
}
System.out.println(“HIT:”+Hit+” FAULT;”+Fault);
}
}
/*
First In First Out page replacement algorithm (FIFO) Output:
Enter the number of inputs :
10
Enter the inputs:
2
3
5
4
2
5
7
3
8
7
—————
HIT:2 FAULT;8
....................................................................................................................................................................................
Optimal (OPT)
The idea is simple, for every reference we do following :
output:-
LRU
In the least Recently Used page replacement algorithm (LRU) we use the recent past as an approximation of the near future, then we will replace the page that has not been used for the longest period of time.
In Least Recently Used page replacement algorithm (LRU) is associated with the each page the time of that page’s last use.When a page must be replaced,In LRU algorithm chooses that page has not been used for longest period of time.The In LRU algorithm (LRU) Policy is often used as page replacement algorithm and is consider to be good.The major problem is how to implement In Least Recently Used page replacement algorithm (LRU).An In LRU algorithm may require substantial hardware assistance.
import java.io.*;
class LRU
{
public static int sort(int c[])
{
int max=-1;
int temp=-1;
for(int k=0;k<3;k++)
{
if(c[k]>max)
{
max=c[k];
temp=k;
}
}
return temp;
}
public static void main(String args[])throws IOException
{
int z,m=0,hit=0,faults=0;
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
System.out.println(“enter the size of the array”);
int n=Integer.parseInt(br.readLine());
int a[]=new int[n];
int flag[]=new int[n];
System.out.println(“enter the elements”);
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(br.readLine());
flag[i]=0;
}
int b[]=new int[3];
int c[]=new int[3];
for(int i=0;i<3;i++)
{
b[i]=-1;
c[i]=0;
}
for(int i=0;i<n;i++)
{
z=a[i];
for(int j=0;j<3;j++)
{
if(z==b[j])
{
flag[i]=1;
hit=hit+1;
break;
}
}
if (flag[i]==0 && b[2]==-1)
{
for(int j=0;j<3;j++)
{
if(b[j]==-1)
{
b[j]=z;
faults=faults+1;
flag[i]=1;
break;
}
}
}
if(flag[i]==0)
{
m=sort(c);
b[m]=z;
faults=faults+1;
flag[i]=1;
for(int k=0;k<3;k++)
c[k]=c[k]+1;
c[m]=0;
}
}
System.out.println(“no of hits”+hit);
System.out.println(“no of faults”+faults);
System.out.println(“hit ratio”+(hit*100)/(hit+faults));
}
}
/*Least Recently Used page replacement algorithm (LRU) output:
enter the size of the array
10
enter the elements
2 3 5 4 2 5 7 3 8 7
no of hits 2
no of faults 8
hit ratio 20
.......................................................................................................................................
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.