从上一节 存储器管理 章节中我们介绍的便是常规的存储管理方式，一次性将程序代码全部加载进内存中，只不过由发展过程，从连续的分配方式，转换到离散的分配方式，只是解决了内存空间利用率的问题，并未解决程序运行内存需求的问题。

什么是内存需求问题呢？ 如果每次运行都需要将一个程序所有的数据代码加载到内存，那么同一个程序，可能就会因为内存的不同，在不同机器上的可运行状态是不同的（一个程序太大，不能一次放入内存，导致无法运行）。再比如，有多个程序需要运行，但是受限于物理内存，就会导致部分程序无法运行。 一个显而易见的解决方法：扩充物理内存，但是这往往会收到机器自身的限制，成本比较高。 如果从物理上我们无法实现，那么我们可以采用逻辑上的扩充内存，这就是 ——— 虚拟存储器

引入

常规存储管理方式的特征

从前面的叙述中，我们知道，在常规的存储管理方式中，每次执行一个作业时，都一次性将相关数据or信息加载到内存，不论是否执行到，并且那些不会执行到的代码也会在作业执行完毕卸载之前留在内存之中。可以概括为：

1. 一次性
2. 驻留性

降低了系统的多道程序度，以及系统的吞吐量和资源利用率

局部性原理

程序运行时呈现出局部性规律：

P.Denning 指出：在程序执行过程中，较短的一段时间内，程序的执行只会局限在某个部分，相应的其访问的存储空间也是局限在某一个区域。 并且他还指出：

1. 程序在执行过程中，除了少部分跳转语句 和 过程调用 指令外，在大多数情况下都是顺序执行的
2. 过程调用将会使程序的执行轨迹由一部分区域跳转至另一部分区域，跳转的深度大多数情况下都不超过 5，即程序在一段时间内，都局限在这些过程的范围内运行
3. 程序存在很多循环结构，这些结构由少数指令构成，但是将会被多次执行
4. 程序中还包括许多对数据结构的处理，这些处理往往局限在很小的范围

局部性又表现在两个方面：

1. 时间局部性：如果某条指令被执行，则在不久以后该指令很有可能再次被执行，如果某条数据被访问过，不久之后很可能再次访问。产生时间局部性的典型原因是 循环操作
2. 空间局部性：一旦程序访问某个存储单元，则不久之后，其附近的存储单元也将会被访问，即程序在一段时间内访问的地址可能集中在一定范围之内。典型情况 —— 程序的顺序执行

通过局部性原理，我们可以知道，应用程序在运行之前，没必要将其全部装入内存，仅需将那些当前运行需要的少许页面或段线装入内存即可，其余部分暂留在磁盘上。当需要的部分不在内存中，则从磁盘上调用需要的部分进入内存，如果内存空间不足，则将一些可能不会使用的页调出，以此腾出足够的空间，来容纳需要的数据、信息 —— 也可以称之为 置换 。

虚拟存储器

定义

通过上述加粗文字，其实虚拟存储器就是实现了这么一个过程的存储器，什么功能呢？请求调入 和 置换功能。通过这两个功能，可以实现逻辑上的对容量进行扩充。让用户程序在执行时，认为实际内存一定比自己需求的大，或者说，用户感觉到的内存容量比实际的内存容量大很多，但这只是一种错觉，是虚的。所以人们称之为 —— 虚拟存储器

特征

1. 多次性：不需要一次性将程序全部加载到内存中，而是可以分为多次调入内存运行
2. 对换性：相对于传统存储管理方式的驻留性而言，一个作业的程序和数据无需一直驻留在内存，允许在运行过程中进行换入换出的 （换到 swap 区），即允许将暂时不使用的代码和数据从内存调出到外存的对换区，待需要时，再次调入到内存中即可
3. 虚拟性：就是指逻辑上扩充内存容量，使用户看到的内容容量远大于实际内存容量

虚拟性是建立在 多次性 和 对唤性 的基础上的，而多次性和对换性又是建立在离散分配的基础上的

实现

