操作系统OPT算法(最佳页面替换算法)

操作系统OPT算法(最佳页面替换算法)

简介：本文是博主当年学习操作系统的时候，所写的操作系统的OPT算法。

import sun.plugin.Link;

import java.util.*;

class Pair
{
    public Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
    public int first;
    public int second;
}

// opt算法的思路是
// 将每个数字和它的出现了的索引的队列做成映射表
// 每次比较内存里面的元素的索引队列的对首元素谁最大
// 最大的那个滚
public class Main
{
    static void ListTrave(List<Integer> list)
    {
        print("list: ");
        for (int i = 0; i < list.size(); ++ i)
        {
            print(list.get(i) + " ");
        }
        println();
    }

    static void QueueTrave(Queue<Integer> q)
    {
        print("Queue:");
        Iterator<Integer> it = q.iterator();
        while(it.hat())
        {
            print(() + " ");
        }
        println();
    }

    static void MapTrave(Map<Integer, Queue<Integer> > map)
    {
        println("map:");
        for (Integer i : map.keySet())
        {
            print(i + ": ");
            Iterator it = map.get(i).iterator();
            while(it.hat())
            {
                print(() + " ");
            }
            println();
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner (System.in);
        // 内存访问顺序
        println("内存的访问顺序：");
        int numPage = ();
//        println(numPage);
        // 页面中断的次数
        int cnt = 0;
        // 内存块的数量
        println("内存的数量：");
        int numMemory = ();
        println("输入内存：");
        Map<Integer, Queue<Integer> > map = new HashMap<>();

        // 把每个元素存一遍
        // 用队列的好处是 可以保证查询的效率是O(1)
        Queue<Integer> q = new LinkedList<>();

        // 存放当前内存中的元素
        List<Integer> list = new ArrayList<>();

        // 把每个元素和它的索引队列做成映射表
        for (int i = 0; i < numPage; ++ i)
        {
            int num = ();
            q.add(num);
            if ((num))
            {
                Queue<Integer> queue = map.get(num);
                queue.add(i);
                map.put(num, queue);
            }
            else
            {
                Queue<Integer> queue = new LinkedList<>();
                queue.add(i);
                map.put(num, queue);
            }
        }

        // 检查
//        QueueTrave(q);
//        MapTrave(map);

        for (int i = 0; i < numPage; ++ i)
        {
            int num = q.poll();
            if (list.size() < numMemory)
            {
                if (!(num))
                {
                    list.add(num);
                    map.get(num).poll();
                    cnt ++;
                }
            }
            else
            {
                if ((num))
                {
                    // 这里是就算 内存里面存在这个元素 但是也是还要假替换的 就是
                    // 把这次新来的num的对应的队列的索引也删掉
                    map.get(num).poll();
                }
                else
                {
                    check((ArrayList<Integer>) list, map);
                    cnt ++;
                    list.add(num);
                    // 把num对应的索引删掉一个
                    map.get(num).poll();
                }
            }
//            ListTrave(list);
        }
//        println("cnt: " + cnt);
        printf("%.1f%%", (double)cnt / (double)numPage * 100);
    }

    // 返回那个要滚的数字
    static int check(ArrayList<Integer> list, Map<Integer, Queue<Integer> > map)
    {
//        println("enter:");
//        ListTrave(list);
//        MapTrave(map);
        // 最后要滚的数字 和 对应的索引
        // 先设置为list的第一个元素
        // 如果这个数字对应的队列映射为空那么 用负数代表索引 表示无穷远
        int t = list.get(0);    // t是内存中的数字
        int idx = 0;  // t对应的索引
        int t2 = map.get(t).size();  // 索引对应的数字对应的队列的大小
        int t;                     // 队列第一个数字的索引
        // 判断是否为空的情况
        if (t2 == 0) t = -1;
        else t = map.get(t).peek();

//        println("t1 + idx + t2 + t=" + t + " " + idx + " " + t2 + " " + t);
        Pair num = new Pair(idx, t);  // num存放需要删除的数字的索引和这个数字对应的队列的队首
        if (num.second == -1)  // 如果到-1的后面的就不用了
        {
            list.remove(num.first);  // remove是按照索引删除
            return list.get(num.first);
        }
//        println("t1 + idx + t2 + t=" + t + " " + idx + " " + t2 + " " + t);
        for (int i = 1; i < list.size(); ++ i)
        {
//            ListTrave(list);
            t = list.get(i);
            idx = i;
            t2 = map.get(t).size();

            if (t2 == 0) t = -1;
            else t = map.get(t).peek();

//            println("t1 + idx + t2 + t=" + t + " " + idx + " " + t2 + " " + t);
            if(t == -1)
            {
                list.remove(idx);
                return list.get(num.first);
            }
            else
            {
                // 让更远的代替
                if (num.second < t)
                {
                    num = new Pair(idx, t);
                }
            }
        }
        // 最后second最大的滚
        list.remove(num.first);
        return list.get(num.first);
    }

}