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

• 作者简介：一名后端开发人员，每天分享后端开发以及人工智能相关技术，行业前沿信息，面试宝典。
• 座右铭：未来是不可确定的，慢慢来是最快的。
• 个人主页：极客李华-CSDN博客
• 合作方式：私聊+
• 这个专栏内容：BAT等大厂常见后端java开发面试题详细讲解，更新数目100道常见大厂java后端开发面试题。
• 我的CSDN社区：https://bbs.csdn.net/forums/99eb3042821a4432868bb5bfc4d513a8
• 微信公众号，抖音，b站等平台统一叫做：极客李华，加入微信公众号领取各种编程资料，加入抖音，b站学习面试技巧，职业规划

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

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

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);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

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