当前位置：首页 > news >正文

【操作系统】页面置换

news 2025/7/8 8:07:22

要求：

1、任意给出一组页面访问顺序（如页面走向是1、2、5、7、5、7、1、4、3、5、6、4、3、2、1、5、2）。

2、分配给该作业一定的物理块（如3块、4块等）。

3、利用某几种页面置换算法模拟页面置换过程并计算其缺页率并分析结果。

4、通过给出特殊的页面访问顺序，分配不同的物理块，利用FIFO算法计算其缺页率，进一步理解Belady现象。

代码实现：

package test;
import java.util.*;
public class Main {private int[] pageSequence;    // 页面访问序列private int frameCount;    // 物理块数public Main(int[] pageSequence, int frameCount) {this.pageSequence = pageSequence;this.frameCount = frameCount;}public void fifo() {//FIFOSystem.out.println("FIFO算法:");Queue<Integer> queue = new LinkedList<>(); // 存放当前内存中的页面Set<Integer> set = new HashSet<>();       // 快速判断页面是否在内存中int pageFault = 0;                       // 缺页次数for (int i = 0; i < pageSequence.length; i++) {int page = pageSequence[i];System.out.print("访问页面" + page + ": ");if (set.contains(page)) {System.out.println("页面已在内存中");continue;}pageFault++;if (queue.size() < frameCount) {set.add(page);queue.add(page);System.out.println("调入页面" + page + ", 无换出");} else {                // 需要置换int outPage = queue.poll();set.remove(outPage);set.add(page);queue.add(page);System.out.println("调入页面" + page + ", 换出页面" + outPage);}}double rate = (double)pageFault / pageSequence.length;System.out.println("缺页次数: " + pageFault + ", 缺页率: " + String.format("%.2f", rate * 100) + "%");}public void lru() {//LRUSystem.out.println("LRU算法:");LinkedList<Integer> list = new LinkedList<>(); // 存放当前内存中的页面，按访问时间排序Set<Integer> set = new HashSet<>();           // 快速判断页面是否在内存中int pageFault = 0;                            // 缺页次数for (int i = 0; i < pageSequence.length; i++) {int page = pageSequence[i];System.out.print("访问页面" + page + ": ");if (set.contains(page)) {                // 页面在内存中，更新访问时间list.remove((Integer)page);list.addFirst(page);System.out.println("页面已在内存中，更新访问时间");continue;}pageFault++;if (list.size() < frameCount) {set.add(page);list.addFirst(page);System.out.println("调入页面" + page + ", 无换出");} else {                // 需要置换int outPage = list.removeLast();set.remove(outPage);set.add(page);list.addFirst(page);System.out.println("调入页面" + page + ", 换出页面" + outPage);}}double rate = (double)pageFault / pageSequence.length;System.out.println("缺页次数: " + pageFault + ", 缺页率: " + String.format("%.2f", rate * 100) + "%");}public void opt() {//OPTSystem.out.println("OPT算法:");List<Integer> frames = new ArrayList<>(); // 当前内存中的页面int pageFault = 0;                        // 缺页次数for (int i = 0; i < pageSequence.length; i++) {int page = pageSequence[i];System.out.print("访问页面" + page + ": ");if (frames.contains(page)) {System.out.println("页面已在内存中");continue;}pageFault++;if (frames.size() < frameCount) {                // 判断是否有空闲frames.add(page);System.out.println("调入页面" + page + ", 无换出");} else {int farthest = -1, replaceIdx = -1;                // 需要置换，找出未来最长时间不被访问的页面for (int j = 0; j < frames.size(); j++) {int nextUse = Integer.MAX_VALUE;for (int k = i + 1; k < pageSequence.length; k++) {if (pageSequence[k] == frames.get(j)) {nextUse = k;break;}}if (nextUse == Integer.MAX_VALUE) {replaceIdx = j;break;} else if (nextUse > farthest) {farthest = nextUse;replaceIdx = j;}}int outPage = frames.get(replaceIdx);frames.set(replaceIdx, page);System.out.println("调入页面" + page + ", 换出页面" + outPage);}}double rate = (double)pageFault / pageSequence.length;System.out.println("缺页次数: " + pageFault + ", 缺页率: " + String.format("%.2f", rate * 100) + "%");}public static void showBelady() {int[] beladySequence = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};System.out.println("Belady现象:");System.out.println("页面访问序列: " + Arrays.toString(beladySequence));// 分别用3个和4个物理块测试FIFO算法System.out.println("当物理块为3时");Main pr3 = new Main(beladySequence, 3);pr3.fifo();System.out.println("当物理块为4时");Main pr4 = new Main(beladySequence, 4);pr4.fifo();}public static void main(String[] args) {// 页面访问序列int[] sequence = {1, 2, 5, 7, 5, 7, 1, 4, 3, 5, 6, 4, 3, 2, 1, 5, 2};System.out.println("页面访问序列: " + Arrays.toString(sequence));System.out.println("当物理块为3时");Main pr = new Main(sequence, 3);pr.fifo();pr.lru();pr.opt();System.out.println("当物理块为4时");Main pr4 = new Main(sequence, 4);pr4.fifo();pr4.lru();pr4.opt();showBelady();        // Belady现象}
}