4.5 虚拟存储器的基本概念

引入虚拟存储器的原因

作业逻辑空间过大时不能被全部装入，导致无法运行

由于内存容量的限制导致大量作业在外存上等待。

4.5.1虚拟存储器的引入

实际存储器，有一个共同特点一次性与驻留性，要求将一个作业全部装入内存方能运行。

实际上有许多作业在每次运行时，并非用到其全部程序，故可以仅把作业的一部分装入内存就能运行，这就是虚拟存储器系统实现的理论基础——程序执行的局部性规律。

时间局限性：某指令被执行或某数据被访问，不久后可能再执行/访问（大量循环存在）
空间局部性：程序访问了某个存储单元，附件的存储单元页将被访问（顺序执行）

虚拟存储器的定义：

虚拟存储器:是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

虚拟存储器的逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却接近于外存。

4.5.2虚拟存储器的实现方法

虚拟存储器的实现建立在离散分配的存储管理方式的基础上:

在虚拟存储器中，允许将一个作业分多次调入内存。如果采用连续分配方式，不仅造成内存资源的浪费，而且无法从逻辑上扩大内存容量。

flowchart LR A(虚拟存储器实现方法) A --- B(请求分页) A --- C(请求分段)

4.5.3虚拟存储器的特征

多次性: 一个作业被分成多次调入内存运行
对换性: 允许在作业的运行过程中进行换进、换出。
虚拟性: 能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

虚拟性以多次性和对换性为基础; 多次性和对换性又必须建立在离散分配的基础上。

4.6 请求分页存储管理方式

4.6.1请求分页中的硬件支持

4.6.1.1请求页表机制

逻辑地址 -> 物理地址

状态位P：指示该页是否已调入内存
访问字段A：记录本页在一段时间内被访问的次数
修改位M：该页在调入内存后是否被修改过
外存地址：该页在外存中的位置，通常是物理块号

4.6.1.2缺页中断机制

请求分页系统中，若要访问的页面不在内存，便产生一缺页中断，请求OS将缺页调入内存。

与一般的中断操作有两个方面不同：

缺页中断是指令执行期间产生和处理中断信号

一条指令在执行期间可能产生多次缺页中断

4.6.1.3地址变换机构

4.6.2内存分配策略和分配算法

最小物理块数的确定

是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。

进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。
物理块的分配策略

在请求分页系统中，可采取两种分配策略——固定和可变分配策略（给每个进程分配的物理块数量是否可变）。

在进行置换时，也可采取两种策略——全局置换和局部置换（每次发现缺页是只换入换出一页（局部）还是一块（全局））。

于是可组合成以下三种策略：

（1）固定分配局部置换策略：物理块数量难以确定

（2）可变分配全局置换策略：易实现，可能导致缺页率增加

（3）可变分配局部置换策略
物理块的分配算法
1. 平均分配算法：可供分配的物理块平均分给每个进程
2. 按比例分配算法：按进程大小比例分配
3. 考虑优先权的分配算法：给优先级高的进程分配更多物理块

4.6.3调页策略

4.7 *页面置换算法

设作业执行中访问页面的总次数为A，其中有F次访问的页面尚未装入主存，故产生了F次缺页中断。现定义缺页中断率 f 为：

$$ f=\frac{F}{A} $$

4.7.1最佳置换算法和先进先出置换算法

最佳置换算法OPT

算法无法实现，但可评价其他算法。

选择的被置换的页面，将是永不使用的页面，或最长时间不使用的页面

优点：可保证最低的缺页率
缺点：不可能真正实现（由于人们无法预知哪个页面在未来最长时间不被访问）

例-设作业分配3个物理块，开始3页不算缺页(后面算法同)：发生了6次页面置换

先进先出置换算法FIFO

选择最先进入内存的页面，即选择在内存中驻留时间最长的页面予以淘汰

优点：算法简单
缺点：性能不佳

例-设作业分配3个物理块，开始3页算缺页(后面算法同)：发生了15次页面置换（开始三页算入了缺页）

Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。

4.7.2最近最久未使用(LRU)算法

选择最近最久未被使用的页面淘汰

优点：性能较好
缺点：需要较多的硬件支持（栈、寄存器）

例-设作业分配3个物理块，开始3页不算缺页(后面算法同)：发生了9次页面置换

移位寄存器

⑴ 采用移位寄存器记录每页的使用情况

⑵ 数据格式：R=Rn-1Rn-2…R2R1R0

⑶ 页面被访问一次，最高位Rn-1置1，每隔一定时间，寄存器右移一位

⑷ R值最小的页面，是将被调出的页面

2和3的R7为1，说明刚刚被访问过。

本样例中，第3个内存页的R值最小，故缺页置换选择它。
栈（后进先出）

⑴ 采用特殊的栈来保存当前使用的各个页面的页面号

⑵ 栈顶保留的是最新被访问的页

⑶ 栈底保留的是最久未被访问的页

4.7.3Clock置换算法NRU

4.7.3.1简单Clock算法

you'jia'p最近未使用算法NRU

LRU算法性能较好，但需要较多硬件支持，故一般使用LRU近似算法，如NRC。

有访问位A，无修改位M

第一轮找A=0,M=0，找过的更改，若没有则进入第二轮

第二轮找A=0,M=1，找过的更改，若没有则进入第三轮

第三轮重复第一轮，失败后进入第四轮

第四轮重复第二轮，此时一定能找到

4.7.3.2改进Clock算法

有访问位A，有修改位M

4.7.4其它置换算法

最少使用置换算法LFU

核心：该算法选择使用次数最小的页面淘汰。

与LRU的区别:

R1-10000000

R2-01110100

LRU-淘汰R2

LFU-淘汰R1

4.7.5综合例子：

4.8 请求分段存储管理方式

4.8.1请求分段段表机制

存取方式:用于标识本分段的存取属性。访问字段A:用于记录本段被访问的频繁程度。修改位M:表示该段在调入内存后是否被修改过。存在位P:指示该段是否已调入内存。增补位:用于表示该段在运行中是否做过动态增长外存地址:用于指出该段在外存上的起始地址(盘块号)。

4.8.2缺段中断机制

缺段中断机制与请求分页的区别：缺段中断同样需要在一条指令的执行期间，产生和处理中断，以及在一条指令执行期间，可能产生多次缺段中断。但不会出现一条指令被分割在两个分段中或一组信息被分割在两个分段中的情况。

4.8.3地址变换机构

请求分段系统中的地址变换机构，是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存，因而在地址变换时，若发现要访问的段不在内存，必须先将所缺的段调入内存并修改段表，然后才能利用段表进行地址变换。在地址变换机构中需增加缺段中断的处理及请求等功能。

4.8.4信息共享

分段比分页的优势就在共享。

4.8.4.1共享段表

为了实现分段共享，设置一个数据结构——共享段表，以及对共享段进行操作的过程。

共享进程计数器count：记录有多少个进程需要共享该分段，设置一个整型变量count。
存取控制字段：设定存取权限。
段号：对于一个共享段，不同的进程可以各用不同的段号去共享该段。

4.8.4.2共享段的分配与回收

省略

count+-1

4.8.4.3分段保护

参考请求分页与请求分段管理方式

[操作系统]存储器管理-虚拟存储器