操作系统OPT算法(最佳页面替换算法)-Toy模板网

这篇具有很好参考价值的文章主要介绍了操作系统OPT算法(最佳页面替换算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

作者简介：一名后端开发人员，每天分享后端开发以及人工智能相关技术，行业前沿信息，面试宝典。

座右铭：未来是不可确定的，慢慢来是最快的。

个人主页：极客李华-CSDN博客

合作方式：私聊+

这个专栏内容：BAT等大厂常见后端java开发面试题详细讲解，更新数目100道常见大厂java后端开发面试题。

我的CSDN社区：https://bbs.csdn.net/forums/99eb3042821a4432868bb5bfc4d513a8

微信公众号，抖音，b站等平台统一叫做：极客李华，加入微信公众号领取各种编程资料，加入抖音，b站学习面试技巧，职业规划

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

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

opt算法,操作系统的学习与提升,算法,java,开发语言

import sun.plugin.javascript.navig.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)
    {
        System.out.print("list: ");
        for (int i = 0; i < list.size(); ++ i)
        {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }

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

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

    public static void main(String[] args) {
        Scanner in = new Scanner (System.in);
        // 内存访问顺序
        System.out.println("内存的访问顺序：");
        int numPage = in.nextInt();
//        System.out.println(numPage);
        // 页面中断的次数
        int cnt = 0;
        // 内存块的数量
        System.out.println("内存的数量：");
        int numMemory = in.nextInt();
        System.out.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 = in.nextInt();
            q.add(num);
            if (map.containsKey(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 (!list.contains(num))
                {
                    list.add(num);
                    map.get(num).poll();
                    cnt ++;
                }
            }
            else
            {
                if (list.contains(num))
                {
                    // 这里是就算 内存里面存在这个元素 但是也是还要假替换的 就是
                    // 把这次新来的num的对应的队列的索引也删掉
                    map.get(num).poll();
                }
                else
                {
                    check((ArrayList<Integer>) list, map);
                    cnt ++;
                    list.add(num);
                    // 把num对应的索引删掉一个
                    map.get(num).poll();
                }
            }
//            ListTrave(list);
        }
//        System.out.println("cnt: " + cnt);
        System.out.printf("%.1f%%", (double)cnt / (double)numPage * 100);
    }

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

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

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

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

}

如果大家觉得有用的话，可以关注我下面的微信公众号，极客李华，我会在里面更新更多行业资讯，企业面试内容，编程资源，如何写出可以让大厂面试官眼前一亮的简历等内容，让大家更好学习编程，我的抖音，B站也叫极客李华。大家喜欢也可以关注一下文章来源地址https://www.toymoban.com/news/detail-528401.html

到了这里，关于操作系统OPT算法(最佳页面替换算法)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！