天天看点
返回

【南邮操作系统实验】页面置换算法 （FIFO、LRU、OPT）Java 版先进先出置换算法（FIFO）最近最久未使用置换算法（LRU）最佳置换算法（OPT）

页面置换算法Java版

  • 先进先出置换算法（FIFO）
  • 最近最久未使用置换算法（LRU）
  • 最佳置换算法（OPT）

帮女朋友写了份 Python版的，Python版戳这里

帮女朋友舍友写了份 C++ 版的，C++版戳这里

老样子，我做实验的原则都是不参考任何网上代码，made by myself。

可能实现的不是很好，但是至少效果达到了。

不过这次实验简单到爆了~应该怎么写都能写出来，以下为源码：

先进先出置换算法（FIFO） 

import java.util.Scanner;
import java.util.Stack;

/**
 * FIFO页面替换算法
 * Author:陆振宇
 * time:2019.11.30
 */
public class FIFO {

    int frameNum;    // 分配给该作业的物理页框数
    int[] pageFrame; // 物理页框
    int pageNum;     // 作业的页面走向总次数
    int[] page;      // 作业的页面走向
    Stack<Integer> stack = new Stack<>(); // 存放淘汰页面的栈
    // Set<Integer> set = new TreeSet<>();  // 存放淘汰页面的set集合

    private void fifoRun() {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入分配给该作业的物理页框块数：");
        this.frameNum = scanner.nextInt();     // 物理页框数

        System.out.print("请输入该作业的页面走向：");
        scanner.nextLine(); // 控制输入格式
        String inputPages = scanner.nextLine();
        String[] split = inputPages.split("\\s+|,|，");
        this.pageNum = split.length;    // 作业的页面走向总次数

        page = new int[pageNum];        // 作业的页面走向
        for (int i = 0; i < pageNum; i++) {
            this.page[i] = Integer.parseInt(split[i]);
        }

        pageFrame = new int[frameNum];     // 物理页框

        int pageMissNum = 0;   // 缺页次数
        int count = 0;
        int helpNum = 0;    // 实现 FIFO 算法
        while (count < pageNum) {

            System.out.println("第" + (count+1) + "次：");

            boolean isMiss = true;    // 判断本次是否缺页
            boolean isEmpty = true;   // 判断物理页框中是否有空位
            boolean isExist = false; // 判断物理页框中是否存在本次页面走向

            // 判断物理页框中是否已经存在本次页面走向
            for (int i = 0; i < frameNum; i++) {
                if (page[count] == pageFrame[i]) {
                    isExist = true;
                    break;
                }
            }
            // 若本次页面走向,物理页框中已存在，则直接进入下次页面走向
            if (isExist == true){
                System.out.println("本次页面走向，页框中已经存在！");
                System.out.print("目前物理页框中页面走向为：");
                for (int i : pageFrame) {
                    System.out.print(i + " ");
                }
                System.out.println();
                count++;
                continue;
            }

            // 判断物理页框有无空位
            for (int i = 0 ; i < frameNum ; i++){
                if (pageFrame[i] == 0){
                    isEmpty = true;
                    break;
                }else{
                    isEmpty = false;
                }
            }
            // 本次页面走向,物理页框中不存在，且有空位，按顺序放入
            if (isExist == false && isEmpty == true){
                for (int i = 0; i < frameNum; i++) {
                    if (pageFrame[i] == 0) {    // 物理页框中有空位则放入
                        pageFrame[i] = page[count];
                        break;      // 从头开始找，找到一个空位即可
                    }
                }
            }

            // 实现 FIFO 算法
            // 本次页面走向，物理页框中不存在，且物理页框中没有空位了
            if (isExist == false && isEmpty == false){
                // 此时的 pageFrame[helpNum%frameNum] 为淘汰页面
                stack.push(pageFrame[helpNum%frameNum]);   // 淘汰页面入栈
                System.out.println("本次淘汰页面：" + pageFrame[helpNum%frameNum]);
                pageFrame[helpNum%frameNum] = page[count]; // 先进先出
                helpNum++;
            }

            if (isMiss == true){  // 计算缺页次数
                pageMissNum++;
            }

            System.out.print("目前物理页框中页面走向为：");
            for (int i : pageFrame) {
                System.out.print(i + " ");
            }
            System.out.println();
            count++;
        }
        System.out.println();

        System.out.println("缺页次数：" + pageMissNum + "次");
        System.out.println("一共调用: " + pageNum + "次");
        System.out.println("缺页中断率：" + pageMissNum*1.0/pageNum*100 + "%" );
        System.out.print("淘汰页面：");
        for (Integer integer : stack) {
            System.out.print(integer + " ");
        }
    }

