Write a program that implements the LRU (Least Recent Used) page replacement algorithm in Java, presented in the virtual memory management. Assume that demand paging is used. The reference code package is given.

Inputs: The program should accept two inputs: the size of a page-reference string and the number of page frames of the RAM. Both inputs should be variable, not hardcoded. The page-reference string has page numbers ranging from 0 to 9.

Output: The output of the program is the number of page faults and the number of page replacements incurred by the algorithm.

Based on the provided reference code package, first, generate a random page-reference string where page numbers range from 0 to 9. Then design and implement a classLRUthat extend ReplacementAlgorithm. The class will implement the insert() method using the LRU page-replacement algorithm.

There are two classes available to test your algorithm:

a. PageGeneratora class that generates page-reference strings with page numbers ranging from 0 to 9. The size of the reference string is an input of the program and passed to the PageGenerator constructor. Once a PageGenerator object is constructed, the getReferenceString() method returns the reference string as an array of integers.

b. Testused to test your LRU implementations of the ReplacementAlgorithm abstract class. Test is invoked as (if you use Java):

java Test <# of page frames>

Once you have implemented the LRU algorithm, experiment with a different number of page frames for a given reference string and record the number of page faults.

PageGenerator.java:

/**

* This class generates page references ranging from 0 .. 9

*

* Usage:

* PageGenerator gen = new PageGenerator()

* int[] ref = gen.getReferenceString();

*/

public class PageGenerator

{

private static final int DEFAULT_SIZE = 100;

private static final int RANGE = 9;

int[] referenceString;

public PageGenerator() {

this(DEFAULT_SIZE);

}

public PageGenerator(int count) {

if (count < 0)

throw new IllegalArgumentException();

java.util.Random generator = new java.util.Random();

referenceString = new int[count];

for (int i = 0; i < count; i++)

referenceString[i] = generator.nextInt(RANGE + 1);

}

public int[] getReferenceString() {

return referenceString;

}

}

ReplacementAlgorithim.java:

/**

* ReplacementAlgorithm.java

*/

public abstract class ReplacementAlgorithm

{

// the number of page faults

protected int pageFaultCount;

// the number of physical page frame

protected int pageFrameCount;

/**

* @param pageFrameCount - the number of physical page frames

*/

public ReplacementAlgorithm(int pageFrameCount) {

if (pageFrameCount < 0)

throw new IllegalArgumentException();

this.pageFrameCount = pageFrameCount;

pageFaultCount = 0;

}

/**

* @return - the number of page faults that occurred.

*/

public int getPageFaultCount() {

return pageFaultCount;

}

/**

* @param int pageNumber - the page number to be inserted

*/

public abstract void insert(int pageNumber);

}

Test.java:

/**

* Test harness for LRU page replacement algorithm

*

* Usage:

* java [-Ddebug] Test

*/

public class Test

{

public static void main(String[] args) {

PageGenerator ref = new PageGenerator(new Integer(args[0]).intValue());

int[] referenceString = ref.getReferenceString();

/** Use the LRU algorithm */

ReplacementAlgorithm lru = new LRU(new Integer(args[1]).intValue());

// output a message when inserting a page

for (int i = 0; i < referenceString.length; i++) {

//System.out.println("inserting " + referenceString[i]);

lru.insert(referenceString[i]);

}

// report the total number of page faults

System.out.println("LRU faults = " + lru.getPageFaultCount());

}

}