精华内容
下载资源
问答
  • 摘要:最近未使用页淘汰(NRU算法或者时钟算法是实际使用的诸多页淘汰算法中的一种。本课程设计是使用C程序设计语言,在windows平台下对页淘汰(NRU算法模拟,通过页淘汰(NRU算法的模拟来进一步的加深...

    摘要:最近未使用页淘汰(NRU)算法或者时钟算法是实际使用的诸多页淘汰算法中的一种。本课程设计是使用C程序设计语言,在windows平台下对页淘汰(NRU)算法模拟,通过页淘汰(NRU)算法的模拟来进一步的加深对使用NRU算法的了解,及对C程序设计语言的使用。

    关键词:页淘汰  NRU  时钟算法

    一.设计的背景介绍

    1.1 介绍相关概念,相关算法

    页淘汰工作通常是由一个系统进程或线程完成的,该进程称为页淘汰进程

    页淘汰的时机:当内存空闲页面数低于系统所配置的最小阈值时启动(唤醒)页淘汰的进程,页淘汰进程被启动后就开始不停地选择和淘汰释放页,直到内存的空闲页面数达到系统所配置的最大阈值为止。此后,页淘汰进程进入睡眠(等待)状态,直到下次因内存空闲页面数少于最小阈值而被再次唤醒(启动)。

    最近未使用页淘汰NRU算法的原理

    ①该算法为每个页面设置两个硬件位访问位和修改位

    访问位= 0:该页尚未被访问过;     访问位= 1:该页已经被访问过

    修改位= 0:该页尚未被修改过;     访问位= 1:该页已经被修改过

    开始时所有页的访问位,修改位都设为0, 访问/修改时再置1

    当页淘汰进程工作时,首先淘汰那些访问位为0的页。然后,如果还要继续淘汰(即空闲页面尚未达到最大阈值),则淘汰那些访问位为1但修改位为0的页。最后如果空闲页面还不够,则淘汰那些修改位为1的页

    由于大多数页迟早要被访问,故页淘汰进程定期遍历内存页将每页的访问位都置为0(周期性地对访问位清零)。这种清除过程类似于时针在时钟面上的运行故NRU算法又称为时钟(clock算法

    1.2 简要介绍设计环境、设计工具

    利用VC++6.0/TC3.0Dos/Windows平台使用最近未使用页淘汰NRU)算法模拟实现页淘汰进程

     

    二.设计思路和总体流程图

    2.1 基本思路 

    以命令行方式运行程序,调用read()函数读入页面请求队列,按照页面请求队列的先后顺序逐个处理请求页面。调用nru()函数通过nru算法选择要淘汰的页面,将其淘汰,调入申请页面,输出相关结果的信息。

    2.2数据文件格式说明

    第一行为工作集大小(wnum

    第二行为申请页面的总数 (pnum)

    第三行为页号(pagenum),修改位(mbit)中间用"|"符号隔开;

    其余为一个页面请求队列,各行两数分别表示页面申请页号和修改位,程序按请求的先后顺序处理申请页。

    用户可根据需要任意修改工作集大小,申请页面的总数,页面请求队列。

    文件样例如下:

    wnum:3

    pnum:10

    pagenum|mbit

    1 1

    2 0

    3 1

    5 1

    3 0

    6 1

    4 0

    2 1

    3 0

    7 1

    2.3数据结构定义

    ⑴定义页面请求队列Page

    typedef struct

    {   int pagenum;      //页面号   

        int mbit;         //修改位

    }Page;

    ⑵定义工作集Wspace

    typedef struct

    {   int pageno;       //页面号

        int rbit;         //访问位

        int mbit;         //修改位

        int status;       //该页的标志位,表示是否被占用

    }Wspace;

    ⑶其他

    int pnum;       //申请页面的总数

        int wnum;       //工作集大小

        int b[4];       //标志位数组,四个数组元素分别表示工作集内是否存在访问位、修改位分别为00011011的页面,初始值为0,当存在时置1

    2.4总体流程图

    1.程序总体流程图

    2.5根据总体流程图进行模块分割、模块功能说明

    本程序共分成2个模块:

    文件读入模块:

    主要用于读入文件信息,并将文件的内容全部输出,检验读入是否正确。此模块通过调用read()函数实现。

    主体函数模块:

    实现nru算法,这是本课程设计的主体模块,通过调用nru() 函数实现。

    调入每个申请页,当工作集满时运用nru算法选择要淘汰的页面,将其淘汰。nru()函数中包括两个子函数print(),callin()

    print()函数:

    信息输出,主要用于输出相关的结果信息,包括申请页面的页面号、修改位,工作集中的各页页面号、访问位、修改位。在程序处理完一页后调用此函数,使用户能清楚的了解处理完一个申请页面后工作集的内容。

    callin()函数:

    调入申请页,主要完成四个操作:申请页面调入;访问位置1,表示被访问;根据请求页面的修改位修改工作集页面的修改位;状态位置1,表示该页已经被占用。该函数在三种情形下可调用①工作集存在空闲页,调入申请页时;②申请页已在工作集中,修改访问位和修改位时;③工作集满时,需淘汰工作集内的页面,调入申请页时。

    三.算法的实现

    3.1 模块流程图及算法实现

    1文件读入模块

    主要用于读入文件信息,并将文件的内容全部输出,检验读入是否正确。通过read()函数实现。

    read() 函数流程图如下:

    2.read( )函数流程图

     

    具体的程序代码如下:

    void read(int argc,char * argv[],Page **page,int *pnum,int *wnum,Wspace **wspace)

    {  FILE *file;

       char temp[80];

       int i;

       if(argc!=2) exit(0);

       if((file=fopen(argv[1],"r"))==NULL)

      {

        printf("read file failed/n");

        exit(0);

      }

       fscanf(file,"%5s %d",temp,wnum);

       fscanf(file,"%5s %d",temp,pnum);

       fscanf(file,"%s",temp);

       *wspace=(Wspace*)malloc(sizeof(Wspace)**wnum);

       *page=(Page*)malloc(sizeof(Page)**pnum);

       for(i=0;i<*wnum;i++)

    {(*wspace)[i].pageno=0;(*wspace)[i].rbit=0;(*wspace)[i].mbit=0; (*wspace)[i].status=0;}

    //遍历工作集各页,将各页的页面号,访问位,修改位,状态位置0

       printf("wnum:%d/n",*wnum);   

       printf("pnum:%d/n",*pnum);

       printf("pagenum mbit/n");

       for(i=0;i<*pnum;i++)

      {    fscanf(file,"%d %d",&((*page)+i)->pagenum,&((*page)+i)->mbit);

        printf("%d %d/n",((*page)+i)->pagenum,((*page)+i)->mbit); }  

    fclose(file);

    }

    2主体函数模块,通过nru()函数实现,该函数可分为三部分

    3 nru()函数流程图

    1)第一步,查找申请页面是否已在工作集内,若是则将该页的访问位置1,修改修改位,输出相关信息,处理下一页。

    2若申请页不在工作集,则进入第二步:

    查找工作集是否存在空闲页,若是则调入该申请页,访问位置1,修改修改位,输出相关信息,处理下一页。

    3)若工作集不存在空页,则进入第三步:

    运用NRU算法选择需要淘汰的页面,将其淘汰,调入申请页,具体的做法是:

    ①定义数组b[4],每个数组元素表示一个标志位,初始值均为0。遍历工作集,如果存在访问位、修改位为00011011的页面,对应地分别将数组的b[0] b[1] b[2] b[3]1。此时,因为申请页面不在工作集,工作集也不存在空闲页面,因此,b数组肯定有一个元素为1

    ②如果b[0]1,查找第一个访问位、修改位分别为00的页面,

    将其淘汰,调入申请页,访问位置1,遍历工作集各页,将各页的访问位置0,转第③步;

    b[0]0,则判断:如果b[1]1,查找第一个访问位、修改位分别为01的页面,将其淘汰,调入申请页,访问位置1,遍历工作集各页,将各页的访问位置0,转第③步;

    b[1]0,则判断:如果b[2]1,查找第一个访问位、修改位分别为10的页面,将其淘汰,调入申请页,访问位置1,遍历工作集各页,将各页的访问位置0,转第③步;

    b[2]也为0,证明b[3]一定为1,此时工作集内各页访问位、修改位均为11,可任意淘汰一页,将其淘汰。现选择淘汰第0页,调入申请页,遍历工作集各页,将各页的访问位置0,转第③步。

    ③每处理完一页即调用print()函数,将申请页面的页面号、修改位,工作集中的各页面号、访问位、修改位输出,处理下一个申请页。

      4)所有的页面申请页都处理完毕,函数结束,返回。

    具体的程序代码如下:

    void nru(Page *page,Wspace *wspace,int pnum,int wnum,int b[4])

    {int i,j,m,n,k;

     for(j=0;j<pnum;j++)                                                       

    //j表示申请页面的序号,处理完一次,j自动加1,直至申请页面全部处理完毕

     {

        for(m=0;m<wnum;m++)

           if(wspace[m].pageno==(page+j)->pagenum) break; 

    //查找申请页是否在工作集

        if(m<wnum)

        {

           callin(page,wspace,m,j);

           print(page,wspace,j,wnum);       

        }

    //若在工作集,则将该页调入至此,访问位置1,并输出相关信息

        else

        {  for(k=0;k<wnum;k++)

             if(wspace[k].status==0) break;     

    //查找工作集是否存在空闲页

           if(k<wnum)

           { 

             callin(page,wspace,k,j);

             print(page,wspace,j,wnum);      

           }

    //若存在空闲页,则将该页调入至此,访问位置1,并输出相关信息

           else

           {

     for(i=0;i<4;i++)  b[i]=0;

    //b数组各元素赋初始值为0

             for(m=0;m<wnum;m++)

             {  if(wspace[m].rbit==0&&wspace[m].mbit==0)  b[0]=1;

    //工作集存在访问位、修改位分别为00的页面时,b[0]1

                if(wspace[m].rbit==0&&wspace[m].mbit==1)  b[1]=1;

    //工作集存在访问位、修改位分别为01的页面时,b[1]1

                if(wspace[m].rbit==1&&wspace[m].mbit==0)  b[2]=1;

    //工作集存在访问位、修改位分别为10的页面时,b[2]1  

                if(wspace[m].rbit==1&&wspace[m].mbit==1)  b[3]=1;

    //工作集存在访问位、修改位分别为11的页面时,b[3]1

             }

            if(b[0]==1)

            {

                for(n=0;n<wnum;n++)

                 if(wspace[n].rbit==0&&wspace[n].mbit==0) break;

                callin(page,wspace,n,j);       

    //如果b[0]=1,查找第一个访问位和修改位为00的页面,调入申请页至此

                for(n=0;n<wnum;n++)  wspace[n].rbit=0;     

    //遍历工作集,将各页访问位置0

                print(page,wspace,j,wnum);   

    //输出相关信息

            }

            else if(b[1]==1)

            {

                for(n=0;n<wnum;n++)

                 if(wspace[n].rbit==0&&wspace[n].mbit==1) break;

                callin(page,wspace,n,j);       

    //如果b[1]=1,查找第一个访问位和修改位为01的页面,调入申请页至此

                for(n=0;n<wnum;n++)  wspace[n].rbit=0;  

    //遍历工作集,将各页访问位置0

                print(page,wspace,j,wnum);   

    //输出相关信息

            }

            else if(b[2]==1)

            {

                for(n=0;n<wnum;n++)

                 if(wspace[n].rbit==1&&wspace[n].mbit==0) break;

                callin(page,wspace,n,j);       

    //如果b[2]=1,查找第一个访问位和修改位为10的页面,调入申请页至此

                for(n=0;n<wnum;n++)  wspace[n].rbit=0;  

    //遍历工作集,将各页访问位置0

                print(page,wspace,j,wnum);   

    //输出相关信息

            }

            else

            {

                callin(page,wspace,0,j);      

    //调入申请页至工作集的第0

                for(n=0;n<wnum;n++)  wspace[n].rbit=0;  

    //遍历工作集,将各页访问位置0

                print(page,wspace,j,wnum);   

    //输出相关信息

            }

          }

      }

      printf("/n");

     }

    }

    3.2 程序编译及使用说明

    编译说明:程序在 c++c语言环境下编译实现。

    使用说明:在Dos环境下实现结果的显示。

    开始→程序→MS-DOS方式→输入程序名(及其所在路径)与参数来启动程序,例如程序hnru.cpp和数据文件hnru.txt存放在F/1中,编译完成后可在F/1/debug产生可执行文件hnru.exe,进入MS-DOS方式后可输入F:/1/debug/hnru.exe  f:/1/hnru.txt,回车即可运行程序,显示运行结果。

    四.结论

    本设计使用最近未使用页淘汰NRU)算法模拟实现页淘汰进程,基本达到老师的要求,程序可处理任一页面请求对列,初始化工作集,并在工作集满的时候使用NRU算法选择淘汰的页面,调入新的申请页,输出结果信息。用户可根据自己的需求,在数据文件内任意修改工作集大小,页面请求队列,运行程序,清楚的了解工作集的内容,包括页面号、访问位、修改位,加深对NRU算法的理解。但本算法存在一定的缺陷,比如,未能处理好当若干个页面的访问位和修改位相同时,算法淘汰哪个页面更为合理的问题。这个问题曾经考虑过,但因某种原因未能实现。

    在设计过程中,因为挺久未使用C语言编程,运用起来有点生疏,导致代码的质量不高,可读性降低。刚开始设计时,对老师的要求没有明确,耽误了一段较长的时间,又花了相当长的时间写文档。通过课程设计,感觉到理论和实践的差距,理论上学得再好,都不如动手参与实践,想和做是截然不同的。以后要加强理论的实践,多动手做点东西。通过设计文档的编写,感觉到做事的严谨性和自己表达能力的不足,做的出来却并不一定能准确地表达出来。大学只剩下短短的一年,这次的课程设计给我挺多感触,一个简简单单的程序却做了那么久,以后要珍惜时间,学好课内的知识,多学些课外的知识。

    五.参考资料

    [1]孟静,操作系统教程高等教育出版社

    [2]潭浩强,《C程序设计语言》,清华大学出版社

    展开全文
  • NRU页面置换算法

    千次阅读 2019-06-09 20:21:05
    最近未使用页面置换算法(NRU)算法,找到最久没有使用的页面置换出去 没找到例子,自己试着理解了一下,可能存在错误理解。 和OPT算法相似的,OPT寻找最远或者不在需要的页面替换 则 NRU是寻找最久未使用,则应该向前...

    NRU页面置换算法
    最近未使用页面置换算法(NRU)算法,找到最久没有使用的页面置换出去
    没找到例子,自己试着理解了一下,可能存在错误理解。
    和OPT算法相似的,OPT寻找最远或者不在需要的页面替换
    则 NRU是寻找最久未使用,则应该向前寻找谁没有距离被置换处最远,则将其置换出
    大概是这个样子
    在这里插入图片描述

    #include <iostream>
    #define N 3
    using namespace std;
    int main()
    {
        int ym[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
        int size=20;
        int opt[N]={1,0,7 };
        int len[N]={0,0,0};
        int sum;
        int dq=3;
        int flag=0;
        int allchagetime=0;
        do{
            for(int i=0;i<N;i++)
            {
                cout<<opt[i]<<"  ";
            }
            cout<<endl;
    
    
          for(int i=0;i<N;i++)
            {
               sum=0;
                if(ym[dq]==opt[0]||ym[dq]==opt[1]||ym[dq]==opt[2])
                 {
                     flag=1;
                     break;
                 }
    
                 else{
                        flag=0;
                     for(int j=dq-1;j>=0;j--)
                  {
    
    
                         sum++;
                 if(opt[i]==ym[j]||j==0)
                 {
                     len[i]=sum;
    
                     break;
                 }
                 }
    
             }
    
                 }
    
    
    
         if(flag==0)
         {
    
    
             int max=len[0];
        int res;
        for(int t=0;t<N;t++)
        {
             if(len[t]>=max)
             {
                res=t;
                 max=len[t];
             }
        }
        opt[res]=ym[dq];
           allchagetime++;
         }
    
            dq++;
        }while(dq!=21);
        cout<<"缺页"<<allchagetime+3-1<<"次,"<<"置换"<<allchagetime-1<<"次"<<endl;
    }
    
    

    在这里插入图片描述

    展开全文
  • 分页算法 对3种分页算法的一些仿真:FIFO,LRU和NRU。 (对3种分页算法的小模拟:FIFO(先进先出),LRU(最近最少使用)和NRU最近未使用)。)
  • 虚拟内存的定义 ...4、时钟置换算法 CLOCK / 最近未使用算法 NRU 请求分段存储管理 请求段页式存储管理 页面分配策略 固定分配 / 可变分配 局部 / 全局置换 何时调入页面 从何处调入页面 驻留集 / 工作集区别

    本文已收录至 Github(MD-Notes),若博客中有图片打不开,可以来我的 Github 仓库https://github.com/HanquanHq/MD-Notes,涵盖了互联网大厂面试必问的知识点,讲解透彻,长期更新中,欢迎一起学习探讨。
    面试必会系列专栏https://blog.csdn.net/sinat_42483341/category_10300357.html
    操作系统系列专栏https://blog.csdn.net/sinat_42483341/category_10519484.html


    第三章 内存管理2 - 虚拟内存


    虚拟内存的定义

    基于局部性原理,在程序装入时,将会用到的部分装入内存,暂时不用的部分留在外存,程序就可以执行。在操作系统的管理下,在用户看来似乎有一个 比实际内存大得多 的内存,这就是 虚拟内存

    • 若访问信息不在内存,由操作系统从将信息从外存调入内存。(请求调页)

    • 若内存空间不够,将暂时不用的信息换出到外存。(页面置换)

    虚拟内存的特征

    1. 多次性:作业运行无需一次全部装入内存,允许多次调入内存。
    2. 对换性:作业运行时无需常驻内存,允许在运行过程中换入换出。
    3. 虚拟性:从逻辑上扩充了内存的容量,用户看到的内存容量远大于实际容量。

    虚拟内存的实现

    请求分页存储管理

    页表机制

    页号 内存块号 状态位 访问字段 修改位 外存地址
    0 c 1 0 0 x
    1 b 1 10 0 y
    2 0 6 1 z

    在基本分页存储管理的基础上,增加了:

    • 状态位:表示页面是否已在内存中
    • 访问字段:记录最近被访问过几次 / 上次访问的时间,供置换算法选择换出页面时间时参考
    • 修改位:表示页面调入内存后是否被修改过,只有修改过的页面才需要在置换时写回外存
    • 外存地址:页面在外存中存放的位置

    缺页中断(内中断)

    在请求分页系统中,若要访问的页面不在内存,则产生一个 缺页中断,由操作系统的 缺页中断处理程序 处理。

    缺页的进程阻塞,放入阻塞队列。调页完成后唤醒,放回就绪队列。

    • 将目标页面调入内存,必要时换出页面

    • 缺页中断属于内中断中的“故障”,即可能被系统修复的异常

    在这里插入图片描述

    • 一条指令在执行过程中可能产生多次缺页中断,如 copy A to B

    地址变换机构

    重点关注与基本分页不同的地方:

    • 找到页表项时,需要检查是否在内存中
    • 若页面不在内存中,需要请求调页
    • 若内存空间不够,需要换出页面
    • 页面调入内存后,需要修改响应页表项

    请求分页中的地址变换过程

    在这里插入图片描述

    页面置换算法

    1、最佳置换算法 OPT

    每次选择 最长时间不再被访问 的页面淘汰,保证缺页率最低。由于无法预测未来,实际上是无法实现的。

    在这里插入图片描述

    2、先进先出置换算法 FIFO

    每次淘汰 最早进入内存 的页面。将页面根据先后顺序排成一个队列,每次淘汰队头页面即可。

    ① 分配 3 个内存块时,缺页次数 9 次

    在这里插入图片描述

    ② 分配 4 个内存块时,缺页次数 10 次

    在这里插入图片描述

    Belady 异常:当为进程分配的物理块数增大时,缺页次数不减反增的异常现象。只有 FIFO 算法会产生 Belady 异常,并没有考虑到金橙世纪运行时规律。算法性能差。

    3、最近最久未使用算法 LRU

    每次淘汰 最近最久未使用 的页面。性能好,但是开销大。需要硬件支持。

    在这里插入图片描述

    4、时钟置换算法 CLOCK / 最近未使用算法 NRU
    1. 简单的 clock 算法

    (访问位) 表示页面状态。0 表示未访问过,1 表示访问过。

    在这里插入图片描述

    算法规则:

    • 某页被访问时,访问位置为 1
    • 第一轮:如果是 0,则将该页换出;如果是1,则置 0 且暂不换出
    • 第二轮:一定能找到访问位为 0 的页面
    1. 改进的 clock 算法

    (访问位,修改位) 表示页面状态。0 表示未被访问 / 未被修改过,1 表示被访问 / 修改过。

    在这里插入图片描述

    算法规则:

    • 第一轮:从当前位置开始扫描到 第一个 (0,0) 的帧用于替换
      • 最近没访问,且没修改的页面
    • 第二轮:第一轮扫描失败则重新扫描,找 第一个 (0,1) 的帧用于替换,同时将 扫描过的访问位改为 0
      • 最近没访问,但修改过的页面
    • 第三轮:第二轮扫描失败则重新扫描,找 第一个 (0,0) 的帧用于替换
      • 最近访问过,但修改过的页面
    • 第四轮:第三轮扫描失败则重新扫描,找 第一个 (0,1) 的帧用于替换
      • 最近访问过,且修改过的页面

    :由于第二轮已将所有帧的访问位置 0,因此经过第三、四轮扫描一定会有帧被选中。

    请求分段存储管理

    暂无

    请求段页式存储管理

    暂无

    页面分配策略

    固定分配 / 可变分配

    驻留集,指请求分页存储管理中给进程分配的物理块的集合。根据 驻留集大小是否可变,分为:

    • 固定分配:驻留集大小不变。操作系统为每个进程分配一组固定数目的物理块
    • 可变分配:先为每个进程分配一定数目的物理块,在进程运行期间,可根据情况做适当的增加或减少。

    局部 / 全局置换

    根据 页面置换时的置换范围,分为:

    • 局部置换:发生缺页时只能选进程自己的物理块进行置换。
    • 全局置换:可以将空闲物理块分配给缺页进程,也可将别的进程的物理块置换到外存,再分配给缺页进程。

    何时调入页面

    • 预调页策略:(运行前调入)略主要用于进程的首次调入,由程序员指出应该先调入哪些部分。
    • 请求调页策略:(进程运行期间使用)发现缺页时,才将所缺页面调入内存。

    从何处调入页面

    在这里插入图片描述

    1. 对换区空间足够

      页面的调入、调出都在内存与对换区之间进行,这样可以保证页面的调入、调出速度很快。在进程运行前,需将进程相关的数据从文件区复制到对换区。

    2. 对换区空间不足

      不会被修改的数据,直接从文件区调入,换出时不写回。

      可能被修改的部分,换出时写回磁盘对换区,需要时再从对换区调入。

    3. UNIX 方式:运行前,进程数据全部放在文件区。使用过的页面换出到对换区,需要时从对换区调入。

    驻留集 / 工作集区别

    • 驻留集:指请求分页存储管理中给进程分配的内存块的集合。
    • 工作集:指在某段时间间隔里,进程实际访问页面的集合。

    操作系统会根据“窗口尺寸”来算出工作集。例:

    某进程的页面访问序列如下,窗口尺寸为4,各时刻的工作集为?

    在这里插入图片描述

    驻留集大小不能小于工作集大小,否则进程运行过程中将频繁缺页,发生抖动现象。

    展开全文
  • 文章目录一、最佳置换算法(OPT)二、先进先出页面置换算法(FIFO)三、最近最久未使用置换算法(LRU)四、最少使用置换算法(LFU)五、Clock置换算法(最近未使用算法 NRU)六、页面缓冲算法(PBA)七、访问内存的...


    地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。
    当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法

    一、最佳置换算法(OPT)

    • 其所选择的被淘汰页面是以后永不使用的,或许是在未来最长时间内不再被访问的页面
    • 采用最佳置换算法,通常可以保证获得最低的缺页率。
    • 但由于人们目前无法预知,哪个页面是未来最长时间不被访问的,所以该算法是无法实现的,但可以用该算法去评价其他算法。
      在这里插入图片描述

    二、先进先出页面置换算法(FIFO)

    • 该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
    • 这种算法的实现和队列是一样,OS维护一个当前在内存中的所有页面的链表,最新进入的页面在尾部,最久的在头部,每当发生缺页中断,就替换掉表头的页面并且把新调入的页面加入到链表末尾。
      在这里插入图片描述

    三、最近最久未使用置换算法(LRU)

    • 当需要淘汰一个页面时,总是选择最近最久未使用的页面予以淘汰
      在这里插入图片描述
    • LRU 置换算法的硬件支持
      • 寄存器
        • 为了记录某进程唉内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器。
          -
        • 每当进程访问某页面时,便将该页面的页面号从栈中移出,将它压入栈顶。
        • 因此,栈顶始终是最新被访问的页面编号,栈底是最近最久未使用的页面编号。
          在这里插入图片描述

    四、最少使用置换算法(LFU)

    • 采用该算法时,应为在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率
    • 当需要淘汰一个页面时,总是选择最近时期使用最少的页面予以淘汰
    • LFULRU访问图完全相同

    五、Clock置换算法(最近未使用算法 NRU)

    • LRU算法的性能接近于OPT,但是实现起来比较困难,且开销大;
    • FIFO算法实现简单,但性能差。所以操作系统的设计者尝试了很多算法,试图用比较小的开销接近LRU的性能,这类算法都是CLOCK算法的变体。
    • 简单的CLOCK算法
      • 给每一帧关联一个附加位,称为使用位。当某一页首次装入主存时,该帧的使用位设置为1;当该页随后再被访问到时,它的使用位也被置为1。
      • 对于页替换算法,用于替换的候选帧集合看做一个循环缓冲区,并且有一个指针与之相关联。当某一页被替换时,该指针被设置成指向缓冲区中的下一帧。当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0的一帧。
      • 每当遇到一个使用位为1的帧时,操作系统就将该位重新置为0;如果在这个过程开始时,缓冲区中所有帧的使用位均为0,则选择遇到的第一个帧替换;如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0,并且停留在最初的位置上,替换该帧中的页。
      • 由于该算法循环地检查各页面的情况,故称为CLOCK算法,又称为最近未用(Not Recently Used, NRU)算法。
        在这里插入图片描述
    • 改进的 Clock 算法
      • CLOCK算法的性能比较接近LRU,而通过增加使用的位数目,可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位,则得到改进型的CLOCK置换算法。这样,每一帧都处于以下四种情况之一:
        • 最近未被访问,也未被修改(u=0, m=0)。
        • 最近被访问,但未被修改(u=1, m=0)。
        • 最近未被访问,但被修改(u=0, m=1)。
        • 最近被访问,被修改(u=1, m=1)。
      • 算法执行如下操作步骤:
        • 从指针的当前位置开始,扫描帧缓冲区。在这次扫描过程中,对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。
        • 如果第1)步失败,则重新扫描,查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中,对每个跳过的帧,把它的使用位设置成0。
        • 如果第2)步失败,指针将回到它的最初位置,并且集合中所有帧的使用位均为0。重复第1步,并且如果有必要,重复第2步。这样将可以找到供替换的帧。
      • 改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回,因而这样做会节省时间。

    六、页面缓冲算法(PBA)

    七、访问内存的有效时间

    展开全文
  • LRU LRU(Least Recently Used)是一种常见的页面置换算法,在计算中,所有的文件操作都要放在内存中进行,然而...LRU 最近最久未使用 FIFO 先进先出置换算法 类似队列 OPT 最佳置换算法 (理想中存在的) NRU C...
  • 该淘汰算法分为最佳淘汰算法(OPT)、先进先出算法(FIFO)、最近最少使用算法(LRU)和最近未使用算法NRU)。  (1)最佳淘汰算法指选择在最远的将来才被访问的页面淘汰。  (2)先进先出算法指选择最早进入...
  • 最近未使用算法NRU Not Recently Used 内存管理方案 1. 无存储器抽象 最原始的方案,每个程序都直接访问物理内存。这种方案下有三种内存的组织方式: 操作系统位于内存顶端的ROM(只读存储器)中 操作系统位于RAM...
  • 虚拟内存换页的算法有哪些? 最近最少使用算法(LRU):指维护一个所有页面的链表,最近最多使用的页面在表头,最近最少使用的页面在表尾,优先淘汰表尾的页面。...最近未使用算法NRU):优先淘汰没有被访问
  • 虚拟内存换页的算法有哪些? 最优页面置换算法:将最长时间内不再被访问的页面置换标记出来,然后把因调用这个页面而发生的...最近未使用页面置换算法NRU):优先淘汰没有被访问的已修改页面。 先进先出页面置换...
  • 常见的置换算法

    2021-05-24 23:12:33
    4)Clock置换算法(LRU算法的近似实现) 5)最少使用(LFU)置换算法 6)工作集算法 7)工作集时钟算法 8)老化算法(非常类似LRU的有效算法) 9)NRU(最近未使用算法 10)第二次机会算法
  • 页面置换算法

    千次阅读 2018-08-11 10:08:23
    2.最近未使用NRU) OS为每一页面设置了两个状态位,这些位设置在页表,每次访问内存时由硬件更新这些位。 页面分为4类: 第三类页面在他的R位被时钟中断清零后变成第一类,不清除M类是因为决定一个页面是否...
  • LRU 最近最久未使用 FIFO 先进先出置换算法 类似队列 OPT 最佳置换算法 (理想中存在的) NRU Clock置换算法 LFU 最少使用置换算法 PBA 页面缓冲算法 最常见的实现是使用一个链表保存缓存数据,详细算法实现如下 ...
  • 实现了六种页面置换算法:最优算法(OPT)、先来先服务(FIFO)、最近最久未使用(LRU)、时钟算法(CLOCK)、近期最少使用(LFU)、最近最不经常使用(NRU
  • 程序地址空间及常见页面置换算法研究背景以及定义虚拟内存操作系统中...简单的Clock置换算法---最近未使用(NRU)算法 研究背景以及定义 环境:32为平台 在了解程序地址空间之前我们需要知道: 地址:内存地址------对
  • 页面置换算法(二)

    2021-04-21 14:13:39
    咳咳,书接上文,这篇讲非常 难 重要的两个算法LRU和工作集,以及它们的一些改进算法,希望我能给你们讲清楚吧~ LRU 上文提过一点点,LRU和最优算法是刚好相对的,LRU就是Least Recently Used...最近未使用NRU) ...
  • 手写LRU缓存淘汰算法

    2021-04-21 06:22:55
    概述 LRU算法全称为Least Recently Used是一种常见...LRU 最近最久未使用 FIFO 先进先出置换算法 类似队列 OPT 最佳置换算法 (理想中存在的) NRU Clock置换算法 LFU 最少使用置换算法 PBA 页面缓冲算法 LRU的原理 L...
  • 3.4 页面置换算法

    2018-03-30 08:55:45
    2. 最近未使用页面置换算法NRU)页表项中有页面的访问位R位和修改位M位。当启动一个进程时,它的所有页面两个位都初始化成0,且R位会被定期清零(如每次时钟中断)以区别最近没有被访问的页面...
  • //最近最久未使用算法 float opt( const int userMem, const int pageAddrStream[] ); //最佳淘汰算法 float nru( const int userMem, const int pageAddrStream[] ); //最近未用算法 float lfu( const int userMem...
  • LRU缓存算法的实现

    万次阅读 多人点赞 2018-11-06 21:54:54
    LRU LRU(Least Recently Used)是一种常见的页面置换算法,在计算中,所有的文件操作都要放在内存中进行,然而...LRU 最近最久未使用 FIFO 先进先出置换算法 类似队列 OPT 最佳置换算法 (理想中存在的) NRU C...
  • 一、前言  缓存算法历史已经很久了,但在楼主查询相关资料时,发现知识零碎,且原理介绍的很不详细,遂有了总结常用缓存算法... NRU算法的思想是保留最近使用过的对象。  2、工作原理  缓存维护两个标记位...
  • 页面置换算法总结 当发生缺页中断时,操作系统必须将内存中选择一个页面置换出去为要...2. 最近未使用页面置换算法(NRU)算法 找到最久没有使用的页面置换出去,页面被访问时设置R位,修改时设置M位,R位定期清...
  • 大部分知识点王道已经覆盖,这里整理的是个人疏忽或者不熟悉的内容 页框锁定: 因为采用虚存技术会使得进程的运行时间变的不确定,所以给每个页框增加一个锁定位,不让...最近未算法NRU 最近最少使用算法LRU 最.
  • OS中的调度

    2019-11-13 20:51:57
    文章目录OS中的算法CPU调度三种调度方式高级调度中级调度低级调度调度的时机进程调度有关进程调度的基本概念算法FCFS先到先来服务SJF短作业优先优先级调度算法HRRN高响应比优先...又称为NRU最近未算法CLOCK的改进...
  • 操作系统

    2019-07-08 23:22:19
    2.最近未使用页面置换算法NRU) 3.先进先出页面置换算法(FIFO) 4.第二次机会页面置换算法 5.时钟页面置换算法 6.最近最少使用页面置换算法(LRU) 7.用软件模拟LRU 8.工作集页面置换算法 9.工作集时钟...

空空如也

空空如也

1 2
收藏数 38
精华内容 15
关键字:

最近未使用算法nru