背景
虚拟存储器作为现代操作系统中存储器管理的一项重要技术，实现了内存扩充功能，但该功能并不是从物理上实际地扩大内存的容量，而是从逻辑上实现对内存容量的扩充，让用户所感觉到的内存容量比实际内存容量大很多。
概述
在***存储器管理章节中***介绍的管理方法都有一个特点就是需要将作业全部装入内存后才能运行。当遇到作业很大、有大量作业运行时，会出现内存容量不足以容纳，如果能从逻辑上扩从内存容量，那么这些问题就会解决。
常规存储器的特征
- 一次性：一次性全部装入内存，才能运行。
- 驻留性：是指作业装入内存后，一直驻留在内存中，其中任何部分都不会被换出。
局部性原理
程序在执行时将呈现出局部性规律，即在较短的一段时间内，程序的执行仅局限于某个部分，相应地，它访问的存储空间也局限于某个区域。
- 程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下是顺序执行的。（空间局限性）
- 过程调用的深度在大多数情况下不会超过5
- 程序中存在许多的循环结构，这些结构由少数的指令构成，被多次调用（时间局限性）
- 程序中包括许多数据结构的处理，如对数组进行操作，这些处理往往都局限在很小的范围。（空间局限性）
虚拟存储器
基本工作情况
基于局部性原理可知，程序仅将那些当前要运行的少数页面或者段先装入内存便可运行，其余部分暂留在盘上，程序运行时如果它要访问的页（段）已调入内存，便可以继续执行下去，但如果尚未掉入内存，便发出缺页（段）中断请求，此时os将利用请求调页（段）功能将他们调如内存，以便程序可以继续执行下去。如果此时内存已满，os还必须使用页（段）的置换功能。
定义
是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每一位的成本却又接近于外存。
特征
- 多次性：必须建立在离散分配的基础上
- 对换性：必须建立在离散分配的基础上
- 虚拟性：是以多次性和对换性为基础
实现方法
由于采用连续分配方式，会造成资源的严重浪费，所以虚拟存储器的实现，都毫无例外建立在离散分配存储管理方式的基础上。
- 分页请求系统：在分页系统的基础上增加了请求调页功能和页面置换功能，置换时以页面为单位，系统必须提供必要的硬件支持和实现请求分页的软件。硬件：请求分页的页表机制、缺页中断机构和地址变换机构。
- 请求分段系统：在分段系统的基础上增加了请求调页功能和页面置换功能，置换时以段为单位，同样需要硬件和软件支持。硬件：请求分段的段表机制、缺段中断机构和地址变换机构。
请求分页存储管理方式
每次调入和换出的基本单位都是长度向固定的页面，这使得请求分页系统在实现上比请求分段系统简单，是目前最常见的一种实现虚拟存储器的方式。
硬件支持
- 请求分页机制：请求页表：页号、物理块号、状态位P、访问字段A、修改位M和外存地址。其中P指示该页是否已掉入内存，A纪录该页最近被访问的次数，或者纪录本页有多久未被访问，提供给置换算法参考，M是否被修改过，未被修改就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若被修改则需要将该页写回到外存，以保证外存副本始终是新的。
- 缺页中断机构：缺页中断和一般的中断有明显区别：1)在指令执行期间产生和处理中断信号，以便能及时将所缺页面调入内存；2）一条指令在执行期间可能产生多次缺页中断。
- 地址变换机构：是在分页系统地址变换机构的基础上，增加了产生和处理缺页中断，以及从内存中换出一页的功能。同样也有快表等。
内存分配
- 最小物理块：是指能保证进程正常进行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法进行。
- 内存分配策略
1）固定分配局部置换：为每个进程分配固定的物理块数，不在改变，当发现缺页时，从分配的n个页面中替换一页出来，然后在调入一页，以保证分配给该进程的内存空间不变。实现该策略的困难是：无法确定每个进程的适当的物理块。
2）可变分配全局置换：是指先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，当发现缺页时，os将所保留的空间物理块取出一块分配给该进程，或者以所有进程的全部物理块为标，选择一块换出，然后将所缺页调入，这样分配给该进程的内存空间就随着增加。
3）可变分配局部置换：当发现进程缺页时，只允许从该进程在内存的页面中选择一页换出，这样就不会影响其他进程的进行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加物理块，直至该进程的缺页率减少到适当程度为止，反之一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加。 - 物理块分配算法：在采用固定分配策略时，通过平均分配算法或者按比例分配算法将系统中可供分配的所有物理块分配给各个进程。
页面调入策略
为使进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。
- 何时调入页面：预调页策略（预测成功率仅为50%）和请求调页策略（目前虚拟机存储器大多采用，但须花销较大的系统开销，增加了磁盘I/O的启动频率）
- 从何处调入页面：请求分页系统中的外存分为：文件存和对换区，所以当系统有足够的对换空间可以全部从对换区调入所需页面，如果系统缺少足够的对换区，这时凡是不会被修改的文件，都直接从文件区调入；对于那些可能被修改的部分，在将他们换出时须调到对换区，以后需要时再从对换区调入，此外还有unix方式，即凡是位运行过的页面都从文件区调入，对于曾经运行过但又被换出的页面，放在对换区。
- 页面调入过程：程序访问P=0的页面 -> 便向cpu发出一缺页中断 -> 缺页中断处理程序找到物理块 -> 将缺页调入内存，修改页表（P=1等）；如果内存已满则置换，从内存中选出一页换出，如果该页没有被修改过，则不必写回磁盘，但如果该页被修改过，则先写回磁盘，然后再调入所缺之页，修改页表（P=1等），并写入快表中。
- 缺页率：f = F / A,其中 F为访问页面失败（需要调入）的次数，S为访问成功的次数，A = S+F；影响的因素：页面大小、进程所分配物理块的数目、页面置换算法和程序固有特性等。
页面置换算法
通常把选择换出页面的算法称为页面置换算法。置换算法的好坏将直接影响到系统的性能，如‘抖动’：即刚被换出的页面又很快又被访问，需要将它重新调入，此时又需要再选出一页调出...如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面的置换工作上。
最佳置换算法（optimal）
选择的被淘汰页面将是以后永不使用的，或者是在最长（未来）时间内不再被访问的页面，采用最佳置换算法可以保证获得最低的缺页率，但是无法预知，所以目前无法实现，但是可以用该算法去评价其他算法。
先进先出页面置换算法（FIFO）
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰，但该算法与进程实际运行的规律不相适应，FIFO实际的效率不够好。
最近最久未使用置换算法（least recently used， LRU）
根据页面调入内存后的使用情况作出决策的，选择最近最久未被访问的页面予以淘汰。
- 利用寄存器实现LRU：为记录进程在内存中的使用情况，须为每个在内存中的页面配置一个移位寄存器，可以表示为：R=Rn-1Rn-2...R2R1R0,当进程访问某物理块时，需要将相应寄存器的Rn-1位置为1，定时信号每隔一定时间100ms将寄存器右移一位，如果把n位数看成一个整数，那么最小数值的寄存器所对应的页面，就是最久未使用的页面。
- 利用栈实现：利用一个特殊的栈保存当前使用的各个页面的页面号，每当进程访问某页面时，便将该页面的页号从栈中移除，将它压入栈顶，因此栈顶始终是最新被访问的页面编号，而栈底则是最近最久未被使用的页号。
最少使用置换算法（LFU）
应为在内存中的每一个页面设置一个移位寄存器，用来记录该页面被访问的频率，由于存储器具有较高的访问速度，所以也是采用周期性右移。
Clock置换算法
一种lru的近似算法
- 简单的Clock置换算法：为每页设置一位访问位，再将内存中的页面都通过链接指针链接成一个循环队列，当某页被访问时，其访问位被置为1，置换算法在选择一页淘汰时，如果访问位是0直接选择换出，如果是1则重新置为0，暂时不换出，给予该页第二次驻留内存的机会，再按照FIFO算法，检查下一个页面，当检查到队列中的最后一个页面时，如果器访问为仍然是1，则再返回队首去检查第一个页面。又称为最近未用算法（not recently used）.
- 改进型Clock置换算法：除了考虑页面的使用情况外，还需再增加一个因素——置换代价。这样，选择页面换出时，即要是未使用过的页面，又要是未被修改过的页面，把同时满足这两个条件作为首选淘汰的页面。具体可分为4类，其中A=0，M=0的优先级最高最新扫描。
页面缓冲算法（PBA）
- 影响页面换进换出效率的因素：页面置换算法、写回磁盘的频率和从磁盘读入内存的频率。
- PBA算法：在内存中设置2个链表，空闲页面链表：是一个空闲物理块链表，用于分配给频繁发生缺页进程，当有一个未被修改的页面要换出时，挂在空闲链表的尾部，当以后需要该页时直接从链表取下，免除了从磁盘读入数据的操作；修改页面链表：当进程需要将一个已修改的页面换出时，系统不会立即把它换出，而是放在一个链表的尾部，等待最后同一写回，降低已修改该页面写回磁盘的频率。
- EAT：还要考虑缺页中断的处理时间，设处理中断的时间为ε，则当被访问页不在内存时：EAT = λ+t+ε+λ+t = ε+2(λ+t)，考虑快表的命中率和缺页率：EAT = λ + at + (1-a)[t + f*(ε+λ+t) + (1-f)*(λ+t)]，其中a表示命中率，f表示缺页率。
工作集
发生‘抖动’的根本原因是同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，频繁的发生缺页。造成每个进程大部分的时间都是用于页面的换出和换入，而几乎不可能去做任务有效的工作，从而导致处理机的利用率急剧下降并趋于0的情况，我们称此时的进程是处于‘抖动’状态。
为了解决抖动问题，提出了工作集的概念
基本概念
- 定义：是指在某段时间间隔Δ里，进程实际所要访问页面的集合。
- 窗口尺寸：就是把某进程在时间t的工作集记为w(t,Δ),其中Δ为窗口尺寸，工作集w(t,Δ)是一个二元函数，即在不同时间t的工作集大小不同，所含的页面数也不同；工作集与Δ有关，是Δ的非降函数，即w(t,Δ)⊆w(t,Δ+1)
抖动的预防方法
为了保证系统具有较大的吞吐量，必须防止‘抖动’的发生。
- 采用局部置换算法：虽然不会影响别的进程，但是在发生抖动后回长期处在磁盘I/O的等待队列中，使队列的长度增加，这会延长其他进程缺页中断的处理时间，也延长了其他进程队磁盘的访问时间。
- 把工作集算法融入到处理机调度中
- 利用“L=S”准则调节缺页率：L是缺页之间的平均时间，S是平均缺页服务时间，即用于置换一个页面的时间。如果L >> S，表示很少发生缺页，磁盘的能力没有充分的利用，反之如果L << S，表示频繁发生缺页。当两者相等时，表名磁盘和处理机都达到了他们的最大利用率。
- 选择暂停进程
请求分段存储管理方式
硬件支持
- 请求段表机制
- 缺段中断机构
- 地址变换机构
分段的共享与保护
- 共享段表：共享进程计数count、存取控制字段和段号
- 共享段的分配与回收：分配时记录第一个请求使用的进程，为共享段分配一个物理区，并记录，count+1；回收：当某进程不在需要共享段是，count-1，当为0时，则系统回收该共享段的物理内存。
分段保护
- 越界检查
- 存取控制
- 环保护机构：低编号的环具有高的优先权，OS核心处于0号环内，有以下规则：1）一个程序可以访问驻留在相同环或者较外环中的数据；2）一个程序可以调出驻留在相同环或较内环中的服务。
