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

本是古典何须时尚 2024-03-31 14:46 36阅读 0赞

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

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

![在这里插入图片描述][5dfe2965b56c41efb3bb8235a4c1b171.png]

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

[5dfe2965b56c41efb3bb8235a4c1b171.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c58972a90f0541699cb742d98a6dd915.png