os:虚拟存储概念（四）

虚存的需求背景

实际的存储受限于成本等原因，为了物尽其用，往往设计为层次结构，大容量存储往往性能较差，性能较好的存储往往设计的很小。

但借助软硬件的协同，将读写较快的内存作为读写较慢的磁盘的缓存来使用，如果处理得当，相当于提高了存储的综合性能。

覆盖技术和交换技术

目前已经有一些解决内存不够的思路，比如之前提到的段式存储中的共用策略（覆盖），连续存储中的交换策略。

这一类时间换空间的方法，都是比较真诚的资本家想法，在于充分的增加内存的时间占用率，让每一块区域尽可能都不闲下来。

覆盖技术：

• 必要部分：常驻
• 可选部分：用到时装入
• 不会同时使用的几个模块：相互覆盖，共用存储

这样就减小了单个程序运行的内存开销，可以在较小的内存上运行较大的程序。

但这种方式，不能自动完成，需要程序员自行指定调用关系，机器才会进行覆盖。这增加了编程的难度。

交换技术着眼于不同进程的调度，区别相对繁忙和闲置的进程，并换入换出。通常我们使用电脑时看到的临时文件.swp就是被换到外存的部分（当然不一定是整个进程）。

交换技术的问题

• 交换时机：何时需要交换？只当内存空间不够或者有不够的可能时换出
• 交换区大小：存放用户进程的所有内存映像的拷贝
• 程序换入时的重定位：换回时需要放回在原处吗？使用动态链接

对比：

	覆盖	交换
操作单位	模块	进程
模块间逻辑结构	需要给出	不需给出
工作环境	程序内部模块	内存进程间

局部性原理

在介绍虚拟内存之前，我们先要给出其一个重要的理论前提，即局部性原理，说白了就是好好利用缓存，一鼓作气干尽可能多的事，可以降低不必要的时间消耗。

程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。这种局部性可以从如下三个层面上来看：

• 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问与下次访问都集中在一个较短时期内；
• 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几条数据都集中在一个较小的区域内；
• 分支局部性：一条跳转指令的两次执行，很可能跳转到相同的内存位置

基于上述的思考，虚拟存储技术是能够实现的，且能获得令人满意的结果。

比如要遍历一个二维数组int a[1024][1024]

有如下两种编写方法：

for (j = 0; j < 1024; j++)
	for (i = 0; i < 1024; i++)
		a[i][j] = 0;

和

for (i = 0; i < 1024; i++)
	for (j = 0; j < 1024; j++)
		a[i][j] = 0;

由于后一次将临近的数据先行访问完，从而造成的缺页中断比前者少一个量级。

虚存的目标

虚拟存储就结合了覆盖和交换两种方法的优劣势：

• 在程序内部（单进程）实现内存与外存的交换，从而获得更多的空闲内存空间。
• 这个过程由操作系统自动完成，不需程序员设定。

决定哪些内容何时换入换出的算法就是下一节要重点讲述的置换算法。

虚存的概念

虚拟存储就是将一部分硬盘当成虚拟内存使用，实现时将不常用的部分内存块暂存到外存。

原理：

• 加载程序时，只将当前指令执行需要的部分页面或段装入内存
• 执行过程中，需要的指令或者数据不在内存中（称为缺页或缺段）时，处理器通知操作系统将相应的页或段调入内存中
• 操作系统将内存中暂时不用的页面或段保存到外存

这样，除却交换过程的开销，整体上就显得内存变大了。

特点：

• 不连续性：物理内存和虚拟地址空间使用非连续
• 内存扩容：提供给用户的虚存大于实际物理内存
• 部分交换：只对部分虚拟地址空间进行调入调出

实现

• 方式：

• • 虚拟页式存储
  • 虚拟段式存储

• 具体的实现包括：

• • 硬件的地址转换机制
  • 操作系统的进程监控
  • 操作系统的置换算法

虚拟页式存储

在之前的页式存储（非连续）的基础上，增加请求调页和页面置换的机制。

思路：

• 只装必要的部分即可运行
• 需要的代码或数据不在内存，发送缺页异常
• 处理异常，从外存调入必要页面

原理框图也比较直接，在之前的页式存储的结构上加入缺页异常的处理即可。
处理方法就是将“不在内存”这个标志位（即驻留位）变成“在内存”。

其他的标志位还有：

• 修改位：表示在内存中的该页是否已经修改过（置换时是否需要写回）
• 访问位：给页面置换算法提供统计支持
• 保护位：表示该页的允许访问方式（只读、可读写、可执行等）

x86页表结构：

缺页异常

发现要找的内存页不在内存当中，就会引发缺页异常。却也异常处理流程如下图：

• 执行命令时CPU给出需要的逻辑地址，查找页表；
• 发现缺页，产生缺页异常；
• 操作系统启用缺页异常例程，查找页面在外存中的位置；
• 从物理内存中找空闲页帧并将页面换入空闲处；
• 将对应页表项修改为有效；
• 重新执行导致异常的指令。

可以看到这是最顺利的情况，如果换入时发现没有空闲页帧的话则需要额外几步：

• 根据页面置换算法选择要被换出的页帧；
• 判断该页帧是否被修改过，如果被修改过则写回外存，否则直接作废；
• 将其对应的页表项改为无效；
• 然后将需要的页帧换入空出来的区域，后续与最开始的流程一致。

虚拟页式存储管理的性能可以用有效存储访问时间（Effective memory access time，EAT）来评定，

可见为了使引入虚拟页式存储的时间尽可能小，必须要保证缺页率 相当低。