专栏首页Web前端开发页面置换算法详解

页面置换算法详解

一、什么是页面置换算法

进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区,其中选择调出页面的算法就称为页面置换算法

好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者以后较长时间内不会再访问的页面先调出

二、常见的页面置换算法

1、FIFO(先进先出算法)

(优先淘汰最早进入内存的页面)

FIFO 算法是最简单的页面置换算法。FIFO 页面置换算法为每个页面记录了调到内存的时间,当必须置换页面时会选择最旧的页面

“FIFO 算法当进程分配到的页面数增加时,缺页中断的次数可能增加也可能减少”

FIFO 算法基于队列实现,不是堆栈类算法

注意,并不需要记录调入页面的确切时间,可以创建一个 FIFO 队列,来管理所有的内存页面。置换的是队列的首个页面。当需要调入页面到内存时,就将它加到队列的尾部

FIFO 页面置换算法易于理解和编程。然而,它的性能并不总是十分理想:

  • 其一,所置换的页面可以是很久以前使用过但现已不再使用的初始化模块
  • 其二,所置换的页面可以包含一个被大量使用的变量,它早就初始化了,但仍在不断使用

2、OPT(最佳置换算法)

(淘汰以后不会使用的页面)

发现 Belady 异常的一个结果是寻找最优页面置换算法,这个算法具有所有算法的最低的缺页错误率,并且不会遭受 Belady 异常。这种算法确实存在,它被称为 OPT 或 MIN

这种页面置换算法确保对于给定数量的帧会产生最低的可能的缺页错误率

FIFO 和 OPT 算法的区别在于:除了在时间上向后或向前看之外,FIFO 算法使用的是页面调入内存的时间,OPT 算法使用的是页面将来使用的时间

3、LRU(最近最少使用算法)

(淘汰最近没有使用的页面)

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

OPT 和 LRU 算法的区别在于:LRU 算法根据各页以前的情况,是“向前看”的,而最佳置换算法则根据各页以后的使用情况,是“向后看”的 LRU 性能较好,但需要寄存器和栈的硬件支持

LRU 是堆栈类的算法,理论上可以证明,堆栈类算法不可能出现 Belady 异常

4、Clock(时钟置换算法)

简单的 CLOCK 算法是给每一帧关联一个附加位,称为使用位。

当某一页首次装入主存时,该帧的使用位设置为1;

当该页随后再被访问到时,它的使用位也被置为1。

对于页替换算法,用于替换的候选帧集合看做一个循环缓冲区,并且有一个指针与之相关联。

当某一页被替换时,该指针被设置成指向缓冲区中的下一帧。

当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0的一帧。

每当遇到一个使用位为1的帧时,操作系统就将该位重新置为0;

如果在这个过程开始时,缓冲区中所有帧的使用位均为0,则选择遇到的第一个帧替换;

如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0,并且停留在最初的位置上,替换该帧中的页。

由于该算法循环地检查各页面的情况,故称为 CLOCK 算法,又称为最近未用( Not Recently Used, NRU )算法。

5、LFU(最不常用算法)

最不经常使用(LFU)页面置换算法要求置换具有最小计数的页面。

这种选择的原因是,积极使用的页面应当具有大的引用计数。然而,当一个页面在进程的初始阶段大量使用但是随后不再使用时,会出现问题。由于被大量使用,它有一个大的计数,即使不再需要却仍保留在内存中。一种解决方案是,定期地将计数右移 1 位,以形成指数衰减的平均使用计数。

6、MFU(最常使用算法)

最经常使用(MFU)页面置换算法是基于如下论点:具有最小计数的页面可能刚刚被引入并且尚未使用。

MFU 和 LFU 置换都不常用。这些算法的实现是昂贵的,并且它们不能很好地近似 OPT 置换。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关于元素间的边距重叠问题与BFC

    BFC(Block Formatting Context),即块级格式化上下文,创建了 BFC 的元素是一个独立的容器,里面无论如何布局都不会影响到外面的元素

    Leophen
  • ES6 数值的扩展

    ES6 提供了二进制和八进制数值的新写法,分别用前缀 0b/0B 和 0o/0O表示。

    Leophen
  • Vue计算属性和侦听器

    模板内的表达式非常便利,但放入太多的逻辑会让模板过重且难以维护,所以,对于复杂的逻辑,可以使用计算属性 computed。

    Leophen
  • 快速学习-系统算法详解(基于人口统计学的推荐算法)

    cwl_java
  • 麦肯锡报告:到2030年机器人将取代8亿人的就业(上)

    麦肯锡全球研究院(McKinsey Global Institute)发布《失业与就业:自动化时代的劳动力转型》报告,称到2030年,全球将有多达8亿人的工作岗...

    人工智能快报
  • 秋招准备,这份GitHub万星的ML算法面试大全请收下

    项目地址:https://github.com/imhuay/Algorithm_Interview_Notes-Chinese

    Datawhale
  • Hanlp自然语言处理工具的使用演练

    Hanlp是由一系列模型与算法组成的工具包,目标是普及自然语言处理在生产环境中的应用。Hanlp具备功能完善、性能高效、架构清洗、语料时新、可自定义的特点;提供...

    IT小白龙
  • Chrome Devtools performance memory模式的理解 (JS Heap、Documents等)

    其中,比较难理解的是Documents。这个代表的是目前tab的内存有多少个Documents,包括当前页面、之前的页面、iframe和插件产生的页面。

    用户1258909
  • 分布式深度学习算法产品及在蚂蚁金服中的应用(附33页PDF下载)

    导读:8月3日-6日,世界公认的“必须参加”的数据盛典Strata + Hadoop World首次登陆中国。作为顶级的数据盛会,美国总统奥巴马曾亲自2015年...

    小莹莹
  • 分布式深度学习算法产品及在蚂蚁金服中的应用(附33页PDF下载)

    大数据文摘

扫码关注云+社区

领取腾讯云代金券