考研笔记

第 3 章 名词库

这一页是复习主入口。 目标是把第 3 章的名词收全，并把每个词的边界和适用范围钉死。

每条最多四行：是（定义）／不是（划掉最常见的误解）／易混（成对的对手）／范围（该结论在什么条件下才成立）。

建设进度：✅ 3.1 内存管理概念　✅ 3.2 虚拟内存管理　（第 3 章完整；3.2.9 地址翻译留作专题）

3.1.1 内存管理的基本原理和要求

逻辑地址 / 物理地址

  • 是：逻辑地址（相对地址）是用户程序和编译器看到的地址，每个进程都从 0 开始编号；物理地址是内存单元的真实编号，全内存统一编址。
  • 不是：用户程序只能看到逻辑地址，连别人的物理地址是多少都不知道——这正是内存保护得以成立的前提。
  • 易混：两者的转换由硬件的地址变换机构完成，操作系统不逐次介入。

编译 / 链接 / 装入

  • 是：编译产出若干目标模块（各自从 0 编址）；链接把它们和库函数合成一个装入模块（统一编址、解析符号引用）；装入把装入模块放进内存。
  • 不是：链接的产物不是可运行的进程，还需装入这一步。
  • 易混：抓住”若干 → 一个”这个数量变化，就不会把编译和链接的职责搞混。

三种链接方式

  • 是：静态链接（运行前全部链接完）、装入时动态链接（边装入边链接）、运行时动态链接（用到时才链接）。
  • 不是：静态链接使每个可执行文件自带一份库副本，磁盘与内存都浪费，且库升级需重新链接。
  • 易混：运行时动态链接最省内存——不会执行到的分支（错误处理、罕见功能）所需模块永远不必装入。

三种装入方式

  • 是：绝对装入（编译时即产生物理地址）、可重定位装入/静态重定位（装入时一次性改完地址）、动态运行时装入/动态重定位（每次访存时实时转换）。
  • 不是：绝对装入只适用于单道程序环境——多道环境下没人知道自己会被放到哪。
  • 易混：三者的分界点是地址在什么时候被固定：编译时 / 装入时 / 访存时。

静态重定位 vs 动态重定位

  • 是：静态重定位在装入时把相对地址一次性改成绝对地址；动态重定位保留逻辑地址，每次访存由硬件做 逻辑地址 + 重定位寄存器。
  • 不是：静态重定位后程序不能再移动（地址已写死），且要求装入时一次分配全部所需内存。
  • 易混：动态重定位是紧凑、挂起、虚拟存储等一切高级功能的前提。
  • 范围：只有位置永久固定的方案才能用静态重定位——单一连续分配、固定分区可以；可变分区（要紧凑）、分页分段（要查表）都不行。

重定位寄存器 / 地址变换机构

  • 是：重定位寄存器存放程序在内存中的起始物理地址；地址变换机构是执行转换的硬件部件。
  • 不是：动态重定位依赖”可重定位装入程序 + 重定位寄存器 + 地址变换机构”三者，不依赖目标程序——目标程序在链接阶段就被消耗掉了。
  • 易混：“可重定位装入程序在重定位过程中执行”这一说法是错误的。它只在装入那一刻执行一次，职责是装入并设置重定位寄存器；运行期间的转换由硬件完成。

内存保护的两种方法

  • 是：① 上、下限寄存器（检查地址是否落在区间内）② 重定位寄存器 + 界地址寄存器。
  • 不是：方法②的检查顺序不可颠倒——必须先查界地址，后加重定位寄存器。
  • 易混：若先加基址再查界，一个越界的逻辑地址加上基址后可能”恰好”落入别人的合法区域，检查就形同虚设。

可重入程序（纯代码）

  • 是：执行过程中不修改自身的代码，因而多个进程可共享内存中的同一份副本，各自只保存私有数据区。
  • 不是：它不改变对换的速度，而是减少对换的数量——共享使内存占用下降，需被换出的进程随之变少。
  • 易混：这里的”对换”指中级调度把整个进程在内存与外存之间换进换出，不是页面置换。

