虚拟内存

容量怎么算

最大容量看地址位数；实际容量取两者较小值：min(内存 + 外存, 2^地址位数)

例：32 位地址（2³² B = 4 GB），内存 512 MB，外存可用 2 GB。

• 最大容量 = 4 GB（地址只能编这么多）
• 实际容量 = min(0.5 + 2, 4) = 2.5 GB

如果外存换成 8 GB，实际容量就是 min(8.5, 4) = 4 GB：外存再大，地址也编不出来。

为什么只能基于离散分配

连续分配要求进程在内存里占一整段。只装一部分、按需调入，意味着每次调进来的页落在哪个空闲块都不确定，必须靠页表逐页记录位置。

所以虚拟内存的三种实现方式都是离散的：请求分页、请求分段、请求段页式。

“虚拟性”靠多次性和对换性实现，而这两者又都建立在离散分配上。

缺页中断属于哪一类

内中断（异常）里的故障（fault）。它由当前指令访问了不在内存的页引起，和外设无关；而且是可以修复的错误，修好了这条指令就能正常执行。

• 故障：返回后重新执行引起异常的那条指令（缺页就是这种）
• 陷入（trap，系统调用）：返回后执行下一条指令
• 终止：不可恢复，不再返回

和一般中断的两点不同

• 在指令执行期间产生和处理。一般中断是一条指令执行完后才检查；缺页发生在取指令或取操作数的半路上，不处理这条指令就进行不下去。
• 一条指令可能多次缺页。例如一条跨两页的指令，把一个跨两页的数据块 A 复制到同样跨两页的 B，最多可能缺页 6 次。

OPT 最佳置换

淘汰以后永远不用、或者最长时间内不再被访问的页

特点缺页率最低，是所有算法的上限

代价无法实现：OS 不可能预知进程以后的访问序列。只用来当标准，评价其他算法

FIFO 先进先出

淘汰最早进入内存的页（队列头）

特点实现最简单，一个队列就够

代价进来得早不代表用得少，常用的页（如主循环所在页）也会被换出，性能差；会出现 Belady 异常：分配的物理块增加，缺页次数反而增加

LRU 最近最久未使用

淘汰过去最长时间没被访问的页

特点用“过去”估计“未来”（时间局部性），性能最接近 OPT；属于栈式算法，不会出现 Belady 异常

代价每次访问都要更新使用时间，需要寄存器和栈等硬件支持，开销大

CLOCK 时钟（NRU 最近未用）

淘汰访问位 A = 0 的页

做法内存中的页连成循环队列，指针依次扫描：A = 1 就清 0、跳过（给第二次机会），A = 0 就换出。新页装入时 A = 1，指针指向下一块。

轮数第一轮可能把所有 A 都清成 0，第二轮一定找到，最多两轮

什么时候调入

• 预调页：根据空间局部性，一次调入若干相邻的页。预测不一定准（成功率约 50%），主要用于进程首次调入，由程序员指出先调哪些页。
• 请求调页：运行中发现缺页才调入，每次只调一页。调入的一定会被用到，但每次都要一次 I/O，开销大。

从哪儿调入

外存分两块：对换区连续分配，读写快；文件区离散分配，读写慢。

1. 对换区空间足够：运行前把进程相关文件从文件区复制到对换区，以后全部从对换区调入。
2. 对换区空间不够：不会被修改的页直接从文件区调入，换出时也不用写回；可能被修改的页，换出时写到对换区，以后从对换区调回。
3. UNIX 方式：没运行过的页从文件区调入；运行过又被换出的页放在对换区，下次从对换区调入。共享页如果已被别的进程调入，就不用再调。

抖动（颠簸）

现象刚换出的页马上又要访问，只好再换入；刚换入的页又被换出。进程大部分时间花在换页上，CPU 利用率骤降。

根本原因分配给进程的物理块不够：它频繁访问的页面数高于可用的物理块数。置换算法选得不好也会加剧。

怎么办给进程更多块（让驻留集 ≥ 工作集）；块不够时降低多道程序度，挂起（换出）部分进程，把腾出的块分给其余进程。

工作集

定义在某段时间间隔（窗口 Δ）里，进程实际访问过的页面集合，记作 W(t, Δ)。

大小工作集大小 ≤ Δ，局部性越好，工作集越小（重复访问同几页）。

分配的物理块数（驻留集）不能小于工作集大小，否则就会频繁缺页，走向抖动。也可以用它选淘汰页：优先换出不在工作集里的页。