package com.process.virtualstorage;
import java.util.*;
public class Optimal {
/**
* Set the number of allocated physical blocks pageNum
* Page number reference string pageQueue
*/
int pageNum;
ArrayList pageQueue;
// The only constructor of the class is allowed to directly determine the number of physical blocks per kilogram page number reference string when creating
public Optimal(int pageNum, ArrayList pageQueue) {
this.pageNum = pageNum;
this.pageQueue = pageQueue;
}
public void run() {
// Define physical blocks and initialize page missing times
ArrayList physicalBlock = new ArrayList(pageNum);
int missingNum = 0;
int index = 0;
Iterator itpQ = pageQueue.iterator();
while (itpQ.hasNext()) {
Object page = itpQ.next();
// Check whether this page is in a physical block
if (!physicalBlock.contains(page)) {
// If the page is missing, then judge based on the physical block situation.
missingNum++;
// If the physical block is sufficient, there is no need to replace it, and it is directly added to the physical block.
if (physicalBlock.size() < pageNum) {
physicalBlock.add(page);
System.out.println("Missing Page" + page + ", no need to replace, current physical block" + physicalBlock);
// When there is insufficient physical block, call the function to find the farthest used one in the future
} else {
List<Object> al = new ArrayList<Object>(pageQueue.subList(index+1, pageQueue.size()));
Object farthest = findFarthest((ArrayList) al,physicalBlock);
int farIndex = physicalBlock.indexOf(farthest);
// Replace in physical block
physicalBlock.set(farIndex, page);
System.out.println("Missing Page" + page + ", replace" + farthest + "Element, current physical block" + physicalBlock);
}
// No shortage of pages
} else {
System.out.println("No shortage of pages," + page + "In the physical block" + physicalBlock + "middle");
}
index++;
}
System.out.println("The page missing rate is" + missingNum + "/" + pageQueue.size() + " = " + missingNum* 100 / pageQueue.size() + "%");
}
// Find out the index and page number of the page that is the farthest used in the physical block.
public Object findFarthest(ArrayList alist, ArrayList pblist) {
// If this element does not exist in the subsequent list, then this will never be used. Return directly
for (Object item : pblist) {
if (!alist.contains(item))
return item;
}
// First, replace the first page by default
Object farthest = pblist.get(0);
// If the index cannot be found, an error will be reported, so the situation that cannot be found will be handled first
int last = alist.indexOf(pblist.get(0));
// traverse the entire physical block
for (Object item : pblist) {
int now = alist.indexOf(item);
// If this element is further away than the previous one, replace it
if (last < now) {
last = now;
farthest = item;
}
}
return farthest;
}
}
class TestO{
public static void main(String[] args) {
// Set the number of allocated physical blocks
int pageNum = 3;
// Initialize the page number reference string
ArrayList pageQueue = new ArrayList();
int[] array = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
for (int i :array){
pageQueue.add(i);
}
Optimal op = new Optimal(pageNum, pageQueue);
op.run();
}
}
