import java.util.ArrayList;
import java.util.List;
import utils.ListUtils;
/**
*
*
*@author cnkeysky
*
*/
public class FIFO {
public void run() {
String[] inputStr = {"1", "2", "3", "4", "2", "1", "2", "3", "5", "2", "3", "7", "6"};
// 内存块
int memory = 3;
List<String> list = new ArrayList<>();
for(int i = ; i < inputStr.length; i++){
if(i == ){
list.add(inputStr[i]);
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
if(ListUtils.find(list, inputStr[i])){
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}else{
if(list.size() < memory){
list.add(inputStr[i]);
}else{
list.remove();
list.add(inputStr[i]);
}
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}
}
}
}
}
import utils.ListUtils;
import java.util.ArrayList;
import java.util.List;
/**
* 最近最久未用置换算法
*@author cnkeysky
*
*/
public class LRU {
public static void main(String[] args) {
String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"};
// 内存块
int memory = 3;
List<String> list = new ArrayList<>();
for(int i = ; i < inputStr.length; i++){
if(i == ){
list.add(inputStr[i]);
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
if(ListUtils.find(list, inputStr[i])){
// 存在字符串，则获取该下标
int index = ListUtils.findIndex(list, inputStr[i]);
// 下标不位于栈顶时，且list大小不为1时
if(!(list.get(list.size() - 1)).equals(inputStr[i]) && list.size() != 1) {
String str = list.get(index);
list.remove(index);
list.add(str);
}
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}else{
if(list.size()>= memory) {
list.remove();
list.add(inputStr[i]);
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}else {
list.add(inputStr[i]);
System.out.println("第" + i + "次" + "访问：\t\t" + ListUtils.listToString(list));
}
}
}
}
}
}
import java.util.ArrayList;
import java.util.List;
import utils.ListUtils;
/**
*
*
*@author cnkeysky
*
*/
public class Clock {
public static void main(String[] args) {
String[] inputStr = {"6", "7", "6", "5", "9", "6", "8", "9", "7", "6", "9", "6"};
List<String> list = new ArrayList<>();
// 内存块
int memory = 3;
// 缺页次数
int count = ;
String[] clock = new String[memory];
int indexNext = ;
int index = ;
// 初始化时钟
for(int i = ; i < memory; i++) {
clock[i] = "0";
}
for(int i = ; i < inputStr.length; i++) {
int indexPre = ;
if (i == ) {
list.add(inputStr[i]);
clock[indexNext] = "1";
indexNext++;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
if(ListUtils.find(list, inputStr[i])) {
indexPre = ListUtils.findIndex(list, inputStr[i]);
if(clock[indexPre].equals("0")) {
clock[indexPre] = "1";
}
count++;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
if(list.size() < memory) {
list.add(inputStr[i]);
clock[indexNext] = "1";
indexNext++;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}else {
index = ListUtils.findZero(indexNext, clock, memory);
list.remove(index);
list.add(index, inputStr[i]);
clock[index] = "1";
indexNext = index + 1;
System.out.println("第"+ i +"次访问：\t\t" + ListUtils.listToString(list));
}
}
}
if(indexNext > memory - 1) {
indexNext = Math.abs(memory - indexNext);
}
}
System.out.println("缺页次数：" + (inputStr.length-count));
}
}
import java.util.List;
public class ListUtils {
public ListUtils() {
}
/**
* 输出
*@param list 将List转为数组并输出, out: 2, 3, 4
*@return
*/
public static String listToString(List list){
StringBuffer content = new StringBuffer();
for(int i = ; i < list.size(); i++){
content.append(list.get(i));
if(i < list.size() - 1){
content.append(",");
}
}
return content.toString();
}
/**
* 在list中查找是否有str
*@param list
*@param str
*@return
*/
public static boolean find(List<String> list, String str){
boolean flag = false;
for(String lis : list){
if(lis.equals(str)){
flag = true;
}
}
return flag;
}
/**
* 在List中查找是否有String,如果有返回下标, 否则返回 -1
*@param list
*@param str
*@return
*/
public static int findIndex(List<String> list, String str) {
int index = ;
for(String lis : list) {
if(lis.equals(str)) {
return index;
}
index++;
}
return -1;
}
public static boolean clockJudge(String[] clock, int index) {
if(clock[index].equals("0")) {
return true;
}
return false;
}
/**
*
*@param index 下标
*@param clock 时钟
*@param range 当前使用内存块
*@return
*/
public static int findZero(int index, String[] clock, int range) {
while(true) {
if(clock[index].equals("0")) {
break;
}else {
clock[index] = "0";
index++;
if(index > range-1) {
index = Math.abs(range - index);
}
}
}
return index;
}
/**
* 在数组中查找是否存在该字符串
*@param obj
*@param str
*@return
*/
public static boolean strJudge(Object[] obj, String str) {
boolean flag = false;
if(obj == null) {
return flag;
}
for(int i = ; i < obj.length; i++) {
if(str.equals(obj[i])) {
flag = true;
break;
}
}
return flag;
}
/**
* 获取二维数组中同一列的行的长度
*@param str 数据
*@param length 二维数组的列
*@param memory 内存块
*@return
*
*/
public static int findNull(Object[][] str, int length, int memory) {
int index = ;
if(str == null) {
return -1;
}
for(int i = ; i < memory; i++) {
if(str[i][length] != null) {
index = i;
}
}
return index;
}
}