3.1.2 连续分配管理方式

单一连续分配 / 固定分区分配 / 动态分区分配

  • 是：单一连续分配的用户区只放一道程序；固定分区预先把用户区划成若干固定大小的分区；动态分区在装入作业时按其实际需要临时划出。
  • 不是：固定分区有内部碎片、无外部碎片；动态分区无内部碎片、有外部碎片。
  • 易混：可变分区 = 动态分区，是同一概念的两个名字。
  • 范围：单一连续和固定分区可用静态重定位（位置永久固定）；动态分区因需紧凑而必须用动态重定位。

内部碎片 vs 外部碎片

  • 是：内部碎片是已分配给某进程却用不上的空间（在分区内部）；外部碎片是尚未分配、但太小无法利用的空闲区（在分区之间）。
  • 不是：紧凑只能消除外部碎片，对内部碎片无能为力——后者已属某进程的合法领地，操作系统无权抠出来。
  • 易混：判据是”这块空间是否已归属某个进程”。归属了却用不着 → 内部；没归属却用不上 → 外部。
  • 范围：规律是——按固定大小的块分配就有内部碎片（固定分区、分页、段页式）；按实际需要的大小分配就有外部碎片（动态分区、分段）。

紧凑（拼接）

  • 是：把内存中的作业统统往一端挪，将零散的空闲区合并成一大块，用以消除外部碎片。
  • 不是：必须配合动态重定位——要移动已装入的作业，地址若已写死就无法移动。
  • 易混：这是”固定分区可用静态重定位、可变分区不能”的根本原因。

顺序搜索的四种分配算法

  • 是：首次适应 FF（地址递增，从头找第一个够大的）、邻近适应 NF（从上次位置继续找）、最佳适应 BF（容量递增，取最小够用块）、最坏适应 WF（容量递减，取最大块）。
  • 不是：“最佳适应”实际效果很差——它总是切出尽可能小的剩余部分，产生大量难以利用的外部碎片。名字最谦虚的首次适应综合性能最好。
  • 易混：判据是哪种算法最少破坏大块连续空间。FF 优先消耗低地址端，高地址端的大块得以保留；NF 使消耗均匀分布，反而把所有大块都切碎。

索引搜索 vs 顺序搜索

  • 是：本质区别只有一个——要不要遍历。 顺序搜索只有一条空闲分区链，每次从头扫；索引搜索按大小分类建索引表，直接定位到对应类别的链，取第一块即可。
  • 不是：“索引”不是指某种数据结构的名字，而是指用一张按大小分类的表把线性查找换成直接定位。
  • 易混：三种实现为快速适应算法（按容量分类，每类一条链）、伙伴系统、哈希算法（以容量为键建哈希表）。
  • 范围：索引搜索类算法整块分配、不切割，因此引入了内部碎片——这是为”查得快”付出的代价，与顺序搜索的四种算法（只有外部碎片）不同。

伙伴系统

  • 是：所有分区大小均为 。分配时若无合适块则把大块对半劈开直到得到所需大小；释放时若伙伴也空闲则合并，并继续向上检查。
  • 不是：“伙伴”不只是”大小相同且地址相邻”，还必须由同一个大块一分为二得来。故第 1 块与第 2 块是伙伴，第 2 块与第 3 块不是。
  • 易混：请求 100K、页面档位为 128K 时会拿到 128K，其中 28K 是内部碎片——这是伙伴系统必然的代价。
  • 范围：伙伴算法管理的是”物理页框的连续性”，与”进程离散分配”不在同一层面，两者不冲突。 分页解决的是”进程的逻辑页可散落到任意物理页框”；而内核仍常常需要物理连续的一批页框（DMA 缓冲区、内核数据结构、大页），伙伴算法服务的正是后者。

3.1.3 基本分页存储管理

