【题目要求】通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

针对一个页框，根据实验数据，以OPT算法为参考，研究FIFO页面淘汰算法、LRU页面淘汰以及CLOCK算法针对同一批实验数据的缺页率，以及研究在不同页框设置下的各算法缺页率表现情况。

页面引用序列为：4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5

（1）固定分配局部置换情况下，驻留集大小为3，针对该内存页面引用序列模拟各算法的运行过程，并计算缺页率。

（2）模拟驻留集大小为4和5的情况下各算法的运行过程和缺页率。

其菜单如下：

**






内存分配和回收

0. 退出
1. OPT算法实现
2. LRU算法实现
3. FIFO算法实现
4. CLOCK算法
5. 显示缺页率对比表
   
   =================================

JAVA代码如下（环境IDEA 2019.3.3）

public class Method {
    // 判断当前是否有需要的页面
    private boolean comparison(int[] need, int[] page, int j) {
        for (int i = 0; i < page.length; i++) {
            if (need[j] == page[i])
                return true;
        }
        return false;
    }

    private boolean comparison(int[] need, int[] page, int j, int[] set, boolean flag) {
        for (int i = 0; i < page.length; i++) {
            if (need[j] == page[i]) {
                if (flag) {
                    setone(set, i);
                } else {
                    setzero(set, i);
                }
                return true;
            }
        }
        return false;
    }

    private int find(int[] need, int[] page, int j) {
        for (int i = 0; i < page.length; i++) {
            if (need[j] == page[i])
                return i;
        }
        return -1;
    }
    private int findMax(int[] time) {
        int max = time[0];
        int index = 0;
        for (int i = 0; i < time.length; i++) {
            if (max < time[i]) {
                max = time[i];
                index = i;
            }
        }
        return index;
    }

    private int findzore(int[] set) {
        for (int i = 0; i < set.length; i++) {
            if (set[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    private void isAllOne(int[] set) {
        boolean flag = false;
        for (int i = 0; i < set.length; i++) {
            if (set[i] != 1)
                break;
            if (i == set.length - 1)
                flag = true;
        }
        if (flag) {
            for (int i = 0; i < set.length; i++) {
                setzero(set, i);
            }
        }
    }

    private void timeadd(int[] time) {
        for (int i = 0; i < time.length; i++) {
            time[i] += 1;
        }
    }

    private void setzero(int[] time, int index) {
        time[index] = 0;
    }

    private void setone(int[] time, int index) {
        time[index] = 1;
    }

    private void Print(int[] page) {
        for (int i = 0; i < page.length; i++) {
            System.out.print(page[i] + "  ");
        }
        System.out.println();
    }

    // 这个函数要完成的任务是，需要统计每一个已经填入的数值，下一次出现的位置
    private int statistics(int[] set, int[] page, int n) {
        int[] next = new int[page.length];
        int index = 0;
        for (int i = 0; i < page.length; i++) {
            for (int j = n; j < set.length; j++) {
                if (page[i] == set[j]) {
                    next[i] = j;
                    // flag = false;
                    break;
                }
                if (j >= set.length - 1) {
                    next[i] = 99;

                }
            }
        }
        //Print(next);
        index = findMax(next);
        //System.out.println("找到的最大值即为可以删掉的值" + index);
        return index;
    }

    public int FIFO(int[] need, int[] page) {
        int index = 0;
        int defect = 0;// 缺失计数
        for (int i = 0; i < need.length; i++) {
            if (!comparison(need, page, i)) {
                page[index] = need[i];
                index++;
                defect++;
            }
            // Print(page);
            index = index % page.length;
            System.out.print("page是");
            Print(page);
        }
        return defect;
    }

    public int LRU(int[] need, int[] page) {
        int index = 0;
        int defect = 0;// 缺失计数
        boolean flag = false;
        // 统计停留时间
        int[] time = new int[page.length];
        for (int i = 0; i < need.length; i++) {
            timeadd(time);
            if (!comparison(need, page, i, time, flag)) {
                index = findMax(time);
                page[index] = need[i];
                setzero(time, index);
                defect++;
            }
            // Print(time);
            System.out.print("page是");
            Print(page);
        }
        return defect;
    }

    public int CLOCK(int[] need, int[] page) {
        int index = 0;
        int defect = 0;// 缺失计数
        boolean flag = true;
        // 统计停留时间
        int[] read = new int[page.length];
        for (int i = 0; i < need.length; i++) {
            if (!comparison(need, page, i, read, flag)) {
                isAllOne(read);
                index = findzore(read);
                page[index] = need[i];
                setone(read, index);
                defect++;
            }
            else {
                index = find(need, page, i);
                setzero(read, index);
            }
            System.out.print("page是");
            Print(page);
        }
        return defect;
    }

    public int Opt(int[] need, int[] page) {
        int index = 0;
        int defect = 0;// 缺失计数
        for (int i = 0; i < need.length; i++) {
            if (!comparison(need, page, i)) {
                index = statistics(need, page, i);
                page[index] = need[i];
                defect++;
            }
            System.out.print("page是");
            Print(page);
        }
        return defect;
    }
    public void restore(int[] set){
        for(int i=0;i<set.length;i++) {
            setzero(set,i);
        }
    }
}



import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Method method =new Method();
        int pages[] = {4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5};
        boolean flag = true;
        @SuppressWarnings("resource")
        Scanner scan =new Scanner(System.in);
        System.out.println("页数为：");
        int num = scan.nextInt();
        int[] page =new int[num];
        int a,b,c,d;
        float e=0;
        int change;
        while(flag) {
            System.out.println("按1键Opt");
            System.out.println("按2键LRU");
            System.out.println("按3键FIFO");
            System.out.println("按4键CLOCK");
            System.out.println("按5键退出");
            System.out.println("作者信息");
            change = scan.nextInt();
            switch(change) {
                case 1:{
                    method.restore(page);
                    d=method.Opt(pages,page);
                    System.out.println("Opt缺页次数为      "+d);
                    e=(float)d/pages.length;
                    System.out.println("Opt缺页率为      "+e);
                    break;
                }

                case 2:{
                    method.restore(page);
                    b = method.LRU(pages, page);
                    System.out.println("LRU缺页次数为      "+b);
                    e =(float)b/pages.length;
                    System.out.println("LRU缺页率为      "+e);
                    break;
                }
                case 3:{
                    method.restore(page);
                    a = method.FIFO(pages,page);
                    System.out.println("FIFO缺页次数为    "+a);
                    e=(float)a/pages.length;
                    System.out.println("FIFO缺页率为    "+e);
                    break;
                }
                case 4:{
                    method.restore(page);
                    c =method.CLOCK(pages, page);
                    System.out.println("CLOCK缺页次数为  "+c);
                    e=(float)c/pages.length;
                    System.out.println("CLOCK缺页率为  "+e);
                    break;
                }
                case 5:{
                    flag=false;
                    break;
                }
                default :{
                    System.out.println("请重新输入");
                    break;
                }
            }
        }
    }

}