5.1 虚拟存储器概述

虚拟存储器的引入

常规存储器管理方式的特征：

• 一次性
• 驻留性

程序运行时的局部性原理：一较短时间内，程序执行仅局限于某个部分，所访问的存储空间也仅局限于某个区域。

• 时间局限性：程序中存在大量的循环操作。
• 空间局限性：程序的顺序执行，导致访问区域局限。

虚拟存储器的定义

所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

虚拟存储器的特征

• 多次性：作业无须一次性地全部装入内存运行，允许被分多次调入内存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。（基础：离散分配存储管理方式）
• 对换性：作业运行时程序和数据无须一直常驻内存，允许作业运行时进行换进、换出，即进程运行期间允许那些暂不使用的代码数据从内存调至外存的对换区（换出），待需要时再将其调回至内存（换进）。有效提高内存利用率。
• 虚拟性：能够从逻辑上扩充内存容量，虚拟内存容量（实际内存容量小），实现小内存运行大作业，改善内存利用率，提高并发程度，增加系统吞吐量。

虚拟存储器的实现方法

请求分页系统

在分页系统的基础上，增加了请求调页功能和页面置换功能。

硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构。

软件：实现请求调页的软件和实现页面置换的软件。

请求分段系统

在分段系统的基础上，增加了请求调段功能和段的置换功能。

硬件支持：请求分段的段表机制、缺段中断机构、地址变换机构。

软件：实现请求调段的软件和实现段的置换的软件。

5.2 请求分页存储方式

请求分页中的硬件支持

请求页表机制

请求页表增加四个字段作为请求分页的数据结构。（请求分页系统中页表诸项：页号 物理块号 状态位P 访问字段A 修改位M 外存地址）

缺页中断机构

当要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺的页面调入内存。经历保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等步骤。

特点：在指令执行期间产生和处理中断信号；一条指令在执行期间，可能产生多次缺页中断。

地址变换机构

分页系统地址变换机构基础上为实现虚拟存储器，增加功能（如产生和处理缺页中断、从内存换出一页等）。

请求分页中的内存分配

最小物理块数的确定

是指能保证进程正常运行所需的最小物理块数。与计算机的硬件结构有关。

内存分配策略

• 分配策略：固定和可变
• 置换策略：全局和局部

1. 固定分配局部置换
2. 可变分配全局置换
3. 可变分配局部置换

物理块分配算法

平均分配算法：这是将系统中所有可供分配的物理块，平均分配给各个进程。

按比例分配算法：考虑优先权的分配算法。一部分按比例分配；另一部分根据优先权增加分配给进程。

页面调入策略

1、何时调入页面

预调页策略（一次调入若干相邻页）

请求调页策略（需要时提出请求）

2、从何处（外存）调入页面

系统拥有足够的对换区空间：全部从对换区调入。

系统缺少足够的对换区空间：不会被修改的文件，从文件区调入；被修改的从对换区调入。

UNIX方式：未运行过的页面，从文件区调入；运行过从对换区调入。该系统允许页面共享，故进程请求页面可能被其他进程调入内存，此时无需再从对换区调入，直接共享。

3、页面调入过程

每当程序所要访问的页面未在内存（存在位为“0”）：

1. 向CPU发缺页中断
2. 中断处理程序保留CPU环境去分析中断原因
3. 转入缺页中断处理程序
4. 通过查找页表得到该页所在外存物理块
5. 若内存未满，启动磁盘I/O，调该缺页入内存，修改页表
6. 若内存已满，置换算法将内存中一页换出，调该缺页入内存，修改页表，置该页面存在位为“1”，页表项写入快表

4、缺页率 ★

进程运行过程中，访问页面成功的次数S，访问页面失败的次数F

缺页率 f = F / (S + F)

影响缺页率的因素：页面大小、进程所分配的物理块数目、页面置换算法、程序固有属性。

5.3 页面置换算法

把选择换出页面的算法称为页面置换算法，应该把那些以后不再会访问的页面换出，或者把那些停留较长时间而不会再访问的页面调出，最终的目的是达到一个较低的页面更换频率。

最佳置换算法

原理：调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。

通常可以获得最低的缺页率。