页 / 页框 / 页表

  • 是：页框是物理内存被等分成的固定大小块；页是进程逻辑地址空间被等分成的块；页表记录页 → 页框的映射，每进程一张。
  • 不是：页和页框大小必须相同——正因如此任意一页才能装进任意一个页框。
  • 易混：页表项通常只存页框号，页号是隐含的（第 个表项对应第 页），不必存储。计算页表大小时要注意这一点。

页表寄存器

  • 是：CPU 中的寄存器，存放页表的始址和页表长度（后者用于越界检查）。
  • 不是：页表本身在内存里，但页表的始址在寄存器里。 若连”页表在哪”都要查内存，就成了先有鸡还是先有蛋。
  • 易混：进程切换时页表寄存器的内容要作为进程上下文保存恢复，这是进程切换昂贵的原因之一。

地址变换机构

  • 是：完成”逻辑地址 → 物理地址”转换的硬件部件（MMU）。
  • 不是：不是由操作系统的软件完成的。 每次访存都要转换一次，若靠软件则开销高到无法接受。
  • 易混：页内偏移原样照抄，不参与计算——页与页框等大，某字节在页内是第几个，在页框内也是第几个。只有页号需要被翻译。

快表（TLB）

  • 是：由相联存储器实现的高速缓存，存放最近用过的页表项，可并行比较所有表项。
  • 不是：TLB 缓存的是”页号 → 页框号”的完整映射，不是各级页表的中间项。 因此不存在”只命中某一级”，命中率也不需要按级数相乘。
  • 易混：命中则整条查表路径被跳过（1 次访存）；未命中则需 次查表 + 1 次取数。
  • 范围：TLB 有效的前提是程序访问的局部性原理，命中率通常在 90% 以上。级数越多，TLB 的价值越大。

多级页表

  • 是：把页表本身也分页，用上一级页表索引下一级，从而页表不必连续存放，且只需装入用到的部分。
  • 不是：代价是访存次数增加—— 级页表需 次查表 + 1 次取数。
  • 范围：设计目标是让每一级页表恰好装进一个页面。因此”一个页面能装多少个页表项”就决定了每级能消化多少位页号，级数 = ⌈页号总位数 ÷ 每级位数⌉，必须向上取整。

平均访存次数

  • 是： 级页表、TLB 命中率 时，平均访存次数 。
  • 不是：命中路径不查任何一级页表，只需 1 次访存取数据。
  • 易混：结果必然落在 区间内，可用于自检。

分页的碎片

  • 是：有内部碎片（最后一页装不满，平均浪费半页），无外部碎片。
  • 不是：外部碎片消失是因为任何空闲页框都能被使用，不存在”太小以致用不上”的空闲块。
  • 易混：由此得出页面大小的权衡——太大则内部碎片大，太小则页表项剧增、页表本身太大。

3.1.4 基本分段存储管理

段 / 段表

  • 是：段按用户的逻辑功能划分（主程序段、子程序段、数据段），每段有名字、从 0 编址、段长由实际内容决定因而可变。段表项含段长和基址。
  • 不是：段表项比页表项多一个”段长”字段——页长固定不必记录，段长各异且要用于越界检查。
  • 易混：命题”按程序中实际的段来分配主存，所以分配后的存储块是可变长的”是正确的。

分段的地址变换

  • 是：两次越界检查（段号 vs 段表长度；段内偏移 vs 段长），物理地址 = 基址 + 段内偏移。
  • 不是：分段是”加”出来的，分页是”拼”出来的。 段长可变，段内偏移无法通过位截断得到。
  • 易混：分页只需一次越界检查——页内偏移位数固定，天然不会超出页面大小。

一维地址空间 vs 二维地址空间

  • 是：分页是一维——程序员只给一个地址，硬件自动按位截断成页号+偏移；分段是二维——必须显式给出段号和段内地址两个信息。
  • 不是：段页式仍是二维，不是三维。页号和页内偏移是系统从”段内地址”里自动截出来的，对用户不可见。
  • 易混：判据是”用户需要显式给出几个数”。根源仍是长度是否固定——固定长度才能靠位截断自动拆分。

