【清华大学】操作系统 陈渝——Part6 全局页面置换算法_全局分配時进程如何知道自己的页被換出-程序员宅基地

技术标签: SSD闪存存储系统  【清华大学】操作系统课堂笔记  操作系统  内存管理  

6.8 局部页面替换算法的问题,工作集模型

局部页面替换算法的问题

OPT,FIFIO,LRU,Clock,LFU 算法都是针对一个程序进程而言的,但操作系统支持多个程序同时运行,如果每个程序采取固定的局部页面置换算法,会带来一些问题。

如下:
采取FIFO算法时,分配3个物理页帧会产生 9 此缺页中断,分配4个物理页帧,会产生 1 次中断,可以看出,物理页帧的大小会对页面置换算法效果产生很大的影响。
如果对一个程序分配一个固定大小的物理页帧制定一个算法,限制了程序产生缺页的特点。
因为程序是动态运行的,它对物理页帧的需求是动态变化的。OPT,FIFIO,LRU,Clock,LFU 算法的研究都有一个假定,即分配给程序的物理空间是固定的,如果内存中只跑了一个程序,那么可以将所有物理内存空间分配给它。
因此,根据程序运行的不同阶段,动态分配物理页帧,调整物理页帧大小,这是全局页面算法考虑的问题。

在这里插入图片描述

工作集模型

OPT,FIFIO,LRU,Clock,LFU 算法都是基于一个前提:即程序的局部性原理。但此原理是否成立?

  • 如果局部性原理不成立,那么各项页面置换算法就没有什么区别,也没有什么意义。例如:假设进程对逻辑页面的访问顺序是1,2,3,4,5,6,7,8,9…即单调递增,那么在物理页面有限的前提下,不愿采用何种置换算法,每次的页面访问都必然导致缺页中断。

  • 如果局部性原理是成立的,那么如何证明它的存在,如何来对它进行定量地分析?这就是工作集模型。

  • 工作集:一个进程当前正在使用的逻辑页面集合,可以用一个二元函数 W(t, Δ \Delta Δ)来表示:
    t :当前执行时刻;
    Δ \Delta Δ:工作集窗口(working-set window),即一个定长页面访问的时间窗口,t + Δ \Delta Δ 形成一个时间段;
    W(t, Δ \Delta Δ):在当前时刻 t 之前的 △ \bigtriangleup 时间窗口当中的所有逻辑页面所组成的集合(随着 t 的变化,该集合也在不断地变化);
    | W(t, Δ \Delta Δ) |::工作集的大小,即页面数目。
    实例:
    在这里插入图片描述
    时刻t1 和 时刻t2 访问特点不一样,表现出了程序在运行的不同阶段对内存访问的特点。t2 的工作集对内存的访问具有很好的局部性,重复的对页面3和页面4访问,t1 的工作集对内存的访问重复性没有那么强烈,但是在某个短暂的时间内,重复的访问了4次页面7,因此具有一定的局部性,整体的局部性不如t2 的工作集效果好。

  • 工作集大小的变化:进程开始执行后,在最初的时间段内,有可能访问的新的页不具有一定的局部性,但随着访问新页面,逐步建立比较稳定的工作集。当访问到局部性比较好的区域,即内存访问的局部性区域的位置大致稳定时,工作集大小也大致稳定;但由于程序本身的特点,局部性区域的位置改变时,工作集快速扩张和收缩过度到下一个稳定值。

    随着程序的执行过程,工作集大小的变化会出现一定的特征,有波峰,有波谷,有平稳的情况,根据这样的特征,来建立基于全局的多个程序的有效页面置换算法。
    在这里插入图片描述

