3.2.3页面置换算法

进程运行时,若其访问的页面不在内存而徐将其调入,但内存已无空闲时间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区。 而选择调入页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者较长时间不会再访问的页面先调出。

1.最佳置换算法(OPT)

最佳(Optimal,OPT)置换算法所选择的被淘汰页面将是以后永不适用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但是由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间不再被访问的,因而该算法无法实现。 最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块,并考虑有以下页号引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 进程运行时,先将7,0,1三个页面依次装入内存。进程要访问页面2时,产生缺页中断,根据最佳置换算法,选择第18次访问才需调入的页面7予以淘汰。然后访问页面0时,因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依次类推。

访问页面

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

物理块1

7

7

7

2

2

2

2

2

7

物理块2

0

0

0

0

4

0

0

0

物理块3

1

1

3

3

3

1

1

缺页否

×

×

×

×

×

×

×

×

×

×

×

2.先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应, 因为在进程中,有的页面经常被访问(空间局部性)。

访问页面

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

物理块1

7

7

7

2

2

2

4

4

4

0

0

0

7

7

7

物理块2

0

0

0

3

3

3

2

2

2

1

1

1

0

0

物理块3

1

1

1

0

0

0

3

3

3

2

2

2

1

缺页否

×

×

×

×

×

FIFO算法比最佳置换算法正好多一倍。 FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象,这时由belady于1969年发现,故称为Belady异常。只有FIFO算法可能出现Belady异常,而LRU和OPT算法永远不会出现Belady异常。

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

选择最近最长时间未访问过的页面予以淘汰,它认为过去时间内一段时间内未访问过的页面,在最近的将来也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。 再对上面的实例采用LRU算法进行页面置换。

访问页面

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

物理块1

7

7

7

2

2

4

4

4

0

1

1

1

物理块2

0

0

0

0

0

0

3

3

3

0

0

物理块3

1

1

3

3

2

2

2

2

2

7

缺页否

×

×

×

×

×

×

×

×

LRU算法根据各页以前的情况是向前看的,而最佳置换算法则是根据各页以后的使用情况,是向后看的。 LRU性能较好,但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明,堆栈类的算法不可能出现belady异常。FIFO基于队列实现,不是堆栈类算法。

4.时钟(CLOCK)置换算法

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

改进型的CLOCK算法优于简单的CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在替换之前必须写回,因而这样会节省时间。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏拂晓风起

cocos2d-js 越来越慢的定时器schedule 制作不变慢的定时器

1204
来自专栏机器之心

业界 | 谷歌正式发布TensorFlow 1.5:终于支持CUDA 9和cuDNN 7

3386
来自专栏颇忒脱的技术博客

面向程序员的网络基本知识 - 子网分割

本系列文章旨在向程序员分享一些网络基本知识,让程序员具备基本的网络常识,以便与网络工程师沟通。本系列文章不会涉及如何组建网络、如何配置交换机/路由器等硬件相关的...

1103
来自专栏小樱的经验随笔

CTF---隐写术入门第三题 打不开的文件

打不开的文件分值:10 来源: 实验吧 难度:中 参与人数:2718人 Get Flag:1222人 答题人数:1276人 解题通过率:96% 咦!这个文件怎么...

51512
来自专栏linux驱动个人学习

vivi虚拟摄像头驱动程序

一、vivi虚拟摄像头驱动 基于V4L2(video for linux 2)摄像头驱动程序,我们减去不需要的ioctl_fops的函数,只增加ioctl函数增...

4414
来自专栏PHP在线

MongoDB数据结构设计中6条重要的经验法则

很多初学者认为在MongoDB中针对一对多建模唯一的方案就是在父文档中内嵌一个数组子文档,但是这是不准确的。因为你可以在MongoDB内嵌一个文档不代表你就必须...

3187
来自专栏互联网杂技

Angular2 脏检查过程

在本文中我将会深入讨论Angular 2 中的变更检测系统。 高层次概览 一个Angular 2 应用就是一颗组件树。 ? Angular 2 应用是一个反馈系...

4148
来自专栏吉浦迅科技

CUDA&OpenCL编程7个技巧及ArrayFire如何帮助您

· 向量化代码Vectorized Code: 加速器执行向量化代码性能会很好因为计算自然地映射到硬件的运算内核上。ArrayFire函数本质上是量化的,因此...

4166
来自专栏沈唁志

文本处理,第2部分:OH,倒排索引

这是我的文本处理系列的第二部分。在这篇博客中,我们将研究如何将文本文档存储在可以通过查询轻松检索的表单中。我将使用流行的开源Apache Lucene索引进行说...

1604
来自专栏Python中文社区

Python量子力学计算模拟以及数据可视化

專 欄 ❈Pytlab,Python 中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,...

7029

扫码关注云+社区