分段的共享与保护

  • 是：因为一个段是逻辑上完整的单位，共享和保护可以以段为粒度进行；被共享的段必须是可重入代码。
  • 不是：分页不便于共享保护——一个逻辑单元可能横跨若干页，而一页里又可能混着两个逻辑单元的内容。
  • 易混：这是分段被发明出来的根本理由。

3.1.5 段页式存储管理

段页式

  • 是：先按逻辑分段，再把每个段分页。地址结构为 段号 ‖ 页号 ‖ 页内偏移，其中后两段合起来才是原来的”段内地址”。
  • 不是：“段可变长”与”按固定页框分配”不矛盾。 段的可变长体现为占用的页数不同，而不是页的大小不同——10KB 的段占 3 页、4KB 的段占 1 页，但每页都是 4KB。
  • 易混：一张段表 + 每段一张页表。段表项存的是该段页表的始址和长度，不是段的基址。
  • 范围：访存 3 次（段表、页表、数据），因此 TLB 几乎必需。越界检查两次，但第二次查的是页号 vs 该段页表长度，页内偏移不必检查。

三种方式的碎片对照

  • 是：分页——有内部、无外部；分段——无内部、有外部；段页式——有内部、无外部。
  • 不是：段页式的内部碎片通常多于纯分页——纯分页是整个进程浪费半页，段页式是每个段各浪费半页，段越多浪费越多。
  • 易混：段页式继承了分页的碎片形态，因为物理分配是按页框进行的。

3.2 虚拟内存管理

一次性 / 驻留性

  • 是：传统存储管理的两个特征——作业必须一次性全部装入内存；装入后一直驻留至运行结束。
  • 不是：这不是优点，恰恰是虚拟存储要否定的两个前提。它们导致大作业装不下、多道程序度上不去。
  • 易混：虚拟存储用多次性否定一次性，用对换性否定驻留性。

局部性原理

  • 是：时间局部性（刚访问过的不久还会访问，源于循环）；空间局部性（访问了某处，附近也快被访问，源于顺序执行与数组）。
  • 不是：它不是定理而是统计规律，正因如此虚拟存储只是”通常很快”，而非”保证很快”。
  • 易混：它同时是 TLB、Cache、虚拟存储三者能够有效的共同基础——都在赌”刚用过的马上还会用”。

虚拟存储器的三个特征

  • 是：多次性（分多次调入）、对换性（可换进换出）、虚拟性（逻辑上扩充容量）。
  • 不是：最重要的是多次性，不是虚拟性——虚拟性是结果，多次性才是那个区别于传统方式的做法。
  • 范围：虚拟存储只能基于非连续分配技术。 连续分配要求作业占一整块连续空间，与”只装一部分、随时换进换出”在逻辑上冲突。

虚拟存储器的容量限制

  • 是：受两个因素中的较小者限制——① CPU 的寻址范围（地址位数决定）② 内存容量 + 外存容量。
  • 不是：不是”只受外存限制”，也不是”只受内存限制”。 前者忽略了寻址范围（32 位系统再大的硬盘也超不过 4GB）；后者则完全否定了虚拟存储的意义。
  • 易混：容量地址位数内存外存。

请求页表的四个新增字段

  • 是：存在位 P（是否在内存）、访问位 A（近期是否被访问）、修改位 M（是否被修改）、外存地址。
  • 不是：P 管”在不在”，A 和 M 管”该淘汰谁”，外存地址管”去哪儿取”，四者各司其职。
  • 易混：只有 M = 1 的页被淘汰时才需写回外存，M = 0 直接丢弃。修改位把”必须写回”变成了”可能不必写回”。