常驻集:是指在当前时刻,进程实际驻留在内存当中的页面集合。

  • 工作集是进程在运行中对页面访问的固有的性质,而常驻集取决于操作系统分配给进程的物理页面数目,以及所采用的页面置换算法,到底要把那些页放到内存中;
  • 如果一个进程的整个工作集都在内存当中,即常驻集 ⊇ \supseteq ( ) 工作集,那么进程将很顺利地运行,而不会造成太多地缺页中断(直到工作集发生剧烈变动,从而过渡到另一个状态);
  • 当进程常驻集的大小达到某个数目之后,再给它分配更多的物理页面,缺页率也不会明显下降,这时候需要一种动态调整,把多余的物理页给其他运行的程序。这样使得整体上,不同的程序总体缺页次数比较少。如果说根据程序的运行特定,给不同的应用程序不同的常驻集,使得整体的缺页中断次数减少,那么整体的性能就将得到提高。采取局部页面算法,不能整体的解决问题,为此需要考虑全局页面算法来解决这个问题。

6.9 全局页面置换算法

1. 工作集页置换算法

工作集窗口记录了当前时间在过去的时间段内工作集的大小,在窗口中表示的是当前时间在过去的时间段内所访问过的逻辑页。

基本思路
如果要替换某个页,要替换不在工作集的中的页,随着程序的运行,工作窗口随着时间的改变在平移,平移的过程中,如果哪个页不在窗口内,这个页也会被丢掉,不是等到缺页才开始丢页,只要随着程序的运行,有哪一页不属于这个窗口中,就把该页丢掉。

实例
在这里插入图片描述
在这里插入图片描述
结论:一共产生5次中断。和局部页面替换算法的区别是,全局页面替换算法当前在物理内存中存放哪些页,取决于是否在工作集窗口之内。如果窗口设置为4,所有老的那些页面(当前时刻-上次访问时刻差值,结果超出4的)都会被换出去,而不是当缺页时才执行换出,这样可以保证物理内存中时刻有足够多的页面供给其他程序使用,从而在系统层面确保缺页层数降低。

2. 可变分配策略

常驻集大小可变。例如:每个进程在刚开始运行的时候,先根据程序大小给它分配一定数目的物理页面,然后在进程运行过程中,再动态地调整常驻集地大小。

  • 可采用全局页面置换的方式,当发生一个缺页中断时,被置换的页面可以是在其它进程当中,各个并发进程竞争地使用物理页面。
  • 优缺点:性能较好,但增加了系统开销。
  • 具体实现:可以使用缺页率算法(PFF ,page fault frequence) 来动态调整常驻集地大小。

缺页率

缺页率表示 “缺页次数 / 内存访问次数” (比率)或 “缺页的平均时间间隔的倒数”。影响缺页率的因素:

  • 页面置换算法
  • 分配给进程的物理页面数目
  • 页面本身的大小
  • 程序的编写方法

和全局页面置换算法的 Δ \Delta Δ 是一个固定值相比,可变分配策略算法需要调整 Δ \Delta Δ ,一个交替的工作集计算明确的试图最小化页缺失

  • 当缺页率过高的时候-增加工作集
  • 当缺页率过低的时候-减少工作集

实例:

在这里插入图片描述

在这里插入图片描述
全局页面置换 和 可变分配策略算法 比较:
对页面调整的时机不一样:全局页面置换算法是在每一次访问时判断需要把页换入换出,而可变分配策略只是在产生缺页中断的时候才会决定把哪些页换入换出。

这两种算法和之前的局部页面置换算法都不一样,是根据工作集和缺页率的大小动态调整整个内存中需要换入换出的页面,这使得经常访问的页可以驻留在内存中,对操作系统来说,当有多个程序运行,全局页面置换算法它的效果好于局部页面置换算法。

6.10 抖动问题(thrashing)

  • 抖动:如果分配给一个进程的物理页面太少,不能包含整个的工作集,即常驻集 ⊂ \subset 工作集,那么进程将会造成很多的缺页中断,需要频繁地在内存与外存之间替换页面,从而使进程地运行速度变得很慢,这种状态称之为"抖动"。
  • 产生抖动的原因随着驻留内存的进程数目增加,分配给每个进程的物理页面不断减小,缺页率不断上升。所以操作系统要选择一个适当的进程数目和进程需要的帧数,以便在并发水平和缺页率之间达到一个平衡
  • 抖动问题可能会被本地的页面置换改善
    更好的规则为加载控制:调整MPL 所以:Better criteria for load control:Adjust MPL so thath:
    • 平均缺失时间 mean time between page faults (MTBF) = 页缺失服务时间 page fault service (PFST)
    • Σ W S i = 内 存 的 大 小 \Sigma WSi = 内存的大小 ΣWSi=

