深入理解【缺页中断】及FIFO、LRU、OPT这三种置换算法

简介:   缺页中断(英语:Page fault,又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等)指的是当软件试图访问已映射在虚拟地址空间中,但是目前并未被加载在物理内存中的一个分页时,由中央处理器的内存管理单元所发出的中断。

 

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: 2 3 2 1 5 2 4 5 3 2 5 2
M=3 2 2 2 2 2 5 5 3 5 5 2 2
    3 3 3 5 3 3 5 4 2 5 5
        1 3 2 4 4 3 4 4 4
F=5 Y Y   Y Y   Y     Y    

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

2.2.1 基本思想

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

2.2.2 算例

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

P: 2 3 2 1 5 2 4 5 3 2 5 2
M=3 2 3 3 1 5 2 4 4 3 3 5 2
    2 2 3 1 5 2 2 4 4 3 5
        2 3 1 5 5 2 2 4 3
F=9 Y Y   Y Y Y Y   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: 0 2 1 3 0 2 4 0 2 1 3 4
M=3 0 2 1 3 0 2 4 4 4 1 3 3
    0 2 1 3 0 2 2 2 4 1 1
      0 2 1 3 0 0 0 2 4 4
F=9 Y Y Y Y Y Y Y     Y Y  

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

P: 0 2 1 3 0 2 4 0 2 1 3 4
M=4 0 2 1 3 3 3 4 0 2 1 3 4
    0 2 1 1 1 3 4 0 2 1 3
      0 2 2 2 1 3 4 0 2 1
        0 0 0 2 1 3 4 0 2
F=10 Y Y Y Y     Y Y Y Y Y Y

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

2.3.1 基本思想

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

2.3.2 算例

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

P: 2 3 2 1 5 2 4 5 3 2 5 2
M=3 2 3 2 1 5 2 4 5 3 2 5 2
    2 3 2 1 5 2 4 5 3 2 5
        3 2 1 5 2 4 5 3 3
F=7 Y Y   Y Y   Y   Y Y    

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

参考

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

目录

 

 

 
谋胆并重
目录
相关文章
|
1天前
|
算法
页面置换算法
页面置换算法
8 1
|
2天前
|
缓存 监控 算法
如何调整InnoDB的LRU算法以提高效率?
【5月更文挑战第14天】如何调整InnoDB的LRU算法以提高效率?
9 2
|
2天前
|
缓存 算法
LRU(Least Recently Used)算法是一种常用的计算机缓存替换算法
【5月更文挑战第4天】LRU算法是基于页面使用频率的缓存策略,优先淘汰最近最久未使用的页面。实现可采用双向链表或数组,前者灵活,后者时间复杂度低。优点是利用时间局部性提高命中率,简单易实现;缺点是占用空间,对循环访问和随机访问场景适应性不佳。
30 0
|
2天前
|
存储 缓存 算法
面试遇到算法题:实现LRU缓存
V哥的这个实现的关键在于维护一个双向链表,它可以帮助我们快速地访问、更新和删除最近最少使用的节点,同时使用哈希表来提供快速的查找能力。这样,我们就可以在 O(1) 的时间复杂度内完成所有的缓存操作。哈哈干净利索,回答完毕。
|
2天前
|
缓存 算法 Java
如何实现缓存与LRU算法以及惰性过期
如何实现缓存与LRU算法以及惰性过期
32 1
|
2天前
|
存储 缓存 算法
从0开始回顾数据结构---LRU,LFU算法
题意解释 请为LFU缓存设计一个数据结构。支持两种操作:get和set。 ● get(key) : 如果key在缓存中,则返回key对应的值;否则返回-1; ● put(key, value): 如果key在缓存中,则更新key对应的值;否则插入(key, value),如果缓存已满,则先删除使用频率最小的key,如果有多个key具有相同的使用频率,则应该删除最久未使用的key。 C++代码 class LFUCache { public: struct Node { Node *left, *right; int key, val;
|
2天前
|
缓存 算法 NoSQL
Redis 为何使用近似 LRU 算法淘汰数据,而不是真实 LRU?
Redis 为何使用近似 LRU 算法淘汰数据,而不是真实 LRU?
33 0
|
2天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
2天前
|
算法 计算机视觉
基于高斯混合模型的视频背景提取和人员跟踪算法matlab仿真
该内容是关于使用MATLAB2013B实现基于高斯混合模型(GMM)的视频背景提取和人员跟踪算法。算法通过GMM建立背景模型,新帧与模型比较,提取前景并进行人员跟踪。文章附有程序代码示例,展示从读取视频到结果显示的流程。最后,结果保存在Result.mat文件中。
|
2天前
|
资源调度 算法 块存储
m基于遗传优化的LDPC码OMS译码算法最优偏移参数计算和误码率matlab仿真
MATLAB2022a仿真实现了遗传优化的LDPC码OSD译码算法,通过自动搜索最佳偏移参数ΔΔ以提升纠错性能。该算法结合了低密度奇偶校验码和有序统计译码理论,利用遗传算法进行全局优化,避免手动调整,提高译码效率。核心程序包括编码、调制、AWGN信道模拟及软输入软输出译码等步骤,通过仿真曲线展示了不同SNR下的误码率性能。
9 1