缺页中断

  • 是：访问某页时发现存在位 P = 0 而产生的中断。属于内中断中的”故障（fault）”。
  • 不是：不是外中断。 它在指令执行期间由当前指令本身引起，而外中断由外部设备发出、在一条指令执行完之后才被检测。
  • 易混：处理完毕后要”重新执行”被中断的那条指令，而不是执行下一条——因为那条指令根本没执行成功。这是”故障”类异常的共同特征。
  • 范围：一条指令可能引发多次缺页中断（指令跨页存放、操作数又在别的页上，最多 4 次），与”一条指令一次中断”没有必然联系。

请求调页 / 预调页

  • 是：请求调页在缺页时才调入；预调页提前批量调入，依据是空间局部性。
  • 不是：预调页主要用于进程的首次调入——此时无访问历史可供预测，只能靠程序员或编译器给出提示。
  • 范围：实际系统中程序员给的是建议而非指定（madvise(MADV_WILLNEED)、posix_fadvise、mmap 的 MAP_POPULATE），且按地址区间给，不按页号点名。真正起主要作用的是内核的自动预取。

文件区 / 对换区

  • 是：外存分为存放文件的文件区（离散分配）和存放对换页面的对换区（连续分配）。对换区的 I/O 速度更快。
  • 不是：三种调入情形不必死记——能放对换区就放（因为快），放不下才做取舍。
  • 易混：判据是——只读的东西可以留在文件区（反正不用写回），会改的东西必须进对换区（因为要写回，而对换区快）。
  • 范围：UNIX 方式（第三种）就是现代 Linux 的做法，且演化为按页的来源分类：文件映射页（有文件作后盾，干净页直接丢弃，不占 swap）与匿名页（无后盾，只能换出到 swap）。

驻留集

  • 是：给进程分配的物理页框的集合。
  • 不是：太小则缺页频繁乃至抖动；太大则内存容纳的进程数减少，多道程序度下降，系统吞吐量反而降低。
  • 易混：↔ 工作集。驻留集是”实际给的量”（供给），工作集是”够用的标准”（需求）。

分配策略 vs 置换策略

  • 是：两个正交的维度。分配策略（固定/可变）问”驻留集大小变不变”；置换策略（局部/全局）问”淘汰对象从哪个集合里选”。
  • 不是：“固定分配 + 全局置换”这个组合不存在——全局置换会抢占别人的页框，必然改变双方的驻留集大小，与”固定”的定义直接矛盾。
  • 易混：三种可行组合中，可变分配局部置换最合理（按缺页率主动调控），可变分配全局置换盲目（先到先得，被抢者无辜）。

抖动（颠簸）

  • 是：进程频繁缺页，绝大部分时间花在调页上，CPU 利用率不升反降。直接原因是分到的页框太少。
  • 不是：不是”缺页率高”的同义词。 程序冷启动时缺页率也很高，但那是正常的。抖动的特征是形成正反馈、系统无法自行恢复。
  • 易混：↔ 死锁。抖动状态下进程一直在动（不停调页），只是几无有效进展；死锁则彻底不动。
  • 范围：有效措施只有两类——① 挂起/撤销部分进程 ② 增加物理内存。无效措施：增大对换区容量（瓶颈是速度不是容量）、增加多道程序度（火上浇油）、提高优先级（改的是调度不是内存分配）、换更快 CPU（CPU 本就闲着）。

工作集

  • 是：在时间窗口 内进程实际访问过的页面集合，是局部性原理的量化。
  • 不是：窗口太小则涵盖不全仍会抖动；太大则把不再使用的页也算进来，造成浪费。
  • 易混：唯一用途是——驻留集 ≥ 工作集 ⟹ 不抖动。它把”驻留集该多大”这个模糊问题变成了可测量的问题。

最佳置换算法 OPT

  • 是：淘汰未来最长时间内不再被访问的页面。缺页率最低。
  • 不是：实际系统无法实现（需预知未来），只能作为衡量其他算法优劣的标尺。
  • 易混：手算时只比较内存中那几页的”下一次出现位置”，取最大者淘汰，不必重扫全串。