通常,随着程序的增多,程序运行速度变慢,因为缺页中断发生了,大量的换入换出操作使得CPU利用率减小。
在这里插入图片描述
我们想要让取消维持在最高峰,使得运行的程序数量可以多,系统利用率也高。因此想要找到一个平衡点,两个缺页产生的平均时间和完成一次中断服务的时间尽量相等。MTBF 和 PFST比值降低。
在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/keke_Memory/article/details/105305098

智能推荐

关于sql server 2019的 卸载_用于sql server 2019的浏览器可以卸载吗-程序员宅基地

文章浏览阅读1w次,点赞9次,收藏15次。这个是需要你下载的卸载sql server 2019的软件由于数据库这门课的需要,我不得不下载一个我非常不愿意下载的软件——sql server 2019(因为我大一被另一个微软软件multisim折磨的头皮发麻)。由于之前被multisim折磨过(之前由于自己蠢,卸载multisim时没有卸载干净,然后又自作聪明的去删注册表导致我的window无法使用,最后那几天的课都是用的untubun,非常的痛苦)我这次下载微软的软件非常小心,但是由于我电脑上的那个b火绒太强了直接禁止了sql server 201_用于sql server 2019的浏览器可以卸载吗

[人工智能教程] 人工智能暑期课实践项目建议_人工智能专业的暑期实践作业-程序员宅基地

文章浏览阅读3k次。哈工大人工智能暑期课实训项目建议这个博客介绍了暑期课实践作业的建议。 时间:7/10 - 7/22. 一周上课, 一周项目实践。 要求:项目实践的过程请用公开的博客记录。 项目的源代码请放到 github 中。 每4 ~ 5 人一个小组,从下面的候选中选择题目:1)手写数字识别增强版。 在MNist 的基础上进一步扩展, 阶段要求: 能实现多个数字的手写体识别 能实现加..._人工智能专业的暑期实践作业

Linux 安装字体库-宋体_linux字体库-程序员宅基地

文章浏览阅读2.9w次,点赞5次,收藏24次。由于需要宋体,所以需要执行命令发现输入命令查看字体列表是提示命令无效:如上图可以看出,不仅没有中文字体,连字体库都没有,那么接下来就记录一下在Linux CentOS 7中如何安装字体库以及中文字体。安装字体库在CentOS 4.x开始用fontconfig来安装字体库,所以输入以下命令即可:yum -y install fontconfig当看_linux字体库

dependencies 和 devDependencies 区别_dependencies devdependencies-程序员宅基地

文章浏览阅读642次。问:dependencies 和 devDependencies 区别依赖就是一定会用到的东西,开发依赖就是在开发中用到的,发布到线上不一定会用到的问:会有这种场景吗?能举个例子吗比如用我用一个gulp打包一个项目,开发的时候我就需要本地起一个服务来便于开发,就会需要一个gulp-connect的包,但是我线上打包的时候是不需要启动服务的,只需要压缩(gulp-uglify)、转换(gulp-babel)就行了。此时就可以把,gulp-connect放入开发依赖中,把gulp-uglif_dependencies devdependencies

JSON格式转换为Java对象_将json数据转换成java对象-程序员宅基地

