精华内容
下载资源
问答
  • 操作系统:页面置换算法(LRU、FIFO、OPT)
    千次阅读
    2021-12-18 17:29:18

    继续重温操作系统系列知识,页面置换的三种常见算法为:LRU(最近最久未使用)、FIFO(先进先出)、最佳置换。

    部分公司的面试会考到LRU的知识。

    LRU置换算法

    所谓LRU置换算法,单看字面意思较为麻烦,实际上在进行页面置换的过程中,被替换的页面块只需要按照“很久之前使用了,但最近没有使用”的规则进行选取就可以了。不需要考虑后续页面走向是否又需要读入符合上述规则的页面,因为这正是LRU的缺点。

    最佳置换算法

    这种算法选取被替换页面的时候,遵循以下两点

    1.某个页面后续走向永远不会访问到,所以它可以直接被置换。

    2.某个页面需要过很久才会访问到,优先替换它。

    这种算法的优点是理论上缺页率比较低。

    先进先出算法

    替换规则为替换当前走向所有的物理块中那个最早进入的页面。

    例题

    假设存在一个走向,4,1,2,5,3,4,6,3,1,2。当分配的物理块M=5时,分别求FIFO、LRU、最佳置换算法的页面走向(假设初始时为空块)。

    例题LRU解法

    LRU表
    走向4125346312
    块14444333333
    块2111144442
    块322226666
    块45555511
    缺页
    置换

    (1).对于LRU,首先按照顺序填好走向,并填满前面的物理块,与其他算法一样。

    很显然在一开始每次都需要调入所需页面。因此,前面几次都是缺页,但没有产生置换。

    (2).开始进入置换过程。

    对于接下来的走向页面3而言,块中无3说明缺页,块中已满调入3则说明需要置换。

    通过观察我们可以得知最近的页面,无论是4、1、2、5,都只是调用了一次,因此我们需要替换最久未使用的4。

    但有的时候并不会这么简单,那如果走向不再是4125,而是是4、1、4、5呢?有2个4,还要不要替换4?

    那么答案是:则应该替换1,因为虽然4是最早入块的,但是最近4使用过,所以不再是最久未使用的。排除4后1最久未使用,5刚刚使用过。

    本题走向为4、1、2、5,因此走向3的块序列为3、1、2、5.

    对于接下来的走向页面4而言,因为上一次的序列为3、1、2、5很显然没有4,但又满物理块,所以既置换又缺页。

    按照刚刚的示例,在前面的走向4、1、2、5、3中,很显然最久未使用的是1,所以需要替换1.

    因此走向4的块序列为3、4、2、5.

    对于接下来的走向6而言,最近最久未使用的是2(其实可以观察2和5的长度,在3、4、2、5中,又无重复项目,而2是最久未使用的)。所以替换2.

    结果是3、4、6、5,很显然缺页6又置换2。

    对于接下来的走向3而言,存在3,所以不需要置换、也不缺页。

    对于1而言,最近的序列为(3、4、6、5),观察发现5和3的序列横向一样长,然而3刚刚调用过,所以需要替换5.

    结果为3、4、6、1

    对于接下来的走向2而言,我们发现最近的序列为(3、4、6、1),通过观察可以发现4-3-6-1走向中4最久未使用,所以替换4.

    结果为3、2、6、1.

    最终我们填写了整个LRU的置换表。

    例题FIFO算法

    走向4125346312
    块14444333332
    块2111144444
    块322226666
    块45555511
    缺页
    置换

    按照先进的先被替换,雷打不动,就可以做出了,这道题答案基本上和LRU一样,就是最后一个走向有些区别。

    解题时候遇到重复性的走向容易出错,规避即可。

    例题最佳置换算法

    页面

    4

    1

    2

    5

    3

    4

    6

    3

    1

    2

    块1

    4

    4

    4

    4

    4

    4

    6

    块2

    1

    1

    1

    1

    1

    1

    块3

    2

    2

    2

    2

    2

    块4

    5

    3

    3

    3

    缺页否

    置换否

    对于走向3而言,我们可以看到后面的走向46312,3、2、1是最久会再次调用的,可以替换2,因为2是最后要访问的,但由于块4的5在后面是永远不会被再次调用的,所以不替换2,要替换5.

    结果为4、1、2、3.

    下一个走向含有4,因此不缺页也不置换。

    接下来的走向6,很显然走向4的页面已经不再需要了(后续走向无4),所以替换走向4,最终结果很巧妙,完全不缺页也不置换。

    以上就是三种常见的解法

    更多相关内容
  • 该C语言代码实现了操作系统os实验中的三种页面置换算法: 最佳置换算法(OPT)、先进先出算法(FIFO)、最近最久未使用算法(LRU) 输入:物理块和页面大小,可选择自行输入数据或程序随机生成页面号序列 输出:显示三种...
  • LRU Least Recently Used C语言

    前言

    LRU算比较经典,而且考的也比较多,LRU算法全称Least Recently Used,译为最近最少使用。用C模拟一下吧。

    Buddy算法:操作系统学习之用C语言模拟伙伴(Buddy)算法
    FIFO算法:操作系统学习之用C语言模拟FIFO算法
    LRU算法:操作系统学习之用C语言模拟LRU算法
    Clock算法:操作系统学习之用C语言模拟CLOCK算法
    本源代码原创,转载请注明,同时由于本人才疏学浅,刚入门操作系统,如有错误敬请指教
    本文原创,创作不易,转载请注明!!!
    本文链接
    个人博客:https://ronglin.fun/?p=202
    PDF链接:见博客网站
    CSDN: https://blog.csdn.net/RongLin02/article/details/117632296

    算法模拟

    教科书原图
    在这里插入图片描述

    算法解释

    先来看看课本上的解释。
    LRU策略置换内存中最长时间未被引用的页。根据局部性原理,这也是最近最不可能访问到的页。实际上,LRU策略的性能接近于OPT(OPTimal 最佳)策略。这种方法的问题是比较难实现。一种实现方法是给每页添加一个最后一次访问的时间戳,并在每次访问内存时更新这个时间戳。即使有支持这种方案的硬件,开销仍然非常大。另一种方法是维护一个关于访问页的栈,但开销同样很大。 ——操作系统-精髓与设计原理(第九版)P227

    代码解释

    简单的来说,就是LRU策略很好,但是实现起来比较复杂,我代码用的是添加时间戳的方式。定义了一个结构体,两个属性,一个用来存储数据(data),另一个就是时间戳(time)。
    在处理每一个到来的"进程"时,先判断其是否在队列中,如果在就更新时间戳,如果不在,就置换走时间戳最早的那个进程。

    源代码

    #include<stdio.h>
    #define MAX_NUM 3
    #define MAX_NUM_PROC 512
    
    
    //进程结构体
    struct LList
    {
        int data;
        int time;
    }LRU_list[MAX_NUM];
    
    /*
    12
    2 3 2 1 5 2 4 5 3 2 5 2
    */
    
    int main()
    {
        for(int i=0;i<MAX_NUM;i++)
        {
           LRU_list[i].data = 0;
           LRU_list[i].time = 0;
        }
    
        int n;
        int a[MAX_NUM_PROC];
        printf("请输入个数:");
        scanf("%d",&n);
        printf("请输入%d个非零数字:\n",n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
    
        for(int i=0;i<n;i++)
        {
            //先找原来的队列中是否存在
            int exist =0;
            for(int j=0;j<MAX_NUM;j++)
            {
                if(LRU_list[j].data == a[i])
                {
                    exist = 1;
                    LRU_list[j].time = i+1;//留下时间戳
                    break;
                }
            }
            //不存在
            if(!exist)
            {
                int i_minn=0;
                for(int j=1;j<MAX_NUM;j++)
                {
                    if(LRU_list[i_minn].time > LRU_list[j].time)
                    {
                        i_minn = j;
                    }
                }
    
                LRU_list[i_minn].data = a[i];
                LRU_list[i_minn].time = i+1;
            }
    
            printf("本次队列情况:");
            for(int j=0;j<MAX_NUM;j++)
            {
                printf("%d",LRU_list[j].data);
                if(j==MAX_NUM-1)
                {
                    if(!exist)
                        printf(" F");
                    printf("\n");
                }
                else
                {
                    printf(" ; ");
                }
            }
        }
        return 0;
    }
    
    

    输出解释

    请输入个数:12
    请输入12个非零数字:
    2 3 2 1 5 2 4 5 3 2 5 2
    本次队列情况:2 ; 0 ; 0 F
    本次队列情况:2 ; 3 ; 0 F
    本次队列情况:2 ; 3 ; 0
    本次队列情况:2 ; 3 ; 1 F
    本次队列情况:2 ; 5 ; 1 F
    本次队列情况:2 ; 5 ; 1
    本次队列情况:2 ; 5 ; 4 F
    本次队列情况:2 ; 5 ; 4
    本次队列情况:3 ; 5 ; 4 F
    本次队列情况:3 ; 5 ; 2 F
    本次队列情况:3 ; 5 ; 2
    本次队列情况:3 ; 5 ; 2
    

    F表示缺页,为了方便,当询问LRU链表为空时也会被判定为缺页。
    可以看到和教科书上的结果相同。
    LRU我用的是增加时间戳,用变量i作为时间戳。

    总结

    LRU算法用C模拟起来比较简单,但是结合起硬件就比较麻烦了,维护其队列开销确实比较大。=w=

    展开全文
  • 可以体现Clock算法和LRU算法的的思想,用于操作系统的课程实训。 任务要求 从置换算法中任选1种(OPT、LRU、Clock); 建立页表 设计的输入数据要能体现算法的思想 模拟缺页中断过程; 求出各置换算法中的缺页...
  • LRU的思想实现缺页中断以及页面置换。C语言实现,按照最近最久未被访问的思想去实现这个算法。输出每一次页面置换之后的过程以及最后的缺页中断次数与缺页中断率。
  • 操作系统实训选题,通过三种算法(OPT、LRU、FIFO)实现模拟页面置换的工作过程。初始设定最多20个页面引用串,设定3个物理块。缺页率如果要输出,去掉注释//,把20改为获取用户输入字符串长度。有三个版本,1.0是...
  • 操作系统页面置换算法模拟实现,fifo、lfu、lru、opt,界面由MFC实现
  • 操作系统LRU算法

    2017-01-14 21:49:52
    操作系统LRU算法
  • c++实现操作系统请求调页功能 分别有FIFO LRU 和OPT 算法
  • 存储管理详细实验报告和cpp文件,含FIFO和LRU的比较,实验报告都是我一个一个字敲进去的。
  • 代码主体非本人原创,主要内容来源于:https://blog.csdn.net/houchaoqun_xmu/article/details/55541715,由于原代码测试中有些问题,因此我经过修改...可以实现LRU、OPT、FIFO算法打印置换情况并计算缺页数、缺页率。
  • 操作系统LRU

    2008-07-06 12:34:25
    操作系统,实验程序,自己根据课本写的 C语言实现
  • 这是一个自己完成软件工程的操作系统课程课程设计题目:此程序用于模拟虚拟磁盘页面置换算法,实现了FIFO页面置换算法和LRU页面置换算法,获得课程设计优秀的好成绩
  • jq实现操作系统LRU置换算法
  • 操作系统FIFO,LRU,OPT算法Java实现
  • 本实验使用一下算法 使用rand()函数随机产生页面号,用数组装入页面号,模拟页面调入内存中发生页面置换的过程。 整个过程,都是使用数组来实现每...最近最久未使用置换算法(LRU): 以“最近的过去”作为“最近的将
  • 操作系统 LRU

    2011-12-09 15:48:50
    用C++ list 标准函数写的LRU算法 希望对大家有帮助
  • 文档内部为实验报告(包含全部代码及演示图)。操作系统lru页面置换
  • 操作系统页面置换LRU,FIFO,OPT,LFU算法实现代码,使用C#动态实现,有TLB快表,可设置页面数量、驻留集大小、自动生成十六进制地址码,分析页号,可设置TLB时间,访问内存时间。
  • 操作系统 页面替换算法(OPT最佳置换算法与LRU最近最久未使用算法)
  • 其基本原理为:当进程在CPU上运行时,如指令中涉及逻辑地址时,操作系统自动根据页表得到页号相关信息。 如果某一个页面被访问了,它很可能还要被访问;相反,如果它长时间不被访问,再最近未来是不大可能被访问的。...

    1.实验目的
    用高级语言模拟页面置换算法LRU,加深对LRU算法的认识。 2.实验要求
    用高级语言模拟页面置换算法LRU,加深对LRU算法的认识。
    3.实验过程描述
    原理(思路)
    其基本原理为:当进程在CPU上运行时,如指令中涉及逻辑地址时,操作系统自动根据页表得到页号相关信息。 如果某一个页面被访问了,它很可能还要被访问;相反,如果它长时间不被访问,再最近未来是不大可能被访问的。

    4.实验代码

    package 实验四;
    public class Lru {
        static int[][] LRU=new int[3][2];
        private static int[][] add(int i) {
            int max=-1;
            int index=0;
            if (NoExist(i)==-1){
                for (int j = 0; j < LRU.length ; j++) {
                    if (LRU[j][1]>max){
                        index=j;
                        max=LRU[j][1];
                    }
                }
                LRU[index]=new int[]{i,-1};
            }else {
                for (int j = 0; j < LRU.length ; j++) {
                    if (LRU[j][0]==i){
                        LRU[j][1]=-1;
                        break;
                    }
                }
    
            }
            for (int j = 0; j <LRU.length ; j++) {
                LRU[j][1]++;
            }
            return LRU;
        }
    
        private static int NoExist(int i) {
            for (int j = 0; j <LRU.length ; j++) {
                if (i==LRU[j][0])return j;
            }
            return -1;
        }
    }
    public static void main(String[] args) {
            int[] page_table={1,2,1,3,6,1,2,3,1,2,3,4,1,3};
            System.out.println("页号 页号 页号  ");
            for (int i :page_table) {
                    LRU=add(i);
                for (int[] J: LRU) {
                    System.out.print(J[0]+"   ");
                }
                System.out.println();
            }
        }
    

    5.实验结果

    在这里插入图片描述

    上一篇操作系统 之 银行家算法 (java)

    如果本文章对你有用 记得点赞哦 ( ̄∇ ̄)

    展开全文
  • 实验报告三 内存页面置换算法的设计 姓名田玉祥 班级计算机科学与技术专业一班 一 实验内容 实现最近最久未使用LRU置换算法 二实验目的 LINUX 中为了提高内存利用率提供了内外存进程对 换机制内存空间的分配和回收均...
  • 操作系统LRU算法C语言实现 前言 本机为微软Surface pro4,为64位,所用操作系统为Windos 10。本机虚拟机版本为Oracle VM VirtualBox 6.1.8,所用操作系统是使用Ubuntu18.04,。Ubuntu的虚拟硬盘设置为200G,显存为...

    操作系统LRU算法C语言实现

    前言
    本机为微软Surface pro4,为64位,所用操作系统为Windos 10。本机虚拟机版本为Oracle VM VirtualBox 6.1.8,所用操作系统是使用Ubuntu18.04,。Ubuntu的虚拟硬盘设置为200G,显存为128MB,内存为4GCPU2个,所用镜像源为清华大学软件镜像源。所使用linux内核为linux-5.11.8

    注意事项
    (1)本LRU算法的实现思路是借鉴网上的相关资源,并非原创。
    (2)本篇博客代码只实现LRU算法的置换显示,采用了固定化的方式。

    LRU算法介绍
    LRU算法:是为虚拟页式存储管理服务的,LRU算法的提出,是基于这样一个事实:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

    Linux下C语言实现LRU算法的代码
    1、使用文件编辑器在主目录下创建一个名为OS3的文件夹。

    2、打开Geany程序,然后点击新建按钮,创建一个新文件。
    (注:创建完成界面如下)

    3、在新建的文件中书写程序。(注:程序如下)

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // 全局变量
    char stack[5] ={0}; //栈
    char visit_pages[11] = {'3', '5', '0', '5', '1', '0', '8', '2', '5', '1', '3'}; //访问轨迹
    
    // 打印栈元素
    void print_stack()
    {
        int m;
        // 打印栈元素
        for (m=0; m<5; m++) {
            if (stack[m] == NULL) {
                printf("  -");
            } else {
                printf("  %c", stack[m]);
            }
        }
        printf("\n\n");
    }
    
    //移动栈值
    void change_stack(int index, int i)
    {
        int temp, k;
        //将栈底元素保存后,依次往前覆盖
        temp = stack[index];
        for (k=index; k<5; k++) { //相等下标值之后,往前覆盖
            if (index != 0) {//只有当栈不满时,可直接跳出循环
                if (stack[k+1] == NULL) {
                    break;
                }
            }
            if (k+1 < 5) {
                stack[k] = stack[k+1];
            }
        }
        // 两种不同情况使用不同赋值
        if (index != 0) {
            if (k == 5) {
                k = 4;
            }
            stack[k] = temp; //冒泡到顶部
            stack[k] = visit_pages[i]; //替换顶部值
        } else {
            stack[4] = temp; //冒泡到顶部
            stack[4] = visit_pages[i]; //替换顶部值
        }
    }
    
    int main()
    {
        int i, j, k;
        int index; //下标
        int temp; //值中间量
    
        //栈赋值
        for (i=0; i<5; i++) {
            stack[i] = NULL;
        }
    
        printf("初始值: \n");
        print_stack(); //初始栈打印
        for (i=0; i<strlen(visit_pages); i++) {
            for (j=0; j<5; j++) {
                if (stack[j] == NULL) {
                    stack[j] = visit_pages[i];
                    break;
                }
                if (stack[j] == visit_pages[i]) {//栈内有访问元素
                    if (j+1 < 5 && stack[j+1] == NULL || j == 4) { //访问的元素为顶部元素,且其再顶部元素为NULL,or, 访问元素为栈顶元素,跳出循环
                        break;
                    }
                    change_stack(j, i); //移动栈值
                } else if (j == 4 && stack[j] != visit_pages[i]) {//栈内无访问元素
                    change_stack(0, i); //移动栈值
                }
            }
            printf("---> %c:\n", visit_pages[i]);
            print_stack();
        }
    
        return 0;
    }
    
    

    4、将程序文件命名lru.c为保存到OS3文件下。(注:如图所示)

    LRU算法实现效果如下
    1、按如下图示中标明顺序点击按钮执行即可(注:效果图如下)

    展开全文
  • 操作系统LRU页面置换算法
  • 操作系统 LRU算法 实验报告 及 程序代码服务一条龙 呵呵
  • 模拟了操作系统页面置换的过程,使用Java语言实现了四种经典算法,即OPT算法、LRU算法、FIFO算法、CLOCK算法,并且利用Java图形库制作了一个粗糙的图形化界面。整个页面置换过程完全使用数组实现,并未定义复杂的...
  • 实验报告三 内存页面置换算法的设计 姓名田玉祥 班级计算机科学与技术专业一班 一 实验内容 实现最近最久未使用 LRU 置换算法 二实验目的 LINUX 中为了提高内存利用率 提供了内外存进程对换机制内存空间的分配和回收...
  • 操作系统LRU置换算法实现

    千次阅读 2020-12-17 20:20:21
    最近最久未使用(LRU)置换算法原理 就是:当需要淘汰某页面时,选择当前一段时间内最久未使用过的页先淘汰, 即淘汰距当前最远的上次使用的页。 例如: 分配给该进程的页块数为3,一个20长的页面访问序列为 :12560,...
  • 缓存需要考虑:(1)缓存数据和目标数据的一致性问题(命中or 缺页) (2)缓存的过期策略(FIFO先进先出,LRU Least Recently Used ...在一个徐i存储管理系统中,假如系统分配给以个作业的内存物理块数是3,并且此作

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 79,233
精华内容 31,693
关键字:

lru 操作系统

友情链接: 3GPP-3D-TR36.873-c10.rar