    public static void main(String[] args) {
        FIFO fifo = new FIFO();
        fifo.fifoRun();
    }

}

运行效果：

请输入分配给该作业的物理页框块数：3
请输入该作业的页面走向：2 3 2 1 5 2 4 5 3 2 5 2
第1次：
目前物理页框中页面走向为：2 0 0 
第2次：
目前物理页框中页面走向为：2 3 0 
第3次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 3 0 
第4次：
目前物理页框中页面走向为：2 3 1 
第5次：
本次淘汰页面：2
目前物理页框中页面走向为：5 3 1 
第6次：
本次淘汰页面：3
目前物理页框中页面走向为：5 2 1 
第7次：
本次淘汰页面：1
目前物理页框中页面走向为：5 2 4 
第8次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：5 2 4 
第9次：
本次淘汰页面：5
目前物理页框中页面走向为：3 2 4 
第10次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：3 2 4 
第11次：
本次淘汰页面：2
目前物理页框中页面走向为：3 5 4 
第12次：
本次淘汰页面：4
目前物理页框中页面走向为：3 5 2 

缺页次数：9次
一共调用: 12次
缺页中断率：75.0%
淘汰页面：2 3 1 5 2 4

最近最久未使用置换算法（LRU） 

import java.util.Scanner;
import java.util.Stack;

/**
 * LRU最近最久未使用页面置换算法
 * Author:陆振宇
 * time:2019.11.30
 */
public class LRU {
    int frameNum;    // 分配给该作业的物理页框数
    int[] pageFrame; // 物理页框
    int pageNum;     // 作业的页面走向总次数
    int[] pages;      // 作业的页面走向
    Stack<Integer> stack = new Stack<>(); // 存放淘汰页面的栈

    private void lruRun() {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入分配给该作业的物理页框块数：");
        this.frameNum = scanner.nextInt();     // 物理页框数

        System.out.print("请输入该作业的页面走向：");
        scanner.nextLine(); // 控制输入格式
        String inputPages = scanner.nextLine();
        String[] split = inputPages.split("\\s+|,|，");
        this.pageNum = split.length;    // 作业的页面走向总次数

        pages = new int[pageNum];        // 作业的页面走向
        for (int i = 0; i < pageNum; i++) {
            this.pages[i] = Integer.parseInt(split[i]);
        }

        pageFrame = new int[frameNum];     // 物理页框

        int pageMissNum = 0;   // 缺页次数
        int count = 0;
        while (count < pageNum) {

            System.out.println("第" + (count+1) + "次：");

            boolean isMiss = true;    // 判断本次是否缺页
            boolean isEmpty = true;   // 判断物理页框中是否有空位
            boolean isExist = false; // 判断物理页框中是否存在本次页面走向

            // Queue<Integer> usedPage = new LinkedList<>();   // 保存之前的页面走向
            // usedPage.offer(pages[count]);   // 将页面走向进队

            // 判断物理页框中是否已经存在本次页面走向
            for (int i = 0; i < frameNum; i++) {
                if (pages[count] == pageFrame[i]) {
                    isExist = true;
                    break;
                }
            }
            // 若本次页面走向,物理页框中已存在，则直接进入下次页面走向
            if (isExist == true){
                System.out.println("本次页面走向，页框中已经存在！");
                System.out.print("目前物理页框中页面走向为：");
                for (int i : pageFrame) {
                    System.out.print(i + " ");
                }
                System.out.println();
                count++;
                continue;
            }

            // 判断物理页框有无空位
            for (int i = 0 ; i < frameNum ; i++){
                if (pageFrame[i] == 0){
                    isEmpty = true;
                    break;
                }else{
                    isEmpty = false;
                }
            }
            // 本次页面走向,物理页框中不存在，且有空位，按顺序放入
            if (isExist == false && isEmpty == true){
                for (int i = 0; i < frameNum; i++) {
                    if (pageFrame[i] == 0) {    // 物理页框中有空位则放入
                        pageFrame[i] = pages[count];
                        break;      // 从头开始找，找到一个空位即可
                    }
                }
            }

            // 本次页面走向，物理页框中不存在，且物理页框中没有空位了
            // 实现 LRU 算法
            if (!isExist && !isEmpty){
                for (int i = 0 ; i < frameNum ; i++){
                    if (pages[count-frameNum] == pageFrame[i]){
                        stack.push(pageFrame[i]);   // 淘汰页面入栈
                        pageFrame[i] = pages[count];
                    }
                }
            }

            if (isMiss == true){  // 计算缺页次数
                pageMissNum++;
            }

            System.out.print("目前物理页框中页面走向为：");
            for (int i : pageFrame) {
                System.out.print(i + " ");
            }
            System.out.println();
            count++;
        }
        System.out.println();

        System.out.println("缺页次数：" + pageMissNum + "次");
        System.out.println("一共调用: " + pageNum + "次");
        System.out.println("缺页中断率：" + pageMissNum*1.0/pageNum*100 + "%" );
        System.out.print("淘汰页面：");
        for (Integer integer : stack) {
            System.out.print(integer + " ");
        }
    }

