一、交换与覆盖
引
(1)、技术
①、交换技术与覆盖技术是在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾
②、覆盖技术主要用在早期的操作系统中
③、交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现
(2)、共同点
进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换
(3)、不同点
控制交换的方式
1、覆盖技术
把程序划分成若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域
(1)、方法
程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段
(2)、要求
个模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由操作系统完成自动覆盖
(3)、缺点
对用户不透明，增加了用户负担
(4)、使用
①、目前这一技术用于小型系统中的系统程序的内存管理上
②、MS-DOS的启动过程中，多次使用覆盖技术
③、启动之后，用户程序区TPA的高端部分与COMMAND.COM暂住模块也是一种覆盖结构
2、交换技术
当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存某些进程换进内存，占用前者所占用的区域。这种技术是进程在内存与外存之间的动态调度，多用于分时系统中
(1)、选择原则
例：分时系统中，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的
特殊情况：从不换出处于等待I/O状态的进程，有些I/O进程因DMA而不能换出内存或换出前需要操作系统的特殊帮助
(2)、交换时机
例：
①、只要不用就换出
②、只在内存空间不够或有不够的危险时换出
(3)、交换时工作
盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝，必须对这些内存映像的直接存取
(4)、换回位置
①、是否需要换回到原位置
②、受地址"绑定"技术的影响，即绝对地址产生时机的限制
3、覆盖与交换的比较
①、覆盖发生在同一进程或作业内，只能覆盖那些与覆盖段无关的程序段
②、交换发生在进程或作业之间，不要求用户给出程序段之间的逻辑覆盖结构
二、虚拟存储器
1、基本思想
程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其他部分保存在磁盘上，并在需要时在内存和磁盘间动态交换
2、局部性原理
(1)、时间局部性
一条指令被执行了，则在不久的将来它可能再被执行
(2)、空间局部性
某一存储单元被使用，则在一定时间内，与其相邻的单元可能被使用
3、虚拟存储器
具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的存储器系统。虚拟存储器就是一个地址空间，且具有比实存大得多的容量
4、容量
一个虚拟存储器的最大容量是由计算机的地址结构确定的，与主存的实际大小没有直接关系，而是由主存和辅存的容量之和所确定
5、虚拟存储技术
(1)、虚存
把内存与外存有机的结合起来使用，从而得到一个容量很大的"内存"，这就是虚存
(2)、实现思想
当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作
(3)、目的
提高内存利用率
三、请求式分页存储管理
又称虚拟页式存储管理，与纯分页存储管理不同。请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面。当内存空间已满，而又需要装入新的页面时，则根据算法淘汰某个页面，以便装入新的页面
1、存在问题
①、系统如何获知进程当前所需页面不在主存
②、当发现缺页时，如何把所缺页面调入主存
③、当主存中没有空闲的页框时，根据什么策略选择淘汰的页面
2、扩充页描述子
①、中断位：表示该页在内存还是外存
②、访问位：表示该页最近被访问过，根据访问位决定淘汰哪页
③、修改位：查看此页是否在内存中被修改过
3、地址变换与缺页中断
查页表时，当存在位(中断位)指示该页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执行子程序，把所缺页面装入主存，然后处理机重新执行缺页时打断的指令
(1)、地址变换流程
(2)、缺页中断
①、中断特征
保护CPU现场
分析中断原因
转入缺页中断处理程序
恢复CPU现场
②、缺页中断特殊性
在指令执行期间产生和处理中断信号(一般中断是在该条指令执行后)
一条指令执行期间，可能产生多次缺页中断
③、缺页中断算法流程
4、页面置换算法
(1)、最佳置换算法
一种理论上的算法，其选择的被淘汰页面，将是以后永不使用的或是在未来最长时间不再被访问的页面，采用最佳置换算法，通常可保证获得最低的缺页率
(2)、先进先出页面置换算法FIFO
①、基本思想
选择最先进入内存的页面换出到外存
进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针指向最老页面
②、特点
简单直观，但不符合进程实际运行规律，性能较差，实际应用少
(3)、最近最久未使用置换算法LRU
①、基本思想
以"最近的过去"作为"最近的将来"的近似，选择最近一段时间最长未被访问的页面淘汰出内存
②、特点
适用于各种类型的程序，性能较好，但需要较多的硬件支持
③、硬件支持
寄存器
为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器
栈
用栈保存当前使用页面时栈的变化情况
(4)、Clock置换算法
简单Clock置换算法(类似LRU)
改进型Clock置换算法
由访问位A和修改位M可以组合成下面四种类型的页面
1类，A=0、M=0：最近未被访问，又未被修改，是最佳淘汰页
2类，A=0、M=1：最近未被访问，但已被修改，不是很好的淘汰页
3类，A=1、M=0：最近已被访问，但未被修改，有可能再被访问
4类，A=1、M=1：最近已被访问，又已被修改，有可能再被访问
执行过程：
①、从指针所指示的当前位置开始，扫描循环队列，寻址A=0、M=0的1类页面，将所遇到的第一个页面作为淘汰页
②、如果①失败，开始第二轮扫描，寻找A=0、M=1的2类页面，将遇到的第一个这类页面作为淘汰页，将所有扫描过的页面访问位都置0
③、如果②失败，将指针返回到开始的位置，并将所有访问位复0，重复①，如果扔失败，则重复②，此时一定能够找到淘汰的页
(5)、最少使用算法LFU
①、基本思想
为内存各页设置一移位寄存器用于记录被访频率，并选择在最近时期使用最少的页面淘汰
②、特点
仅用移位寄存器有限个位来记录会导致访问一次与访问多次的等效性，不能真实反映页面使用情况
(6)、页面换出算法PBA
①、设立空闲页面链表和已修改页面链表
②、采用可变分配和基于先进先出的局部替换策略，并规定被淘汰页先不做物理移动，而是依据是否修改挂到空闲页面链表或已修改页面链表
③、空闲页面链表同时用于物理块分配
④、当已修改页面链表达到一定长度时一起写回磁盘，可显著减少磁盘I/O操作次数
5、请求分页虚拟存储系统软硬件支持
①、技术组成
分页+请求调页+页面置换
②、硬件支持
请求分页的页表机制+缺页中断机构+地址变换机构
③、软件支持
请求调页功能模块+页面置换功能模块
6、影响缺页次数的因素
①、分配给进程的物理页面数
②、页面本身的大小
③、程序的编制方法
④、页面淘汰算法
7、性能问题
颠簸(抖动)：
在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃
原因：
①、页面淘汰算法不合理
②、分配给进程的物理页数太少
8、页面共享
对于数据页面共享，可以安排在作业地址空间中的任何一个页面上；对于库例程共享，要求必须把共享的例程安排到所有共享它的作业地址空间中相同的页面中
当共享页从主存中淘汰或被重新装入主存时，共享此页面的所有作业页表中的相应"页面存在"位都必须更新，可以采用如下技术：
为那些被共享的页面独立设置一张公共页表，当某个被共享页面与辅存交换时，对这个公共页表的表目加一更新，至于有共享页面的作业的页表，则在其相应表目设一指针，指向该页在公共页表的表目即可
四、请求分段存储管理
又称虚拟段式存储管理
1、段表项扩充
2、缺段中断
3、地址变换
