【OS学习笔记】页面置换算法的Java版实现

小咪咪 2022-10-15 04:54 147阅读 0赞

一、背景

> 程序的运行，需要将指令和数据装入内存中进行执行，可内存的资源十分有限（目前常用的差不多8G,16G）。而虚拟内存就是解决该问题的。

> 局部性原理：（1）时间局部性：程序中的某条指令一旦执行或数据访问，不久后会再次执行或访问。典型原因是循环操作 （2）空间局部性：程序在一段时间内访问的地址在一定范围内。  
> 基于局部性原理，在程序装入时，将程序的一部分装入内存，而将其余部分留在外存，启动程序执行。当所访问的信息不在内存时，由OS将所需的部分**调入**内存，暂时不需要的内容**换出**（置换）到外存上。

二、置换算法

（1）分类

1.  OPT（最佳置换算法）  
    选取未来最久才使用的页面进行调出到外存。需要知道未来的请求，所以至少需要访问两次，将未来的请求序列存下来。由于计算机执行具有异步性推进，所以难以实现。
2.  FIFO（先进先出算法）  
    选取最先进来的换出，采用队列实现即可。实现简单，但性能差。
3.  LRU（最近最久未使用算法）  
    选取在此之前最久未使用的页面进行调出，采用堆栈实现（实际需要寄存器和栈的硬件支持）。性能较好，实现较复杂。

（2）实现

package practice.os.practice.memorymodule;
    
    import java.util.*;
    import java.util.concurrent.atomic.AtomicInteger;
    import java.util.function.Predicate;
    
    /** * @AUTHOR LYF * @DATE 2021/5/23 * @VERSION 1.0 * @DESC * 优质参考（C语言版）：https://www.cnblogs.com/wasi-991017/p/13072328.html * 缺页和置换的概念 * 当页面内存中不存在时，则出现缺页需要调入。 * =>在调入时，内存已满，需要选择某个页面进行调出，则需要置换 * 1.FIFO * 2.LRU * 3.OPT * OPT算法是无法实现的，因为，在程序运行过程中无法对以后要使用的页面做出精确的断言 * * 4.CLOCK */
    public class ReplacementAlg { 
        // 页面请求序列
        static private List<Integer> reqPageSeq = new ArrayList<>();
        // 内存容量
        /** * @PARAM * */
        static int size = 6;
    
        static { 
            for(int i=0;i<256;i++){ 
                reqPageSeq.add(new Random().nextInt(10));
                try { 
                    Thread.sleep(2);
                } catch (InterruptedException e) { 
                    e.printStackTrace();
                }
            }
            System.out.println("PageStreamSeq...");
            reqPageSeq.stream().forEach(e->System.out.print(" "+e));
    
        }
    
        /** * FIFO */
        void fifoStrategy(){ 
             System.out.println("FIFO...");
             AtomicInteger allPages = new AtomicInteger();
             AtomicInteger missPages = new AtomicInteger();
             AtomicInteger replacePages = new AtomicInteger();
             allPages.set(0);
             missPages.set(0);
             replacePages.set(0);
             Queue<Integer> blocks = new ArrayDeque<>();
    // blocks.add(4);
    // blocks.add(1);
             reqPageSeq.stream().forEach(
                     e->{ 
                         allPages.getAndIncrement();
                         if(!blocks.contains(e)){ 
                             // 不存在则缺页
                             missPages.getAndIncrement();
                             if(blocks.size()==size){ 
                                 // 置换
                                 replacePages.getAndIncrement();
                                 // FIFO 先进来的先置换出去
                                 blocks.poll();
                             }
                             blocks.add(e);
                         }
                         System.out.println("memory:"+(size-blocks.size())+";allPages:"+allPages.get()+";missPages:"+missPages.get()+";replacePages:"+replacePages.get()+
                                 ";missPageRate:"+Float.parseFloat(missPages+"")/Float.parseFloat(allPages+""));
                     }
             );
        }
    
        /** * LRU算法 * 采用栈记录物理块，当出现命中的块时，将其调整到栈顶 * 未出现则判断是否满内存，若满则删除栈底元素，添加新的元素到栈顶 */
        void lruStrategy(){ 
            System.out.println("LRU...");
            AtomicInteger allPages = new AtomicInteger();
            AtomicInteger missPages = new AtomicInteger();
            AtomicInteger replacePages = new AtomicInteger();
            allPages.set(0);
            missPages.set(0);
            replacePages.set(0);
            Stack<Integer> stack = new Stack<>();
            reqPageSeq.stream().forEach(e->{ 
                allPages.getAndIncrement();
                System.out.println("stack0..");
                stack.stream().forEach(e1-> System.out.print(e1+" "));
                if(!stack.contains(e)){ 
                    missPages.getAndIncrement();
                    if(stack.size()==size){ 
                        replacePages.getAndIncrement();
                        // 移除栈底元素
                        stack.remove(0);
                    }
                }else{ // 包含，则考虑调整优先级，将其放在栈顶
                    stack.remove((Object)e);
                }
                stack.add(e);
                System.out.println("stack1..");
                stack.stream().forEach(e1-> System.out.print(e1+" "));
                System.out.println();
                System.out.println("memory:"+(size-stack.size())+";allPages:"+allPages.get()+";missPages:"+missPages.get()+";replacePages:"+replacePages.get()+
                        ";missPageRate:"+Float.parseFloat(missPages+"")/Float.parseFloat(allPages+""));
            });
    
        }
    
        void optStrategy(){ 
            System.out.println("OPT...");
            int allPages = 0;
            int missPages = 0;
            int replacePages = 0;
            List<Integer> list = new LinkedList<>();
            for(int i=0;i<reqPageSeq.size();i++){ 
                allPages++;
                if(!list.contains(reqPageSeq.get(i))){ 
                    missPages++;
                    if(list.size()==size){ //移除
                        replacePages++;
                        List<Integer> tempList = new LinkedList<>();
                        tempList.addAll(list);
                        for(int j=i+1;j<reqPageSeq.size();j++){ 
                            if(tempList.size()==1){ 
                                // 若移除的只剩下一个，那么只能是这个了，否则一直移动
                                break;
                            }else{ 
                                tempList.removeIf(Predicate.isEqual(reqPageSeq.get(j)));
                            }
                        }
                        list.remove(tempList.get(0));
                    }
                    list.add(reqPageSeq.get(i));
                }
            }
            System.out.println();
            System.out.println("memory:"+(size-list.size())+";allPages:"+allPages+";missPages:"+missPages+";replacePages:"+replacePages+
                    ";missPageRate:"+Float.parseFloat(missPages+"")/Float.parseFloat(allPages+""));
        }
    
        public static void main(String[]args){ 
            ReplacementAlg replacementAlg = new ReplacementAlg();
            replacementAlg.fifoStrategy();
            replacementAlg.lruStrategy();
            replacementAlg.optStrategy();
        }
    }