    public static void main(String[] args) {
        LRU lru = new LRU();
        lru.lruRun();
    }

}

运行结果：

请输入分配给该作业的物理页框块数：3
请输入该作业的页面走向：2 3 2 1 5 2 4 5 3 2 5 2
第1次：
目前物理页框中页面走向为：2 0 0 
第2次：
目前物理页框中页面走向为：2 3 0 
第3次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 3 0 
第4次：
目前物理页框中页面走向为：2 3 1 
第5次：
目前物理页框中页面走向为：2 5 1 
第6次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 5 1 
第7次：
目前物理页框中页面走向为：2 5 4 
第8次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 5 4 
第9次：
目前物理页框中页面走向为：3 5 4 
第10次：
目前物理页框中页面走向为：3 5 2 
第11次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：3 5 2 
第12次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：3 5 2 

缺页次数：7次
一共调用: 12次
缺页中断率：58.333333333333336%
淘汰页面：3 1 2 4

最佳置换算法（OPT） 

import java.util.Scanner;
import java.util.Stack;

/**
 * OPT最佳页面置换算法
 * Author:陆振宇
 * time:2019.11.30
 */
public class OPT {

    int pageFrameNum;    // 分配给该作业的物理页框数
    int[] pageFrame; // 物理页框
    int pageFrontNum;     // 作业的页面走向总次数
    int[] pages;      // 作业的页面走向
    Stack<Integer> stack = new Stack<>(); // 存放淘汰页面的栈