FIFO 与 Belady 异常

  • 是：FIFO 淘汰最早进入内存的页面。Belady 异常指增加页框数、缺页次数反而增多的反常现象。
  • 不是：只有 FIFO 会出现 Belady 异常，LRU 和 OPT 都不会。
  • 易混：根源是 LRU 和 OPT 属于栈算法——保证页框数为 时的驻留集必然包含 时的驻留集，故缺页只减不增。FIFO 的依据是”进入先后”，与”是否还会被访问”无关，不满足该性质。

LRU 最近最久未使用

  • 是：淘汰最近最久未被访问的页面。是 OPT 的”过去镜像”，实际效果最接近 OPT，无 Belady 异常。
  • 不是：代价高的根源是”每次访存都必须更新使用顺序”——包括命中时也要更新。 这个频率高到只能由硬件承担，故选择题答”需要硬件的特殊支持”。
  • 易混：两种硬件实现——寄存器/计数器（记最后访问时刻，取最小者淘汰）与栈（访问即移到栈顶，栈底即最久未用）。“需要对所有页排序”是表象，LRU 从不执行排序算法。

CLOCK 时钟置换算法

  • 是：LRU 的低成本近似，只用一位访问位 A。扫描时遇 A=0 则淘汰，遇 A=1 则置 0 并后移（给第二次机会）。最多扫描两轮。
  • 不是：它不是另一种思路，而是用一位信息近似”最近有没有用过”，以精度换取实现成本。
  • 易混：硬件在页面被访问时自动置 A=1，这一步是免费的——这正是 Clock 相对 LRU 便宜的原因。

改进型 CLOCK 算法

  • 是：同时看访问位 A 和修改位 M。淘汰优先级 = 把 (A,M) 当作两位二进制数，从小到大：(0,0) → (0,1) → (1,0) → (1,1)。最多扫描四轮。
  • 不是：这个顺序不必硬记。A 为何是高位——因为”价值优先于代价”：A 管”这页还会不会再用”（未来价值），M 管”淘汰要花多少代价”（写不写回）。马上要用的页哪怕零成本也不该淘汰；不会再用的页哪怕要写回也值得淘汰。
  • 范围：四轮扫描为——① 找 (0,0) 不清 A ② 找 (0,1) 并清 A ③ 再找 (0,0) ④ 再找 (0,1)。第 2 轮已把 A 全部清零，故第 3 轮必然能找到。

页面缓冲算法 (PBA)

  • 是：被淘汰的页面不立即扔掉，先挂到链表上。空闲页框链表存干净的被淘汰页（可直接捞回，省”读”）；修改页面链表存脏页（攒够了批量写回，省”写”）。
  • 不是：它不参与”淘汰谁”的决策，只负责善后。与置换算法是配合关系而非替代。
  • 易混：最重要的结论——配合 PBA 后，即使采用 FIFO，性能也能接近 LRU。因为选错了还能捞回来，算法精度就不那么关键了。
  • 范围：被挂入空闲页框链表的页，从进程角度看已不在内存（存在位为 0，仍会触发缺页中断），但物理内容还在，故可直接摘回，把一次磁盘 I/O 降为几条内存指令。

页框回收

  • 是：设上下两个阈值——空闲页框低于下限时唤醒回收进程，高于上限时停止。目的是提前储备一批空闲页框。
  • 不是：与页面置换不是一回事。置换是”缺页且内存满时”被动触发、进程必须阻塞等待；回收是主动的、异步的，进程无感。
  • 易混：一句话——置换是”现用现找”，回收是”提前备货”。
  • 范围：回收对象按代价从低到高——干净的文件映射页（零 I/O，直接丢弃）→ 脏的文件映射页（写回原文件）→ 匿名页（必须写对换区，最贵）。这解释了为什么内存吃紧时最先被丢掉的总是页缓存。

