虚拟存储器管理

内容纲要

虚拟存储技术

虚拟存储技术：**将外存作为内存的补充，从逻辑上扩充内存。虚拟存储器是指具有请求调入功能和置换功能，能够从逻辑上对内存空间进行扩展，允许用户的逻辑地址空间大于物理内存地址空间的存储器系统。

首先，物理的内存空间被划分为等长的物理块，并对块编号。同时，用户程序也进行分页，这些与页式存储管理相同。
在用户程序开始执行前，不将该程序的所有页都一次性装入内存，而是先放在外存。当程序被调度投入运行时，系统先将少数页装入内存，随着程序运行，如果所访问的页在内存中，则对其管理与分页存储管理情况相同。
若发现所要访问的数据或指令不在内存中，就会产生缺页中断，到外存寻找包含所需数据或指令的页，并将其装入到内存的空闲块中。
在装入一页的过程中，若发现内存无空闲块或分配给该进程的物理块已用完，则需要通过页面置换功能从已在内存的页中挑选一个将其淘汰，释放所占用的物理块后将新的页面装入该块，进程继续运行。
被淘汰的页面如果刚才被修改过，则还需要将其回写到外存，以保留其最新内容。

请求分页虚拟存储的硬件支持包括：

请求分页的页表机制：

页面分配策略：页面分配负责为多个进程分配相应的物理块，分配时需要综合考虑系统的并发性、吞吐量和缺页中断率等因素。

页面调入策略：

页面置换策略：

衡量页面置换算法的重要的指标是缺页率
一个进程或一个作业在运行中成功的页面访问次数为S，即所访问的页面在内存中；不成功的页面访问次数为F，即访问的页面不在内存，需要缺页中断并调入内存；需要访问的页面的总次数为A = S + F。则缺页率f为：f = F / A

影响缺页率的因素：

先进先出（FIFO）页面置换算法：总是选择最先进入内存的页面或驻留时间最长的页面先淘汰。该算法最早出现，易于实现。

Belady异常现象：当页数在一定范围内时，缺页率反而随分配给进程的物理块数的增加而增加。

最佳（OPT）页面置换算法：在选择页面置换时应该考虑该页面将来使用的情况，将来最长时间不用的页面被淘汰。在进程采用固定页面分配的情况下，最佳页面置换算法具有最低的缺页率。

最近不常用(LRU)页面置换算法：（与最佳页面置换相反）

时钟（clock）置换算法：

将内存中所有的页面组织成一个循环队列，形成一个类似于时钟表面的环形表，循环队列指针类似于钟的指针，用来指向可能被淘汰的页面，指针开始时指向最先进入内存的页面，如图5.34所示。
时钟置换算法需要在页表中为每一页增加一个访问位R。当页面首次装入内存时，R的初值设置为“0”。当某个页面被访问过后，R的值被设置为“1”。
选择淘汰页面的方法是从指针当前指向的页面位置开始扫描时钟环，如果某个页面页表中的R为“1”，表明该页被访问过，将R清“0”，并跳过该页；如果某个页面页表中的R为“0”，表明该页没有被访问过，该页被淘汰，指针推进一步；如果所有的页面都被访问过，指针绕环一圈，将所有页面的R清“0”，指针回到起始位置，选择该页淘汰，指针推进一步。

时钟置换改进：为了提高置换效率，在页面置换时，如果被淘汰的页面没有被修改过，则不需写回外存。这样，将页表中的引用位R和页表中的修改位M配合。

最近没有被引用（R = 0），没有被修改（M = 0）从指针当前位置开始，选择第一个R = 0，M = 0的页面淘汰。
最近没有被引用（R = 0），但是被修改（M = 1）如果没有R = 0，M = 0的页面，则从开始位置重新开始查找第一个R = 0，M = 1的页面并淘汰之。
最近被引用（R = 1），没有被修改（M = 0）如果没有R = 0，M = 1的页面，表示所有的页面R = 1。在再次回到开始位置时，所有页面的引用位R都被清“0”。从开始位置查找第一个M = 0的页面并淘汰之，此时不用将淘汰页面“写”回外存。
最近被引用（R = 1），被修改（M = 1）；当前面三种情况都不存在时才考虑R = 1，M = 1的情况。

影响请求页式存储管理性能的因素：