    private void optRun() {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入分配给该作业的物理页框块数：");
        this.pageFrameNum = scanner.nextInt();     // 物理页框数

        System.out.print("请输入该作业的页面走向：");
        scanner.nextLine(); // 控制输入格式
        String inputPages = scanner.nextLine();
        String[] split = inputPages.split("\\s+|,|，");
        this.pageFrontNum = split.length;    // 作业的页面走向总次数

        pages = new int[pageFrontNum];        // 作业的页面走向
        for (int i = 0; i < pageFrontNum; i++) {
            this.pages[i] = Integer.parseInt(split[i]);
        }

        pageFrame = new int[pageFrameNum];     // 物理页框

        int pageMissNum = 0;   // 缺页次数
        int count = 0;
        while (count < pageFrontNum) {

            System.out.println("第" + (count+1) + "次：");

            boolean isMiss = true;    // 判断本次是否缺页
            boolean isEmpty = true;   // 判断物理页框中是否有空位
            boolean isExist = false; // 判断物理页框中是否存在本次页面走向

            // 判断物理页框中是否已经存在本次页面走向
            for (int i = 0; i < pageFrameNum; i++) {
                if (pages[count] == pageFrame[i]) {
                    isExist = true;
                    break;
                }
            }
            // 若本次页面走向,物理页框中已存在，则直接进入下次页面走向
            if (isExist == true){
                System.out.println("本次页面走向，页框中已经存在！");
                System.out.print("目前物理页框中页面走向为：");
                for (int i : pageFrame) {
                    System.out.print(i + " ");
                }
                System.out.println();
                count++;
                continue;
            }

            // 判断物理页框有无空位
            for (int i = 0; i < pageFrameNum; i++){
                if (pageFrame[i] == 0){
                    isEmpty = true;
                    break;
                }else{
                    isEmpty = false;
                }
            }
            // 本次页面走向,物理页框中不存在，且有空位，按顺序放入
            if (isExist == false && isEmpty == true){
                for (int i = 0; i < pageFrameNum; i++) {
                    if (pageFrame[i] == 0) {    // 物理页框中有空位则放入
                        pageFrame[i] = pages[count];
                        break;      // 从头开始找，找到一个空位即可
                    }
                }
            }

            // 本次页面走向，物理页框中不存在，且物理页框中没有空位了
            // 实现 OPT 算法
            if (isExist == false && isEmpty == false){
                boolean isExistEle = false; // 是否存在未来不再出现的元素
                boolean isFound = false;    // 是否找到未来下标的元素
                int frameIndex = 0; // 记录的物理页框下标
                Stack<Integer> helpStack = new Stack<>(); // 辅助栈
                // 寻找将来不再出现的，存在于当前物理页框中的元素
                for (int i = 0 ; i < pageFrameNum ; i++){
                    for (int j = count ; j < pageFrontNum ; j++){
                        if (pageFrame[i] == pages[j]){  // 若当前物理页框中，不存在未来不再出现的元素
                            helpStack.push(j);  // 记录当前未来将遇见的下标
                            isFound = true;     // 找到未来下标的元素
                        }
                    }
                    // 当前物理页框中，存在未来不再出现的元素
                    if (!isFound){
                        frameIndex = i; // 记录当前物理页框
                        isExistEle = true; // 存在未来不再出现的元素
                        break;
                    }
                    isFound = false;
                }

                /*for (Integer integer : helpStack) {
                    System.out.println(integer);
                }
                System.out.println("TEST  " + frameIndex);
                System.out.println("isExistEle  " + isExistEle);
                System.out.println("isFound  " + isFound);*/

                if(isExistEle){ // 存在未来不再出现的元素
                    stack.push(pageFrame[frameIndex]); // 淘汰页面入栈
                    pageFrame[frameIndex] = pages[count];
                }else{ // 不存在未来不再出的元素
                    int t = 0;
                    for (Integer integer : helpStack) {
                        if(t < integer){
                            t = integer;
                        }
                    }
                    for (int i = 0 ; i < pageFrameNum ; i++){
                        if (pageFrame[i] == pages[t]){
                            stack.push(pageFrame[i]);  // 淘汰页面入栈
                            pageFrame[i] = pages[count];
                        }
                    }
                }
            }

            if (isMiss == true){  // 计算缺页次数
                pageMissNum++;
            }

            System.out.print("目前物理页框中页面走向为：");
            for (int i : pageFrame) {
                System.out.print(i + " ");
            }
            System.out.println();
            count++;
        }
        System.out.println();

        System.out.println("缺页次数：" + pageMissNum + "次");
        System.out.println("一共调用: " + pageFrontNum + "次");
        System.out.println("缺页中断率：" + pageMissNum*1.0/ pageFrontNum *100 + "%" );
        System.out.print("淘汰页面：");
        for (Integer integer : stack) {
            System.out.print(integer + " ");
        }
    }

    public static void main(String[] args) {
        OPT opt = new OPT();
        opt.optRun();
    }

}

运行效果：

请输入分配给该作业的物理页框块数：3
请输入该作业的页面走向：2 3 2 1 5 2 4 5 3 2 5 2
第1次：
目前物理页框中页面走向为：2 0 0 
第2次：
目前物理页框中页面走向为：2 3 0 
第3次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 3 0 
第4次：
目前物理页框中页面走向为：2 3 1 
第5次：
目前物理页框中页面走向为：2 3 5 
第6次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 3 5 
第7次：
目前物理页框中页面走向为：4 3 5 
第8次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：4 3 5 
第9次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：4 3 5 
第10次：
目前物理页框中页面走向为：2 3 5 
第11次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 3 5 
第12次：
本次页面走向，页框中已经存在！
目前物理页框中页面走向为：2 3 5 

缺页次数：6次
一共调用: 12次
缺页中断率：50.0%
淘汰页面：1 2 4
# 南邮(通达)实验 页面置换算法 操作系统 操作系统实验 南邮实验
上一篇: 南邮计算机实验,南邮操作系统实验一
下一篇: 南邮操作系统实验之文件系统实验——实现简单多用户文本1、实验概述2、结构体设计3、文件系统的流程图4、一些测试截图5、总结

继续阅读