1. 背景
之前的内存管理方法需要进程在执行之前将整个进程放在内存中。虚拟内存技术允许执行进程不必完全在内存中。这使得程序可以大于内存的大小。
特点
① 将逻辑内存和物理内存分开
② 允许文件或内存通过共享页为多个进程共享
（1）虚拟地址空间
进程如何在内存中存放的逻辑视图
（起始仔细看看，它很像进程的PCB）
理解：
① 栈堆之间的空白空间为虚拟地址的一部分，只有栈和堆生长时，才需要实际的物理页。
② 稀地址空间：包含空白的虚拟地址空间
（2）共享页
① 通过将共享对象映射到虚拟地址空间，系统库可为多个进程共享。库按照只读的方式链接每个进程。
② 虚拟内存允许进程共享内存。允许进程创建内存区域，用于进程间共享
③ 允许系统调用for()创建进程进行期间的共享页
问题：为什么使用虚拟内存，它的优点是什么？
① 程序大小不受内存的限制： 进程不必完全装入内存
② CPU利用率提高： 每个程序占用的物理内存减少，更多的进程可以同时进行
③ 运行速度加快： 载入或交换程序到内存的I/O次数减少
③ 允许文件或内存通过共享页为两个或多个进程共享
2. 按需调页
定义
对于按需调用虚拟内存，只有程序执行需要时才载入页，那些从未访问的页不会调入物理内存。
按需调页系统
① 进程驻留在第二级存储器上（通常是磁盘）
② 当需要执行进程时，使用懒惰交换。将进程执行需要页调入内存
纯粹按需调页
所有的页都不在内存中，就开始执行进程。会不断出现页错误直到所有的页均在内存中。
问题：交换程序与调页程序的区别
① 交换程序是对整个进程进行操作
② 调页程序是对单个页进行操作。
2.1 基本概念
调页程序不是调入整个进程，而是把那些必须的页调入内存。
（1）调页程序的优点
① 减少了交换时间
② 减少了所需的物理内存空间
当换入进程时，调页程序推测在该进程再次换出之前会用到那些页。因此需要一定形式的硬件支持来区分哪些页在内存里，哪些页在磁盘中。
（2）有效位-无效位
在页表中同时存储有效/无效位。
有效：相关页有效且在内存中
无效：相关页无效（不在进程的逻辑空间内）、页有效但在磁盘上
页错误陷阱：当进程需要执行和访问不在内存中的页时（分页硬件发现页设置为无效），会产生页错误陷阱，陷入操作系统。
当进程执行和访问驻留在内存中的页时，执行会正常进行。对标记无效的访问会产生“页错误陷阱(page-fault trap)”，陷入操作系统。
问题：如何处理页错误？
（3）处理页错误的步骤
①访问：进程执行和访问未装入内存的页时，分页硬件发现已设置了无效位，产生页错误陷阱。
②捕获页错误：产生中断，陷入操作系统，检查内部页表引用是否合法。若引用非法则终止进程，否则需要调入页面。
③装入失效页：找到一个空闲帧，调度一个磁盘操作，以便将所需的页调入刚分配的帧。
④重置页表
⑤重启因陷阱而中断的指令：这种重复的工作不会很多（小于一个完整指令）
问题：从局部性的角度说明按需调用的合理性
背景： 单个指令可能访问多个页的内存，从而一个指令可能产生多个页错误。这会产生无法接收的系统性能。
分析： 这种情况是极为少见的。
① 局部模型说明，进程执行时是从一个局部移向另一个局部。局部是一个经常使用页的集合。
② 在同一局部内，进程只会在所需页均装入内存之前发生页错误。
2.2 按需调页的性能
（1）有效内存访问时间
对于绝大数计算机系统而言，内存访问时间（ma）的范围为 10~200ns.
有
效
访
问
时
间
=
(
1
−
p
)
×
m
a
+
p
×
页
错
误
时
间
有效访问时间 = (1-p)\times ma+p\times 页错误时间
有效访问时间=(1−p)×ma+p×页错误时间
其中，p为页错误的概率。
（2）页错误时间
主要有三部分组成：①处理页错误中断、②读入页、③重新启动进程。
问题：有效内存访问时间的计算方法
举例
设平均页错误处理时间为8ms，内存访问时间为200ns，则有效内存访问时间为
=
(
1
−
p
)
×
200
+
p
×
8000000
=
200
+
7999800
×
p
=(1-p) \times 200 + p \times 8 000 000 \\ =200+7999800 \times p
=(1−p)×200+p×8000000=200+7999800×p
① 当每1000次访问有一个页错误时，有效访问时间为
8200
n
s
=
8.2
μ
s
8200ns=8.2 \mu s
8200ns=8.2μs
② 如需要性能减低不超过10%，那么需要：
200
(
1
+
0.1
)
≥
200
+
7999800
×
p
p
<
0.0000025
200(1+0.1) \geq 200+7999800 \times p \\ p < 0.0000025
200(1+0.1)≥200+7999800×pp<0.0000025
对于按需调用，降低页错误率非常重要。否则，有效访问时间会增加，会显著降低进程的执行速度。
3. 写时复制
背景
采用系统调用fork()创建的进程的开始阶段不需要按需调页。fork()将子进程创建为父进程的复制品，但对父进程地址空间的赋值可能没有必要。
（1）写时复制
允许子进程和父进程开始时共享同一页面。如果任何一个进程需要对页进行写操作，那么就创建一个共享页的副本。
过程
进程1试图修改页C，操作系统将C识别为写时复制页并为其创建一个副本。将副本映射到进程1的地址空间内修改。
注意
只有可能修改的页才标记为写时复制页。所有非修改页为父进程和子进程共享。
（2）按需填零
操作系统从空闲缓冲池为写时复制提供空闲页。采用按需填零在分配之前先填零清除以前的内容。
4. 页面置换
（1）缺页
定义
操作系统将页从磁盘调度到内存时，发现空闲帧列表上没有空闲帧，所有内存都被使用。
产生原因
过度分配
解决方案
① 终止用户进程
② 交换出一个进程，并释放其所有帧
③ 页面置换
4.1 基本页置换
（1）步骤
①查找空闲帧：如果找到空闲帧，就是用它。否则使用置换算法选择一个牺牲帧。
②换出牺牲页，改变页表和帧表：将牺牲页写入磁盘
③换入所需页，改变页表和帧表：将所需页载入内存
④重启用户进程
如果没有空闲帧，那么需要采用两个页传输。这种情况把页错误处理时间加倍了，也增加了有效访问时间。
（2）修改位或脏位
定义
每页或帧有一个修改位，通过硬件与之相连。当页内的任何字或字节被写入时，硬件就会设置该页修改位表示该页已修改。
优化方案
如果某页被选作替换页时，当：
①修改位已被设置：换出此页（把此页写到磁盘上），再换入新页。
②修改位未被设置：直接换入新页（磁盘、内存保存着相同内容，无需磁盘备份）
此方案可显著降低处理页错误所需要的时间。当页没有被修改时，可以降低一半I/O时间。
（3）选择置换算法
通常采用最小错误率的算法
页错误数量
页错误数量与引用串和可用帧数相关。
可用帧数量
随着可用帧数的增加，页错误数量会相应减少，直到降低到最小值（页数量）。即每个页首次引用都会产生一个页错误。
问题：可用帧数越多，页错误数量越少吗？
理解： 随着可用帧数的增加，页错误数量会相应减少，直到降低到最小值（页数量）。因为每个页至少产生一次页错误。
4.2 FIFO页置换
（1）思路
为每个页记录该页调入内存的时间（向前看）。当必须置换一页时，选择最旧的页作为替换页。
求页错误数量
创建FIFO队列管理所有页。队列中首页被置换，新页加入队列尾部。
上图中，总共有15次页错误。
（2）优缺点
优点：
最简单的页置换算法
缺点：
性能不稳定，且有Belady异常（所替换页可能是以前初始化并且不断使用的常用变量）
（3）Belady异常
页的错误率随着可用帧数量的增加而增加
4.3 最优置换（OPT）
（1）思路
OPT会置换最长时间不会使用的页（向后看）。
理解：
最长不会使用的页 = 最迟引用的页
（2）优缺点
优点
产生页错误率最低，且绝没有Belady异常的问题。
缺点
难以实现，需要引用串的未来知识。
4.4 LRU页置换
（1）思路
使用离过去最近作为不远将来的近似。置换最长时间没有使用的页（向后看）
理解
是对OPT的近似，都属于栈算法
（2）优缺点
优点
最常用的置换算法，页错误率低，且绝没有Belady异常的问题。
缺点
如果没有硬件支持，内存引用很慢。
①LRU和OPT都需要特殊硬件的支持，但很少有计算机系统能支持LRU页置换。
②如果没有硬件支持，每个内存引用都必须更新时钟域或栈，会使内存引用慢至少10倍
（3）实现方案
①计数器：为每个页表项关联一个使用时间域。置换具有最小时间的页。
②栈：每引用一个页，将该页从栈中删除并放在顶部。这样栈顶是最近使用的页，栈底总时LRU页。
4.5 近似LRU页置换
（1）思路
通过检查引用位，确定那些页使用过而那些页未被使用过。
引用位
页表内的每项都关联着一个引用位。每当引用一个页时，相应的引用位就会被硬件置位。
附加引用位算法
思想
在规定时间间隔内记录引用位，获得额外顺序
实现
1）为内存中每个页保留8位字节
2）时钟定时器产生中断，操作系统将每个页的引用位移到这8位的最高位，并将其他位右移一位。
3）将这8位数字作为无符号整数，具有最小值的页就是LRU页
二次机会算法（简单时钟算法）
思想
当要选择一页时，先检查其引用位。当引用位为1时，给它第二次机会，并将其引用位置0.
实现
采用循环队列。指针向前移动直到找到引用位不为0的页作为牺牲页。在向前移动时，将清除引用位。
增强型二次机会算法（改进型时钟算法）
四种类型
将引用位和修改位作为一对有序对（引用位，修改位）考虑。
（0，0）：最近没有修改也没有使用——最佳置换页
（0，1）：最近没有使用但修改的页——置换前需要写出磁盘
（1，0）：最近使用但没修改过的页——很快会被使用
（1，1）：最近使用且修改过的页——很快就会使用，在置换前需要写出到磁盘
思想
每个类都属于四种类型之一。给修改过的页更高级别，来降低IO数量。
问题：比较增强型二次机会算法与简单时钟算法（二次机会算法）
理解： 增强型二次机会算法给已经修改过的页更高级别，来降低了IO数量。
4.6 基于计数的页置换
硬件基础
为每个页记录其引用次数的计数器
（1）最不常使用页置换算法（LFU）
思想： 置换计数最小的页
问题： 一个页在进程开始时使用很多，但以后很少使用时，仍会具有高引用次数
解决： 定期将计数寄存器右移一位，形成指数衰减。
（2）最常使用页置换算法
问题
实现费时，且不能很好近似OPT置换算法。
4.7 页缓冲算法
可以通过采取具体措施来减少置换时间（写入+写出+磁盘IO）。比如优化牺牲页写出时间与减少磁盘IO。
（1）空闲帧缓冲池
在牺牲帧写出之前，所需要的页就从缓冲池读到内存。牺牲帧在写出后，才加入到空闲帧池。
目的： 允许进程尽可能快的重启
（2）已修改列表
每当调页设备空闲时，选择一个修改页并写到磁盘。
目的： 增加选择置换时干净页的概率而不必写出。
（3）空闲帧池
当帧写到磁盘上内容并没有改变，那么可以直接从空闲帧池中取出来使用。
目的： 减少IO次数
5. 帧分配
解决如何在各个进程之间分配一定的空闲内存。
5.1 帧的最少数量
（1）规则
进程所分配的帧不能超过可用帧数量，也不能低于最少分配数量。
问题：为什么需要分配至少数量的帧？
理解： 随着分配给进程的帧数减少，页错误会增加，从而减慢进程的执行。
（2）大小
帧的最少数量由体系结构决定，最大数量由物理内存的数量来决定。
5.2 分配算法
在n个进程之间分配m个帧
（1）平均分配
思想
给每个进程平均值
m
n
\frac{m}{n}
nm
优缺点
优点：公平性好
缺点：可能造成帧浪费
（2）可使用比例分配
思想
根据进程大小，将可用内存分配给进程。假设进程
p
i
p_i
pi的虚拟内存大小为
s
i
s_i
si
S
=
∑
i
=
1
n
s
i
a
i
=
m
×
s
i
S
S=\sum_{i=1}^{n} s_i \\ a_i = m \times \frac{s_i}{S}
S=i=1∑nsiai=m×Ssi
优缺点
优点：内存的使用率较大（降低了帧浪费）
缺点：公平性差
（3）帧的数量与多道程序级别关系
多道程序程度增加，每个进程分配的帧数减小。
多道程序程度减小，每个进程分配的帧数增加。
5.3 全局置换和局部置换
问题：全局置换和局部置换的定义及其优缺点
（1）定义
全局置换： 允许一个进程从所有帧中选取一个置换帧。
局部置换：进程仅从自己的分配帧中进行选择。
（2）优缺点
（可用帧数量、页错误率）
全局置换
优点：
① 增加了所分配帧的数量
② 提高系统的吞吐量，更为常用
缺点：
① 不能控制页错误率
② 容易产生系统颠簸
局部置换
优点：
① 可以选取页置换算法控制页错误率
② 可以限制系统颠簸
缺点：
进程所分配帧的数量固定。
6. 系统颠簸
（1）颠簸
定义
频繁的页调度行为
原因
覆盖进程局部性所需的帧大于系统分配给进程的帧
6.1 系统颠簸的原因
（1）原因
（CPU利用率低 –> 新进程 –> 更多的页错误和更长的设备队列）
① CPU调度程序发现CPU使用率降低，会增加多道程序的程度。
② 新进程试图从运行进程中拿到帧，会引起更多的页错误，形成更长的调页设备队列。
③ CPU使用率进一步降低，多道程序程度再增加，从而出现系统颠簸
问题：多道程序程度越大，CPU利用率越高吗？
理解： 不是。随着多道程序程度增加，CPU使用率增加直到最大值。然后系统颠簸开始，CPU使用率急速下降。
问题：采用局部置换可以完全解决系统颠簸吗？
理解： 不可以。（平均长度 –> 平均等待时间 –>未颠簸的有效访问时间）
① 采用局部置换能限制系统颠簸（不能使其他进程也颠簸）。如果进程颠簸，其绝大多数时间也会排队等待调页设备。
② 由于调页设备更长的平均队列，页错误的平均等待时间增加，因此对于其他未颠簸进程的有效访问时间也会增加。
6.2 局部性模型
定义
当进程执行时，它从一个局部移向另一个局部。局部是一个经常使用页的集合
特点
进程在新定义的局部内会发生页错误，直到所有页均在内存中。接着不会再出现页错误直到改变局部为止。
页错误率变化
对一个新局部按需调页时，页错误率进入波峰。一旦新局部的工作集合在内存时，页错误率开始下降，
6.3 工作集合模型
工作集合
最近
Δ
\Delta
Δ个引用的页集合。
（1）工作集合的精确度
如果
Δ
\Delta
Δ太小，则不能包含整个局部。如果
Δ
\Delta
Δ太大，则可能包含多个局部。假设每个进程的工作集合为
W
W
S
i
WWS_i
WWSi，则：
D
=
∑
W
S
S
i
D=\sum WSS_i
D=∑WSSi
如果总的需求D大于可用帧数量，有的进程就得不到足够的帧，从而会出现颠簸。
（2）工作集合模型
操作系统跟踪每个进程的工作集合，为进程分配大于其工作集合的帧数。
若还有空闲帧，则可启动另一进程。
如果工作集合之和超过可用帧的总数，那么操作系统会暂停一个进程并释放该进程的页。
（3）工作集合的优缺点
优点：
① CPU使用率提高：防止了颠簸，增加了多道程序的程度。
缺点：
① 跟踪工作集合实现困难
② 控制颠簸不灵活
6.4 页错误频率
思想
为所期望的页错误率设置上限和下限。如果实际错误率超过上限，则为进程分配更多帧，否则移走部分帧。