精华内容
下载资源
问答
  • 几种缺页中断算法(FIFO,LRU与LFU)的实现过程

    万次阅读 多人点赞 2016-10-13 22:36:25
    几种缺页中断算法(FIFO,LRU与LFU)的实现过程 2015-09-05 20:34:02 分类: LINUX  最近在做笔试题,其中虚拟存储管理中几种缺页中断算法经常考到,虽然这类题可说非常简单,但概念上却容易混淆...
     
    

    分类: LINUX

      最近在做笔试题,其中虚拟存储管理中几种缺页中断算法经常考到,虽然这类题可说非常简单,但概念上却容易混淆而且如果不掌握正确的做法很容易出错,因此觉得有必要把这三种算法的实现过程理一遍,并从源代码级别去思考它们的实现。
     首先推荐一个博客,对这两个算法给出了不易错的演算步骤,也给了我一些启示,这篇博客也给出了源代码,但我没有去验证。
     http://www.cnblogs.com/freeyiyi1993/archive/2013/05/18/3084956.html
     再给出腾讯的笔试题原题: 在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的页面序列是1,2,3,4,1,2,5,1,2,3,4,5.假定分配给该作业的页数为3且作业初始时未装载页面,那么采用FIFO调度算法产生的缺页中断数为多少,采用LRU调度算法产生的缺页中断数为多少?
     FIFO算法:(First In First Out),先进先出,一般看到这类思想,首先想到的数据结构应当是队列,但是我们这里最好是用vector,因为调页过程中需要遍历队列检查该页是否已存在,当算法的存储结构是队列或栈,但实现过程中需要经常遍历全队列或全栈的内容时,最好用vector,这是《剑指Offer》面试题25给我的启发。给出一个访问序列的模拟算法到此应该非常简单了,为了节省时间,下面仅给出题目计算步骤,代码今后再补。
               访问序列:1,2,3,4,1,2,5,1,2,3,4,5
                       1,2,3先调入内存,内存结构:3      2      1    缺页次数:3  
                       4调入内存,1调出,  内存结构:4      3      2    缺页次数:4
                       1调入内存,2调出,  内存结构:1      4      3    缺页次数:5
                       2调入内存,3调出,  内存结构:2      1      4    缺页次数:6
                       5调入内存,4调出,  内存结构:5      2      1    缺页次数:7
                       1存在,内存结构不改变
                       2存在,内存结构不改变
                       3调入内存,1调出,  内存结构:3      5      2    缺页次数:8
                       4调入内存,2调出,  内存结构:4      3      5    缺页次数:9
                       5存在,内存结构不改变
                共缺页9次,缺页中断率 = 缺页中断次数 / 总访问页数 = 9 / 12    
    LRU算法:最近最少使用(Least Recently Used),先看一下调页过程
                 访问序列:1,2,3,4,1,2,5,1,2,3,4,5
                    
    1,2,3先调入内存,内存结构:3      2      1    缺页次数:3  
                    4调入内存,1调出,  内存结构:4      3      2    缺页次数:4
                    1调入内存,2调出,  内存结构:1      4      3    缺页次数:5
                    2调入内存,3调出,  内存结构:2      1      4    缺页次数:6
                    
    5调入内存,4调出,  内存结构:5      2      1    缺页次数:7
               到这一步其实和FIFO并没有区别
                  1调入内存,由于内存中存在1,故没有缺页中断,但由于1最近被访问过,所以要将其位置调换,
                  使它最后一个被淘汰,内存结构:1      5      2
                  2调入内存,没有缺页中断,但内存位置要变化,内存结构:2      1      5
                      3调入内存,5调出,  内存结构:3      2      1    缺页次数:8
                      4调入内存,1调出,  内存结构:4      3      2    缺页次数:9
                      5调入内存,2调出,  内存结构:5      4      3    缺页次数:10
               共缺页10次,缺页中断率:10/12
    算法总结:数据结构应该还是一个队列,开始内存页面不满时按序把页面填入,之后如果调入的页不存在,则按照先进先出顺序,淘汰队头页面,如果调入的页存在,则将该页换至页尾,该页之后的元素前移,这个最好用什么数据结构?
    其实觉得腾讯这道题的序列没有代表性,要真正理解LRU过程中内存存储页面结构的变化情况,还是推荐看一下上面的博客。
    LFU算法:最近最不经常使用(Least Frequently Used),相比于前两个,LFU算法的资料要少得多,因为它的实现更加复杂,在网上搜到这个博客,http://www.cnblogs.com/tingyuxuan007/p/3823537.html,这个博客有这三个算法思想的讨论及图解,有利于初学者去彻底弄懂这个问题,现摘录一些它的语句来说清楚这个算法的思想:
    这是一个基于访问频率的算法.与LRU不同,LRU是基于时间的,会将 时间上 最不常访问的数据淘汰;LFU为将 频率上 最不常访问的数据淘汰.既然是基于频率的,就需要有存储 每个数据访问的次数 .从存储空间上,较LRU会多出一些持有计数的空间.”,它描述这个算法的图也很经典
                
    我想有这幅图就已经不需要再多说什么了,如果还有不明白的,去原博客看一下叙述就行了。
    还是把腾讯这道题用LFU算法再做一遍:
        访问序列:1,2,3,4,1,2,5,1,2,3,4,5  
         最初:                3(1)      2(1)      1(1)       缺页次数:3      括号中是其访问次数   
            调入4                 4(1)       3(1)      2(1)       淘汰1,缺页次数:4 
            调入1                 1(1)       4(1)      3(1)       淘汰2,缺页次数:5 
            调入2                 2(1)        1(1)      4(1)       淘汰3,缺页次数:6 
            调入5                 5(1)        2(1)       1(1)       淘汰4, 缺页次数:7
            调入1                 1(2)       5(1)      2(1)
            调入2                 2(2)       1(2)      5(1)
            调入3                 2(2)        1(2)      3(1)       淘汰5,缺页次数:8 
            调入4                 2(2)       1(2)      4(1)       淘汰3,缺页次数:9
            调入5                 2(2)       1(2)      5(1)       淘汰4,缺页次数:10
        共缺页10次,缺页中断率:10/12
    展开全文
  • 页面置换又叫缺页中断算法,是为了解决: 在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其...

    1 - 页面置换算法

    页面置换又叫缺页中断算法,是为了解决:

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

    • 最佳置换法(OPT)
    • 先进先出置换法(FIFO)
    • 最近最久未使用置换法(LRU)
    • 时钟置换(CLOCK)

    下面分别介绍

    最佳置换(OPT)

    每次选择淘汰的页面时以后永不使用的页面,或者是在最长时间内不会使用的页面,保证最低的缺页率

    缺页率 = 缺页中断次数 / 访问页面总数

    注意缺页中断次数≠页面置换次数,因为内存中还有空闲的内存块时,只发生了缺页中断,然后调入页,没有发生页面置换

    但是只有在进程执行过程中预测不了下一次将要访问的页面是谁,所以该算法在实际应用上时实现不来的

    先进先出置换法(FIFO)

    每次置换出内存的页是进入内存时间最久的页

    实现:内存页面根据调入内存的时间进行排序,进入内存时间最早的排在队首,这样每次只需要置换出队首页面,将置换进内存的页面排在最后

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

    每次置换出内存的页面时最近最久没有使用到的页面

    实现:和FIFO一样维护一个队列,但是排序规则不再是进入内存的时间了,每次页面访问后,若目标页面存在,将它排到队首,表示它是最近使用的一个页面,若目标页面不在内存中,将目标页面调入内存,排在队首(还表示它是最近使用的页面);将队尾页面(最不常使用)置换出内存

    时钟置换(CLOCK)

    使用链接指针将内存中的页面连成一个循环队列,为每个页面设置一个访问位。某页被访问后,访问位置1。淘汰页面时,检查页的访问位,若为0就置换出内存,若为1就将其置为0(不置换出内存),继续看下一个页面,直到第一轮扫描结束要是还没有置换出页面,就开始第二轮扫描(第二轮扫描一定会有被置0的页面存在,把它置换出去)

    2 - 进程调度算法

    无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,以使之执行。

    常见的进程调度算法如下:

    • 先来先服务(FCFS)
    • 短作业优先(SJF)
    • 最短剩余时间优先(SRTN)
    • 时间片轮转
    • 高优先级优先
    • 多级反馈队列

    下面分别介绍:

    先来先服务(FCFS)

    按照进程的请求顺序来调度CPU为为哪个进程服务

    短作业优先(SJF)

    非抢占式,每一次调度当前运行时间最短的进程(运行时间是估计出来的)。一个进程被调度后会一直执行完才会调度下一个

    最短剩余时间优先(SRTN)

    抢占式,一个新作业(进程请求CPU视为一个作业)到达时,与当前执行的作业比较剩余执行时间(也是估计的),谁最短就执行谁,说明当前进程有可能还没有执行完就挂起了

    时间片轮转

    所有就绪进程按照到达时间排队,每次调度队首的进程,分配给他一个时间片,时间片用完之后将该进程排在队尾(如果还没有执行完的话)

    高优先级优先

    每个进程分配优先级,每次调度优先级最高的进程

    多级反馈队列

    是时间片轮转与高优先级优先的结合

    设置多个优先级队列,不同队列的优先级不同,不同队列的时间片也不同,如果进程在小时间片队列中没有完成作业,就把它排进时间片更大的队列中

    3 - 动态分区分配算法

    所谓动态分区分配,就是指内存在初始时不会划分区域,而是会在进程装入时,根据所要装入的进程大小动态地对内存空间进行划分,以提高内存空间利用率,降低碎片的大小

    将空闲内存看做一张表的话,动态分区就是在不同的算法下按照某算法对应的规则从空闲内存表的一段取出来

    • 首次适应算法
    • 最佳适应算法
    • 最坏适应算法
    • 邻近适应算法

    下面分别介绍:

    首次适应算法

    从低地址开始找,找到第一个满足大小的空闲分区

    最佳适应算法

    遍历空闲分区表,找到满足要求的最小的分区

    最坏适应算法

    遍历空闲分区表,找到满足要求的最大的空闲分区

    邻近适应算法

    每次分配内存都从上次查找结束的位置开始查找空闲分区表,找到第一个满足要求的空闲分区

    4 - 磁盘调度算法

    磁盘调度简言之,就是怎样移动磁头来寻找磁盘上的存储数据

    常见的磁盘调度算法有:

    • 先来先服务
    • 最短寻道时间优先
    • 电梯扫描

    下面分别介绍:

    先来先服务

    按照磁盘请求的顺序

    最短寻道时间优先

    优先调度与当前磁头所在磁道距离最近的磁道

    电梯扫描

    先按照一个方向(比如升序、降序)来晋城磁盘调度,直到该方向上没有未完成的磁盘请求,然后再做反方向的(注意一定是从峰值/谷值做的反方向)

    展开全文
  • 缺页中断算法(FIFO,LRU)

    千次阅读 2018-09-19 09:30:04
    1. 缺页中断  在请求分页系统中,可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时,会产生一次缺页中断,此时操作系统会根据页表中的外存地址在外存中找到所缺的...

     

    1. 缺页中断

      在请求分页系统中,可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时,会产生一次缺页中断,此时操作系统会根据页表中的外存地址在外存中找到所缺的一页,将其调入内存。 
      缺页本身是一种中断,与一般的中断一样,需要经过4个处理步骤: 
      1. 保护CPU现场 
      2. 分析中断原因 
      3. 转入缺页中断处理程序进行处理 
      4. 恢复CPU现场,继续执行 
      但是缺页中断时由于所要访问的页面不存在与内存时,有硬件所产生的一种特殊的中断,因此,与一般的中断存在区别: 
       1. 在指令执行期间产生和处理缺页中断信号 
       2. 一条指令在执行期间,可能产生多次缺页中断 
       3. 缺页中断返回时,执行产生中断的那一条指令,而一般的中断返回时,执行下一条指令

    2. 页面置换算法

      进程运行过程中,如果发生缺页中断,而此时内存中有没有空闲的物理块是,为了能够把所缺的页面装入内存,系统必须从内存中选择一页调出到磁盘的对换区。但此时应该把那个页面换出,则需要根据一定的页面置换算法(Page Replacement Algorithm)来确定。

    2.1 最佳置换(Optimal, OPT)

    2.1.1 基本思想

      置换以后不再被访问,或者在将来最迟才回被访问的页面,缺页中断率最低。但是该算法需要依据以后各业的使用情况,而当一个进程还未运行完成是,很难估计哪一个页面是以后不再使用或在最长时间以后才会用到的页面。所以该算法是不能实现的。但该算法仍然有意义,作为很亮其他算法优劣的一个标准。

    2.1.2 算例

      采用固定分配局部置换的策略,嘉定系统为某进程在内存中分配了3个物理块,页面访问顺序为2、3、2、1、5、2、4、5、3、2、5、2。假定系统未采用预调页策略,即未事先调入任何页面。进程运行时,一次将2、3、1三个页面调入内存,发生3次缺页中断。当第一次访问页面5时,产生第4次缺页中断,根据OPT算法,淘汰页面1,因为它在以后不会在使用了;第5次缺页中断时,淘汰页面2,因为它在5、3、2三个页面中,是在将来最迟才会被页面访问的页面。以此类推: 
      注意:第4次中断时将最后不会访问的1剔除,将最后才访问的3放入最下面的内存块中,以后的调度过程中,最后不会访问或最后才被访问的页面总是放在最下面的内存块中。内存块从上到下依次存放最先访问的页面。 
      中断次数为6,缺页中断率为6/12*100% = 50%。

    P:232152453252
    M=3222225535522
      33353354255
        132443444
    F=5YY YY Y  Y  

    2.2 先进先出置换算法(First In First Out, FIFO)

    2.2.1 基本思想

      置换最先调入内存的页面,即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列,从队尾进入,从队首删除。但是该算法会淘汰经常访问的页面,不适应进程实际运行的规律,目前已经很少使用

    2.2.2 算例

      仍然以OPT算例为例子。 
      中断次数为9,缺页中断率为9/12*100% = 75%。

    P:232152453252
    M=3233152443352
      22315224435
        231552243
    F=9YY YYYY Y  Y

    2.2.3 Belady异常

      一般来说,分配给进程的物理块越多,运行时的缺页次数应该越少,使用FIFO时,可能存在相反情况,分配4个物理块的缺页竟然比3个物理块的缺页次数还多! 
      例如:进程访问顺序为0、2、1、3、0、2、4、0、2、1、3、4。 
      M=3时,缺页中断9次。缺页中断率9/12*100% = 75%。

    P:021302402134
    M=3021302444133
      02130222411
       0213000244
    F=9YYYYYYY  YY 

      M=4时,缺页中断10次。缺页中断率10/12*100% = 83.3%。

    P:021302402134
    M=4021333402134
      02111340213
       0222134021
        000213402
    F=10YYYY  YYYYYY

    2.3 最近最久未使用置换算法(Least Recently Used, LRU)

    2.3.1 基本思想

      置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理,刚被访问的页面,可能马上又要被访问;而较长时间内没有被访问的页面,可能最近不会被访问。 
      LRU算法普偏地适用于各种类型的程序,但是系统要时时刻刻对各页的访问历史情况加以记录和更新,开销太大,因此LRU算法必须要有硬件的支持。

    2.3.2 算例

      仍然以OPT算例为例子。 
      中断次数为7,缺页中断率为7/12*100% = 58.3%。

    P:232152453252
    M=3232152453252
      23215245325
        321524533
    F=7YY YY Y YY  

      堆栈实现LRU: 
      系统使用特殊的堆栈来存放内存中每一个页面的页号。每当访问一页时就调整一次,即把被访问页面的页号从栈中移出再压入栈顶。因此,栈顶始终是最新被访问页面的页号,栈底始终是最近最久未被访问的页号。当发生缺页中断时,总是淘汰栈底页号所对应的页面。 
      

    参考

    1. 温静,计算机操作系统原理,武汉大学出版社  

     

     

     

     

    展开全文
  • 处理缺页中断可使用如下算法进行对比: 1. 先来先服务算法; 2. LRU算法
  • 处理缺页中断时使用LRU算法进行 实验具体包括:首先对给定的地址进行地址转换工作,若发生缺页则先进行缺页中断处理,然后再进行地址转换;最后编写主函数对所作工作进程测试。
  • 缺页中断就是要访问的页不在主存,需要操作系统将其调入主存后再进行访问。 在进行内存访问时,若所访问的页已在主存,则称此次访问成功; 若所访问的页不在主存,则称此次访问失败,并产生缺页中断。 最佳置换法...

    缺页中断就是要访问的页不在主存,需要操作系统将其调入主存后再进行访问。

    在进行内存访问时,若所访问的页已在主存,则称此次访问成功;

    若所访问的页不在主存,则称此次访问失败,并产生缺页中断。

    最佳置换法:

    例如:假定系统为某进程分配了3个物理块,进程访问的页面的顺序为0,7,6,5,7,4,7,3,5,4,7,4,5,6,5,7,6,0,7,6.求在访问过程中缺页中断?

    解答:进程运行时先将0,7,6三个页面装入内存,当访问到第5时,产生页面中断,根据最佳置换法,(将未来最长时间内不再访问的页面置换出去),页面0将在18次才被访问到,所以它是这三页中最久不被访问到的页面,所以被淘汰置换出来,将5换进去。接着访问第7页,因为第7页是在内存中,所以不会产生缺页中断,以此类推……

    采用最佳置换算法,产生了9次缺页中断,发生了6次页面置换。

     

    转载于:https://www.cnblogs.com/dyc-1234/p/6768649.html

    展开全文
  • 缺页中断处理算法

    千次阅读 2018-01-22 10:42:40
    缺页中断:在请求分页系统中,可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存是,会产生一次缺页中断,此时操作系统会根据页表中的外存地址在外存中找到所缺的一页,...
  • 模拟请求页式存储管理中硬件的地址转换和缺页中断,并用先进先出调度算法FIFO处理缺页中断.doc
  • 模拟分页式虚拟存储管理中硬件的地址转换和缺页中断,以及选择页面调度算法处理缺页中断
  • 缺页中断及页面置换算法

    千次阅读 2017-10-06 13:57:19
    缺页中断 在请求分页系统中,可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时,会产生一次缺页中断,此时操作系统会根据页表中的外存地址在外存中找到所缺的一页,...
  • $多系汕乂琴实验报告 课程名称 操作系统原理 实验名称 虚拟页式管理 姓 名 学号 ...并用 先进先出调度算法FIFO处理缺页中断 1内容模拟请求页式存储管理中硬件的地址转换和缺页中断处理 2.思想 装入新页置换旧页时若旧页
  • 缺页中断与页面置换算法

    千次阅读 2019-04-06 17:42:26
    缺页中断 页面置换算法: LRU算法 缺页中断 缺页:如果进程被调度,该进程需要使用的外存页(数据)不存在于数据块中,这个现象就叫做缺页。如果这个数据此时不在,就会将这个数据从加入到数据块首部。缺页本身...
  • 程名称 操作系 原理 名称 虚 式管理 姓 名 学号 班 网 日期 成 指 教 安科 目的 原理主要 器 内容与步 数据 与 理 果与分析 建 实验二 模拟请求页式存储管理中硬件的地址转换和缺页中断 并用 先进先出调度算法 ...
  • 缺页中断FIFO算法模拟实现——vector(c++) 原理 和名字一样,最近最久未使用页面置换算法 实现 下面以 {2,3,2,1,5,2,4,5,3,2,5,2}为申请装入的页号, 页表大小为3。 在FIFO算法基础上,只需要PageFault()函数内,对...
  • 置换以后不再被访问,或者在将来最迟才回被访问的页面,缺页中断率最低。 Optimal最佳置换算法,该算法是不能实现的。但该算法仍然有意义,作为衡量其他算法优劣的一个标准。 实现 下面以 {2,3,2,1,5,2,4,5,3,2,5,2}...
  • 1. 缺页中断 2. 缺页中断的断点 缺页中断是指令执行过程中产生的中断,而非(一般的中断)在一条指令执行完成后产生的。 3. 缺页中断的断点压入 当CPU执行指令希望访问一个不在内存的页面时,将产生缺页中断,系统...
  • 1.模拟分页式存储管理中硬件的地址转换和产生缺页中断。 2.用先进先出(FIFO)页面调度算法处理缺页中断
  • 实现功能: 1、模拟分页式存储管理中硬件的士转换和产生缺页中断 2、用先进先出(FIFO)页面调度算法处理缺页中断 3、用最近最少用(LRU)页面调度算法处理缺页中断
  • 记录一下,后续有时间可能会增加简便的模拟算法实现。 原理:先进先出 下面以 {2,3,2,1,5,2,4,5,3,2,5,2}为申请装入的页号, 页表大小为3。 准备 vector v 存储所要访问的页面 :{2,3,2,1,5,2,4,5,3,2,5,2} vector ...
  • 缺页中断

    2019-09-24 05:19:30
    缺页中断缺页中断就是要访问的页不在主存,需要操作系统将其调入主存后再进行访问。在这个时候,被内存映射的文件实际上成了一个分页交换文件。  中断:是指计算机在执行程序的过程中,当出现异常情况或特殊请求...
  • Linux——缺页中断与内存置换算法,你想知道的都在这里!缺页中断页面置换算法缺页次数一、先进先出(FIFO)二.最近最久未使用(LRU)三、最佳置换算法(OPT) 缺页中断 缺页中断就是要访问的页不在主存,需要操作...
  • 1、 缺页中断 在请求分页系统中,可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时,会产生一次缺页中断,此时操作系统会根据页表中的外存地址在外存中找到所缺的一...
  • 先进先出调度算法处理缺页中断

    千次阅读 2019-09-23 07:31:59
    模拟页式虚拟存储管理中硬件的地址转换和用先进先出调度算法处理缺页中断 实验内容与步骤↓↓↓ 编写程序,模拟页式虚拟存储管理中硬件的地址转换和用先进先出调度算法处理缺页中断。 假定主存的每块长度为...
  • 详解缺页中断-----缺页中断处理(内核、用户)

    万次阅读 多人点赞 2018-08-06 18:21:42
    一、什么是缺页中断? 进程线性地址空间里的页面不必常驻内存,在执行一条指令时,如果发现他要访问的页没有在内存中(即存在位为0),那么停止该指令的执行,并产生一个页不存在的异常,对应的故障处理程序可通过...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,272
精华内容 3,708
关键字:

缺页中断算法