8.1 虚拟存储器
8.1.1 虚拟存储器的定义
1. 虚存定义
通过请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
2. 优势和应用
- 用户地址空间可以大于物理内存空间，使得内存可以保存数量较多的进程，提高了并发性；
- 运行速度接近于内存，而成本又接近外存；
- 广泛应用于大中小微型计算机中。
8.1.2 虚拟存储器的特点
- 多次性：一个进程的数据会多次装入内存。
- 对换性：允许程序在运行过程中从内存换入和换出。
- 虚拟性：未改变系统中内存物理的大小。
8.2 请求页式分配
8.2.1 请求分配硬件支持
1. 新增多个属性的页表
| 页号 | 物理块号 | 状态位 | 访问位 | 修改位 | 外存地址 |
- 状态位：表明该页是否在外存
- 访问位：根据访问位来决定淘汰哪一页
- 修改位：查看此页是否在内存中被修改过
- 外存地址：该页在外存上的地址，便于调入
2. 缺页中断机构及其特点
如果访问的页不在内存，就产生一个缺页中断。
缺页中断特点
- 同样要经历中断步骤
- 在指令执行期间产生（和普通中断不同，普通中断是在一条指令结束后才产生）
- 恢复执行被中断指令
3. 地址变换机构
和普通的页式存储相同：
8.2.2 内存分配策略
1. 内存分配要考虑的问题
如果分配进程的物理块少，那么内存中进程数越多，进程缺页的可能性就越高；
但是进程分配的物理块超过一定数目后，分配更多物理块对进程缺页率没有影响。
2. 分配置换的三种组合
- 固定分配局部置换
- 可变分配局部置换
- 可变分配全局置换
分析：
准备或运行时，
固定分配：
给进程的 每个物理块 分配数量固定，
运行时数量固定，按照分配数量。
可变分配：
分配时数量固定，
运行时数量不固定。
缺页时，
局部置换：
缺页进程独立，
置换分配给自身的物理块。
全局置换：
从操作系统中抠一块给缺页进程；
或者从其他进程抠一块下来，经过外存，又调回给缺页进程。
为什么没有固定分配–全局置换？
因为，固定分配要求自身缺页时，替换自身；不能要求其他进程的置换，与全局置换相悖。
8.3 页面置换算法
有关页面置换的说明：
- 所需页不在内存，该进程在内存没有可用的块。
- 不同置换选择会使系统效率有很大不同。
- 几个算法都采用固定分配局部置换策略。
8.3.1 最优页面置换算法 OPT
算法特点——发生缺页，有两个考虑的顺序:
- 当前内存中有的页以后不再被访问，置换出去
- 当前内存中几页都要被访问，选择一个最后用到的页，并把它置换出去
注意：不仅置换，调入页面也算缺页！
| 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | |
| 1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||
| 2 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | |||||||||||
| 3 | 1 | 1 | 3 | 3 | 4 | 3 | 1 | 1 | ||||||||||||
| 缺页 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
缺页率：50%
8.3.2 先进先出置换算法 FIFO
置换最先进入内存的页：
| 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | |
| 1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||
| 2 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||
| 3 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | |||||||
| 缺页 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
缺页率：75%
8.3.3 最近最久使用置换算法 LRU
从缺页的那里开始逆向检查，找到最久之前使用的页面，将其置换掉：
| 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | |
| 1 | 7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 | 1 | 1 | 1 | ||||||||
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||
| 3 | 1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||
| 缺页 | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ | √ |
缺页率：60%
8.3.5 时钟算法 Clock
1. 算法流程
需要给每个物理块增加一个附加位，称为使用位u；
当某一页装入内存时，该物理块的使用位设为1，当该物理块被使用时，它的使用位也设为1；
对于页面置换算法，把用于替换的物理块集合看作是一个循环缓冲区，并且有一个指针与之关联；
当需要进行页面置换时，两种考虑：
- 若指针所指页面u=0，置换它，指针指向下一个；
- 若指针所指页面u=1，置为0后继续扫描，直到找到一个u=0的物理块。
2. 示意图
左图为页面置换前状态，右图为页面置换后状态：