内存映射文件

  • 是：把磁盘文件映射到进程虚拟地址空间，之后像访问内存一样访问它，由缺页机制按需调入。
  • 不是：建立映射时不搬运任何数据，也不占用相应大小的内存——只是在页表里做记号。映射一个远大于物理内存的文件是合法的。
  • 易混：三个好处——省一次内核到用户的拷贝、省掉每次读写的系统调用、天然支持共享（映射同一文件即共享存储）。
  • 范围：修改不立即写回，只在页被置换出去（且 M=1）、解除映射、进程退出或主动同步时才写。

文件映射页 vs 匿名页

  • 是：文件映射页内容来自某个文件（代码、mmap 的文件、页缓存）；匿名页无对应文件（堆、栈）。
  • 不是：文件映射页干净时可直接丢弃、不占 swap；匿名页没有”原本”，只能换出到 swap。
  • 易混：这解释了为什么”已缓存文件很高”不代表内存紧张——页缓存随时可回收。即 Linux 那句”空闲的内存是被浪费的内存”。

有效访问时间 EAT

  • 是：，其中 为缺页率、 为访存时间、 为缺页处理时间。
  • 不是：缺页代价约为访存的 倍（100ns vs 8ms）。仅千分之一的缺页率就能让平均访存时间变成 81 倍。
  • 范围：因此缺页率必须低至 量级性能才可接受，这全靠局部性原理支撑。

TLB 缺失 vs 缺页

  • 是：TLB 缺失指映射关系不在 TLB 但页在内存；缺页指页根本不在内存。
  • 不是：代价相差约 倍——前者只是多访存几次（百纳秒级），后者是一次磁盘 I/O（毫秒级）。且 TLB 缺失不产生中断，由硬件自行处理。
  • 易混：判据是存在位 P。P=1 但 TLB 里没有 → TLB 缺失；P=0 → 缺页。

虚拟存储性能的四个影响因素

  • 是：页面大小（双向权衡）、驻留集大小（收益递减，最优点在工作集附近）、置换算法、程序编制方法。
  • 不是：页面大小的权衡必须两边都答——大则内部碎片大、页表小、I/O 效率高；小则反之。
  • 范围：程序编制方法的影响可能大于算法选择。经典例子：int A[1024][1024] 按行遍历 1024 次缺页，按列遍历约 100 万次缺页，相差 1024 倍。换置换算法通常只改善百分之几十。

附：本章高频”范围限定”清单

结论成立范围
绝对装入可用仅单道程序环境
可用静态重定位仅单一连续、固定分区（位置永久固定）
不需要地址变换机构仅单一连续、固定分区
紧凑能消除碎片仅外部碎片；且必须配合动态重定位
有内部碎片仅按固定大小块分配者：固定分区、分页、段页式、索引搜索类算法
有外部碎片仅按实际大小分配者：动态分区、分段
首次适应最好就”少破坏大块连续空间”这一标准而言
伙伴算法管连续性是物理页框层面，与”进程离散分配”不同层，不冲突
TLB 命中率相乘不成立——TLB 存完整映射，不存在只命中某一级
每级页表装进一页这是多级页表的设计目标，级数计算的唯一依据
地址是二维的分段和段页式都是二维；分页是一维
能实现虚拟存储仅非连续分配：请求分页/分段/段页式
虚拟存储容量受”寻址范围”与”内外存之和”两者较小值限制
淘汰时需写回仅修改位 M=1 时
预调页主要用于进程首次调入
Belady 异常仅 FIFO；LRU、OPT 是栈算法故不会
抖动有效措施仅”挂起进程”与”增加内存”；其余一律无效
增加页框收益超过工作集后收益递减，且损害多道程序度
”固定分配全局置换”不存在——两者定义互相矛盾
干净页可直接丢弃仅文件映射页；匿名页必须写到 swap
FIFO 性能接近 LRU仅在配合页面缓冲算法（PBA）时
页框回收 vs 页面置换前者主动提前备货，后者被动现用现找

链接

反向链接