当前位置:   article > 正文

Linux——缺页中断与内存置换算法,你想知道的都在这里!_lru置换算法计算432143543215

lru置换算法计算432143543215

缺页中断

缺页中断就是要访问的页不在主存,需要操作系统将其调入主存后再进行访问。在这个时候,被内存映射的文件实际上成了一个分页交换文件。
一句话概括:当前虚拟地址要找的数据不在物理内存中

页面置换算法

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

缺页次数

物理块+页面置换次数

题目如下:
在这里插入图片描述

一、先进先出(FIFO

把内存中驻留时间最久的页面置换算法予以淘汰

例子:

在分页中,采用FIFO页面置换算法,序列 1、3、2、1、2、1、5、1、2、3,当物理块为3时,计算缺页次数和缺页率?

算法执行如下操作步骤:

  1. 程序运行,将1、3、2三个页面装入内存
  2. 接着1、2、1已经有存在内存,不必产生缺页中断
  3. 访问页面5时,内存中不存在该页面,发生缺页中断,根据FIFO算法,先进先出,将1置换出去
  4. 访问页面1时,内存中不存在该页面,发生缺页中断,根据FIFO算法,先进先出,将页面3置换出去
  5. 访问页面3时,内存中不存在该页面,发生缺页中断,根据FIFO算法,先进先出,将2置换出去

在这里插入图片描述

总共进行了三次页面置换,所以缺页数=3+3=6,缺页率为6/10=0.6;

优点:先进先出算法实现简单,是最直观的一个算法
缺点:性能最差,可能出现Belady 异常:当所分配的物理块数增大而页故障数不减反增的异常现象

二.最近最久未使用(LRU)

选择最近且最久未被使用的页面进行淘汰

例子:

在分页中,采用LRU页面置换算法,序列 1、3、2、1、2、1、5、1、2、3,当物理块为3时,计算缺页次数和缺页率?

算法执行如下操作步骤:

  1. 程序运行,将1、3、2三个页面装入内存
  2. 接着1、2、1已经有存在内存,不必产生缺页中断
  3. 访问页面5时,内存中不存在该页面,发生缺页中断,根据LRU算法,页面1、3、2中3最近且最久未被使用,将3置换出去
  4. 访问页面3时,内存中不存在该页面,发生缺页中断,根据LRU算法,页面5、1、2中5最久未被使用,将页面5置换出去

在这里插入图片描述
总共进行了两次页面置换,所以缺页数=3+2=5,缺页率为5/10=0.5;

优点:LRU性能较好,但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明,堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现,不是堆栈类算法。

三、最佳置换算法(OPT)

当要调入一页而必须淘汰旧页时,应该淘汰以后不再访问的页,或距现在最长时间后要访问的页面,即被淘汰页面是以后永不使用或最长时间内不再访问的页面

例子:

在分页中,采用OPT页面置换算法,序列 1、3、2、1、2、1、5、1、2、3,当物理块为3时,计算缺页次数和缺页率?

算法执行如下操作步骤:

  1. 程序运行,将1、3、2三个页面装入内存
  2. 接着1、2、1已经有存在内存,不必产生缺页中断
  3. 访问页面5时,内存中不存在该页面,发生缺页中断,根据OPT算法,页面1、3、2中3最长时间内不被访问,将3置换出去
  4. 访问页面3时,内存中不存在该页面,发生缺页中断,根据OPT算法,将5置换出去

在这里插入图片描述
总共进行了两次页面置换,所以缺页数=3+2=5,缺页率为5/10=0.5;


如有错误,欢迎指正!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/687595
推荐阅读
相关标签
  

闽ICP备14008679号