本文主要是介绍操作系统学习笔记 页面置换算法(一),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
置换算法的功能和目标
-
功能
- 当出现缺页异常,需调入新页面而内存已满时,置换算法选择被置换的物理页面
-
设计目标
- 尽可能减少页面的调入调出次数
- 把未来不再访问或者短期内不访问的页面调出
-
页面锁定(frame locking)
- 描述必须常驻内存的逻辑页面
- 操作系统的关键部分
- 要求响应速度的代码和数据
- 页表中的锁定标志位(lock bit)
页面置换算法分类
-
局部页面置换算法
页面总数是不会变化的
- 置换页面的选择范围仅限于当前进程占用的物理页面内
- 最优算法、先进先出算法、最近最久未使用算法
- 时钟算法、最不常用算法(这两个是LRU的近似)
-
全局页面置换算法
- 置换页面的选择范围是所有可换出的物理页面
- 工作集算法、缺页率算法
最优、先进先出、最近最久未使用算法
最优页面置换算法(OPT,optimal)
先进先出算法(First-In First-out,FIFO)
- 思路
- 实现
- 维护一个记录所有位于内存中的逻辑页面链表
- 链表元素按驻留内存的时间排序,链首最长,链尾最短
- 出现缺页时,选择链首页面进行置换,新页面加到链尾
- 特征
- 实现简单
- 性能较差,调出的页面可能是经常访问的
- 进程分配物理页面数增加时,缺页并不一定减少(Belady现象)
- 很少单独使用
最近最久未使用(Least Recently Used,LRU)
-
思路
- 选择最长时间没有被引用的页面进行置换
- 如某些页面长时间未被访问,则它们在将来还可能会长时间不会访问
-
实现
- 缺页时,计算内存中每个逻辑页面的上一次访问时间
- 选择上一次使用到当前时间最长的页面
-
特征
LRU算法的可能实现办法
-
页面链表
- 系统维护一个按最近一次访问时间排序的页面链表
- 链表首节点是最近刚刚使用过的页面
- 链表尾节点是最久未使用的页面
- 访问内存时,找到相应页面,并把它移到链表之首
- 缺页时,置换链表尾节点的页面
-
活动页面栈
- 访问页面时,将此页号压入栈顶
- 如果是栈内相同的页号抽出放到栈顶
- 缺页时,置换栈底的页面
-
特征
时钟置换算法和最不常用算法
时钟置换算法(Clock)
-
思路
-
数据结构
- 在页表项中增加访问位,描述页面在过去一段时间的内访问情况
- 各页面组织成环形链表
- 指针指向最先调入的页面
-
算法
- 访问页面时,在页表项记录页面访问的情况
- 缺页时,从指针处开始顺序查找未被访问的页面进行量
-
特征
改进的clock算法
- 思路
- 算法
- 在页面中增加修改位,并在访问时进行修改
- 缺页时,修改页面标志位,以跳过有修改的页面
最不常用算法(Least Frequently Used LFU)
- 思路
- 实现
- 每个页面设置一个访问计数
- 访问页面时,访问计数加1
- 缺页时,置换计数最小的页面
- 实现
- 算法开销大
- 开始时频繁使用,但以后不使用的页面很难置换
- LRU和LFU的区别
- LRU关注多久未访问,时间越短越好
- LFU关注访问次数,次数越多越好
Belady现象和局部置换算法比较
Belady现象
- 现象
- 采用FIFO等算法时,可能出现分配的物理页面数增加,缺页次数反而升高的异常现象
- 原因
- FIFO算法的置换特征与进程访问内存的动态特征矛盾
- 被它置换出去的页面并不一定是进程近期不会访问的
LRU、FIFO和Clock的比较
这篇关于操作系统学习笔记 页面置换算法(一)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!