The second programming was implementing three replacement policy(FIFO, LRU, RANDOM) and calculate the hit ratio for different block sizes and show its result on our monitor and output.txt
There are hints
Hints:
LRU - This policy can be implemented easily with a
stack of the same size of the frame. The head of the stack or queue should hold
the most recently used address. If there is a hit on an item in the frame then
that address should be moved to the head of the stack
FIFO – This policy can be most easily
implemented with a queue of fixed length. If there is write to the cache frame
then the new address would be added to the queue and any items on the queue
exceeding the frame size should be removed.
Random – A simple array will suffice for this policy.
When writing to the cache frame just randomly generates an index of the array
to write to.
For example if the address string is:
1
|
2
|
4 | 2 | 5 | 1 | 2 | 8 | 9 | 2 | 4 |
5
| 7 | 9 | 1 | 9 | 3 | 7 | 9 | 5 | 8 |
4
|
3
|
If there are 3 frames, and the replacement policy is FIFO,
you use a queue and output could show:
i = 0:
|
1
|
2
|
4 | 4 | 5 | 1 | 2 | 8 | 9 | 9 | 4 | 5 | 7 | 9 | 1 | 1 | 3 | 7 | 9 |
5
|
8 | 4 |
3
|
i = 1:
|
1
|
2
|
2 | 4 | 5 | 1 | 2 | 8 | 8 |
9
|
4
|
5
|
7
|
9
|
9
|
1
|
3
|
7
|
9
|
5
|
8
|
4
|
|
i = 2:
|
1
|
2
|
2
|
4 | 5 | 1 | 2 | 2 |
8
|
9 |
4
|
5
|
7
|
7
|
9
|
1
|
3
|
7
|
9
|
5
|
8
|
||
Hits:
|
*
|
*
|
Total = 23
Hit = 3
Hit ratio = 3/23 = 0.13043478260869565
And there are 3 frames, and the replacement policy is LRU, you
use a stack and output could show:
i = 0:
|
1
|
2
|
4 |
2
|
5
|
1
|
2
|
8
|
9
|
2
|
4
|
5
|
7
|
9
|
1
|
9
|
3
|
7
|
9
|
5
|
8
|
4
|
3
|
i = 1:
|
1
|
2
|
4
|
2
|
5
|
1
|
2
|
8
|
9
|
2
|
4
|
5
|
7
|
9
|
1
|
9
|
3
|
7
|
9
|
5
|
8
|
4
|
|
i = 2:
|
1
|
1
|
4
|
2
|
5
|
1
|
2
|
8
|
9
|
2
|
4
|
5
|
7
|
7
|
1
|
9
|
3
|
7
|
9
|
5
|
8
|
||
Hits:
|
*
|
*
|
*
|
*
|
*
|
Total = 23
Hit = 5
Hit ratio = 5/23 = 0.21739130434782608
Objective:
To see the effect frame size has on different replacement
policies. Learn how to do simulation of cache performance. Use the simulator to compare the hit
ratio for cache with different block sizes and replacement strategies. Write a report describing the results of
FIFO, LRU and RANDOM replacement policy simulations for various numbers of possible
addresses, and frame sizes.
Written By : Hun Wie (Theo)
/**
* @author Hun Wie <skyhuni82@hotmail.com>
* @CS147 Prof. Sin-Min Lee
* @date 2011.04.26
*/
package fifo;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.*;
/**
* This program implemented FIFO,LRU, and Random replacement policy and user choose either manual input or
* random input, and print out to monitor as well as to output.txt
*/
public class Main {
public static void main(String[] args) {
// TODO code application logic here
int numberOfAddress =0;
numberOfAddress = getNumberOfAddress(numberOfAddress);
int frame = 0;
frame = getFrame(frame);
String replacementInput = getReplacementPolicy();
// System.out.println("You will use FIFO replacement policy");
int inputArray [] ={};
inputArray = getInputSource(inputArray, numberOfAddress);
int [][] arrayForEachPosition = new int[frame][inputArray.length];
int[] asterisk = new int [inputArray.length];
int hit = 0;
if (replacementInput.equals("F"))
{
System.out.println("You will use FIFO replacement policy");
hit = putInQueueFifo( inputArray,frame, arrayForEachPosition, asterisk);
}
else if(replacementInput.equals("L"))
{
System.out.println("You will use LRU replacement policy");
hit = putInQueueLru ( inputArray, frame, arrayForEachPosition, asterisk);
}
else if(replacementInput.equals("R"))
{
System.out.println("You will use Random replacement policy");
hit = putInQueueRandom ( inputArray, frame, arrayForEachPosition, asterisk);
}
printOutQueue(inputArray, frame, arrayForEachPosition, asterisk, hit);
}
/**
* getReplacementPolicy method get the method, FIFO, LRU, or Random
* @return inputSource input method
*/
static String getReplacementPolicy()
{
Scanner in = new Scanner(System.in);
System.out.print("Which replacement policy would you like to use? F for FIFO, L for LRU, R for Random: ");
String inputSource = in.nextLine();
while(!inputSource.toUpperCase().equals("F") && !inputSource.toUpperCase().equals("L")
&& !inputSource.toUpperCase().equals("R"))
{
{
System.out.print("You entered invalid input. Enter again. F for FIFO, L for LRU, R for Random: ");
inputSource = in.nextLine();
}
if (inputSource.toUpperCase().equals("F"))
{
System.out.println("You will use FIFO replacement policy");
}
else if (inputSource.toUpperCase().equals("L"))
{
System.out.println("You will use LRU replacement policy");
}
else if (inputSource.toUpperCase().equals("R"))
System.out.println("You will use Random replacement policy");
else
;
}
return inputSource.toUpperCase();
}
/**
* getInputSource method gets input method either for user input or random input
*
* @param inputArray[] empty array of address
* @param numberOfAddress maximum number of address user can input
* @return inputArray[] filled array of address
*/
static int [] getInputSource(int []inputArray, int numberOfAddress)
{
Scanner in = new Scanner (System.in);
System.out.print("Which input source would like to use? a / A for user input b / B for random input:");
String inputSource = in.nextLine();
int copyInputArray[]; // for invalid input of user
int copyCheckNumber; // check if copyCheckNumber is same as numberOfAddress
while(!inputSource.toUpperCase().equals("A") && !inputSource.toUpperCase().equals("B"))
{
System.out.print("You entered invalid input. Enter again. a / A for user input b / B for random input:");
inputSource = in.nextLine();
}
if (inputSource.toUpperCase().equals("A"))
{
copyInputArray = new int [ numberOfAddress];
copyCheckNumber = getAddress( copyInputArray, numberOfAddress );
inputArray = new int[copyCheckNumber];
//store returned array from user into inputArray
for ( int j = 0; j < copyCheckNumber; j++)
{
// System.out.print(copyInputArray[i]);
inputArray[j] = copyInputArray[j];
}
}
//randon input address
else
{
int number = 0;
boolean isCorrect = false; // Assume an error
while (!isCorrect) { // loop while the entered value > 1
try {
System.out.print("How many addresses should be generated? It should be <="+ numberOfAddress+" :");
number = in.nextInt();
if ( number <= numberOfAddress && number >=1)
{
isCorrect = true; // integer has been entered
}
else
{
System.out.print("You entered wrong number.Enter again.");
in.nextLine();
}
}
catch (Exception e)
{
System.out.println("You entered wrong input");
in.nextLine();
}
}
inputArray = new int [ number];
getRandomAddress( inputArray, number);
}
return inputArray;
}
/** getNumberOfAddress method gets the maximum number of address user would
* like to enter
*
* @param numberOfAddress empty number
* @return numberOfAddress filled maximum number of address user can input
*/
static int getNumberOfAddress(int numberOfAddress){
Scanner in = new Scanner (System.in);
boolean isCorrect = false; // Assume an error
while (!isCorrect) { // loop while the entered value > 1
try {
System.out.print("Enter the number of possible address > 0 : ");
numberOfAddress = in.nextInt();
if ( numberOfAddress > 1)
{
isCorrect = true; // integer has been entered
}
else
{
System.out.print("You entered number <= 0 ");
isCorrect = false;
}
}
catch (Exception e)
{
System.out.println("You entered wrong input");
in.nextLine();
}
}//end of while
return numberOfAddress;
}
/** getFrame method gets frame size
*
* @param frame empty number
* @return frame filled frame size
*/
static int getFrame(int frame){
Scanner in = new Scanner (System.in);
boolean isCorrect = false; // Assume an error
while (!isCorrect) { // loop while the entered value > 1
try {
System.out.print("Enter the size of frame > 0 : ");
frame = in.nextInt();
if ( frame > 0)
{
isCorrect = true; // integer has been entered
}
else
{
System.out.print("You entered number <= 0 ");
isCorrect = false;
}
}
catch (Exception e)
{
System.out.println("You entered wrong input");
in.nextLine();
}
}//end of while
return frame;
}
/** getRandomAddress method gets random number and store it into array
*
* @param array[] empty array
* @param number maximum number of address user can input for array
*/
static void getRandomAddress(int [] array, int number)
{
Scanner in = new Scanner (System.in);
for ( int i = 0; i < number; i++ )
{
array[i] = (int)(Math.random() * 9 + 1);
}
}
/** getAddress method gets address from user input and store it into array
*
* @param array[] empty array
* @param numberOfAddress maximum number of address user can input for array
* @return numberOfAddress if user entered invalid input, return the number until
* user enters valid input, otherwise return the maximum number of address
*/
static int getAddress(int [] array, int numberOfAddress)
{
Scanner in = new Scanner (System.in);
boolean isInputValid = false;
int i = 0;
while (!isInputValid)
{
try{
System.out.print("Enter the string of address, number between 1-9 ");
array[i] = in.nextInt();
isInputValid = false;
if ( array[i] < 1 || array[i] > 9) //not number 1-9
{
System.out.println("You entered invalid address");
isInputValid = true;
array[i] = -1;
}
i++;
if ( i == numberOfAddress) // maximum number of address
{
System.out.println("You reached maximum number of address");
isInputValid = true;
}
} catch (Exception e) {
System.out.println("You entered invalid address");
in.nextLine();
isInputValid = true;
}
}
return numberOfAddress = i;
}
/**
* putInQueue method uses queue to store its queue to array for FIFO
*
* @param array[] array of address
* @param frameSize address size
* @param arrayOfEachPosition[][] to store each address
* @param asterisk[] array to represent hit
* @return hit hit number
*/
static int putInQueueFifo (int [] array, int frameSize, int[][] arrayOfEachPosition, int [] asterisk)
{
int hit =0;
boolean isContainElement = false;
Stack<Integer> queueOfIntAddress = new Stack<Integer>();
//fill stack with 0 to prevent exception when getting empty queue
for ( int i = 0; i < frameSize; i++)
{
queueOfIntAddress.add(0);
}
for ( int i = 0; i < array.length; i++){
isContainElement = queueOfIntAddress.contains(array[i]);
if(isContainElement) // check if it contains element
{
asterisk[i] = 1;
hit++;
isContainElement = false;
}
for (int column = 0; column < frameSize; column++){
isContainElement = queueOfIntAddress.contains(array[i]);
if(isContainElement) // check if it contains element
{
isContainElement = false;
}
else if(queueOfIntAddress.size() < frameSize)// < fram size
{//if queue size is less than frame size, put element into queue
queueOfIntAddress.add(array[i]);
}
else {//don't contain element, same size
queueOfIntAddress.removeElementAt(0);
queueOfIntAddress.add(array[i]);
}
}
for (int column = 0; column < frameSize; column++){
arrayOfEachPosition[column][i] = queueOfIntAddress.get(column);
}
}
return hit;
}
/**
* putInQueueLru method uses queue to store its queue to array for LRU
*
* @param array[] array of address
* @param frameSize address size
* @param arrayOfEachPosition[][] to store each address
* @param asterisk[] array to represent hit
* @return hit hit number
*/
static int putInQueueLru(int [] array, int frameSize, int[][] arrayOfEachPosition, int [] asterisk)
{
int hit =0;
boolean isContainElement = false;
Stack<Integer> queueOfIntAddress = new Stack<Integer>();
//fill stack with 0 to prevent exception when getting empty queue
for ( int i = 0; i < frameSize; i++)
{
queueOfIntAddress.add(0);
}
for ( int i = 0; i < array.length; i++){
isContainElement = queueOfIntAddress.contains(array[i]);
if(isContainElement) // check if it contains element
{
asterisk[i] = 1;
hit++;
isContainElement = false;
}
for (int column = 0; column < frameSize; column++){
int indexOfElement = 0;
isContainElement = queueOfIntAddress.contains(array[i]);
if(isContainElement) // check if it contains element
{
indexOfElement = queueOfIntAddress.indexOf(array[i]);
queueOfIntAddress.removeElementAt(indexOfElement);
queueOfIntAddress.add(array[i]);
isContainElement = false;
}
else if(queueOfIntAddress.size() < frameSize)// < fram size
{//if queue size is less than frame size, put element into queue
queueOfIntAddress.add(array[i]);
}
else {//don't contain element, same size
queueOfIntAddress.removeElementAt(0);
queueOfIntAddress.add(array[i]);
}
}
for (int column = 0; column < frameSize; column++){
arrayOfEachPosition[column][i] = queueOfIntAddress.get(column);
}
}
return hit;
}
/**
* putInQueueRandom method uses queue to store its queue to array for Random replacement policy
*
* @param array[] array of address
* @param frameSize address size
* @param arrayOfEachPosition[][] to store each address
* @param asterisk[] array to represent hit
* @return hit hit number
*/
static int putInQueueRandom(int [] array, int frameSize, int[][] arrayOfEachPosition, int [] asterisk)
{
int hit =0;
boolean isContainElement = false;
Stack<Integer> queueOfIntAddress = new Stack<Integer>();
//fill stack with 0 to prevent exception when getting empty queue
for ( int i = 0; i < frameSize; i++)
{
queueOfIntAddress.add(0);
}
for ( int i = 0; i < array.length; i++){
isContainElement = queueOfIntAddress.contains(array[i]);
if(isContainElement) // check if it contains element
{
asterisk[i] = 1;
hit++;
isContainElement = false;
}
for (int column = 0; column < frameSize; column++){
isContainElement = queueOfIntAddress.contains(array[i]);
if(isContainElement) // check if it contains element
{
isContainElement = false;
}
else if(queueOfIntAddress.size() < frameSize)// < fram size
{//if queue size is less than frame size, put element into queue
queueOfIntAddress.add(array[i]);
}
else {//don't contain element, same size
if(queueOfIntAddress.firstElement() == 0)
{
queueOfIntAddress.removeElementAt(0);
queueOfIntAddress.add(array[i]);
}
else
{
int randomIndex = (int)(Math.random() * frameSize );
queueOfIntAddress.removeElementAt(randomIndex);
// queueOfIntAddress.elementAt(randomIndex);
queueOfIntAddress.add(randomIndex, array[i]);
}
}
}
for (int column = 0; column < frameSize; column++){
arrayOfEachPosition[column][i] = queueOfIntAddress.get(column);
}
}
return hit;
}
/**
* printOutQueue method print out frame to monitor as well as to file named "output.txt"
*
* @param array[] array of address
* @param frameSize address size
* @param arrayOfEachPosition[][] to represent each address
* @param asterisk[] array to represent hit
*/
static void printOutQueue (int [] array, int frameSize, int[][] arrayOfEachPosition, int [] asterisk, int hit)
{
try{
// Create file
FileWriter fstream = new FileWriter("output.txt");
BufferedWriter out = new BufferedWriter(fstream);
//Close the output stream
for ( int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
out.write(array[i] + " ");
}
System.out.println("");
out.newLine();
for ( int i = 0; i < array.length; i++)
{
System.out.print("- ");
out.write("- ");
}
System.out.println("");
out.newLine();
for ( int j = frameSize-1; j >= 0; j-- ){
for ( int i = 0; i < array.length; i++) {
System.out.print(arrayOfEachPosition[j][i] +" ");
out.write(arrayOfEachPosition[j][i] +" ");
}
System.out.println("");
out.newLine();
}
for ( int i = 0; i < array.length; i++)
{
if(asterisk[i] == 1 && i==0)
{
System.out.print("* ");
out.write("* ");
}
else if(asterisk[i] == 1)
{
System.out.print("* ");
out.write("* ");
}
else
{
System.out.print(" ");
out.write(" ");
}
}
System.out.println("");
out.newLine();
System.out.println("Total= " + array.length);
out.write("Total= " + array.length);
out.newLine();
System.out.println("Hit= " + hit);
out.write("Hit= " + hit);
out.newLine();
System.out.println("Hit ratio= "+ hit+"/"+array.length+ "= " + (double)hit/array.length);
out.write("Hit ratio= "+ hit+"/"+array.length + "= " + (double)hit/array.length);
out.newLine();
out.close();
}catch (Exception e){//Catch exception if any
System.err.println("Error: " + e.getMessage());
}
}
}
/*1st
* Enter the number of possible address > 0 : 10
Enter the size of frame > 0 : 3
You will use FIFO replacement policy
Which input source would like to use? a / A for user input b / B for random input:b
How many addresses should be generated? It should be <=10 :10
8 1 3 3 1 2 6 1 4 9
- - - - - - - - - -
8 1 3 3 3 2 6 1 4 9
0 8 1 1 1 3 2 6 1 4
0 0 8 8 8 1 3 2 6 1
* *
Total= 10
Hit= 2
Hit ratio= 2/10= 0.2
*
* 2nd
Enter the number of possible address > 0 : 10
Enter the size of frame > 0 : 4
You will use FIFO replacement policy
Which input source would like to use? a / A for user input b / B for random input:a
Enter the string of address, number between 1-9 8
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 3
Enter the string of address, number between 1-9 3
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 2
Enter the string of address, number between 1-9 6
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 4
Enter the string of address, number between 1-9 9
You reached maximum number of address
8 1 3 3 1 2 6 1 4 9
- - - - - - - - - -
8 1 3 3 3 2 6 6 4 9
0 8 1 1 1 3 2 2 6 4
0 0 8 8 8 1 3 3 2 6
0 0 0 0 0 8 1 1 3 2
* * *
Total= 10
Hit= 3
Hit ratio= 3/10= 0.3
*
* 3rd
Enter the number of possible address > 0 : 10
Enter the size of frame > 0 : 5
You will use FIFO replacement policy
Which input source would like to use? a / A for user input b / B for random input:a
Enter the string of address, number between 1-9 8
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 3
Enter the string of address, number between 1-9 3
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 2
Enter the string of address, number between 1-9 6
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 4
Enter the string of address, number between 1-9 9
You reached maximum number of address
8 1 3 3 1 2 6 1 4 9
- - - - - - - - - -
8 1 3 3 3 2 6 6 4 9
0 8 1 1 1 3 2 2 6 4
0 0 8 8 8 1 3 3 2 6
0 0 0 0 0 8 1 1 3 2
0 0 0 0 0 0 8 8 1 3
* * *
Total= 10
Hit= 3
Hit ratio= 3/10= 0.3
*
* fourth
Enter the number of possible address > 0 : 10
Enter the size of frame > 0 : 6
You will use FIFO replacement policy
Which input source would like to use? a / A for user input b / B for random input:a
Enter the string of address, number between 1-9 8
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 3
Enter the string of address, number between 1-9 3
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 2
Enter the string of address, number between 1-9 6
Enter the string of address, number between 1-9 1
Enter the string of address, number between 1-9 4
Enter the string of address, number between 1-9 9
You reached maximum number of address
8 1 3 3 1 2 6 1 4 9
- - - - - - - - - -
8 1 3 3 3 2 6 6 4 9
0 8 1 1 1 3 2 2 6 4
0 0 8 8 8 1 3 3 2 6
0 0 0 0 0 8 1 1 3 2
0 0 0 0 0 0 8 8 1 3
0 0 0 0 0 0 0 0 8 1
* * *
Total= 10
Hit= 3
Hit ratio= 3/10= 0.3
*
* fifth
Enter the number of possible address > 0 : 8
Enter the size of frame > 0 : 3
Which replacement policy would you like to use? F for FIFO, L for LRU, R for Random: r
Which input source would like to use? a / A for user input b / B for random input:b
How many addresses should be generated? It should be <=8 :8
You will use Random replacement policy
9 6 8 1 8 9 6 7
- - - - - - - -
9 6 8 8 8 9 9 9
0 9 6 6 6 6 6 6
0 0 9 1 1 1 1 7
* *
Total= 8
Hit= 2
Hit ratio= 2/8= 0.25
* sixth
Enter the number of possible address > 0 : 11
Enter the size of frame > 0 : 3
Which replacement policy would you like to use? F for FIFO, L for LRU, R for Random: l
Which input source would like to use? a / A for user input b / B for random input:b
How many addresses should be generated? It should be <=11 :11
You will use LRU replacement policy
6 2 5 6 1 3 1 1 7 8 1
- - - - - - - - - - -
6 2 5 6 1 3 1 1 7 8 1
0 6 2 5 6 1 3 3 1 7 8
0 0 6 2 5 6 6 6 3 1 7
* * * *
Total= 11
Hit= 4
Hit ratio= 4/11= 0.36363636363636365
*
*/
This was more OO compared to the first programming assignment. :)
This was more OO compared to the first programming assignment. :)
No comments:
Post a Comment