由于允许将存储分多次调入和调出内存，如果使用连续分配方式，就需要提前为程序开辟足够的空间，这就会导致空间浪费等一系列问题，那调入和调出操作就是无意义的。所以我们得采用离散分配的方法 —— 分页、分段

请求分页存储管理方式

请求分页建立在基本的分页基础上， 为了能支持虚拟的存储器功能，增加了 请求调页功能 和 页面置换功能。每次调入和换出的基本单位都是长度固定的页面，这使得请求分页系统的实现要比请求分段系统简单（后者在换进和换出上都是可变长的段）

在基础的分页基础上怎么才能实现一个虚拟存储管理方式呢？

1. 首先，我们不在是将所有的程序和数据一次性加入到内存中，而是分次加入。那么就需要 一个策略来实现 内存分配问题，比如一个进程分配几页 几块？ —— 内存分配策略
2. 其次，当执行到一定位置，发现数据or代码不在内存，则需要请求调入缺失的内存页，所以 需要一个机构来响应并处理调页的功能，并且还需要知道其在外存中的位置 —— 缺页中断机构、页表记录关键信息
3. 当内存不足时，调入页面之前需要调出页面，而调出页面的选择则需要通过算法来确定，算法又需要关键信息的支撑 —— 页面置换算法、页表记录页面使用信息
4. 同时，我们将页面置换出来时，需要考虑该页是否有被修改，从而决定是否将其重新刷入到磁盘中进行更新

综上：我们需要改进页表、内存分配策略、缺页中断机构、页面置换算法。

页表改进

1. 状态位 P：表示当前页是否在内存中，供程序访问时参考
2. 访问字段 A：用于记录程序访问情况，便于在页面置换算法中作为参考
3. 修改位 M：标志该页是否被修改
4. 外存地址：指出该页在外存中的地址，通常是物理块儿号，供调入该页时参考

缺页中断机构

当所要访问的页面不在内存中时，就会产生缺页中断，请求OS将所缺之页调入内存中。缺页中断作为中断同样需要经历如 保护CPU环境、分析中断原因、转入中断处理程序等几个步骤。

但是 缺页中断 又和普通的中断有着明显的区别：

1. 通常 CPU都是在一条指令执行完之后，才会检查是否有中断请求到达。有则响应，否则继续执行下一条指令。而缺页中断则是访问的 指令 或者 读取数据 不在内存中时，便立即产生和处理缺页中断信号，以便及时将需要访问的页调入内存中。
2. 一条指令在执行时，可能产生多次缺页中断，比如需要访问的数据分布在不同的页面上

内存分配策略

在进行内存分配过程中，为每个进程分配的页数最小值（低于该值，程序无法正常运行）是需要确定的，否则可能会导致内存分配了，但是程序无法正常运行，这个数值称为 —— 最小物理块数

然后又回到了怎么进行内存分配的问题上，从上一章中的传统存储管理方式可知，都是可以分为 固定分配 和 动态分配 两种分配方式的：

1. 固定分配：为每个进程分配一组固定数目的物理块，在进程运行期间不再进行更改
2. 动态分配：也就是可变分配，先为进程分配一定数目的物理块，在进程运行过程中可以动态的增加或减少物理块儿的数量

除了分配过程，还有置换过程，即当内存放不下要装入的页时，就需要将一些页面进行置换出去，置换的方式也分为两种：

1. 全局置换： 如果发现缺页，就从空闲物理块队列中取出一块儿用于分配，如果不存在空闲物理块儿，则会在全部进程的物理块儿中选出一块置换出去
2. 局部置换：每次发现缺页时，需要选择将当前进程中的一块儿换出，才能够将需要换入的物理块儿放入

综合 分配方式 以及 置换方式 后，可以组合出 3 种策略：

1. 固定分配局部置换
2. 动态分配局部置换
3. 动态分配全局置换

可能这里的动态分配局部置换可能有一些不解：
其实就是在最初时，为进程先确定一个分配的物理块儿数目，当每次调入页面时，需要换出本身的一页，才能进行调入。不过因为需要的块儿数很难确定，高了导致吞吐量太低，减少了并行度，少了导致进程频繁出现缺页中断，影响效率。所以该策略会在缺页率较高时，为其分配另外的空闲物理块儿，较低时，置换出更多的物理块儿，即减少分配。

