操作系统（五）页面置换算法与分配策略_opt页面置换算法

操作系统（五）页面置换算法与分配策略

一、页面置换算法

1、最佳置换算法（OPT）

• 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率

实际上就是从当前内存块的页面中淘汰一个最后出现的页面。

• 最佳置换算法是缺页率最低的算法
• 由于进程运行中无法获取进程要访问的全部页面，因此最佳置换算法是无法实现的

2、先进先出置换算法（FIFO）

• 把调入内存的页面形成一个队列，每次发生置换时选择队头页面即可

• 实现简单
• 算法性能差
• 会产生Belady异常（当为进程分配的物理块增大时，缺页次数不减反增）

3、最近最久未使用算法（LRU）

• 每次淘汰最近最久没有使用的页面

• 性能好
• 实现困难，需要专门的硬件支持，开销大

4、时钟置换算法（CLOCK）

• 又称最久未用算法（NRU）

为每个页面设置一个访问位，首先在页面中选择访问位为0的页面，并将访问位为1的页面置为0

• 性能与开销比较均衡
• 未考虑页面是否被修改

5、改进型时钟置换算法

• 如果一个页面在访问过程中被修改了，那么它需要执行I/O操作写回外存，因此在其他条件相同时，应该优先淘汰未修改的页面

为每个页面增加一个修改位

1.寻找标志位为（0,0）即最近未访问未修改的页面

2.寻找标志位为（0,1）即最近未访问但修改过的页面，并将扫描过的页面的访问位设为0

3.寻找标志位为（0,0）即最近访问过但未修改过的页面

4.寻找标志位为（0,1）即最近访问过且修改过的页面

个人觉得这样设计的依据是根据局部性原理，最近访问过的页面接下来也可能被访问，所以会优先淘汰未访问的

6、小结

• OPT算法是无法实现的

• 只有FIFO算法会导致Belady异常

二、页面分配策略

1、驻留集

指请求分页存储管理中给进程分配的物理块的集合

• 驻留集太小，会导致缺页频繁，系统会花费大量的时间去处理缺页
• 驻留集太大，会导致多道程序并发度下降，资源利用率低

2、页面分配、置换策略

固定分配：操作系统给进程分配的物理块数目在进程运行期间固定不变，即驻留集大小不变

可变分配：驻留集大小可变

局部置换：发生缺页时只能选择进程自己的物理块进行替换

全局替换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

3、调入页面的时机

4、从何处调页

5、抖动（颠簸）现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面又要马上换出外存，这种频繁的页面调度行为称为抖动或颠簸

6、工作集

基于工作集的可变分配方式的最大窗口尺寸一般是窗口尺寸+1

工作集指在某段时间间隔里，进程实际访问页面的集合。

7、小结

• 系统为某进程分配了n个物理块等价于系统为该进程分配的驻留集大小为n
• 不存在固定分配全局置换，因为固定分配进程的驻留集大小是不会改变的，所以一定不会发生全局置换