文章浏览阅读1.6k次,点赞4次,收藏3次。(一)转换为Java对象代码@Test public void test04() throws IOException { String json ="{\"gender\":\"男\",\"age\":23,\"username\":\"ALworm\"}"; ObjectMapper mapper = new ObjectMapper(); ..._将json数据转换成java对象

c深入剖析跨函数调用指针(多级指针)问题-程序员宅基地

文章浏览阅读2.7k次,点赞2次,收藏5次。在c语言中,如果想要通过函数调用来改变值,有两种方式,第一种是通过指针的传递来改变值(这种可以一次改变多个变量的值),第二种是通过函数的返回值来传递值。第一种,中传递的时候其实只是地址的传递,相对第二种的值传递来说,第一种的效率要高不少,因为第一种传递的是地址,四个字节(部分计算机)大小的地址。特别,是在c中做字符串的处理时,这种第一种情况用的非常的多,我当时也是在做字符串处理的时候遇到这些问题,_跨函数调用

随便推点

参考三相异步电动机按速度原则实现的单向反接制动控制电路,设计按速度原则双向反接制动控制电路_按速度原则控制,电路应如何设计?-程序员宅基地

文章浏览阅读4.9k次,点赞5次,收藏3次。参考三相异步电动机按速度原则实现的单向反接制动控制电路,设计按速度原则双向反接制动控制电路功能双向电动双向制动自动识别制动方式设计电路图如下:江苏科技大学_172219602130QQ:728272412版权所有,引用请标明:@七月雨..._按速度原则控制,电路应如何设计?

php工程师有证吗,php工程师证有用吗-程序员宅基地

文章浏览阅读584次。php工程师证有用吗php工程师证有用吗?所有的证书都是有一定的含金量,而且所有的证书都能够证明你曾经的努力,这是对未来将面试你的面试官最好的简历,其次也是随你自己学习的一个回报和欣慰。php工程师证有用吗?很长一段时间内php语言没有获得相应的地位,知道随着今年的流行php才获得了广大开发人员的承认,下面北京达内php培训专家就给大家简单介绍下php:在多数WEB开发者眼中,asp和jsp都被认..._php工程师证书

sparksql-1.sparksql的schema和udf_spark 获得schem-程序员宅基地

文章浏览阅读809次。1.spark根据schema读取json数据进行sparksql操作注意:读取json数据,特别是数据量比较大的json数据,需要定义schema,减少读取的数据量,不然加载太多数据浪费集群资源,而且太浪费时间,吃力不讨好。1)定义schemaimportorg.apache.spark.sql.types.{StructField, _}vallogSche_spark 获得schem

myeclipse注释行模板的安装步骤-程序员宅基地

文章浏览阅读54次。注释比代码还重要??当然!在一个项目的完整的生命周期中,其维护费用,往往是其开发费用的数倍。因此项目的可维护性、可复用性是衡量一个项目好坏的关键。而注释行则是可维护性中必不可少的一环。安装方法:打开eclipse/myeclipse选择 window-->Preferences-->JAVA-->Code-->Code Templates 右边点Import 选择你写好的模...

注册控件时,弹出 [ 模块"C:\Program"加载失败 ]_模块“c:\program”加载失败-程序员宅基地

文章浏览阅读3.8k次。注册控件时,弹出 [ 模块"C:\Program"加载失败 ]只需加上双引号“”即可!!regsvr32 c:\program files\common files\system\ole db\msdasql.dll || \/r..._模块“c:\program”加载失败

如何选择laravel的身份认证系统_laravel spa 和 auth 区别-程序员宅基地

文章浏览阅读753次。laravel认证生态系统概述Laravel提供了一些与身份验证相关的软件包。在继续之前,我们将回顾Laravel中的常规身份验证生态系统,并讨论每个软件包的预期目的。首先,请考虑身份验证的工作原理。使用网络浏览器时,用户将通过登录表单提供其用户名和密码。如果这些凭据正确,则应用程序将在用户的会话中存储有关经过身份验证的用户的信息。发布给浏览器的cookie包含会话ID,以便对应用程序的后续请求可以将用户与正确的会话相关联。接收到会话cookie后,应用程序将基于会话ID检索会话数据,注意身份验证信_laravel spa 和 auth 区别

推荐文章

热门文章

相关标签