缺页中断

Miracle
1034
文章
50
评论
2017年9月14日19:23:19 评论 2024字阅读6分44秒

转自网页

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

继续阅读
  • 版权声明: 发表于 2017年9月14日19:23:19
  • 转载注明:https://x1995.cn/1379.html
欧盟隐私法即将生效,谷歌努力缓解担忧 IT相关

欧盟隐私法即将生效,谷歌努力缓解担忧

谷歌周四举行会议,希望缓解在线内容发布商对即将生效的欧洲数据隐私新规的担忧。 本周五生效的欧盟《通用数据保护条例》(GDPR)是欧洲20多年来对数据隐私法规最大的一次调整。根据这项新规,相关组织必须对...
科学家暗示外星生命隐藏在平行宇宙中 IT相关

科学家暗示外星生命隐藏在平行宇宙中

据国外媒体报道,假如在我们所处的宇宙中找不到外星生命,不妨将目光投向其它宇宙。由英国皇家天文学会开展的新研究指出,平行宇宙中很可能存在拥有外星生命的星球,尽管暗能量足以使这些宇宙分崩离析。 平行宇宙理...
关于微信与抖音摩擦的一点看法 IT相关

关于微信与抖音摩擦的一点看法

头条的崛起也是一路薅着微博、朋友圈的羊毛,当它们发现并想封杀时,轻舟己过万重山。抖音的极速爆发微信起着至关重要传播裂变的作用,现在想封杀已经来不及了,抖音的装弱碰瓷更像是一场挑衅,有人依稀记得3Q大战...
Google-ch:一场谷歌搜索“重返中国”的乌龙 IT相关

Google-ch:一场谷歌搜索“重返中国”的乌龙

一个名为Google-CH的网站在微博上引起了关注。这个域名为www.google-ch.com的网站不仅可以很方便的打开,而且搜索结果也与Google搜索一致。一时间,甚至有人认为这是Google在...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: