OS@页面置换算法@抖动@工作集

文章目录

• ​​页面置换算法​​
• ​​页面算法评价​​
• ​​最佳置换算法OPT​​

• ​​例​​

• ​​先进先出算法FIFO​​
• ​​最近最久未使用算法LRU​​
• ​​时钟置换算法(CLOCK/NRU)​​

• ​​访问位的修改@页面的换出​​

• ​​首次扫描@修改​​
• ​​二次扫描​​
• ​​页架未满​​
• ​​页架已满​​

• ​​小结​​

• ​​改进型CLOCK算法 CLOCK^+ CLOCK+​​
• ​​抖动​​
• ​​工作集​​
• ​​MMF@内存映射文件​​
• ​​虚拟存储器性能影响因素​​

页面置换算法

• 此处主要讨论内存-辅存层次的页面置换算法,其是实现虚拟内存的关键之一
• 进程运行时,如果其访问的页面不在内存中,则需要将其从外存调入
• 如果调入之前,内存中已经没有空闲的时候,就需要从内存中调出一页程序或数据,送入磁盘的对换区
• 页面置换算法:选择调出页面的算法

页面算法评价

• 好的页面算法具有较低的页面更换评率

• 做页面调换的时候,算法应该将之后较长时间不会再次访问的页面调出
• 而不是(尽量不要)调出还会被频繁使用的那些页面,否则容易引起抖动

最佳置换算法OPT

• 最佳置换算法选择的被淘汰页面

• 在最长时间内不再被访问的页面(包括以后永不使用的页面)，以便保证获得最低的缺页率。

• 假设长度为n(访问次数)的有序(区分顺序的)访问序列为

• 即L的元素值i表示第i次访问操作,有顺序区别

• 假设第i次访存时发现

• 分配给进程p的s=3个页架中都有内容,且分别记为

• 
• 这时需要页面置换,采用OPT算法操作

• 设表示第i次想要访问的页面是v

• v不一定存在于进程的p的s个页架中,如果不存在,需要从辅存调入

• 子序列,相当于L的后缀(从第i个元素到最后一个元素)
• 序列,表示L(i)包含的各个访存操作要访问的页面号
• 记表示:进程p第i次要求访存,从要发生页面置换的时刻算起,下一次(最近)再访问到页面需要的等待时间(跳数,或间隔数)

• 在OPT算法中

• 
• 
• 的计算,

• 如果子序列包含的访存操作要访问的页面序列中不存在
• 那么,这表示进程p的第i次以及之后的访存都不再访问页面
• 这里就是用跳数来衡量’时间’的

• 在实际笔算的过程中,可通过列表(二维)来求解

• 在不至于引起混淆的情况下,可以省略掉第一个参数i

• 计算

• 具体步骤是,分别计算并统计,比较出最大的值,作为M
• 假设满足
• 被替换的页面就是

• 然而，由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，
• 因而该算法无法实现。
• 但可利用该算法去评价其他算法
• 该算法可以对某一个给定的页面访问序列做模拟替换操作(实际上访问序列是难以确定)

例

• 假定页面访问序列为

• 7,0,1,2,0,3,0,1,2
• Note:不同的序列(长短/结尾)的不同,都会导致求解过程的不同
  标签：抖动,访问,算法,内存,进程,缺页,OS,页面
  From： https://blog.51cto.com/u_15672212/5950771