in.txt文件：
4 3 4 3 4 3 5 4 3 2 1 5
page.java类：
public class Page {
private int id = -1; //页号编码
private int count = 0; //存入内存中的时间记录
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public void inc() {
count++;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
}
1. 先进先出(FIFO)页面置换算法
优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。
package mysysy;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
// 页面调度算法 -- fifo
/**
* fifo 的关键是研判earlist的变化，只用记录唯一一个存入最早的页表号，替换目标就是他
*/
public class FIFO {
private static List<Integer> pageList = new ArrayList<Integer>(); //记录页访问顺序
private static int SIZE = 3; //分配虚拟内存页数
private static Page[] pages = new Page[SIZE]; //记录当前虚拟页分配情况
private static int earlist = 0; //最早调入的页号
private static int missPage = 0; //缺页次数
public static void main(String[] args) {
input();
fifo();
}
//fifo遍历
private static void fifo() {
for (int i = 0; i < pageList.size(); i++) { // 开始队列遍历
if (pagesIsFull() == false) { //虚拟内存页未满
if (search(pageList.get(i)) == false) { //判断虚拟内存 不包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
pages[earlist % SIZE].setId(pageList.get(i)); //用当前查询页 置换 最早调入的页号
earlist++;
missPage++; //缺页次数++
} else { //判断虚拟内存 包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
}
} else { // 虚拟内存页满了
if (search(pageList.get(i)) == false) { //判断虚拟内存 不包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "替换掉ID：" + pages[earlist % SIZE].getId());
pages[earlist % SIZE].setId(pageList.get(i)); //用当前查询页 置换 最早调入的页号
earlist++;
missPage++; //缺页次数++
} else { //判断虚拟内存 包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
}
}
display();
System.out.println();
}
System.out.println("查询："+pageList.size()+"次. "+"缺页："+missPage+"次. "+"缺页率："+((double)missPage/ pageList.size()));
}
//查询当前虚拟内存情况
private static void display() {
System.out.print("当前虚拟内存：");
for (int i = 0; i < pages.length; i++) {
System.out.print("\t" + pages[i].getId());
}
System.out.println();
}
//判断当前页是否满了
private static boolean pagesIsFull() {
boolean bool = true;
for (int i1 = 0; i1 < pages.length; i1++) {
if (pages[i1].getId() == -1) {
bool = false;
break;
}
}
return bool;
}
//查询是否包含该页
private static boolean search(Integer i) {
boolean bool = false;
for (int i1 = 0; i1 < pages.length; i1++) {
if (pages[i1].getId() == i) {
bool = true;
break;
}
}
return bool;
}
//读取查询顺序
private static void input() {
File file = new File("in.txt"); //读取字符文件
try {
BufferedReader br = new BufferedReader(new FileReader(file));
String line = br.readLine();
String[] splits = line.split(" ");
for (String split : splits) {
pageList.add(Integer.valueOf(split));
}
System.out.println(pageList);
} catch (Exception e) {
e.printStackTrace();
}
//初始化
for (int i = 0; i < pages.length; i++) {
pages[i] = new Page();
}
}
}
2. 最近最久未使用(LRU)置换算法
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。3
package mysysy;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
/*
最近最久未使用(LRU)置换算法
选择最近最长时间未访问过的页面予以淘汰，
它认为过去一段时间内未访问过的页面，
在最近的将来可能也不会被访问。
该算法为每个页面设置一个访问字段，
来记录页面自上次被访问以来所经历的时间，
淘汰页面时选择现有页面中值最大的予以淘汰。
LRU算法的关键是记录虚拟内存中每一个页表号的count值，每次要先选出count值最大的哪一个页表号，即为替换目标
*/
public class LRU {
private static List<Integer> pageList = new ArrayList<Integer>(); //记录页访问顺序
private static int SIZE = 3; //分配虚拟内存页数
private static Page[] pages = new Page[SIZE]; //记录当前虚拟页分配情况
private static int missPage = 0; //缺页次数
public static void main(String[] args) {
input();
lru();
}
//LRU遍历
private static void lru() {
for (int i = 0; i < pageList.size(); i++) { // 开始队列遍历
if (pagesIsFull() == false) { //虚拟内存页未满
if (search(pageList.get(i)) == false) { //判断虚拟内存 不包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
add(pageList.get(i)); //添加当前查询页
countFresh(); //更新内存表时间记录
missPage++; //缺页次数++
} else { //判断虚拟内存 包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
countFresh();
}
} else { // 虚拟内存页满了
if (search(pageList.get(i)) == false) { //判断虚拟内存 不包含当前调用页
replace(pageList.get(i)); //用当前查询页 置换 已调入最近最久未使用的页号
countFresh(); //更新内存表时间记录
missPage++; //缺页次数++
} else { //判断虚拟内存 包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
countFresh();
}
}
display();
/*for (Page page : pages) {
System.out.print(page.getCount() + "\t");
}
System.out.println();*/
System.out.println();
}
System.out.println("查询：" + pageList.size() + "次. " + "缺页：" + missPage + "次. " + "缺页率：" + ((double) missPage / pageList.size()));
}
//添加当前查询页
private static void add(Integer integer) {
for (int i = 0; i < pages.length; i++) {
if (pages[i].getId() == -1) {
pages[i].setId(integer); //更新当前位置记录页号
reset(i); //更新当前页号时间记录
break;
}
}
}
//更新当前页表编号的时间记录为0
public static void reset(int id){
pages[id].setCount(0);
}
//更新虚拟内存时间记录
private static void countFresh() {
for (int i = 0; i < pages.length; i++) {
pages[i].inc();//时间记录更新
}
}
//替换算法
private static void replace(Integer num) {
int max = pages[1].getCount(), ind = 0;
for (int i = 0; i < pages.length; i++) {
if (max < pages[i].getCount()) {
max = pages[i].getCount(); //查找到时间记录最大的那一个
ind = i;
}
}
System.out.println("当前查询id：" + num + "替换掉ID：" + pages[ind].getId());
pages[ind].setId(num); //更新当前位置记录页号
reset(ind); //更新当前页号时间记录
}
//查询当前虚拟内存情况
private static void display() {
System.out.print("当前虚拟内存：");
for (int i = 0; i < pages.length; i++) {
System.out.print("\t" + pages[i].getId());
}
System.out.println();
}
//判断当前页是否满了
private static boolean pagesIsFull() {
boolean bool = true;
for (int i1 = 0; i1 < pages.length; i1++) {
if (pages[i1].getId() == -1) {
bool = false;
break;
}
}
return bool;
}
//查询是否包含该页
private static boolean search(Integer i) {
boolean bool = false;
for (int i1 = 0; i1 < pages.length; i1++) {
if (pages[i1].getId() == i) {
bool = true;
reset(i1);
break;
}
}
return bool;
}
//读取查询顺序
private static void input() {
File file = new File("in.txt"); //读取字符文件
try {
BufferedReader br = new BufferedReader(new FileReader(file));
String line = br.readLine();
String[] splits = line.split(" ");
for (String split : splits) {
pageList.add(Integer.valueOf(split));
}
System.out.println(pageList);
} catch (Exception e) {
e.printStackTrace();
}
//初始化
for (int i = 0; i < pages.length; i++) {
pages[i] = new Page();
}
}
}
3. 最佳置换算法(OPT)
最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。
package mysysy;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
/*
最佳置换算法(OPT)
最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，
或者是在最长时间内不再被访问的页面,
这样可以保证获得最低的缺页率。
但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。
强行实现一下“向后看”，实现的关键是在已有的虚拟内存中，哪一个是下一次访问时最晚会被访问的，找到它即为替换目标。
*/
public class OPT {
private static List<Integer> pageList = new ArrayList<Integer>(); //记录页访问顺序
private static int SIZE = 3; //分配虚拟内存页数
private static Page[] pages = new Page[SIZE]; //记录当前虚拟页分配情况
private static int latest = 0;
private static int missPage = 0; //缺页次数
public static void main(String[] args) {
input();
opt();
}
//opt遍历
private static void opt() {
for (int i = 0; i < pageList.size(); i++) { // 开始队列遍历
if (pagesIsFull() == false) { //虚拟内存页未满
if (search(pageList.get(i)) == false) { //判断虚拟内存 不包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
pages[latest].setId(pageList.get(i)); //用当前查询页 置换 最早调入的页号
latest++;
missPage++; //缺页次数++
} else { //判断虚拟内存 包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
}
} else { // 虚拟内存页满了
if (search(pageList.get(i)) == false) { //判断虚拟内存 不包含当前调用页
replace(pageList.get(i), i); //用当前查询页 置换 最晚将调入的页号
} else { //判断虚拟内存 包含当前调用页
System.out.println("当前查询id：" + pageList.get(i) + "不替换.");
}
}
display();
System.out.println();
}
System.out.println("查询：" + pageList.size() + "次. " + "缺页：" + missPage + "次. " + "缺页率：" + ((double) missPage / pageList.size()));
}
//替换算法
/**
* @param num 当前查询页号
* @param ind 当前查询顺序下标
* 分三种情况
*/
private static void replace(int num, int ind) {
int cnt = 0;
int repInd = 1;
for (int i = ind+1; i < pageList.size(); i++) {
for (int j = 0; j < pages.length; j++) {
if (pageList.get(i) == pages[j].getId() || pageList.get(i) == num) { //包含
if (pages[j].getCount() == 0) {
pages[j].setCount(1);
cnt++;
if (cnt == pages.length - 1) { // 即将饱和
for (int k = 0; k < pages.length; k++) {
if (pages[k].getCount() == 0) {
repInd = k;
//替换
System.out.println("当前查询id：" + num + "替换掉ID：" + pages[repInd].getId());
pages[repInd].setId(num);
missPage++; //缺页次数++
break;
}
}
}
}
} else { //忽略
}
}
}
for (int j = 0; j < pages.length; j++) {
pages[j].setCount(0);
}
}
//查询当前虚拟内存情况
private static void display() {
System.out.print("当前虚拟内存：");
for (int i = 0; i < pages.length; i++) {
System.out.print("\t" + pages[i].getId());
}
System.out.println();
}
//判断当前页是否满了
private static boolean pagesIsFull() {
boolean bool = true;
for (int i1 = 0; i1 < pages.length; i1++) {
if (pages[i1].getId() == -1) {
bool = false;
break;
}
}
return bool;
}
//查询是否包含该页
private static boolean search(Integer i) {
boolean bool = false;
for (int i1 = 0; i1 < pages.length; i1++) {
if (pages[i1].getId() == i) {
bool = true;
break;
}
}
return bool;
}
//读取查询顺序
private static void input() {
File file = new File("in.txt"); //读取字符文件
try {
BufferedReader br = new BufferedReader(new FileReader(file));
String line = br.readLine();
String[] splits = line.split(" ");
for (String split : splits) {
pageList.add(Integer.valueOf(split));
}
System.out.println(pageList);
} catch (Exception e) {
e.printStackTrace();
}
//初始化
for (int i = 0; i < pages.length; i++) {
pages[i] = new Page();
}
}
}
版权声明：本文为qq_45134373原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。