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.

// I've finished my code, but can someone check to see if what I have follows the instructions well?

//Thanks.

package pagereplacement;

import java.io.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

public class PageReplacement { public static int sort(int c[]) //LRU { int max = -1; //LRU int temp = -1; //LRU for(int k = 0; k < 3; k++) //LRU { if(c[k] > max) //LRU { max = c[k]; //LRU temp = k; //LRU } } return temp; //LRU }

/** * @param args the command line arguments */ public static void main(String[] args) throws IOException { int fifo[] = new int[3]; //Fifo int n; //Fifo BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); //works on all Page Replacement Algorithms int frames, pointer =0, hit =0, fault = 0, ref_len; //OPT boolean isFull = false; //opt int buffer[]; //opt int reference[]; //opt int mem_layout[][]; //opt int z, m =0, ht = 0, faults =0; //LRU InputStreamReader isr = new InputStreamReader(System.in); //LRU //BufferedReader br = new BufferedReader(isr); //LRU //Prompts user to make the inputs to calculate the FIFO replacement algorithm System.out.println("FIFO CALCULATION"); //FIFO System.out.println("---------------------------------"); //FIFO System.out.println("Please enter the quantity of inputs you want to make for First In First Out (FIFO): "); //FIFO System.out.println(" "); //FIFO n = Integer.parseInt(br.readLine()); //FIFO int input[] = new int[n]; //FIFO System.out.println("Enter the inputs (Please press the 'Enter' key after you make each input): "); //FIFO //System.out.println("---------------------------------"); //FIFO System.out.println(" "); //FIFO for(int i = 0; i < n; i++) //FIFO input[i]=Integer.parseInt(br.readLine()); //FIFO //System.out.println(); for(int i = 0; i <3; i++) //FIFO fifo[i] = -1; //FIFO int Hit = 0; //FIFO int Fault =0; //FIFO int j = 0; //FIFO boolean check; //FIFO for(int i = 0; i { check =false; //FIFO for(int k = 0; k< 3; k++) //FIFO if(fifo[k] == input[i]) //FIFO { check = true; //FIFO Hit = Hit + 1; //FIFO } if(check == false) //FIFO { fifo[j] = input[i]; //FIFO j++; //FIFO if(j >= 3) //FIFO j =0; //FIFO Fault = Fault +1; //FIFO } } //Prompts user to make the inputs to calculate the OPT replacement algorithm System.out.println("---------------------------------");//OPT System.out.println(" "); System.out.println(" "); System.out.println("OPT CALCULATION");//OPT System.out.println("---------------------------------"); //OPT System.out.println("Please enter the number of Frames: "); //OPT frames = Integer.parseInt(br.readLine()); //OPT System.out.println(" "); //OPT System.out.println("Please enter the length of the reference string: "); //OPT ref_len = Integer.parseInt(br.readLine()); //OPT reference = new int[ref_len]; //OPT mem_layout = new int[ref_len][frames]; //OPT buffer = new int[frames]; //OPT for(int q = 0; q < frames; q++) //OPT buffer[q] = -1; //OPT System.out.println("Please enter the reference string (Please press the 'Enter' key after you make each input): "); //OPT //System.out.println("---------------------------------"); //OPT System.out.println(" "); //OPT for (int i = 0; i < ref_len; i++) //OPT { reference[i] = Integer.parseInt(br.readLine()); //OPT } System.out.println(); //OPT for(int i = 0; i < ref_len; i++) //OPT { int search = -1; //OPT for(int q = 0; q < frames; q++) //OPT { if(buffer[q] == reference[i]) //OPT { search = q; //OPT hit++; //OPT break; //OPT } } if(search == -1) //OPT { if(isFull) //OPT { int index[]= new int[frames]; //OPT boolean index_flag[] = new boolean[frames]; //OPT for(int q = i + 1; q < ref_len; q++) //OPT { for(int k = 0; k < frames; k++) //OPT { if((reference[q] == buffer[k]) && (index_flag[k] == false)) //OPT { index[k] = q; //OPT index_flag[k] = true; //OPT break; //OPT } } } int max = index[0]; //OPT pointer =0; //OPT if(max ==0) //OPT max = 200; //OPT for(int q = 0; q < frames; q++) //OPT { if (index[q] == 0) //OPT index[q] = 200; //OPT if(index[q] > max) //OPT { max = index [q]; //OPT pointer = q; //OPT } } } buffer[pointer] = reference[i]; //OPT fault++; //OPT if(!isFull) //OPT { pointer++; //OPT if(pointer == frames) //OPT { pointer =0; //OPT isFull = true; //OPT } } } for(int q = 0; q < frames; q++) //OPT mem_layout[i][q] = buffer[q]; //OPT } for(int i = 0; i < frames; i++) //OPT { for(int q = 0; q < ref_len; q++) //OPT System.out.printf("%3d ",mem_layout[q][i]); //OPT System.out.println(); //OPT } //Prompts user to enter the size of the array for LRU System.out.println("---------------------------------"); //LRU System.out.println(" "); System.out.println(" "); System.out.println("LRU CALCULATION"); //LRU System.out.println("---------------------------------"); //LRU System.out.println("Please enter the size of the array: "); //LRU System.out.println(" "); //LRU int p = Integer.parseInt(br.readLine()); //LRU int a[] = new int[p]; //LRU int flag[] = new int[p]; //LRU //Prompts user to enter the elements for LRU System.out.println("Please enter the elements (Please press the 'Enter' key after making each input): "); //LRU //System.out.println("---------------------------------"); //LRU System.out.println(" "); //LRU for(int i =0; i < p; i++) //LRU { a[i] = Integer.parseInt(br.readLine()); //LRU flag[i] = 0; //LRU } int b[] = new int[3]; //LRU int c[] = new int[3]; //LRU for(int i = 0; i <3; i++) //LRU { b[i] = -1; //LRU c[i] = 0; //LRU } for(int i =0; i< p; i++) //LRU { z =a[i]; //LRU for(int r =0; r<3; r++) //LRU { if(z == b[r]) //LRU { flag[i] =1; //LRU hit = hit +1; //LRU break; //LRU } } if (flag[i] == 0 && b[2] == -1) //LRU { for(int r=0; r < 3; r++) //LRU { if(b[r] == -1) //LRU { b[r] = z; //LRU faults = faults +1; //LRU flag[i] = 1; //LRU break; //LRU } } } if(flag[i] == 0) //LRU { m = sort(c); //LRU b[m] = z; //LRU faults = faults+1;//LRU flag[i] =1; //LRU for(int k = 0; k<3; k++) //LRU c[k] = c[k] +1; //LRU c[m] = 0; //LRU } } //Hits and Faults results for FIFO System.out.println("---------------------------------"); System.out.println(" "); System.out.println(" "); System.out.println("The HITS and FAULTS for FIFO"); System.out.println("---------------------------------"); System.out.println("HIT: " + Hit ); System.out.println("FAULT: " + Fault); System.out.println("---------------------------------"); System.out.println(" "); //Number of Hit Ratios in OPT System.out.println("The HITS calculation for OPT"); System.out.println("---------------------------------"); System.out.println("The number of Hits: " + hit); System.out.println("Hit Ratio: " + (float)((float)hit/ref_len)); System.out.println("The number of Faults: " + fault); System.out.println("---------------------------------"); System.out.println(" "); //Number of Hits in LRU System.out.println("The number of HITS calculated for LRU"); System.out.println("---------------------------------"); System.out.println("Number of hits: " + hit); System.out.println("Number of faults: " + faults); System.out.println("Hit ratio: " + (hit*100)/(hit + faults)); System.out.println("---------------------------------"); System.out.println(" "); } }