内存管理校招面试题｜操作系统
内存管理校招面试题｜操作系统
本章先解释程序为什么需要自己的地址空间，再沿着分页、地址转换和缺页处理理解内存如何被使用，最后讨论内存紧张时怎样回收页面。以下地址和容量都是教学假设，不是某台机器的实测数据。
贯穿示例
设页大小为4 KiB，即4096字节。进程A的教学地址空间为16 KiB，包含页0～3：页0映射到物理帧3，页1到帧5，页3到帧1；页0、1可读写，页3只读。页2是文件map.bin的一页合法只读映射，初始未驻留。进程B的页1映射到帧2。
示意物理帧0～7中，0由内核占用，1、3、5属于A，2属于B，4、6空闲，7为其他占用。这只是部分内存，不计算系统全部管理开销。各题从这个初始状态开始；只有明确写出的前后变化才延续。
1. 什么是物理内存？程序直接使用物理地址有什么问题？
物理内存是实际供处理器保存和访问运行中数据的RAM。物理地址用于定位其中的位置；程序的指令、变量和栈最终都需要获得可访问的数据，但程序使用的地址不必直接等于物理地址。
同一个地址为何会产生冲突
先假设两个程序都能直接写物理地址0x5234，又没有正确的保护机制。A刚把计数写成10，B就将同一位置写成20，A随后读到20，自己的状态便被破坏。问题不是数字相同本身，而是两个程序在无协调的情况下控制了同一块存储。
直接使用固定物理位置还带来装载困难：A原定区域被占用时，不能简单把它放到别处，因为程序内部引用仍可能指向旧位置。操作系统也难以随意调整内存布局，错误程序甚至可能改写其他程序或内核的数据。
让程序使用地址，把位置交给映射
现代通用系统通常让普通进程使用虚拟地址。A与B都可以访问0x1234，但通过各自映射，A访问物理地址0x5234，B访问0x2234。两处末尾偏移都为0x234，物理位置却不同，因此互不覆盖。
操作系统建立映射和访问权限，硬件在访存时使用这些规则。如果一个进程试图访问不属于自己的区域，系统可以阻止访问，而不是允许它任意破坏其他程序。这也让装载位置不必暴露给应用：物理位置变化时，可调整映射而保留应用使用的地址。
对照无保护的物理位置冲突与两个进程的独立映射。
隔离不等于禁止共享。操作系统也能有意将两个进程的部分虚拟页映射到同一物理页，用于共享内存；这时需要另外协调并发访问。某些嵌入式或特殊环境也不采用普通进程虚拟内存模型。关于地址空间提供隔离与重定位的背景，可参阅OSTEP：地址空间。
面试回答
物理内存是实际存放运行数据的RAM，物理地址定位其中的位置。如果程序无保护地直接使用固定物理地址，容易互相覆盖，也不便于装载和调整位置。现代通用系统通常给进程独立虚拟地址空间，由操作系统维护映射和权限、硬件执行转换。同一虚拟地址可对应不同物理位置，既方便重定位又实现隔离；需要共享时也能显式映射到共同物理页。
2. 什么是覆盖技术和交换技术？
覆盖和交换都用于缓解内存容量不足，但替换对象不同：覆盖是在一个程序内部轮流装入互斥模块，经典整进程交换则是在内存和后备存储之间移出、移入进程。
程序总量大，但模块不同时使用
假设可用内存100 KiB，一个程序有共同部分20 KiB、模块A 80 KiB、模块B 70 KiB。全部同时装入需要170 KiB，放不下；但若执行A时不需要B，执行B时也不需要A，就可让共同部分常驻，其他部分使用同一覆盖区。
先装共同部分与A，总量100 KiB。切换到B前，程序必须到达不再依赖A的执行点，随后由覆盖组织和装载机制用B替换A，总量变成90 KiB。共同代码负责切换或维持必需状态，不能在A中仍有活动调用时随意覆盖它。这里节省的是互斥模块同时占用的空间，代价是程序组织复杂且可能反复装载。装载可以由程序自行组织，不一定需要内核提供专门的覆盖机制；经典背景见哥伦比亚大学课程：内存管理中的覆盖与交换，这是历史教学资料，不作为现代实现默认规则。
当前进程暂时不用，让出内存
仍假设100 KiB可用，进程P需要80 KiB，Q需要70 KiB，二者不能同时完整驻留。经典交换可保存P的内存内容及必要运行状态，将它从内存移出，再把Q换入；轮到P运行时，再进行相应恢复。P并没有被删除，保存下来的内容用于继续执行。
这类操作需要操作系统管理，交换过程中还要处理地址重定位、可运行状态和未完成I/O等限制，不能把正在被设备访问的区域任意搬走。进程越大，整体搬运成本越高。
分别跟踪一个程序的模块替换与两个进程的整体换入换出。
不要把历史模型当成现代统一流程
覆盖需要程序组织与装载机制配合，不等于操作系统自动按页调入。现代系统常以页面为单位回收和换入，并可能直接丢弃可从文件重新读取的干净页；这不等于每次都把整个进程写入交换区。按页后备存储的机制见OSTEP：超越物理内存的机制。
面试回答
覆盖是在同一程序内让不同时使用的模块共用内存区域，共同部分保留，执行到切换点再装入另一模块，因此需要程序组织与装载配合。经典交换则由操作系统保存并移出整个进程，再换入另一个进程，之后可以恢复执行。二者分别改变模块与进程的驻留情况，都会付出搬运成本；现代按页换入换出不能简单等同于历史整进程交换。
3. 什么是虚拟内存？为什么需要虚拟地址空间？
虚拟内存是一套让程序通过虚拟地址访问数据的机制：操作系统与硬件共同管理地址到物理位置的映射、访问保护，以及哪些页面需要实际驻留。虚拟地址空间是进程所能表达的地址范围，其中并非每个地址都已建立合法映射。
地址范围与实际占用是两回事
在本章模型中，A能够表达0x0000～0x3FFF，总计16 KiB。页0、1、3当前在RAM里，页2对应map.bin，属于合法映射，但还没有占用示例中的物理帧。于是“知道要访问哪个地址”和“那个页面已经准备好”是两个不同问题。
当A第一次读页2时，硬件无法直接完成访问，内核判断映射合法，再准备文件内容并建立驻留映射。程序随后重试原访问。这样可以只为实际需要的数据准备RAM，不必在程序启动时把全部映射内容装入。具体异常流程会在第9题展开。
为什么不把实际布局暴露给程序
若每个程序必须自行避开其他程序占用的位置，内存布局一变化，应用的安排就可能失效。独立地址空间让应用在相对稳定的地址环境里运行；操作系统可以把不同进程的页面放到不同位置，并按映射权限限制读、写或执行。
共享也通过映射表达。例如两个进程读取同一份只读内容时，可以在适当条件下共用物理页，而各自仍保有独立地址空间。这些能力并不只为“内存不够时借磁盘”服务。关于映射、共享与权限的具体接口，可参阅Linux mmap 手册。
用连续的虚拟页、分散的物理帧和未驻留文件页说明三种关系。
容易混淆的边界
虚拟内存不是一块磁盘，也不是“RAM＋交换区”的简单加法。没有交换区，系统仍可使用地址转换与保护。虚拟空间也不一定总比物理内存大，本章故意使用较小空间便于计算。同一进程中的线程通常共享所属进程地址空间，因此线程有各自栈并不意味着具有彼此隔离的整套地址空间。
面试回答
虚拟内存通过映射和访问规则，让程序使用虚拟地址而不必依赖实际RAM布局。虚拟地址空间是进程看到的地址范围，其中只有建立合法映射的区域才能按规则访问，合法页面也可能暂未驻留。它支持隔离、重定位、共享和按需准备内容，不只是借磁盘扩大容量。线程通常共享进程地址空间，虚拟空间的大小与当前物理占用也不能直接画等号。
4. 什么是分页内存管理？
分页把虚拟地址空间划分为固定大小的页，把物理内存划分为对应大小的页框，再通过页表记录页到页框的映射。页框也称物理帧；本章普通页与帧均为4 KiB。
连续地址不再要求连续存放
A的页0在帧3，页1在帧5，页3在帧1。应用仍按虚拟地址使用自己的空间，物理位置却可以分散。操作系统分配一个普通页时，只要找到合适的空闲页框并建立映射，通常不必为整个进程寻找一整片连续RAM。
程序访问地址时，先确定虚拟页号，再在该页内确定偏移。页表替换的是页号对应的物理位置，偏移不变；否则同一页中的第几个字节就会错位。页表不仅记录位置，还要给出访问控制和状态信息。
固定大小简化分配，也留下末页空余
假设某段6 KiB数据按整页独立分配，需要两个4 KiB页：第一页装4096字节，第二页装2048字节，末尾还有2048字节没有用于这段数据。已分配容量是8 KiB，而不是6 KiB。分配单元内部未使用的部分叫内部碎片。
与可变大小的连续分配相比，基本页框分配减少了“总空闲量够，但空闲区域被分散而找不到完整大块”的外部碎片问题。不过，不代表所有内存请求都不再需要连续区域。例如大页或某些底层分配仍可能受连续空间约束。该6 KiB例子也不声称每次小对象分配都必须各占完整页，运行时可以在页内进一步管理对象。
同时展示页与帧的对应关系，以及6 KiB数据的末页空余。
分页带来的灵活性需要管理结构与地址转换作为代价。后面将解释页表占用、TLB加速和多级组织。不同平台可以支持不同页大小，4 KiB只是这里的固定模型，不能据此判断所有机器配置。页与帧的基本概念见OSTEP：分页入门。
面试回答
分页将虚拟空间和物理内存分别划分为固定大小的页和页框，通过页表建立映射。连续虚拟页可以放在不连续物理帧中，基本页分配因此不必为整个进程寻找连续大块空间。地址转换用物理帧号替换虚拟页号，页内偏移保持不变。分页仍有页表与转换成本，也可能有末页内部碎片；它并没有消除大页等请求的连续分配困难。
5. 什么是分段？分页和分段有什么区别？
经典分段按代码、数据等逻辑区域组织地址空间，每个段可以有不同长度；分页则按固定大小划分，不要求页边界恰好对应某个逻辑模块。二者都能进行地址映射和保护，划分依据不同。
段地址先判断边界，再加基址
在独立经典教学模型中，某数据段的物理基址为12288，长度为1024。段内偏移300合法，因为0 ≤ 300 < 1024，转换得到12288 + 300 = 12588。
偏移1024则非法，因为长度1024意味着只有偏移0～1023。不能先算出13312，再把那个数字当作合法段地址。段表用来记录每个段的基址、范围及权限；程序通过段的选择与段内偏移表达位置。
用同一访问任务看两种组织
分页不按模块整体找连续空间，而按页映射。例如本章0x1234拆成页1与偏移0x234，页1对应帧5，结果为0x5234。分段则在选定逻辑段后检查段内范围，并相对基址定位。
| 比较点 | 经典分段 | 基本分页 |
|---|---|---|
| 划分依据 | 代码、数据等逻辑单位 | 固定大小单位 |
| 大小 | 各段可不同 | 同一基本页模型内相同 |
| 地址组成 | 段选择与段内偏移 | 虚拟页号与页内偏移 |
| 典型连续性 | 单段通常连续放置 | 不同页可分散到页框 |
| 典型碎片问题 | 可变连续分配产生外部碎片 | 末页可能产生内部碎片 |
对照段内边界判断与页号替换，避免把两个地址公式混用。
经典分段的逻辑区域便于按区域设置权限，但可变大小分配需要找到合适连续空间。分页把物理分配粒度固定下来，却需要管理页表。实际系统也可能组合机制。尤其不要把“进程有代码段、堆、栈”等软件布局名称直接等同于硬件采用经典分段。模型原理见OSTEP：分段；现代x86-64常规地址管理主要依靠分页，平台实现不能从本例反推。
面试回答
分段按代码、数据等逻辑区域划分空间，段可长短不同，典型转换是选段、检查偏移小于段长度，再加基址。分页按固定大小划分，通过页表将虚拟页映射到物理帧，保留页内偏移。经典分段主要面对可变连续分配的外部碎片，分页可能有末页内部碎片。二者不是单纯优劣关系，软件里的段名称也不证明现代硬件采用经典分段。
6. 页表项通常包含哪些信息？
页表项是页表中用于描述一次映射的记录。它既要帮助确定物理位置，也要说明是否可以直接访问、允许什么访问，以及页面是否被使用或修改。具体字段及编码取决于处理器架构和操作系统。
位置和权限分别回答不同问题
帧号回答“驻留内容在哪里”；驻留或present状态回答“硬件能否通过当前表项直接找到在内存中的映射”；读写、执行、用户/内核等权限回答“当前访问能不能做”。因此，找到了物理位置并不等于允许写入。
下面是抽象教学表，不是某款处理器的逐位布局。虚拟页号用于标识表中哪一行，不表示每个真实页表项内部都存放这个字段。
| 虚拟页 | 帧号 | 驻留P | 权限 | 访问R | 脏D |
|---|---|---|---|---|---|
| 0 | 3 | 1 | 读写 | 1 | 0 |
| 1 | 5 | 1 | 读写 | 1 | 1 |
| 2 | — | 0 | 只读 | — | — |
| 3 | 1 | 1 | 只读 | 0 | 0 |
读页1时，帧5驻留且权限允许，可继续访问。写页3时，即便它已经在帧1中，本例真正只读的映射也不允许修改。访问页2时，需要进入异常处理，由内核查看它是合法文件映射，而不是仅凭P=0断言地址非法。
访问与修改状态为什么有用
访问状态R表示页面是否被访问，可帮助回收算法估计哪些页最近被使用；这里R不是英文Read权限的缩写。脏状态D表示内容发生过修改，有助于判断回收前是否需要保存内容。D=1不代表已经写回文件，D=0也不能单独证明文件与内存始终完全一致。
表项中还可能存在缓存策略、页大小等架构相关信息。Linux页表体系及架构差异见Linux页表文档。操作系统还会用其他结构记录映射范围、后备对象等信息，所以“映射是否合法”不能只看一个硬件present位。
将位置、驻留、权限、访问和脏状态对应到三个访问判断。
面试回答
页表项通常包含物理帧定位、驻留或present状态、读写执行等权限，以及访问、脏等状态信息。帧号说明内容在哪里，权限决定操作能否执行，访问和脏状态帮助回收与写回判断。字段布局依架构而异；present为0只说明不能按当前映射直接完成访问，是否合法还需内核检查映射信息。虚拟页号常用于索引表项，不一定存于每项内部。
7. 虚拟地址如何转换为物理地址？
在分页模型中，地址转换把虚拟页号换成对应物理帧号，保留页内偏移。操作系统负责建立与维护映射，常见硬件管理的体系中，处理器的内存管理单元MMU负责在访存时使用这些映射。
把地址拆成“哪一页”和“页内哪里”
本题先忽略TLB，假设A读取0x1234，页1驻留且允许读取。页大小4096字节，即0x1000，所以：
0x1234 = 1 × 0x1000 + 0x234
虚拟页号 VPN = 1
页内偏移 offset = 0x234（十进制564）
页表告诉我们VPN1对应PFN5。物理帧5从5 × 0x1000 = 0x5000开始，于是目标字节是：
PA = 5 × 0x1000 + 0x234 = 0x5234
低12位用于定位4 KiB页内的字节；改变它就改变了同一页中的访问位置。不能用物理基址再加原始0x1234，因为那会重复计入虚拟页号部分。
谁维护规则，谁执行规则
操作系统装载进程、分配页面或调整权限时维护页表，并在必要时使已有翻译缓存与新映射一致。随后CPU执行读指令，MMU依据当前进程对应的地址转换环境取得翻译、检查权限，再继续数据访问。
这不表示每次成功访问都先调用一次内核函数。实际系统用TLB缓存地址翻译，页表还可能是多级结构；这里拆开步骤只为把计算说清。硬件查表与软件管理翻译的不同架构见OSTEP：TLB。本题算出的物理地址也不意味着一定立刻访问RAM芯片，后续还可能由CPU数据缓存满足读取。
追踪页号的替换与始终保持不变的偏移。
若表项不能提供映射或权限不允许，则不能继续套公式完成读取，需要进入对应异常处理。地址转换的前提始终包括正确的当前地址空间、有效状态和允许的访问方式。
面试回答
分页地址转换先按页大小拆出虚拟页号和页内偏移，再依据当前进程映射取得物理帧号，保留偏移组合物理地址。例如4 KiB页下，0x1234对应页1、偏移0x234，页1映射帧5，所以结果是0x5234。操作系统维护映射，常见体系由MMU使用它，并由TLB加速。转换还要检查驻留与权限，失败时不能直接访问目标位置。
8. 什么是多级页表，为什么需要多级页表？
多级页表将大页表拆成有层次的结构：上级表指向下级表，只有需要映射某一片地址范围时才分配对应下级结构。它主要解决稀疏地址空间中，平铺表为大量未使用地址也预留表项的开销。
为什么一张平铺表可能很大
本题另用32位教学模型，不沿用前面16 KiB空间。页为4 KiB，地址中12位作偏移，剩余20位作页号，共有2^20个潜在页。每项4字节时，一张覆盖整个空间的平铺表需：
2^20 × 4 = 4,194,304字节 = 4 MiB
即使程序只使用几小片地址，完整平铺结构仍要容纳这些索引位置。多级组织则把20位页号分成10位目录索引和10位叶表索引。一张叶表有1024项，占4 KiB；根表也占4 KiB。
按分支分配，而不是为整个范围填满
假设使用地址仅落在根项0、1覆盖的两片范围，每片各需一个叶表，其余根项不分配叶表。此时页表内存为根4 KiB＋两个叶表8 KiB＝12 KiB，不计数据页及其他管理开销。
这是按地址分布得到的结果，不是每个进程固定只要12 KiB。若映射散布在许多不同分支，即便数据页数量不多，也可能需要更多下级表；若接近覆盖全部空间，节省可能很小，且多出上级结构。
一次两级定位
0x00401234按10＋10＋12位拆分，目录索引为1，叶索引为1，偏移为0x234。根[1]找到叶表1，再由叶[1]取得帧5，结果仍为0x5234。这里的虚拟地址与第7题不同，物理位置相同只是我们独立设定的映射。
对照结构容量并沿目录1、叶项1走完定位路径。
用空间换取更复杂的查找
翻译未命中时，多级结构可能需要逐层取得表项，查找比理想平铺索引更复杂；TLB和其他硬件缓存可以减少反复遍历。多级设计的空间收益依赖稀疏性，而不是免费消除全部代价。层次化原理见OSTEP：更小的页表；Linux支持的层级及折叠见Linux页表文档，不能将本题两级结构当成现代x86-64固定格式。
面试回答
多级页表用上级索引指向下级表，未使用地址范围可以不分配对应下级结构，从而降低稀疏空间的管理成本。32位、4 KiB页、4字节表项时平铺表需4 MiB，而根表和两个叶表只需12 KiB。收益取决于映射分布，代价是翻译可能逐层查找，通常由TLB等缓存缓解。具体层数依架构和系统而异，不能把两级教学模型普遍化。
9. 什么是缺页异常？操作系统如何处理？
缺页异常表示当前访存不能按现有页面映射和访问状态直接完成，需要由内核判断原因并处理。页面暂未驻留是常见原因，但缺页类异常也可能涉及保护、写时复制等情况，并不等于每次都要读磁盘。
沿一页文件映射走完处理过程
A读取0x2340，页号为2，偏移为0x340。页2是合法只读map.bin映射，但初始未驻留。常见硬件路径发现不能直接访问后，保存异常信息并转入内核。
内核先根据故障地址和访问类型检查映射：这里允许读取，也确实有后备文件页。随后取得空闲帧6，准备这一页内容。如果文件内容已在适合复用的缓存中，可能无需新设备I/O；否则读取后备内容，等待期间当前线程可能阻塞，CPU可以运行其他工作。
内容准备好后，内核建立页2到帧6的映射、设置相应状态和权限，并完成必要的翻译缓存同步。返回后重试原访存，得到6 × 0x1000 + 0x340 = 0x6340。不是让程序跳过失败指令，也不是随便给出一个空页假装文件内容。
把合法文件缺页的恢复路径与非法访问的错误路径分开。
为什么有时不读存储，有时不能恢复
首次触及合法匿名区域时，系统可能准备零填充页：这类内容没有对应文件，交付初始为0的内容，不必从存储取回，还能避免把旧使用者的数据泄漏给新使用者。写时复制COW则是暂时共享页面，在合法写入发生时准备私有副本：硬件写保护引起异常不一定代表应用违法。
反过来，访问本模型之外的0x9000，或写入本例真正只读且不允许COW写的页3，不能靠“补一页”解决。Linux常对非法访存报告如SIGSEGV的信号；文件映射还可能遇到其他故障类型。即便映射合法，资源不足或I/O错误也可能导致无法恢复。接口的保护与映射语义见Linux mmap 手册。
页框不足时，还可能需要先回收其他页；干净可重读页与必须保存的脏页成本不同。本题选择空闲帧6，是为了单独展示缺页流程，不暗示每次故障都进行页面置换。
面试回答
缺页异常是当前访存无法按现有映射和权限直接完成时进入内核的处理入口。内核先检查地址和访问是否合法，合法时准备所需页面、更新映射及必要TLB状态，再重试原指令；文件页可能需要I/O，零填充或COW则未必读存储。非法访问不能盲目补页，合法处理也可能因资源或I/O失败而失败。缺页与页面置换不是一一对应关系。
10. 什么是 TLB？TLB Miss 等于缺页吗？
TLB（Translation Lookaside Buffer，常称快表）是处理器用于缓存地址翻译及相关访问属性的结构。TLB Miss只是所需翻译没有命中这个缓存；缺页则涉及页面映射或保护状态导致访问无法直接完成，因此二者不是同一个事件。
同一个地址，可以命中也可以未命中
先读取A的0x1234。如果TLB已有页1到帧5的翻译且权限允许，处理器取得帧号并与偏移组合，访问0x5234，不必重新遍历完整页表。
如果这个翻译刚好不在TLB中，同样的地址会产生TLB Miss。在硬件遍历页表的教学路径中，硬件找到页1的表项，确认驻留且权限允许，补充翻译后仍可读取0x5234。内容原本就在内存，缺的是翻译缓存记录，而不是数据页；没有理由因此必然读取磁盘。
只有发现页面状态不满足，才进入相关异常
改为读取初始未驻留页2的0x2340。TLB未命中后，遍历发现当前页2不能直接访问，于是进入第9题的处理。文件页准备到帧6并建立映射后重试，得到0x6340。这条路径同时出现了TLB Miss和缺页，但前一条只有TLB Miss。
用三条独立访问路径比较命中、未命中与需要缺页处理。
TLB保存的不是文件内容，也不是所有页表的完整副本。命中仍要遵守权限，不能写本例只读页3。它也不同于CPU数据缓存：前者回答地址怎样翻译，后者缓存实际数据；地址翻译命中并不证明数据缓存也命中。
以上主要采用硬件遍历页表的路径。某些体系由软件处理TLB未命中，不能把“TLB Miss完全不进入内核”当成所有架构的规则。具体区分见OSTEP：TLB。上下文切换和映射修改还需要避免使用错误或陈旧翻译，处理方式取决于架构。
面试回答
TLB缓存虚拟地址到物理位置的翻译及相关权限，减少重复查页表。TLB Miss表示翻译缓存未命中，不代表页面不在RAM；若页表显示驻留且权限允许，取得翻译后就能继续。若页面未驻留或访问状态不满足，才需要相应异常处理。TLB不是数据缓存，命中也不能绕过权限；未命中的处理方式还分硬件遍历与软件管理等架构。
11. 常见页面置换算法有哪些？Clock 算法如何工作？
页面置换是在需要页框却没有足够可用页框时，选择哪些驻留页面可以被回收的策略。关键不是找出“最早的数字”，而是预测回收哪一页后，近期再次需要它的代价较小。
在同一引用串上比较选择规则
独立例子有3个初始空页框，依次访问7、0、1、2、0、3、0、4、2、3、0、3、2。只统计这13次引用造成的缺页，不加入预读或并发行为。M为缺页，H为命中。
| 算法 | 逐次事件，对齐上述13次引用 | 缺页次数 |
|---|---|---|
| FIFO | M M M M H M M M M M M H H | 10 |
| LRU | M M M M H M H M M M M H H | 9 |
| OPT | M M M M H M H M H H M H H | 7 |
前三次把7、0、1装满。第四次访问2时，FIFO按装入先后淘汰7；随后命中0并不改变FIFO队列。访问3时FIFO淘汰原来较早装入的0，所以下一次访问0又缺页。
LRU按最近访问先后选择。访问2淘汰7之后，命中0会把0记成刚用过的页；访问3时淘汰更久没用的1，因此下一次0命中。这解释了两种规则在第7次引用出现差异，而不是只背“一个10、一个9”。
OPT选择未来最晚再使用，或以后不再使用的页。第四次需要2时，7、1之后都不再出现，可以任选其一淘汰；本文取7。之后需要3时可淘汰不再使用的1。OPT可以作为该模型的比较基准，但实际系统不知道未来完整引用串，不能直接照做。三种策略的含义见OSTEP：页面置换策略。
为核对全部结果，下表列出每次访问后的驻留页集合，按页号排序仅便于阅读，不是FIFO队列顺序或LRU先后顺序。OPT遇到同样不再使用的页面时，按当前记录顺序选先出现者；这种平局选择不改变本例缺页次数。
| 步骤／引用 | FIFO | LRU | OPT |
|---|---|---|---|
| 1／7 | {7} M | {7} M | {7} M |
| 2／0 | {0,7} M | {0,7} M | {0,7} M |
| 3／1 | {0,1,7} M | {0,1,7} M | {0,1,7} M |
| 4／2 | {0,1,2} M | {0,1,2} M | {0,1,2} M |
| 5／0 | {0,1,2} H | {0,1,2} H | {0,1,2} H |
| 6／3 | {1,2,3} M | {0,2,3} M | {0,2,3} M |
| 7／0 | {0,2,3} M | {0,2,3} H | {0,2,3} H |
| 8／4 | {0,3,4} M | {0,3,4} M | {2,3,4} M |
| 9／2 | {0,2,4} M | {0,2,4} M | {2,3,4} H |
| 10／3 | {2,3,4} M | {2,3,4} M | {2,3,4} H |
| 11／0 | {0,2,3} M | {0,2,3} M | {0,2,3} M |
| 12／3 | {0,2,3} H | {0,2,3} H | {0,2,3} H |
| 13／2 | {0,2,3} H | {0,2,3} H | {0,2,3} H |
对齐13次引用的命中和缺页，不用拥挤的全状态大图。
Clock用访问位给页面第二次机会
精确维护每次访问的先后顺序可能成本较高。基础Clock将候选页组织成环，维护扫描指针和访问位R：访问会使R为1；扫描遇R=1，先清成0并继续；遇R=0，便可选择该页。它近似利用近期访问情况，不是精确LRU。
另设独立状态A=页1/R1、B=页2/R0、C=页3/R1，指针从A开始，期间没有额外访问。装入并访问页4时：先清A的R而保留页1；走到B发现R0，替换页2为页4/R1；下一扫描位置设为C。最终是A1/R0、B4/R1、C3/R1。清访问位不等于移除页，C没有被扫描，R仍为1。
逐步展示清访问位、选择受害页与移动下一扫描指针。
选中以后，还要考虑内容怎样保存
访问位不是脏位。若选择的是仍需保存的修改内容，不能直接丢弃；干净且可重新读取的文件页则可能无需写回。因此现代系统的回收还会考虑页类型、写回和负载等因素，不能把基础Clock当成Linux全部实现。不同引用串也不会固定得到10/9/7，增加FIFO页框甚至并非所有输入都减少缺页。
面试回答
FIFO按装入先后淘汰，命中不改变队列；LRU选择最久未访问页；OPT看未来最晚使用，是知道完整引用串的比较基准。基础Clock循环扫描访问位，遇1先清零给一次机会，遇0选择受害页，近似利用近期访问而不等同精确LRU。选中页面后还需判断内容能否丢弃或必须保存，真实系统回收比这些教学规则更复杂。
12. 什么是工作集和内存抖动？
工作集描述进程在最近一段观察窗口中访问过的不同页面，用来估计当前活跃需求。内存抖动则是系统因活跃页面难以驻留而反复准备、回收页面，花大量时间在换页和等待上，正常工作进展很慢。
数访问过的不同页，而不是引用次数
以最近4次访问为窗口，A的序列1、2、1、3得到工作集{1,2,3}，只有3页，重复的1不能算两页。B的4、5、4、6得到{4,5,6}，也是3页。窗口移动后，旧访问退出、新访问进入，工作集也会变化，不是程序固定不变的全部页面。
这种观察利用局部性：一段执行时期往往重复访问少数相关页。如果给这些页面足够驻留空间，后续访问更容易命中。反过来，窗口太短可能低估需求，太长又可能把已经不用的页面算进去。
活跃需求放不下，回收可能制造下一次缺页
假设A、B持续访问各自上述3页，但各只分2帧，总共4帧。A需要第三页时必须回收一页；后来再次访问刚回收的活跃页，又得装回并回收另一页。B也可能如此。总活跃需求6页超过这次分配的4帧，持续相似访问便可能形成重复换页。
如果需要设备I/O，等待成本通常比普通命中访问高，降低程序有效进展；即使没有每次都读磁盘，反复故障、准备和回收也会带来开销。这不是由“虚拟地址空间大”单独决定的：保留很多从不访问的地址，不等于有很大的活跃工作集。
对照两个3页工作集与仅4帧的供给，再展示两种改善方向。
改善的是供需关系，不只是换一种算法
在本例，可以增加到6帧，给A、B各3帧；也可以暂缓B、降低同时活跃的进程数量，给A至少3帧。这是两种替代方案，不要求必须连续实施。改善访问局部性、减少活跃数据也能降低需求。
真实排查需要结合缺页类型、回收、I/O等待、可用内存与负载，不能只看一次缺页计数就认定抖动。工作集的经典窗口定义可查Denning原始论文：The Working Set Model for Program Behavior。本章只用4次访问窗口演示集合，不声称它是任何系统固定参数。
面试回答
工作集是在观察窗口内访问过的不同页面集合，用来估计当前活跃内存需求，会随执行阶段和窗口变化。若活跃需求持续超过可获得页框，回收的页面很快又被访问，就可能反复换入换出，形成抖动。应结合局部性、并发度、可用帧和I/O判断，而不是仅看虚拟空间大小；增加有效内存、降低并发或减少活跃需求都可能改善这种供需失衡。
阅读导航
