一、起因

内存相对于寄存器速度慢，所以内存和寄存器之间有 cache

硬盘比内存容量大，但是速度慢

磁带比硬盘容量还大

计算机系统中，尤其是多道程序运行下内存不够用

二、覆盖技术

1、目标

较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用

2、原理

• 程序划分为独立程序模块
• 共享内存、分时执行
• 常用功能常驻内存、不常用功能放于外存

3、缺点

覆盖模块从外存装入内存，实际上是以时间延长换取空间节省

三、交换技术

1、目标

多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源

2、原理

暂时不能运行的程序送到外存

3、存在的问题

• 交换时机的确定：只当内存空间不够或者有不够的危险时
• 交换区的大小：足够存放进程的所有内存映像的拷贝；能对这些内存映像直接存取
• 程序换入时的重定位：动态地址映射

4、与覆盖技术的区别

覆盖：发生在一个程序里，程序员需要手动指定逻辑关系；

交换：发生在程序之间，由操作系统内部完成，不需要程序员设置

四、虚存技术

1、目标

覆盖技术做的更好：由操作系统自动完成

交换技术做的更好：只对进程的部分内容在内存和外存之间进行交换

2、程序的局部性原理

• 时间局部性：连续两次访问集中在一个较短时期
• 空间局部性：访问的数据在较近的区域

3、基本概念

可以在页式或段式内存管理的基础上实现

• 需要执行的部分页面或者段装入到内存
• 执行过程中，将尚未在内存但是须执行的程序调入到内存
• 内存中暂时不使用的页面或段保存在外存

4、基本特征

• 大的用户空间：物理内存和外存相结合
• 部分交换：部分虚拟地址空间进行的
• 不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续

5、实现 —— 虚拟页式存储管理

（1）页表

• 完成逻辑页到物理页帧的映射

（2）虚拟页式存储管理技术

• 在页式存储管理的基础上增加请求调页和页面置换功能
• 运行过程中程序或者要访问的数据不在内存中，则向系统发出缺页中断请求
• 系统在处理这个中断时，将外存中相应页面调入内存，使得程序继续运行

（3）页表表项

• 驻留位：表示该页是在内存还是外存
• 保护位：表示允许对该页做何种类型的访问
• 修改位：该页在内存中是否被修改过（决定是否把它的内容写回外存）
• 访问位：该页面被访问过则设置此位（用于页面置换算法）

（4）缺页中断

（5）后备存储

• 一个虚拟地址空间的页面可以被映射到一个文件（在二级存储中）的某个位置
• 代码段：映射到可执行二进制文件
• 动态加载的共享库程序段：映射到动态调用的库文件
• 其他段：可能被映射到交换文件

五、页面置换算法

1、功能

当缺页中断发生，需要调入新的页面而内存已满时，选择内存中哪个物理页面被置换

2、目标

尽可能地减少页面的换进换出次数（即缺页中断的次数）

3、最优页面置换算法（局部页面置换算法1）

（1）基本思路：距离下一次访问等待时间最长的逻辑页面作为置换的页面

（2）理想情况，可作为其他算法的性能评价的依据

4、先进先出算法 FIFO（局部页面置换算法2）

（1）基本思路

• 选择在内存中驻留时间最长的页面并淘汰之
• 当发生一个缺页中断时，把链首页面淘汰出去，把新的页面添加到链表的末尾

（2）性能较差，并且有 belady 现象

5、最近最久未使用算法 LRU（局部页面置换算法3）

（1）基本思路

选择最久未使用的那个页面，并淘汰之

（2）最优页面置换算法的近似，基于程序的局部性原理

（3）LRU 算法需要记录各个页面使用时间的先后顺序，开销比较大

（4）实现方法

• 系统维护一个页面链表
• 设置一个活动页面栈

6、时钟页面置换算法（局部页面置换算法4）

基本思路：

（1）LRU的近似，FIFO的改进

（2）装入内存页面的页表项的访问位初始化为0，被访问置为1；各个页面组织成环形链表，指针指向最老页面

7、二次机会法

（1）修改 clock 算法，使它允许脏页总是在一次时钟头扫描中保留下来，同事使用脏位和使用位来指导置换

（2）Enhanced Clock algorithm

8、最不常用算法 LFU（局部页面置换算法5）

（1）基本思路

当一个缺页中断发生时，选择访问次数最少的那个页淘汰之

（2）实现方法

对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加一。在发生缺页中断时，淘汰技术值最小的那个页面

（3）LRU和LFU的区别

LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频度，访问次数越多越好

9、Belady 现象

（1）现象

在采用 FIFO 算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象

（2）原因

FIFO 算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面）

因此，被它置换出去的页面并不一定是进程不会访问的

（3）LRU页面置换算法没有Belady现象

10、LRU、FIFO、Clock 的比较

（1）LRU、FIFO 本质上都是先进先出的思路

（2）LRU 是针对页面的最近访问时间来排序、开销大

（3）FIFO 是针对页面进入内存的时间来排序、开销小

（4）如果一个页面进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。即 LRU 退化为 FIFO