精华内容
下载资源
问答
  • 【OS学习笔记】页面置换算法Java版实现
    2021-05-23 18:34:30

    一、背景

    程序的运行,需要将指令和数据装入内存中进行执行,可内存的资源十分有限(目前常用的差不多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();
        }
    }
    
    
    更多相关内容
  • 操作系统os 页面置换算法java实现) Clock.java Lru.java Opt.java Fifo.java
  • 该压缩包是页面置换算法的综合设计,包括五种页面置换算法,optimal算法,Fifo算法,lru算法,Lfu算法,改进型Clock算法,而且拥有完整的页面操作,可以直接在IDEA中导入工程,编译即可通过。
  • 页面置换算法java

    2021-02-26 14:01:11
    页面置换算法 在一个请求分页系统中,分别采用最佳置换算法、先进先出置换算法、最近最久未使用置换算法(LRU)时,假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数M分别为3和...

    页面置换算法

      在一个请求分页系统中,分别采用最佳置换算法、先进先出置换算法、最近最久未使用置换算法(LRU)时,假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数M分别为3和4时,试计算在访问过程中所发生的缺页次数和缺页率,并比较所得结果。

    实验步骤与记录

    (一)准备阶段
      因为作业的页面走向是一串数字,因此可以定义一个数组 pageString[] 来储存将要发送请求的页号,同时还需要定义一个数组 inStore[] 作为分配给该作业的内存物理块以及定义一个变量times记录缺页次数。
      根据题目要求内存物理块数M分别为3和4,所以我构造了一个方法 setInStore() ,用来初始化内存物理块,并将内存物理块中的数值置为无实际含义的“-1”:
    在这里插入图片描述
    (二)置换方法实现阶段
    1、最佳置换算法和最近最久未使用置换算法(LRU)
      分析发现这两种算法几乎相同,只是一个向后看,一个向前看,因此将两个算法的代码放在一起分析:
      以内存物理块数是3为例,进程运行时,内存未满时,先将4、3、2三个页面依次装入内存。
    在这里插入图片描述
      内存满后,进程要访问页面,先判断该页是否在内存中,如果在内存中则不会产生缺页中断。
    在这里插入图片描述
      如果不在内存则需要将内存中的页根据最佳置换方法置换出来。即由请求页在作业的页面走向( pageString[ ] )数组中的位置为起点,如果是“最佳置换算法”则分别计算当前内存中各页下次出现的距离(即由起点向后遍历 pageString[ ] 数组),而“LRU置换算法”则由起点向前遍历 pageString[ ] 数组,分别计算当前内存中各页到起点的距离(需注意的是将遍历结束后再也不出现的页号的距离置为最大值),这需要定义一个大小与内存物理块数相同的数组( num[ ] )来存放计算出来的距离。(这是两种算法唯一的不同点)
    在这里插入图片描述
    在这里插入图片描述
      比较距离的大小,将距离最远的替换出来。
    在这里插入图片描述
    2、先进先出置换算法(FIFO)
      内存空间未满时将请求页依次放入内存。内存满后,判断请求页是否在内存中,如果在内存则不产生缺页中断(此段代码与最佳算法相同),反之则产生缺页中断需要依据先进先出规则对内存中的页面进行置换。即将内存中最早进入的页换出。这需要数组( num[ ] )用来存放内存中各页面进入内存的先后顺序,内存中最早进入的页面的序号标记为“1”,第二早的标记为“2”,依次将内存中的页标记好,最后换出最早进入的页面(即序号标记为“1”的页)
    在这里插入图片描述
    (三)输出内存变化过程以及计算缺页次数和缺页率
    1、构建一个方法( putInstore() )输出内存的当前状态
    在这里插入图片描述
    2、定义一个变量 times 作为访问过程中所发生的缺页次数,每发生一次缺页中断 times 就+1。然后根据“缺页率=缺页次数/进程总页面访问次数”构造一个方法( pagef() )计算缺页率。
    在这里插入图片描述

    运行结果

      当分配给该作业的物理块数为3时:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
      当分配给该作业的物理块数为4时,最佳置换算法缺页中断次数为6,缺页率为0.5;先入先出算法缺页中断次数为10,缺页率为0.8333333;LRU置换算法缺页中断次数为8,缺页率为0.6666667。

    代码文件下载

    链接: https://download.csdn.net/download/qq_49101550/15482296

    展开全文
  • java实现页面置换算法

    2020-08-18 15:57:05
    主要为大家详细介绍了java实现页面置换算法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 操作系统存储管理页面置换算法-----最佳页面置换算法模拟(JAVA实现) 话不多说,我们直接展示 package com.company; import java.util.Arrays; /** * @Auther: Bender * @Date: 2021/11/14 - 16:57 * @...

    操作系统存储管理页面置换算法-----最佳页面置换算法模拟(JAVA实现)

    话不多说,我们直接展示

    package com.company;
    
    import java.util.Arrays;
    
    /**
     * @Auther: Bender
     * @Date: 2021/11/14 - 16:57
     * @Description: com.company
     * @version: 1.0
     */
    
    //注释掉的是第一次做的程序,考虑不充分失败了
    public class MyAlg {
        public static boolean isIn(int a, int[] arr) {                  //判断某个数是否在数组中,返回true或者false
            for(int i: arr){
                if(a==i){
                    return true;
                }
            }
            return false;
    
        }
    
        public static int isIn(int[] arr, int a) {                      //isIn方法重载,返回相等元素的数组下标,没有则返回下标
            for(int i=0; i<arr.length; i++){
                if(arr[i] == a)
                    return i;
            }
            return -1;
    
        }
        public static void optAdd(int[] contain, int[]list, int k) {                //最佳置换算法的缺页处理(前提:内存区已满)
            /*分析:应该分为多种情况,******需要注意的是当作业队列中出现多次已经存在内存中的作业时(例子:内存区[5,6,7]   作业队列[1,6,7,6]),我们只取第一个******
            1.当后续作业队列中没有找到内存中已有的作业时
              例子:内存区[6,7,8]   作业队列[1,2,3,4,5]
              处理方式:默认替换0号元素
            2.当后续作业队列中找到一个已经在内存中存在的作业时
              例子:内存区[1,2,3]   作业队列[5,6,7,1,8]
              处理方式:从0号元素开始,将未在作业队列中的元素依次替换
            3、当后续作业队列中找到两个已经在内存中存在的作业时
              例子:内存区[5,6,7]   作业队列[8,5,6]
              处理方式:直接替换掉未出现的元素
            4.当后续作业队列中找到内存区所有元素
              例子:内存区[5,6,7]    作业队列[8,5,6,7]
              处理方式:替换掉最后出现的元素
             */
            int[] index = {-3,-3,-3};                           //要返回的下标队列,选取其中最小的值作为第k个元素要替换的下标******
            int inum = 3;                                       //给index中的元素复制,随着赋值次数递减,最小的就是要替换的
            int goalindex = 0;
            for(int i=k+1; i<list.length; i++){                 //从k的下一个元素开始遍历,原因:第K个元素调用此方法的前提是这个元素并不在内存中
                if(isIn(list[i],contain)){                      //该元素在内存中
                    int num = isIn(contain,list[i]);            //返回相同的元素下标
    
                    if(index[num]==-3)                          //确保只取第一次,后续忽略
                        index[num] = inum--;
                }
            }
            if(index[0]<0 && index[1]<0 && index[2]<0 ){  //情况一:默认替换第0个元素
                index[0] = -4;
            }
            int temp = index[0];
            for(int i=1; i<index.length; i++){              //找出index中的最小值
                if(index[i]<temp) {
                    temp = index[i];
                    goalindex = i;
                }
    
            }
            contain[goalindex] = list[k];
            System.out.println("缺页中断"+ Arrays.toString(contain));
    
    
        }
        public static void opt(int[] list) {
            System.out.println("-----这是最佳页面置换算法-----");
            int times = 0;                      //记录缺页率
            int[] contain = new int[3];         //模拟内存空间,大小为3
            int isempty = 0;                    //对contain模拟内存中的元素进行计数
            /*此循环的作用:将contain模拟内存装满
    
             */
            int i;                                          //在循环体外定义循环变量i是为了当循环结束时返回i的值(当内存区满后,对作业队列的执行从i+1开始)
            for(i=0; i<list.length; i++) {
                if(!isIn(list[i],contain)){                  //当要放入的元素不在内存区中
                    contain[isempty] = list[i];
                    isempty++;                              //内存区元素加一
                    System.out.println("缺页中断"+Arrays.toString(contain));
                    times++;
                    if(isempty==3) {                         //当内存区的元素个数为3(内存区已满的情况)即可跳出此循环
                        break;
                    }
                }//当要访问的元素在内存区已经存在时,我们不做任何操作
            }
            //执行至此处内存区已满,下面对作业队列遍历,缺页时执行页面置换操作,不缺页时不做任何操作
            //具体的页面置换我希望单独设计成一个方法(前提:内存区此时已满,不达成这个前提,程序设计会复杂的多)
            for(++i; i<list.length; i++){                   //从上一个循环的下一个位置开始遍历作业队列
                if(!isIn(list[i],contain)){                 //缺页时的操作
                    optAdd(contain,list,i);
                    times++;
                }//不缺页不执行任何操作
    
            }
            System.out.println("缺页次数:" + times + ",缺页中断率:" + (float)times / list.length);
    
        }
    //    public static int search(int[] contain, int[] arr, int index){      //返回在之后的作业队列中,内存中最后一个被访问的内存块的下标
    //        int renum = 0;                                              //最后该方法的返回值,指明要替换的主存块
    //        for(int i=index; i<arr.length; i++){                        //对之后的作业队列进行遍历
    //            int num = isIn(contain,arr[i]);
    //            if(num!=-1)
    //                renum = num;
    //        }
    //        return renum;
    
    //    }
    
    //    public static void opt(int[] arr) {
    //        System.out.println("-----这是最佳置换算法-----");
    //        System.out.println("作业队列:"+Arrays.toString(arr));
    //        int times = 0;                          //用于记录置换次数(缺页中断次数),计算缺页率
    //        int elements = 0;                       //记录内存中的作业数
    //        int[] contain = new int[3];             //模拟主存空间
            for(int i=0; i<3; i++){                 //三个作业装入,现在主存装满
                contain[i] = arr[i];
            }
    //        contain[0] = arr[0];                    //先将第一个作业放入内存
    //        times++;                                 //缺页中断次数加一
    //        elements++;                              //内存作业数加一,变为1
    //        System.out.println("主存块:"+Arrays.toString(contain));
    //        for(int i=1; i<arr.length; i++){           //遍历作业队列
    //            if(!isIn(arr[i],contain)){              //当要访问的作业不在主存时
    //                times++;                            //缺页终断率加一
    //                if(elements>=3){                     //内存已满
                        int index = search(contain,arr,i);
                        contain[index] = arr[i];
    //                    System.out.println("中断:"+times+"次,"+Arrays.toString(contain));                   //打印置换后的内存情况
    //                }else{                              //内存未满,直接加如内存
    //                    contain[elements] = arr[i];
    //                    elements++;
    //                }
    //            }else{                                  //当要访问的作业就在内存时,将被访问的作业调至最后,其他作业依次向前移,因为当后续作业队列中的作业都不在主存时,默认替换主存数组的第0个元素(即距离上次调用的时间最长)
    //                if(elements>=3){                    //内存区已满的情况
    //                    int index = isIn(contain,arr[i]);
    //                    if(index==1){
    //                        int temp = contain[1];
    //                        contain[1] = contain[2];
    //                        contain[2] = temp;
    //                    }else if(index == 0){
    //                        int temp = contain[0];
    //                        contain[0] = contain[1];
    //                        contain[1] = contain[2];
    //                        contain[2] = temp;
    //                    }
    //                    System.out.println("未发生中断"+Arrays.toString(contain));
    //                }
    //            }
    //            System.out.println("主存块:"+Arrays.toString(contain));
    //
    //        }
    //
    //    }
    
        public static void main(String[] args) {
            int[] arr = {6,7,6,5,9,6,8,9,7,6,9,6};
            opt(arr);
        }
    }
    
    

    运行结果的展示:
    在这里插入图片描述
    看了这篇页面置换算法的文章,试运行了一下发现错误很多,很多点没有考虑到,所以自己重写了一下
    链接: https://blog.csdn.net/TianXiaobie/article/details/110451353?utm_source=app&app_version=4.18.0&code=app_1562916241&uLinkId=usr1mkqgl919blen.

    展开全文
  • 一:页面置换算法简介 在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存已无 空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送磁盘 的对换区中。但应将哪个...

    一:页面置换算法简介

    在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存已无

    空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送磁盘

    的对换区中。但应将哪个页面调出,须根据一定的算法来确定。通常,把选择换出页面的

    算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏,将直接影响到系统

    的性能。

    一个好的页面置换算法,应具有较低的页面更换频率。从理论上讲,应将那些以后不

    再会访问的页面换出,或把那些在较长时间内不会再访问的页面调出。目前存在着许多种

    置换算法,它们都试图更接近于理论上的目标。

    二:常用到的页面置换算法

    1、最佳置换算法(Optimal)) (该算法主要是用来度量其他算法)

    最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面,

    将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,

    通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面

    中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用

    该算法去评价其它算法。

    2、先进先出置换算法(FIFO)

    这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻

    留时间最久的页面予以淘汰。先进先出这个特性会想到的是队列,算法思想就是先写入到同一个队列

    里面,然后设置一个指针(替换指针),让它指向最老的页面。

    下面就是Java代码模拟FIFO置换算法:

    使用队列记录对应内存空间位置以及页面数据:

    PrintUtils这个工具类主要输出的是过程数据
    
    /** * 没有用计数方法,使用的队列记录对应位置 * @param numbers * @param memorySize */public static void FIFOPages(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    String[] ways = new String[memorySize];    Queue<Page> queue = new LinkedList<>();    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        int number = numbers[i];        long count = queue.stream().filter(page -> page.getData().equals(number)).count();        if (count <= 0) {            int size = queue.size();            if (size >= memorySize) {                size = queue.poll().getMemoryPosition();            }            queue.add(new Page(number, size));            pages[size] = numbers[i];            sum++;            sums[i] = true;        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}@Setter@Getter@AllArgsConstructor@ToStringpublic class Page {    private Integer data;    private Integer memoryPosition;}

    3、最近最久未使用置换算法(LRU:Least Recently Used)

    LRU 置换算法虽然是一种比较好的算法,但要求系统有较多的支持硬件。为了了解一

    个进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速地知道哪一页是最

    近最久未使用的页面

    模拟代码:

    public static void URLPage(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    // 页面计数    int[] counts = new int[memorySize];    String[] ways = new String[memorySize];    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        if (!havePage(pages, numbers[i], counts)) {            int maxCount = getMaxCount(counts);            pages[maxCount] = numbers[i];            counts[maxCount] = 1;            sum++;            sums[i] = true;        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}
    
    /** * 获取最先进入的数据,如果计数最大说明是最先进来的,并且每一个对应计数+1 * * @param counts * @return */private static int getMaxCount(int[] counts) {    int index = 0;    int max = 0;    for (int i = 0; i < counts.length; i++) {        if (counts[i] == -1) {            index = i;            break;        }        if (counts[i] > max) {            max = counts[i];            index = i;        }        counts[i]++;    }    return index;}
    /** * 查看当前内存块中是否有当前页,如果没有就是要置换掉最先进入的页,并且计数+1,有就计数变为1,因为已经被访问了 * * @param pages * @param page * @param counts * @return */private static boolean havePage(int[] pages, int page, int[] counts) {    boolean isHave = false;    for (int i = 0; i < pages.length; i++) {        counts[i]++;        if (pages[i] == page) {            isHave = true;            counts[i] = 1;        }    }    return isHave;}

    4、Clock置换算法

      (1)简单的Clock置换算法

    当采用简单 Clock 算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过

    链接指针链接成一个循环队列。当某页被访问时,其访问位被置 1。置换算法在选择一页淘

    汰时,只需检查页的访问位。如果是 0,就选择该页换出;若为 1,则重新将它置 0,暂不

    换出,而给该页第二次驻留内存的机会,再按照 FIFO 算法检查下一个页面。当检查到队列

    中的最后一个页面时,若其访问位仍为 1,则再返回到队首去检查第一个页面。图 4-31 示

    出了该算法的流程和示例。由于该算法是循环地检查各页面的使用情况,故称为 Clock 算法。

    但因该算法只有一位访问位,只能用它表示该页是否已经使用过,而置换时是将未使用过

    的页面换出去,故又把该算法称为最近未用算法 NRU(Not Recently Used)

    模拟代码如下:

    public static void ClocksPage(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    // 页面计数    int[] counts = new int[memorySize];    int index = 0;    String[] ways = new String[memorySize];    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        int number = numbers[i];        if (havePage(pages, number, counts)) {            index = (index + 1) % memorySize;        } else {            while (true) {                int indexs = (index + 1) % memorySize;                if (pages[index] == -1 || (counts[index] == 0 && pages[index] != number)) {                    pages[index] = number;                    counts[index] = 1;                    sum++;                    sums[i] = true;                    index = indexs;                    break;                }                if (pages[index] != number) {                    counts[index] = 0;                    index = indexs;                }            }        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}
    /** * 查看当前内存块中是否有当前页 * * @param pages * @param page * @param counts * @return */private static boolean havePage(int[] pages, int page, int[] counts) {    boolean isHave = false;    for (int i = 0; i < pages.length; i++) {        if (pages[i] == page) {            isHave = true;            counts[i] = 1;        }    }    return isHave;}

       (2)改进型Clock置换算法

    简单时钟只有一个标记位,但是改进型是多加了一个标记位,简单时钟最多遍历2遍,改进型的最多比遍历4遍。

    算法书里面是这样描述的:

    假设 search标识访问标记位,update表示修改标记位,下面就有这样的一个规则

    •  

    • 1 类( search  =0, update  =0):表示该页最近既未被访问,又未被修改,是最佳淘汰页。

    • 2 类( search  =0, update  =1):表示该页最近未被访问,但已被修改,并不是很好的淘汰页。

    • 3 类( search  =1, update  =0):表示该页最近已被访问,但未被修改,该页有可能再被访问。

    • 4 类( search  =1, update  =1):表示该页最近已被访问且被修改,该页可能再被访问。 

    (1) 从指针所指示的当前位置开始,扫描循环队列,寻找 search  =0 且  update  =0 的第一类页面,

    将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位  search  。

    (2) 如果第一步失败,即查找一周后未遇到第一类页面,则开始第二轮扫描,寻找  search  =0

    且  update  =1 的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所

    有扫描过的页面的访问位都置 0。

    (3) 如果第二步也失败,亦即未找到第二类页面,则将指针返回到开始的位置,并将所

    有的访问位复 0。然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到

    被淘汰的页。

    该算法与简单 Clock 算法比较,可减少磁盘的 I/O 操作次数。但为了找到一个可置换的

    页,可能须经过几轮扫描。换言之,实现该算法本身的开销将有所增加。

    模拟代码如下:

    public static void ClocksPage(int[] numbers, int memorySize) {    // 模拟内存空间    int[] pages = new int[memorySize];    Arrays.fill(pages, -1);    // 记录访问状态    int[] search = new int[memorySize];    // 记录修改状态    int[] update = new int[memorySize];    int index = 0;    String[] ways = new String[memorySize];    // 缺页次数    int sum = 0;    // 缺页记录    boolean[] sums = new boolean[numbers.length];    for (int i = 0; i < numbers.length; i++) {        int number = numbers[i];        boolean isHave = false;        for (int page : pages) {            if (page == number) {                isHave = true;                break;            }        }        if (!isHave) {            sums[i] = true;            sum++;            int count = 0;            int start = index;            while (true) {                int j = (index + 1) % memorySize;                if (j == start) {                    ++count;                }
                    if (count == 0 || count == 2) {                    if (search[index] == 0 && update[index] == 0) {                        pages[index] = number;                        search[index] = 1;                        update[index] = 1;                        index = j;                        break;                    }                } else {                    if (search[index] == 0 && update[index] == 1) {                        pages[index] = number;                        search[index] = 1;                        update[index] = 1;                        index = j;                        break;                    }                }                if (count != 0) {                    search[index] = 0;                }                index = j;            }        }        PrintUtils.setWays(ways, pages);    }    PrintUtils.printResult(numbers, sums, memorySize, sum, ways);}

     

    5、最少使用置换算法(LFU:Least Frequently Used)

    在采用最少使用置换算法时,应为在内存中的每个页面设置一个移位寄存器,用来记

    录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。由于存

    储器具有较高的访问速度,例如 100 ns,在 1 ms 时间内可能对某页面连续访问成千上万次,

    因此,通常不能直接利用计数器来记录某页被访问的次数,而是采用移位寄存器方式。每

    次访问某页时,便将该移位寄存器的最高位置 1,再每隔一定时间(例如 100 ms)右移一次。

    这样,在最近一段时间使用最少的页面将是∑Ri 最小的页。

    LFU 置换算法的页面访问图与 LRU 置换算法的访问图完全相同;或者说,利用这样一

    套硬件既可实现 LRU 算法,又可实现 LFU 算法。应该指出,LFU 算法并不能真正反映出

    页面的使用情况,因为在每一时间间隔内,只是用寄存器的一位来记录页的使用情况,因

    此,访问一次和访问 10 000 次是等效的。

    6、页面缓冲算法(PBA:Page Buffering Algorithm)

    虽然 LRU 和 Clock 置换算法都比 FIFO 算法好,但它们都需要一定的硬件支持,并需

    付出较多的开销,而且,置换一个已修改的页比置换未修改页的开销要大。而页面缓冲算

    法(PBA)则既可改善分页系统的性能,又可采用一种较简单的置换策略。VAX/VMS 操作系

    统便是使用页面缓冲算法。它采用了前述的可变分配和局部置换方式,置换算法采用的是

    FIFO。该算法规定将一个被淘汰的页放入两个链表中的一个,即如果页面未被修改,就将

    它直接放入空闲链表中;否则,便放入已修改页面的链表中。须注意的是,这时页面在内

    存中并不做物理上的移动,而只是将页表中的表项移到上述两个链表之一中。

    空闲页面链表,实际上是一个空闲物理块链表,其中的每个物理块都是空闲的,因此,

    可在其中装入程序或数据。当需要读入一个页面时,便可利用空闲物理块链表中的第一个

    物理块来装入该页。当有一个未被修改的页要换出时,实际上并不将它换出内存,而是把

    该未被修改的页所在的物理块挂在自由页链表的末尾。类似地,在置换一个已修改的页面

    时,也将其所在的物理块挂在修改页面链表的末尾。利用这种方式可使已被修改的页面和

    未被修改的页面都仍然保留在内存中。当该进程以后再次访问这些页面时,只需花费较小

    的开销,使这些页面又返回到该进程的驻留集中。当被修改的页面数目达到一定值时,例

    如 64 个页面,再将它们一起写回到磁盘上,从而显著地减少了磁盘 I/O 的操作次数。一个

    较简单的页面缓冲算法已在 MACH 操作系统中实现了,只是它没有区分已修改页面和未修

    改页面。

    参考书籍:《计算机操作系统第三版》汤小丹等著

    完整代码地址:

    https://gitee.com/yh128/SpringDemoProject/tree/master/blog-code

     

     

                                                文章同时会更新到公众号,觉得对你有帮助或者有用的可以关注一下哦 

     

    展开全文
  • 页面置换算法.java

    2019-05-21 19:04:07
    一次操作系统算法的描述,有最佳置换算法,先进先出置换算法,和最近最久未使用和最少使用算法(这是一个),需要的人自行下载 代码类型:JAVA 附注释,每行方便理解,最难写的是opt算法。 算法要求:(1)给出页面...
  • 页面置换算法java

    2021-03-03 14:04:40
    实验报告五实验名称: 模拟页面置换算法 FIFO、LRU 的实现 日期:2015-12-9 班级:13 级计科 学号: 一、 实验目的 二、 实验内容 Java 编程语言实现 FIFO 和 ......操作系统常用页面置换算法课程设计_计算机软件及应用_...
  • 一个页面置换算法性能比较程序,包括了最佳置换,先进先出,LRU,随机置换,简单时钟和改进时钟六个算法。使用了队列,链表,循环链表等数据结构。随机产生请求页号,计算六种算法的缺页率。
  • 基于Java链表实现的页面置换算法,有FIFO,Clock,LRU,OPT四种,实现统计分析功能,具有数据纠正功能。
  • java实现的页面置换算法

    千次阅读 2018-06-10 11:01:26
    java实现的页面置换算法,包括FIFO、LRU、Clock三种算法
  • 理解算法才能实现算法,要不然就和我一样无从下手,抓破头皮也没用!!!LRU算法:http://flychao88.iteye.com/blog/1977653import java.util.*;import java.io.*;public class Main{public static void main(String...
  • JAVA实现页面置换算法(OPT,FIFO,LRU)

    万次阅读 多人点赞 2016-11-29 10:30:59
    System.out.println("**** 选择最近最远未使用置换算法请按3 ***"); } public void OPT(){//最佳置换算法 int j; for (int i=0;i;i++) { int k=list.get(i);//待处理元素 //System.out.print(map); ...
  • 3.2.3页面置换算法

    千次阅读 2016-07-20 21:38:12
    而选择调入页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者较长时间不会再访问的页面先调出。1.最佳置换算法(OPT)最佳(Optimal,OPT)置换算法所选择...
  • 页面置换算法.doc

    2020-03-23 22:48:13
    深入掌握内存调度算法的概念原理和实现方法,编写程序实现: (1) 先进先出页面置换算法(FIFO) ...操作系统页面置换算法课程设计,完整的课设结构,有详细的流程图、Java源码,还有调试截图!!!
  • 页面置换算法实验报告包括:实验题目,实验目的,实验内容及要求,实验结果,实验总结,及后附有详细C++源代码 实验内容及要求: 1) 最佳置换算法(OPT):将以后永不使用的或许是在最长(未来)时间内不再被访问的页面...
  • Java语言实现模拟页面置换算法-Read.doc前言在存储管理当中,页面置换算法通常可分为两种:一种基于进程驻留集大小不变;另一种基于驻留集大小可变。在驻留集大小不变的页面置换算法当中,常用的算法主要有:FIFO、...
  • 页面置换算法综合实现(JavaJava Swing实现)

    千次阅读 多人点赞 2019-12-27 22:55:37
    页面置换算法综合实现(JavaJava Swing)算法导入算法分析一、界面分析二、界面设计三、界面相关算法设计算法展示一、操作展示二、算法比较结尾 算法导入        失踪人口回归...
  • 最近最少使用算法(LRU)是⼀种缓存淘汰策略,它是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。该算法的思路是,发生缺页中断时,选择未使用时间最长的页面置换出去。从程序运行的原理来看,...
  • 定义:OPT(最佳置换算法):从主存中移出永远不再需要的页面,如果没有这样的页面存在,那就选择最长时间不需要访问的页面,来保证最低的缺页率。 import java.util.*; public class OPT { private static List&...
  • 操作系统之三种页面置换算法(OPT,FIFO,LRU)--Java实现

    千次阅读 多人点赞 2020-12-03 16:25:37
    页面置换算法的定义: 程序运行过程中,有时要访问的页面不在内存中,而需要将其调入内存。但是内存已经无空闲空间存储页面,为保证程序正常运行,系统必须从内存中调出一页程序或数据送到磁盘对换区,此时需要一定...
  • 页面置换算法

    2014-07-25 17:06:52
    页面置换算法Java代码,有注释,易学易懂
  • 最佳(Optimal)置换算法 其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。 采用最佳置换算法,可保证获得最低的缺页率。 [外链图片转存失败,源站可能有防盗链机制,建议将...
  • 学院:软件学院 专业:计算机科学与技术 年级/班级:19级JAVA2班 2020—2021学年第二学期 课程名称 操作系统 指导教师 学号姓名 魏一鸣 ...
  • 《操作系统之Java实现模拟页面置换算法

    千次阅读 多人点赞 2018-05-13 18:08:58
    一. 页面置换三大算法简介 1. FIFO(先进先出置换算法) 2. LRU(最近最久未使用置换算法) 3. OPT(最佳置换算法) 二....1. 基于随机数产生该程序...5. 执行页面置换算法的模拟过程 三. 实现关键思路 1. FIFO 2....
  • 操作系统页面置换法FIFO,LRU,OPT调度算法Java实现
  • 操作系统 页面置换算法实现 import java.util.Scanner; public class page_change { final int M=3; final int N=20; class block { int iPageNum; //物理块里存储的页面号 int iBlockFlag; //在三种算法...
  • 为了加深对虚拟内存页面置换概念的理解,进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。 (1)输入的形式:输入1-3的整数选择算法,比如输入1调用FIFO算法,输入2调用LRU算法,输入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,753
精华内容 1,501
关键字:

页面置换算法java代码

java 订阅