操作系统：Java实现页⾯置换算法（OPT,FIFO,LRU）
前⾔
代码有很多冗余，因为是写作业时写的，不过代码简单易懂，看看就可以改了。
置换算法介绍
页⾯置换算法（也称为页⾯淘汰算法）是⽤来选择换出页⾯的算法。
在请求页式存储管理⽅式中，由于⼀个进程运⾏的时候不是所有的页⾯都在内存中，所以会出现缺页中断。
当缺页的时候内存没有空闲的物理块时就需要换出内存中的⼀页，具体换出哪⼀页⾯是由页⾯置换算法决定的，页⾯置换算法的优劣直接影响到系统的效率
要注意把页⾯置换和连续分配⽅式中的交换区别开来，页⾯置换的单位是页⾯⽽不是整个进程，交换的单位是整个进程
当发⽣缺页中断后，系统不⼀定会执⾏页⾯置换算法。因为发⽣缺页中断仅仅说明需要执⾏的页⾯没有在
内存中，如果内存空间中还有空闲块的话，只需要⽤缺页中断处理程序把需要的页⾯从外存调⼊内存即可。不需要页⾯置换算法：只有内存中没有空闲块的时候才需要页⾯置换算法。
所以，缺页中断不⼀定导致执⾏页⾯置换算法。
1. 最佳置换算法（OPT）
在预知⼀个进程的页⾯号引⽤串的情况下，每次都淘汰以后不再使⽤的或以后最迟再被使⽤的页⾯，这种算法就是最佳置换算法
显然，最佳置换算法是最优的，具有最低的缺页率。但由于实际操作中往往⽆法事先知道以后会引⽤到所有页⾯的信息，所以最佳置换算法⽆法实现，只能作为⼀个标准来衡量其他置换算法的优劣
2. 先进先出算法（FIFO）
FIFO算法是最简单的页⾯置换算法，每次总是淘汰最先进⼊内存的页⾯，也就是将在内存存驻留时间最长的页⾯淘汰掉
该算法实现简单，⽤⼀个队列的数据结构就可以实现，将页⾯按照次序排成⼀个队列，并设置指针指向最先进⼊的页⾯，每次需要淘汰页⾯时，将指针所指的页⾯淘汰即可，不过FIFO算法可能会产⽣Belady
⼀场（缺页次数随着分配的物理块号的增加⽽增加），⽽且由于FIFO算法与进程实际运⾏规律不符，可能会选择淘汰程序经常使⽤的界⾯，实际效果不好
3. 最近最少使⽤算法（LRU）
选择最近最久没有被使⽤的页⾯予以淘汰，其思想是⽤以前的页⾯引⽤情况来预测将来会出现页⾯引⽤情况，也就是假设⼀个页⾯刚被访问，那么不久该页⾯还会被访问。即最佳置换算法是“向后看”，⽽“LRU”算法则是“向前看”
该算法可以⽤寄存器组和栈来实现，性能较好
关于算法中的judge
在考虑如何实现判断那⼀个页⾯被置换出时，原本是想通过⼀次次的遍历来得到答案，但是这样代码显得臃肿，于是我添加了⼀个和frame⼀样长度的ArrayList：judge，
在 opt 算法中，judge中的数代码页⾯在以后出现的位置，初始judge给的很⼤；
在 fifo 算法中，judge中的数代表页⾯在物理块中存在的时间，初始为0，越⼤代表存在的时间；
在 lru 算法中 judge 中的数代表没被使⽤的时间，每访问⼀个页⾯将访问时间设置为 1，没被访问的其他页⾯则加1。
如此⼀来，三种算法都是将judge对应frame中最⼤的替换出去（就是说三种算法有冗余，还请各位⾃⼰修改修改^ - ^。
代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/*
* 中北⼤学
* ⼤数据学院
* 数据科学与⼤数据技术
* 19070542 1907040446
* */
public class Page_replace {
// 最佳置换算法
// opt 最佳页⾯置换算法
static void opt(ArrayList<Integer> frame, ArrayList<Integer> page) {
System.out.println("============最佳页⾯置换算法============");
// 框和页⾯长度
int n_f = frame.size();
int n_p = page.size();
// 缺页
int n_lack = n_f;
// 判断块：初始每个块对应的页⾯很⼤
ArrayList<Integer> judge = new ArrayList<Integer>(n_f);
for (int i = 0; i < n_f; i++) {
judge.add(99);
}
for (int i = 0; i < n_p; i++) {
System.out.(i) + "===");
if (i < n_f) {
// 预装⼊
frame.set(i, (i));
System.out.println(frame);
} else {
if ((i))) {
// 页⾯已经存在在物理快中
System.out.println("页⾯已经存在于物理块");
} else {
// 更新往后页⾯第⼀次出现的位置
for (int j = 0; j < 3; j++) {
int index = 99;
for (int k = i + 1; k < n_p; k++) {
if ((j) == (k)) {
index = k;
break;
}
}
// 更新（
judge.set(j, index);
}
// 根据出现最后的（即judge对应最⼤的）替换
int index_max = judge.indexOf(Collections.max(judge));
int rep_page = (index_max);
frame.set(index_max, (i));
System.out.print(frame);
System.out.println("  替换掉了页⾯：" + rep_page);
n_lack = n_lack + 1;
}
}
}
float p_lack = 100 * (float) n_lack / n_p;
System.out.println("===================================");  System.out.printf("缺页次数：%d\n", n_lack);
System.out.printf("缺页率： %.2f%%\n", p_lack);
System.out.println("==================================="); }
// fifo 先⾏先出算法
// fifo 先进先出置换算法
static void fifo(ArrayList<Integer> frame, ArrayList<Integer> page) {
System.out.println("============先进先出置换算法============");  // 框和页⾯长度
int n_f = frame.size();
int n_p = page.size();
// 缺页
int n_lack = n_f;
// 判断块：初始每个块对应的出现次数
// 因为在预装⼊之后才会有相应的判断
// 使⽤我将判断的状态直接设置成预装⼊之后即为 3 2 1
ArrayList<Integer> judge = new ArrayList<Integer>(n_f);
for (int i = 0; i < n_f; i++) {
judge.add(3 - i);
}
for (int i = 0; i < n_p; i++) {
System.out.(i) + "===");
if (i < n_f) {
// 预装⼊
frame.set(i, (i));
System.out.println(frame);
} else {
// 每个页⾯存在次数加1
for (int j = 0; j < n_f; j++) {
judge.set(j, (j) + 1);
}
if ((i))) {
// 页⾯已经存在在物理块中
System.out.println("页⾯已经存在于物理块");
} else {
// 根据存在最久的（即judge对应最⼤的）替换
int index_max = judge.indexOf(Collections.max(judge));
int rep_page = (index_max);
frame.set(index_max, (i));
/
/ 将新换进的存在状态设置为1
judge.set(index_max, 1);
System.out.print(frame);
System.out.println("  替换掉了页⾯：" + rep_page);
n_lack = n_lack + 1;
}
}
}
float p_lack = 100 * (float) n_lack / n_p;
System.out.println("===================================");  System.out.printf("缺页次数：%d\n", n_lack);
System.out.printf("缺页率： %.2f%%\n", p_lack);
System.out.println("==================================="); }
// lru 最近最久未使⽤算法
static void lru(ArrayList<Integer> frame, ArrayList<Integer> page) {
System.out.println("===========最近最久未使⽤算法===========");  // 框和页⾯长度
int n_f = frame.size();
int n_p = page.size();
// 缺页
int n_lack = n_f;
// 和fifo类似先设置为 3 2 1
ArrayList<Integer> judge = new ArrayList<Integer>(n_f);
for (int i = 0; i < n_f; i++) {
judge.add(3 - i);
}
for (int i = 0; i < n_p; i++) {
System.out.(i) + "===");
springboot 原理解析if (i < n_f) {
// 预装⼊
frame.set(i, (i));
System.out.println(frame);
} else {
// 每个页⾯存在次数加1
for (int j = 0; j < n_f; j++) {
judge.set(j, (j) + 1);
}
if ((i))) {
// 页⾯已经存在在物理块中
System.out.println("页⾯已经存在于物理块");
// 这⼀步fifo没有
// 将页⾯的使⽤重置为1
judge.set(frame.(i)), 1);
} else {
// 根据最久未使⽤的（即judge对应最⼤的）替换
int index_max = judge.indexOf(Collections.max(judge));
int rep_page = (index_max);
frame.set(index_max, (i));
// 将新换进的使⽤状态设置为1
judge.set(index_max, 1);
System.out.print(frame);
System.out.println("  替换掉了页⾯：" + rep_page);
n_lack = n_lack + 1;
}
}
}
float p_lack = 100 * (float) n_lack / n_p;
System.out.println("===================================");
System.out.printf("缺页次数：%d\n", n_lack);
System.out.printf("缺页率： %.2f%%\n", p_lack);
System.out.println("===================================");
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输⼊分配给该作业的物理页框块数：");
int n_frame = Int(); // 物理页框数
ArrayList<Integer> frame = new ArrayList<Integer>(n_frame);
for (int i = 0; i < n_frame; i++) {
frame.add(-1);
}
System.out.print("请输⼊该作业的页⾯⾛向：");
String inputPages = Line();
String[] split = inputPages.split("\\s+|,|，");
int n_page = split.length; // 作业的页⾯⾛向总次数
ArrayList<Integer> page = new ArrayList<Integer>(n_page); // 作业的页⾯⾛向  for (int i = 0; i < n_page; i++) {
page.add(Integer.parseInt(split[i]));
}
scanner.close();
// 测试输⼊
// 3
// 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
opt(frame, page);
fifo(frame, page);
lru(frame, page);
}
}
结果

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。