考研笔记

虚拟存储器性能影响因素

本章最后一节把前面各处的性能结论收拢起来，回答一个总问题：虚拟存储到底慢在哪儿，怎么让它快一点。

核心只有一句话：缺页一次的代价是访存一次的百万倍量级，所以一切优化都围绕”少缺页”展开。

机制

缺页的代价有多大

先把数量级摆出来，后面所有结论都由它导出：

操作典型耗时相对倍数
访问一次内存约 100 ns1
处理一次缺页（机械硬盘）约 8 ms约 倍

这个悬殊的差距意味着：即使缺页率极低，它也会主导整体性能。

用有效访问时间（EAT）来量化。设访存时间为 、缺页处理时间为 、缺页率为 ：代入 、：

  • 时：EAT = 100 ns
  • 时：EAT 8100 ns

仅仅千分之一的缺页率，就让平均访存时间变成了 81 倍。

结论：要让虚拟存储的性能可接受，缺页率必须低到 量级。 而这之所以可能，全靠局部性原理。

四个影响因素

① 页面大小

这是一个双向权衡，两头都不能走极端：

页面太大页面太小
内部碎片大（每进程平均浪费半页）内部碎片小
页表项少，页表小页表项剧增，页表本身太大
一次调入的内容多，可能调入大量用不到的部分缺页次数增多，I/O 次数上升

现代系统通常取 4KB，正是这个权衡的经验解。

② 分配给进程的页框数（驻留集大小）

页框越多，缺页率越低——但如 3.2.3 所述，这个关系不是线性的，而且存在明显的收益递减：

当驻留集达到进程的工作集大小之后，再增加页框，缺页率的下降就非常有限了——因为当前活跃的页已经全在内存里了。

所以最优点就在工作集附近：低于它会抖动，高于它是浪费（挤占了其他进程的页框，降低多道程序度）。

③ 页置换算法

好的算法能显著降低缺页率。性能排序见 3.2.4：但要注意算法的选择空间是有限的——OPT 不可实现，精确 LRU 代价太高，所以工程上基本都在 Clock 系列里做文章。相比之下，把驻留集调到工作集大小的收益往往更大。

④ 程序自身的编制方法

这一条最容易被忽略，但效果可能最显著——因为它直接影响局部性的好坏。

经典例子是二维数组的遍历顺序。设页面大小 4KB，数组 int A[1024][1024]，按行存储（C 语言的方式），则每一行 1024 个 int 恰好 4KB，正好占一页。

按行遍历（正确写法）：

for (i = 0; i < 1024; i++)
    for (j = 0; j < 1024; j++)
        A[i][j] = 0;

每访问完一整行（一页）才换下一页 → 总共 1024 次缺页。

按列遍历（灾难写法）：

for (j = 0; j < 1024; j++)
    for (i = 0; i < 1024; i++)
        A[i][j] = 0;

A[0][j]、A[1][j]、A[2][j]…… 每一个都在不同的页上！ 若驻留集小于 1024 页，则每访问一个元素就缺一次页 → 总共 1024 × 1024 ≈ 100 万次缺页。

同样的功能，仅仅交换了两层循环，缺页次数相差 1024 倍。

这个例子是本节最值得记住的东西：它说明局部性不是操作系统单方面的事，程序员的写法直接决定了局部性的好坏。同样的道理也适用于 Cache——这两处的优化方向完全一致。

边界

缺页率与 TLB 缺失是两回事

两者都会拖慢访存，但代价差了好几个数量级，绝不能混为一谈：

TLB 缺失缺页
意味着映射关系不在 TLB，但页在内存页根本不在内存
后果多访存 次（查页表）一次磁盘 I/O
量级百纳秒级毫秒级（约 倍）
是否产生中断否，硬件自行处理是，缺页中断

判据：存在位 P 是分界线。 P = 1 但 TLB 里没有 → TLB 缺失；P = 0 → 缺页。

一次访存最坏的情况是”TLB 缺失 + 缺页”同时发生，但即便如此，主导耗时的仍然是那次磁盘 I/O。

页面大小的权衡是双向的

考题喜欢问”增大页面大小会怎样”，必须两边都答：

  • 好处：页表项减少 → 页表变小；一次 I/O 传输更多数据，磁盘效率更高
  • 坏处：内部碎片增大；可能调入大量根本不会用到的内容

任何一边单独说都是不完整的。

增加页框数的收益会递减

“多给页框总是好的”这个直觉在超过工作集之后就失效了。

而且从系统整体看还可能是负面的——多给一个进程页框，就意味着其他进程少拿页框、或者内存中容纳的进程数减少，多道程序度下降，CPU 利用率可能反而降低。

这与 3.2.3 的”局部最优 vs 全局最优”是同一件事。

程序编制方法的影响可能大于算法选择

这是本节最有价值的一条认识。

换一个置换算法，缺页率的改善通常是百分之几十的量级；而把嵌套循环的顺序改对，缺页次数可以差上千倍。

操作系统能做的优化有天花板，程序的局部性才是根本。 这也解释了为什么性能优化的第一步往往是改代码，而不是调系统参数。

对照速查

有效访问时间
访存时间，约 100 ns
缺页处理时间，约 8 ms（ 倍）
结论缺页率须低至 量级，性能才可接受
影响因素方向
页面大小双向权衡：大则内碎片大、页表小；小则反之
驻留集大小越大缺页越少，但收益递减，最优点在工作集附近
置换算法OPT > LRU > CLOCK > FIFO，但选择空间有限
程序编制方法影响最大：按行 vs 按列遍历可差 1024 倍
TLB 缺失缺页
页在不在内存在不在
代价多访存几次一次磁盘 I/O
判据P=1 但 TLB 无P=0

考点

  • EAT 公式及”缺页代价约为访存的 倍”这一数量级
  • 页面大小的双向权衡，两边都要答
  • 驻留集增大的收益递减，最优点在工作集附近
  • 程序编制方法对局部性的影响可能大于算法选择（按行/按列遍历的经典例子）
  • TLB 缺失与缺页的区别：判据是存在位 P

链接

反向链接