页面置换算法（FIFO,LRU,OPT）

1.先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
2．最佳置换算法（OPT）（理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
3．最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

具体代码实现：

/**
* 先进先出页面置换算法FIFO
* 借助JDK内置数据结构队列
*/

package com.page_replacementAlgorithm;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
public class FIFO {

    private final int capacity = 3;
    private int index = 0;
    // 构造一个初始容量为3的空列表
    private Queue<Integer> queue = new ArrayBlockingQueue<Integer>(capacity);

    public FIFO(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (queue.size() < capacity) { // 小于queue初始容量
                if (!queue.contains(arr[i])) { // queue没有该页面，将其添加进queue尾部
                    queue.add(arr[i]);
                } else {
                    continue;
                }
            } else {// 超出queue容量，置换掉最先调入内存的页面
                if (!queue.contains(arr[i])) {
                    queue.poll();//获取并移除此队列的头，如果此队列为空，则返回 null。
                    queue.add(arr[i]);
                } else {
                    continue;
                }
            }
            traverse();
        }
        System.out.println("访问页面需从外存调入的次数为："+(num-1));
        System.out.println("缺页率为："+(float)(num-1)/arr.length);
    }

    /**
     * 遍历queue容器
     */
    int num = 1;
    public void traverse() {
        System.out.print("第" + (num++) + "次" + "页面置换：\t");
        for (int i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

************************-***************************************
/**
* 最佳置换算法OPT
* 借助ArrayList数据结构
*/

package com.page_replacementAlgorithm;

import java.util.ArrayList;
import java.util.List;


public class OPT {

    private final int capacity = 3;
    private int[] index = new int[2];
    private List<Integer> list = new ArrayList<Integer>(capacity);
    public OPT(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (list.size() < capacity) { // 小于list初始容量
                if (!list.contains(arr[i])) { // list没有该页面，将其添加进list尾部
                    list.add(arr[i]);
                } else {
                    continue;
                }
            } else {// 超出list容量
                index[0] = 100;
                index[1] = 101;
                if (!list.contains(arr[i])) { // 下一个页面如果不在list中
                    int a = 0;
                    for (int j = i; j < arr.length; j++) {
                        if (list.contains(arr[j])) { // arr[j]这个页面会在测试数据中会出现较早
                            if (index[0] != list.indexOf(arr[j])) {

                                index[a++] = list.indexOf(arr[j]);// 返回此列表中首次出现的指定元素的索引
                                if (a == 2) {
                                    break;
                                }
                            }
                        }
                    }
                    list.set(noExist(), arr[i]);// 置换掉永不使用的,或许在最长时间内不再访问的页面
                } else { // 下一个页面在list中
                    continue;
                }
            }
            traverse();
        }
        System.out.println("访问页面需从外存调入的次数为："+(num-1));
        System.out.println("缺页率为："+(float)(num-1)/arr.length);
    }

    /**
     * 遍历list容器
     */
    int num = 1;

    public void traverse() {
        System.out.print("第" + (num++) + "次" + "页面置换：\t");
        for (int i : list) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    /**
     * 返回要替换的下标
     */
    private int noExist() {
        int[] brr = { 0, 1, 2 };
        if (brr[0] != index[0] && brr[0] != index[1])
            return brr[0];
        if (brr[1] != index[0] && brr[1] != index[1])
            return brr[1];
        if (brr[2] != index[0] && brr[2] != index[1])
            return brr[2];
        return 2;
    }
}

************************************ -****************

/**
* 最近最久未使用和最少使用置换算法 LRU
* 自己写的一个栈MyStack数据结构
*/

package com.page_replacementAlgorithm;

public class LRU {

    // 初始化一个容量为 5 的栈
    private MyStack<Integer> stack = new MyStack<Integer>(5);
    private int index = 0;// 一个数组下标的标识，用来除去栈底元素

    public LRU(int[] arr) {
        for (int i = 0; i < arr.length; i++) {// 将数组里 数据存入栈中
            if (stack.getLength() < stack.size()) { // 判断栈不满
                if (!stack.exist(arr[i])) { // 判断栈中有没有该元素，有的话返回true
                    stack.push(arr[i]);
                     stack.traverse();
                } else { // 如果有该元素，删除掉栈中该元素，并将该元素置于栈顶
                    stack.removeSameElement(arr[i]);
                    stack.push(arr[i]);
                    stack.traverse2();
                }
            } else { // 栈已满，删除到栈底元素
                if (stack.exist(arr[i])) { // 继续判断如果栈中存在相同元素，将该元素从栈中取出放到栈顶
                    stack.removeSameElement(arr[i]);
                    stack.push(arr[i]);
                    stack.traverse2();
                } else { // 栈中没相同元素，删除栈底元素，在栈顶加新元素
                    stack.remove(arr[index++]);
                    stack.push(arr[i]);
                    stack.traverse(); // 遍历栈中元素
                }
            }
        }
        System.out.println("访问页面需从外存调入的次数为："+(stack.getNum()-1));
        System.out.println("缺页率为："+(float)(stack.getNum()-1)/arr.length);
    }
}

*-***************************
以下是栈
****************-***********

package com.page_replacementAlgorithm;

import java.util.EmptyStackException;

/**
 * @ClassName: MyStack
 */
public class MyStack<E> {

    private Object[] Capacity;
    private int size = 0;
    private int length = 0;
    private int index = 0;
    /**
     * 初始化一个空栈
     */
    public MyStack() {
    }

    /**
     * 初始化一个大小为 Capacity 的栈
     */
    public MyStack(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        Capacity = new Object[initialCapacity];
        size = initialCapacity;
    }

    /**
     *  栈的大小
     */
    public int size() {
        return  size;
    }
    /**
     * 把项压入堆栈顶部
     */
    public E push(E item) {
        if(length < size()) {
            Capacity[index++] = item;
            length++;
        }else {
            try {
                throw new Exception("栈满");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return item;
    }

    /**
     * 移除堆栈顶部的对象，并作为此函数的值返回该对象。
     */
    public synchronized E pop() {
        int len = getLength();
        if (len == 0)
            throw new EmptyStackException();
        Capacity[--index] = null;
        length--;
        index--;
        return (E) Capacity[index];
    }

    /**
     * 移除堆栈中的对象，并作为此函数的值返回该对象。
     */
    public synchronized boolean removeSameElement(E element) {
        int len = getLength();
        if (len == 0)
            throw new EmptyStackException();

        int in = searchIndex(element);
        if(in!=-1) {
            int i=in;
            for(; i<size()-1;i++) {
                if(Capacity[i+1]!=null) {
                    Capacity[i] = Capacity[i+1];
                }
            }
            Capacity[i] = null;
            length--;
            index--;
            return true;
        }
        return false;
    }

    /**
     * 栈满的话，移除栈底元素
     */
    public synchronized boolean remove(E element) {
        int len = getLength();
        if (len == 0)
            throw new EmptyStackException();
        int i;
        for (i = 0; i < size() - 1; i++) {
            Capacity[i] = Capacity[i + 1];
        }
        Capacity[i] = null;
        length--;
        index--;
        return true;
    }

    /**
     * 查看堆栈顶部的对象，但不从堆栈中移除它。
     */
    public synchronized E peek() {
        int len = size();
        if (len == 0)
            throw new EmptyStackException();
        return (E) Capacity[index-1];
    }

    /**
     * 测试堆栈是否为空。
     */
    public boolean empty() {
        return getLength() == 0;
    }

    /**
     * 返回堆栈对象的个数
     */
    public int getLength() {
        return length;
    }

    /**
     * 根据下标查找堆栈中的对象
     */
    public E search(int i) {
        if(i<size() || i>=0)
            return (E) Capacity[i];
        throw new ArrayIndexOutOfBoundsException();
    }

    /**
     * 根据元素查找此在堆栈中的下标
     * 返回-1 表示查找失败
     */
    public int searchIndex(E element) {
        for(int i=0; i<getLength(); i++) {
            if(Capacity[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 查看堆栈中是否存在 该对象
     */
    public boolean exist(E element) {
        for (Object object : Capacity) {
            if(object != null) {
                if(object.equals(element) || object==element)
                    return true;
            }
        }       
        return false;
    }

    /**
     * 从栈底到栈顶遍历堆栈中的对象
     */
    int num = 1;
    public void traverse() {
        System.out.print("第"+(num++)+"次"+"页面置换：\t\t");
        for (Object object : Capacity) {
            System.out.print(object+"\t");
        }
        System.out.println(); 
    }
    public void traverse2() {
        System.out.print("容器内未置换页面：\t");
        for (Object i : Capacity) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
    public int getNum() {
        return num;
    }
}

***************************-**

/**
 * 测试页面置换算法
 */
package com.page_replacementAlgorithm;

import java.util.Scanner;


public class Test {

    /**
     * OPT课本数据 20个页面
     * 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
     */
    /**
     * FIFO课本数据    20个页面 
     * 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
     */

    /**
     * LRU课本上的数据   11个数据 
     * 4 7 0 7 1 0 1 2 1 2 6
     */
    private static boolean flag = true;
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        while (flag) {
            System.out.println("*************************");
            System.out.println("   请输入  1或2或3 进行选择        ");
            System.out.println("          1.OPT          ");
            System.out.println("          2.FIFO         ");
            System.out.println("          3.LRU          ");
            System.out.println("*************************");

            int result = s.nextInt();
            // int[] arr = input();
            if(result == 1) {
                new OPT(input());
                isContinue();
            } else if (result == 2) {
                new FIFO(input());
                isContinue();
            } else if (result == 3) {
                new LRU(input());
                isContinue();
            } else {
                System.out.println("您输入的信息有误，请重新输入！");
                isContinue();
            }
        }
    }

    private static int[] input() {
        System.out.println("请输入有多少个页面：");
        Scanner s = new Scanner(System.in);
        int num = s.nextInt();
        System.out.println("在输入页面号，以空格隔开");
        int[] arr = new int[num]; // 用来保存输入的页面数据
        for (int i = 0; i < num; i++) {
            arr[i] = s.nextInt();
        }
        return arr;
    }

    private static void isContinue() {
        Scanner s = new Scanner(System.in);
        while(true) {
            System.out.println("是否继续： y/n");
            String result = s.nextLine();
            if(result.equalsIgnoreCase("n")) {
                flag = false;
                System.out.println("***********************");
                System.out.println("*        谢谢观赏            *");
                System.out.println("***********************");
                break;
            } else if(result.equalsIgnoreCase("y")) {
                break;
            }else {
                System.out.println("输入有误");
            }
        }
    }
}