在固定分配方法中确定每个进程的物理块儿数目的方法有以下几种

1. 平均分配算法
2. 按比例分配算法
3. 考虑优先权算法

页面调入策略

既然我们已经知道了如何为进程分配内存块儿，以及页面的置换流程，那么页面的调入策略是什么样的呢？

页面什么时候调入？

为了确定系统将进程运行时所缺的页面调入内存的时机，有两种方式：预调页策略 和 请求调页策略
概括的来说，请求调页就是每次只调入一页，很显然，每次只调入一页，那么会经常触发调页的行为就会影响到运行效率。
所以又有 预调页策略，就是一次调入多个页面，至于需要调用哪些页面，则可以通过预测 或者 记录表的形式实现，可知该方法实现较为复杂，并且在预测情况下，如果预测不准确也会导致性能损耗。

从何处调入？

注意交换区中的数据由于经常访问，很频繁，所以采用了顺序分配的方式存储换出的页面

当发生缺页中断时，分为以下三种情况：

1. 对换区中有足够的对换区空间，这时，在程序运行之前，我们将进程相关的所有数据、代码拷贝到 交换区，然后缺页中断时，从交换区获取，这是由于交换区是顺序存储的，所以访问速度更快
2. 对换区空间不足，那么不会进行修改的文件，就不存入交换区，那么每次获取都要从文件区中调入，并且换出时，也是直接丢弃；如果可能修改的部分，在将它们换出时便需调到对换区，以后需要时再从对换区换入。
3. UNIX方式。与进程相关的文件都放在文件区，未运行过的页面都从文件区调入，曾经运行过又被换出的页面，由于是被放入对换区，因此在下次调入时应该从对换区调入。并且UNIX系统允许页面共享

页面置换算法

最佳置换算法

怎么才能使换出的页是最划算的呢？其实就是需要换出以后都不用，或者是最长时间不使用的，这样就可以减少以后发生缺页中断重新调入页面。
所以理想情况下，就是每次在选择换出页面时，都是换出的以后不再使用，或者最长时间不使用的。这样就可以降低缺页率了。
但是该算法只是一个理想算法，只是一个理论，并没有实现，毕竟很难去判断每个页面的使用时机，从而判断何时使用或者不再使用。

其实后面的算法无非是对最久不使用的页面做一个推理

1. 先进入内存的
2. 最久没有使用的
3. 使用次数最少的

FIFO先进先出置换算法

最简单的算法，就是先淘汰最早调入内存的页面，其实就是一个队列的形式，将已经分配的内存块儿通过队列的形式组织，维护一个指针，从头往后移动，每次需要置换页面时，将指针所指位置置换出去，并挪动指针

LRU最近最久未使用算法

怎么样记录访问时间？通过标志位记录时间，然后遍历查找？其实也有些类似：

1. 通过移位寄存器实现
2. 通过栈实现

怎么使用移位寄存器来实现呢？
每个页面在页表部分都记录一个n位的值，每次访问时就在 n-1 位置置 1，并在固定的时间间隔来将该数右移一位，这样在需要置换时，找到该值最小的页面就是最久未使用过的。

怎么使用栈来实现呢？
使用容器来实现呢，肯定是要维护一个序列，这个序列刚好是按照上一次使用时间的排序。最新使用的放栈顶，栈底自然就是最久没有使用的。
流程：准备一个特殊的栈，栈中存放页面的页号。需要访问一个页面，先检查栈中是否存在，如果存在，将该页面号挪动到栈顶，否则直接压栈。所以当需要置换算法时，直接使用栈底元素交换即可。

LFU最少使用置换算法

重点就是怎么记录访问次数。。。。。

CLock置换算法

近似LRU实现，省去了LRU需要的硬件支持

PBA页面缓冲算法

分析了干扰页面置换效率的因素，通过缓存的方式以及对修改页的处理方式的改善，来减少干扰，而在算法上则是使用的 FIFO先进先出置换算法