虚拟存储器:页面置换算法
一. 请求分页存储管理方式
- 请求分页:建立在基本分页基础上,增加了请求调页功能和页面置换功能,以支持虚拟存储器功能。
- 请求页表机制:将用户地址空间中的逻辑地址映射为内存空间中的物理地址。
- 每个页表包含项:页号、物理块号、状态位P、访问字段A、修改位M、外存地址。
- 请求分页中的地址变换过程:
二. 页面置换算法
- 应该将哪个页面调出,需要根据一定的算法来确定。
- 不适当的算法,可能会造成“抖动”(即刚被换出的页面很快又要被访问,又要调入,如此频繁地更换页面)。
- 常见的页面置换算法:最佳置换算法(optimal)、先进先出算法(FIFO)、第二次机会算法(SCR)、最近最久未使用算法(LRU)、最少使用置换算法(LFU)。
1. 最佳置换算法(Optimal)
- 该算法所选择调出的页面:①可能是以后永不使用的 ②可能是在未来最长时间内不会再被访问的。
- 该算法可以保证最低的缺页率,但人们很难做到上述的预知,因此该算法可以说是无法实现的。
2. 先进先出算法(FIFO)
- 该算法总是调出最先进入内存的页面,实现非常简单。
- 实现过程:把一个进程已调入内存的页面按照先后次序链接为一个队列,设置一个叫替换指针的,总是指向最老的页面。
3. 第二次机会算法(SCR)
- 第二次机会算法的基本思想是与FIFO相同的,但是有所改进,避免把经常使用的页面置换出去。
- 当选择置换页面时,检查它的访问位。如果是0,就淘汰这页;如果访问位是1,就给它第二次机会,并选择下一个FIFO页面。
- 当一个页面得到第二次机会时,它的访问位就清为0,它的到达时间就置为当前时间。如果该页在此期间被访问过,则访问位置1。
4. 最近最久未使用算法(LRU)
- LRU(Least Recently Used):因为无法预测未来,所以利用“最近的过去”来预测“最近的未来”。
- LRU算法是选择最近最久未使用的页面淘汰。
- 算法赋予每个页面一个访问字段,用于记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时,选择现有页面中t最大的淘汰。
-
所需硬件支持(两种实现方式):
①寄存器:记录某进程在内存中各页的使用情况。
内存的每一个页面都配置一个寄存器,例如:R=Rn-1 Rn-2 Rn-3 …… R2 R1 R0。开始时Rn-1为1,然后每隔一定时间寄存器右移一位。如果把寄存器当做一个整数,最小的那个,就是最近最久未使用页面。
②栈:用一个特殊的栈保存当前各个页面号,每当进程访问一个页面时,便将其从栈的下面移出,将它压入栈顶。这栈顶始终是最新被访问的页面,而栈底则是最近最久未使用页面的页面号。
5. 最少使用置换算法(LFU)
- LFU(Least Frequently Used):内存中的每个页都会有一个寄存器,用于记录该页面被访问的频率。
- 算法会选择最近时间内,用得最少次的页面淘汰。