无法预知在进程中那个页面是未来最久时间不再被访问，因此，算法无法实现。

先进先出(FIFO)置换算法

淘汰在内存中驻留时间最久的页面。（性能较差）

最近最久未使用(LRU)置换算法

根据页面调入内存后的使用情况，记录一个页面自上次被访问以来所经历的时间t，淘汰现有页面中t值大的。

硬件支持

寄存器：为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3 … R2R1R0。

当访问到某物理块时，将相应寄存器的Rn-1位置成1。每隔一段时间将寄存器右移一位。淘汰寄存器值最小的页面。

栈：利用一个特殊的栈来保存当前使用的各个页面的页面号，每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。则栈底为最近最久为使用页面的页面号。

Clock置换算法

简单Clock置换算法（最近未用算法NRU）

原理：淘汰最近一段时间内未被访问的一页。

设置访问位A（A=0 最近未被访问；A=1 最近被访问）。

将所有页面链接成一个循环队列。

循环地检查各页面的应用情况，最近未用算法。

改进型Clock置换算法

首选置换页面：既是未使用过的页面；又是未修改的页面。

由访问位A和修改位M可以组合成下面四种类型的页面：

• 1类（A=0，M=0） 最近既未被访问，又未被修改；
• 2类（A=0，M=1） 最近既未被访问，但已被修改；
• 3类（A=1，M=0） 最近被访问，未被修改；
• 4类（A=1，M=1） 最近被访问，且被修改。

步骤：

1. 扫描循环队列，找出一类页面，找到则淘汰该页。
2. 未找到，开始第二轮扫描，找第二类页面，找到淘汰该页，并将所有经过的页面的访问位置0。
3. 都失败，重复1，2，直到找到淘汰页面。

最少使用(LFU)置换算法 ○

淘汰访问次数最少的一页。在页表中增加访问计数。

设置移位寄存器（每一页）：高位置1，定时右移。

页面缓冲(PBA)算法 ○

采用可变分配和局部置换方式的内存分配策略，系统为每个进程分配一定数目的物理块的同时自己保留一部分空闲物理块。

置换算法采用FIFO，淘汰的页面挂在下列两个链表的尾部：空闲页面链表和已修改页面链表。当修改页面达到一定数量，再写回磁盘。

• 空闲页面链表：实际上是空闲物理块链表，是系统掌控的物理块，用于分配给频繁发生缺页的进程。
• 修改页面链表：已修改的页面不立即换出至外存，而是将其所在物理块挂在修改页面链表的末尾。

5.4 “抖动”与工作集

抖动

“抖动”的含义：进程的大部分时间用于页面的换进/换出，几乎无法去做任何有效的工作。

产生“抖动”的原因：运行的进程太多，每一个进程的物理块太少，频繁地出现缺页。使得在系统中排队等待页面调进/调出的进程数目增加。对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于0的情况。我们称此时的进程是处于“抖动”状态。

工作集

所谓工作集，是指在某段时间间隔Δ里，进程实际所要访问页面的集合。

其中Δ为工作集的窗口尺寸。

进程在时间间隔(t-Δ, t)中引用的页面集合。

抖动的预防方法

（1）采取局部置换策略

（2）把工作集算法融入到处理机调度中

（3）利用“L=S”准则调节缺页率

（4）选择暂停的进程

5.5 请求分段存储方式 ▽

请求分段中的硬件支持

段表机制：

请求分段系统中的中断处理过程：

请求分段系统的地址变换过程：

分段的共享与保护

共享段表

共享段的分配与回收

第一次请求调入时，把共享段调入内存一物理区，修改请求调入进程的段表的相应项，还要在共享段表中增加一表项，填写相关数据，把count置1。

当进程不需要该段，应将该段释放，撤销在段表中共享段对应的表项，执行count：=count-1操作，如果结果为0，则系统回收该共享段，以及取消共享段表中所对应的表项。

分段保护

越界检查

存取控制检查

(1) 只读

(2) 只执行

(3) 读/写

环保护机构

(1)一个程序可以访问驻留在相同环或较低特权环中的数据。

(2)一个程序可以调用驻留在相同环或较高特权环中的服务。