背景知识

时间局限性

如果程序中某条执行被执行，则不久后该指令还可能被在次执行。如果某条数据被访问过，则不久以后该数据还可能被继续访问。产生时间局限性经典原因是存在程序中存在大量的循环操作 空间局限性:一旦程序访问了程序访问了某个存储单元，在不久以后其附近的存储单元也将被访问，即程序在一段时间内访问的地址可能集中在一定的范围之内，其典型情况便是程序的顺序执行(虽然存在过程调用，使程序的执行轨迹由一部分区域转向另一部分区域，，但研究表明，过程调用的深度在大多数情况下不超过5)。

虚拟存储器基本工作情况

基于程序的局部性原理可知，应用程序在运行前没必要将作业全部装入内存，而仅将当前要运行的少数页面装入内存便可运行，其余部分暂留在盘上。程序运行时，若它所要访问的页已调入内存，便可继续执行下去，但若未调入内存(称为缺页或缺段)，便发出缺页/缺段请求，此时，os将利用请求调页/段功能将它们调入内存，以便进程能继续执行下去。如果此时内存已满，无法装入新的页/段，os还需利用页/段置换功能，将内存中暂时不用的页/段调至盘上，腾出足够的内存空间后，再将要访问的页/段调入内存，是程序继续执行下去。
虚拟存储器的定义:具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种储存器系统(基于程序的局部性原理)。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近内存，而每位成本却又接近于外存。

虚拟存储器的实现方法

分页请求系统:在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页面时虚拟存储系统。置换时以页为单位。请求分段系统:在分段系统的基础上，增加了请求调段及分段置换功能所形成的段式虚拟存储系统。置换时以段为单位。页面置换算法:

最佳置换算法

所选择的被淘汰页面是以后永不使用的，或是在最长时间内不再被访问的页面。但由于目前人们无法预知哪个页面时未来最长时间内不再被访问的，因此该算法是无法实现的。

先进先出(FIFO)页面置换算法

总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。实现方法为:把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针(称为替换指针)，始终指向最老的页面。但是该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如含有全局变量，常用函数，例程等的页面，FIFO算法不能保证这些页面不被淘汰。不需要特定的硬件支持，实现方式简单。

最近最久未使用(LRU)置换算法

选择最近最久未使用的页面予以淘汰，利用“最近的过去”，作为预测“最近的将来”的依据。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的淘汰。实现方法:可利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，再将它压入栈顶。因此栈顶始终是最新访问页面的编号，栈底永远是最近最久未被访问的页，若发生缺页中断，且内存已满的情况时，应选择栈底页面予以淘汰。需要特定的硬件支持，如寄存器和栈，实现方式较FIFO复杂。