页框分配与回收

2026 大纲 三（二）3 页框分配与回收。

该给一个进程几个页框

前面四篇讨论的都是"页框满了该踢谁"，但都默认了一件事：这个进程有几个页框，是已经定好的。 定好的那个数是怎么来的？

这一节要回答的就是它，而且要分两层回答，因为这里其实藏着两个完全不同的问题：

第一层是可行性：少到什么程度，进程就根本跑不动了？ 注意是跑不动，不是跑得慢。原因在请求分页那一节埋过——缺页要重新执行整条指令， 如果一条指令同时需要的页面数超过它拥有的页框数，那么每次重执行都会缺页， 进程会卡在同一条指令上永远走不下去。所以存在一个硬下限，由指令集架构决定， 跟进程有多大、内存有多大都没关系。

第二层是性能：在下限之上，多分一点少分一点，缺页率差多少？ 这一层没有硬答案，只有一个目标——分给它的页框数，要盖得住它当前真正在用的那些页。 "当前真正在用的那些页"就是工作集，它是需求侧；分给它的页框是驻留集，是供给侧。 供给小于需求，就会抖动。

两层之外还有两件配套的事：页从哪里调进来（对换区还是文件区，两者速度差很多）， 以及换出去的页立刻扔掉太可惜（页面缓冲算法就是加在这条路径上的缓冲层）。

一、最少页框数的四个台阶

沿着"指令复杂度"这条轴一级级往上推：

情形	需要同时驻留的页面	最少页框数
单地址指令 + 直接寻址	指令 1 页 + 数据 1 页	2
单地址指令 + 间接寻址	指令 1 页 + 存放操作数地址的间址单元 1 页 + 数据 1 页	3
双地址指令 + 直接寻址	指令 1 页 + 源操作数 1 页 + 目的操作数 1 页	3
指令本身可能跨页，源、目的所涉区域也各可能跨页	指令 2 页 + 源 2 页 + 目的 2 页	6

对照请求分段：段是信息的逻辑单位，一条指令不会被分割到两个段里，所以请求分段没有"跨块"这一档。这条差别正是分页与分段在这个问题上的分水岭。

二、三种组合各自的取舍

分配策略分固定 / 可变（页框数创建时定死还是运行中动态调整），置换范围分全局 / 局部（缺页时能否淘汰别的进程的页面）。两两相配去掉自相矛盾的一种，剩下三种：

组合	特点	代价
固定 + 局部	页框数按进程类型（交互型 / 批处理型）或人工建议在创建时确定，运行中不变	核心困难是事先难以确定该分多少：分少了频繁缺页、吞吐量下降；分多了驻留进程数减少，CPU 与其他资源可能空闲，进程对换也更费时间
可变 + 全局	最容易实现，很多 OS 采用。系统维护一个空闲页框队列，缺页时优先分配空闲页框，用完了才从内存中选一页调出	被选中调出的页可能属于任何一个进程，那个进程的页框数因此减少、缺页率上升——一个进程的缺页会波及别人
可变 + 局部	缺页只换自己的页，不影响别人；频繁缺页就再追加页框直到缺页率降下来，缺页率特别低则适当回收（但不应引起缺页率明显上升）	实现复杂，但效果最好——它其实就是缺页频率 PFF 策略在分配侧的落地

三种分配算法在同一组数据上各算一遍，含"最少页框数"硬约束怎么修正比例（想看分母的选择如何改变驻留比例时展开）

系统可供分配的页框数 $m=60$，三个进程页面数分别为 $S_1=10$、$S_2=30$、$S_3=80$。（数据自造）

(1) 平均分配

$$b_1=b_2=b_3=\lfloor 60/3\rfloor =20$$

问题有两头：$P_1$ 一共才 10 页却拿到 20 个页框，至少 10 块被闲置；$P_3$ 有 80 页也只得 20 块，只有四分之一能驻留内存，缺页率必然很高。平均分配的"公平"是对进程个数公平，而缺页率取决于驻留比例 $b_i/S_i$——这三个进程的驻留比例分别是 200%、67%、25%，差了 8 倍。公平的口径选错了，结果就是实质上的不公平。

(2) 按比例分配

$$S=10+30+80=120$$$$b_1=\frac{10}{120}\times 60=5,b_2=\frac{30}{120}\times 60=15,b_3=\frac{80}{120}\times 60=40$$

校验：$5+15+40=60$ ✓。三者驻留比例都是 50%，拉齐了。

(3) 加上"不得低于最少页框数 6"的约束

$b_1=5<6$ 不满足。修正办法是先把 $P_1$ 补到下限，再对剩下的页框重新按比例分配：

$$b_1=6,\text{剩余}=60-6=54$$$$b_2=\frac{30}{30+80}\times 54=14.7\to 14,b_3=\frac{80}{30+80}\times 54=39.3\to 39$$

此时 $6+14+39=59$，还剩 1 块，按小数部分最大者补（$P_2$ 的 0.7 大于 $P_3$ 的 0.3），$b_2=15$，最终 $(6,15,39)$，合计 60。

顺序不能反：最少页框数是硬约束（低于它进程跑不起来），按比例只是软目标。硬约束必须先满足，剩下的资源再去逼近软目标——反过来就会得到一个"比例很漂亮但 $P_1$ 跑不动"的分配。

(4) 考虑优先权的分配

先用 48 块按比例分：

$$b_1=\frac{10}{120}\times 48=4,b_2=\frac{30}{120}\times 48=12,b_3=\frac{80}{120}\times 48=32$$

剩下的 $60-48=12$ 块按优先权全部拨给实时进程 $P_2$：

$$(b_1,b_2,b_3)=(4,24,32),4+24+32=60$$

$P_2$ 的驻留比例从 40% 提到 80%，代价是 $P_1$ 与 $P_3$ 都从 50% 降到 40%。

三问对照着看就清楚了：平均分配按"进程个数"分，按比例分配按"进程大小"分，考虑优先权按"进程重要性"分——三种算法的差别不在算术，在于选了哪个分母。

三、从哪里调入：两个区与三种规则

位置	存放内容	分配方式	I/O 速度
对换区（Swap Area）	进程被换出的页面	连续分配	快
文件区（File Area）	可执行文件的代码和数据	离散分配	慢

调入规则按对换区够不够大分三种情况：

1. 对换区空间足够：进程运行前先把相关文件从文件区拷贝到对换区，此后全部从对换区调入，以提高调页速度。
2. 对换区空间不足：不会被修改的部分（如代码段）直接从文件区调入——它们换出时无须写回（外存那份就是最新的），以后仍从文件区调入；可能被修改的部分换出时写到对换区，以后从对换区调入。
3. UNIX 方式：与进程有关的文件都在文件区，未运行过的页面一律从文件区调入；曾运行过又被换出的页面放在对换区，下次从对换区调入。由于 UNIX 允许页面共享，某进程请求的页面可能已被其他进程调入内存，此时无须再调。

四、工作集与驻留集

	工作集 $W(t,\mathrm{\Delta })$	驻留集
定义	进程在时间区间 $(t-\mathrm{\Delta },t)$ 内实际访问过的页面集合	该进程当前实际驻留在内存中的页面集合
回答的问题	程序需要什么	内存里有什么
由谁决定	程序自身的行为（访问模式）	操作系统（分配给它多少页框）
大小	随 $t$ 和 $\mathrm{\Delta }$ 变化，OS 只能估计	= 分配给该进程的页框数，OS 说了算
能不能直接控制	不能	能

工作集的三处用法：分配给进程的页框数不应小于工作集大小；采用工作集的系统里每个进程有一张记录运行时工作集的表，进程被调度运行时把工作集中的所有页一次调入（这正是预调页的主要用武之地）；把各进程工作集大小加起来与可用页框总数比较，就得到了判断系统会不会抖动的直接判据（见虚拟存储性能与改进）。

在一个 12 次访问的序列上把窗口从 2 试到 12，看平台期怎么显形（想看局部性转移点如何被窗口跨过时展开）

某进程的页面访问序列为 $1,2,1,3,2,1,4,5,4,6,5,4$（共 12 次，从左到右按时间先后），$t$ 取序列末尾。

第一步：按定义取最近 $\mathrm{\Delta }$ 次访问，去重——工作集就是"最近 $\mathrm{\Delta }$ 次访问碰过哪些页"，做的只是取最后 $\mathrm{\Delta }$ 项再去重。

$\mathrm{\Delta }$	最近 $\mathrm{\Delta }$ 次访问	工作集 $W$	$|W|$
2	5, 4		2
3	6, 5, 4		3
4	4, 6, 5, 4		3
6	4, 5, 4, 6, 5, 4		3
9	3, 2, 1, 4, 5, 4, 6, 5, 4		6
12	全串		6

$|W|$ 随 $\mathrm{\Delta }$ 单调不降，正是 $W(t,\mathrm{\Delta })\subseteq W(t,\mathrm{\Delta }+1)$ 这条性质的表现。

第二步：读出这串数据里的局部性结构——前 6 次访问集中在 {1, 2, 3}，后 6 次集中在 {4, 5, 6}，在第 6 次到第 7 次之间发生了一次局部性转移。

第三步：判断三档 $\mathrm{\Delta }$ 的后果

$\mathrm{\Delta }$	$|W|$	判断	后果
2	2	过小：漏掉了页 6，没能覆盖当前局部性的全部三页	据此只分 2 个页框，实际需要 3 个 → 缺页率高，甚至抖动
3～6	3	合适：出现了平台期——$\mathrm{\Delta }$ 在这个区间怎么变，$|W|$ 都是 3	分 3 个页框，供给正好覆盖需求
9～12	6	过大：窗口跨过了第 6 次那个转移点，把已经不再访问的 {1,2,3} 也算了进来	据此分 6 个页框 → 多出的 3 块被白占，能同时驻留的进程数下降，系统吞吐量降低

结论：$\mathrm{\Delta }$ 应当大到足以覆盖一个局部性阶段内的全部页面，小到不跨越局部性的转移点。可操作的判据就是第三步那个平台期。

五、页面缓冲算法（PBA）

影响换进换出效率的有三个因素：置换算法好不好（从根上减少换进换出次数）、写回磁盘的频率（每换出一个脏页就启动一次磁盘则开销极大）、读入内存的频率（刚换出的页马上又要用就得再读一次盘）。PBA 用两个链表对付后两条：

链表	什么时候挂进去	怎么用	解决的是哪个因素
空闲页面链表	未修改的页面被换出时，不写回磁盘，把页框挂到链表末尾，页框中的数据仍然保留	需要新页框时从头部取（先进先出，让数据在链表里尽量待久一点）；若该页面被再次访问，直接从链表中取下复用，无需从磁盘读入	第 3 条——把"换出又换回"的代价从一次磁盘读降到一次链表操作
修改页面链表	已修改（脏页）被换出时，不立即写回，把页框挂到链表末尾	攒到一定数量（例如 64 个页面）批量写回磁盘	第 2 条——把 64 次磁盘启动合成 1 次；顺带也解决第 3 条（还没写回时被再次访问可直接取回）

缺页时：空闲页面链表头 ──取页框──► 装入新页面

未修改页换出：页框 ──► 空闲页面链表尾（数据保留，可原样取回）
已修改页换出：页框 ──► 修改页面链表尾（攒够一批再写盘）

VAX/VMS 就是在"可变分配 + 局部置换"之上，再让系统自己保留一部分空闲页框来实现它的。

六、哪些页框可以回收

类别	能否回收	判据
内核代码、内核数据、内核栈	不可回收	回收它们意味着 OS 自己会缺页，而处理缺页的代码正在这些页里，会死锁
进程的代码段（只读，文件区有副本）	可回收，且无须写回	外存那份就是最新的，直接丢弃
进程的数据段、堆、栈（脏页）	可回收，须先写回对换区	内存中的副本才是最新的
文件映射页（脏）	可回收，须先写回原文件	后备存储是文件本身，见内存映射文件
共享内存页	可回收，写回对换区	须等所有共享者都不再需要

按"写回代价"排序，回收的优先次序自然就出来了：干净页（零 I/O）→ 脏页（一次写盘），这和改进 CLOCK 优先淘汰 (0,0) 类是同一条道理。

实现层面：Linux 用守护进程 kswapd 定期检查空闲页框数量，低于水位线时主动发起回收。这属于具体系统的实现细节，了解即可；需要掌握的是"为什么必须提前回收"那条推理，以及回收与置换的分工。

七、系统一侧：空闲页框怎么记账

上面谈的是"分给某个进程几个页框"。系统这一侧还要回答另一个问题： 哪些页框现在是空的？

分页的记账比连续分配简单得多，原因在基本分页那一节说过—— 页框等大。等大意味着任何一个空闲页框都能满足任何一次分配请求， 既不需要记大小，也不需要在回收时合并相邻块。剩下的信息只有一个比特：这一框占了没有。

所以最自然的结构就是位图（位示图）：每个页框对应 1 个二进制位，1 表示已占用、0 表示空闲。 分配就是找一个 0 并置 1，回收就是把对应位清 0——天然不需要合并。

位图占多大空间是一个纯粹的两步换算：

$$\text{页框总数}=\frac{\text{物理内存大小}}{\text{页面大小}},\text{位图大小}=\text{页框总数}\times 1\text{bit}$$

比如物理内存 16 GB、页大小 4 KB：页框总数 $={\displaystyle \frac{2^{34}}{2^{12}}}=2^{22}$ 个， 位图 $=2^{22}$ bit $={\displaystyle \frac{2^{22}}{8}}$ B $=2^{19}$ B $=\mathbf{\text{512 KB}}$。

⚠️ 两处会错的地方：别忘了除以 8（题目问的是字节，位图算出来是比特）， 以及别把页框数当成字节数——一个页框只占 1 位，不是 1 字节。

考点速记

1. 最少页框数是可行性下限，不是性能问题：少于它进程跑不动（不是跑得慢）。判据只有一条——一条指令从取指到执行完毕，最多同时需要几个页面驻留；因为缺页要重新执行整条指令，页面凑不齐就会陷入"每次重执行都缺页"的死循环。它由指令集架构决定，与代码段长度、虚拟地址空间、物理内存大小都无关。
2. 两个最易漏的档：间接寻址——存放操作数地址的间址单元本身也占一页，多一级间址就多一页；跨页——一条 4 字节指令可能有 2 字节落在页 $n$、2 字节落在页 $n+1$，一次跨页就把该项的页面需求翻倍。台阶为 2 → 3 → 6。
3. 分配策略与置换范围只有三种组合成立：固定+局部、可变+全局、可变+局部。⚠️固定+全局自相矛盾——全局置换会从别的进程抢页框，两边的页框数都在变，与"固定"直接冲突。
4. 三种分配算法的差别在选了哪个分母：平均分配按进程个数、按比例分配按进程页面数 $b_i=\frac{S_i}{S}\times m$、考虑优先权的按进程重要性。⚠️ $b_i$ 取整后必须大于最少页框数这条硬约束。
5. 调入时机：预调页赌空间局部性、成功率约五成 ⇒ 主要用在进程首次装入；请求调页调进来的页一定会被访问但每次都要等一次磁盘 I/O ⇒ 是运行期主力。
6. 对换区比文件区快的根源：对换区连续分配，一次磁盘 I/O 能读到连续多块、寻道与旋转开销被摊薄；文件区离散分配，每块都可能要重新寻道。
7. 工作集是需求侧、驻留集是供给侧，分配目标是 $\text{驻留集}\supseteq W(t,\mathrm{\Delta })$；供给小于需求就抖动。
8. 工作集是二元函数：对 $t$ 局部性会转移；对 $\mathrm{\Delta }$ 是非降函数（窗口只开大不开小）。$\mathrm{\Delta }$ 的取值判据是平台期——过小则漏掉当前局部性的页，过大则跨过局部性转移点、把已不再访问的旧页也算进来。
9. PBA 既不是分配策略也不是置换算法，它是加在换出路径上的缓冲层：淘汰选谁仍归置换算法，分多少页框仍归分配策略，它只改变"换出之后发生什么"。正因为换入换出开销被压低，才能采用较简单的置换策略（如 FIFO），且不需要特殊硬件。
10. 回收 vs 置换：置换由缺页触发、被动、一次一页；回收由空闲页框低于阈值触发、主动、一次一批。必须提前回收——释放脏页要先写盘、写盘需要一块临时页框做缓冲，页框归零时这块缓冲拿不出来，回收会把自己卡死。负责救火的资源不能自己也烧掉，这与"内核页框不可回收"是同一条道理。
11. 位图管空闲页框：$\text{页框数}={\displaystyle \frac{\text{物理内存}}{\text{页面大小}}}$，$\text{位图大小}=\text{页框数}\times 1\text{bit}$。⚠️ 问字节数时记得除以 8。

这一节在真题里被考过的形式：

考法很散，六道题几乎各考一个知识点，没有反复出现的题型。 好在每一条判据都很短，属于"记住就得分"的类型。

• 问确定最少页框数时要考虑什么指标（2025-27）。答指令系统支持的寻址方式。⚠️ 另三个选项（代码段长、虚拟地址空间大小、物理地址空间大小）都很有迷惑性，但它们决定的是"分多少才跑得快"，不是"少到多少就跑不动"。这道题就是速记第一条那个"可行性 vs 性能"的分界。
• 问页面分配策略与置换策略哪种组合不能用（2015-30）。答固定分配 + 全局置换。理由是速记第三条——全局置换必然改变各进程的页框数，与"固定"自相矛盾。
• 给访问序列和窗口大小，求某时刻的工作集（2016-29）。窗口为 6 ⇒ 从 $t$ 时刻往前数 6 次访问，取其中不重复的页号。$t$ 之前最近 6 次是 6,0,3,2,3,2，去重得 $\{6,0,3,2\}$。⚠️ 两个坑：窗口往前数不往后数（工作集是对过去的观察）；要去重（工作集是集合不是序列）。
• 问系统发生抖动时可采取的有效措施（2011-29）。答仅撤销部分进程。⚠️ 增加交换区容量没用——抖动的根源是物理内存不够分，换出去的地方再大也不解决问题；提高优先级更是反向操作，只会让这个进程抢更多 CPU 去继续换页。抖动的完整讨论见虚拟存储性能与改进。
• 给页大小和物理内存，算位图占多大空间（2023-25）。16 GB / 4 KB $=2^{22}$ 个页框，每框 1 位 ⇒ $2^{22}$ bit $=$ 512 KB。⚠️ 四个选项分别对应"忘了除以 8""按字节记账""正确""把页框数当字节"，每一步换算错都能对上一个选项。
• 给一套自定义的局部置换策略，模拟驻留集与空闲页框链的变化（2012-45，大题）。这道题不考现成算法，考的是按题面给的规则老实模拟——扫描周期、回收进空闲页框链尾、以及"曾用过且还在链表中则重新放回驻留集"这条特殊规则。⚠️ 它同时挂在置换与分配两个标签下，属于把本章多节串起来的综合题。

复习优先级：条条都要记，但都不难。 速记第一、三条是选择题的固定答案； 第八条的工作集求法要练一遍（往前数、去重）；第十一条的位图换算是纯计算， 练一次就不会错。第九、十条（PBA 的定位、回收与置换的分工）属于容易被设成错项的概念边界。

易错：认为最少页框数与代码段长度或虚拟地址空间大小有关。它只由指令系统的寻址方式决定。

易错：算最少页框数时漏掉间址单元或跨页。间址单元自己也占一页，跨页会让该项需求翻倍。

易错：认为"固定分配 + 全局置换"可以组合。全局置换会改变各进程页框数，与"固定"矛盾。

易错：求工作集时往后数、或者不去重。窗口是往前数的，且工作集是集合。

易错：认为增加交换区容量能缓解抖动。抖动的根源是物理内存不够分，扩大外存无用。

易错：算位图大小时忘了除以 8。位图算出来的单位是比特，题目通常问字节。

易错：把 PBA 当成一种置换算法或分配策略。它是换出路径上的缓冲层，只改变"换出之后发生什么"。

易错：认为页框回收可以等到完全没有空闲页框时再做。释放脏页要先写盘，写盘需要一块缓冲页框，归零时就卡死了。

教材出处

• 最小物理块数的定义与三个台阶（单地址指令+直接寻址为 2；允许间接寻址则至少 3；指令本身可能跨两个页面、源地址与目标地址所涉区域也各可能跨两页，故至少 6）：汤小丹《计算机操作系统》5.2.2 节「最小物理块数的确定」，p159
• 固定分配局部置换、可变分配全局置换、可变分配局部置换三种策略及各自代价：同书 5.2.2 节「内存分配策略」，p159–160
• 三种物理块分配算法——平均分配（"貌似公平，由于未考虑各进程本身的大小，会造成实际上的不公平"）、按比例分配 $b_i=\frac{S_i}{S}\times m$（"$b_i$ 应该取整，它必须大于最小物理块数"）、考虑优先权的分配（把物理块分成两部分，一部分按比例、一部分按优先权，实时控制系统可能完全按优先权）：同书 5.2.2 节「物理块分配算法」，p160
• 预调页策略"目前预调页的成功率仅约 50%"、请求调页策略、以及从何处调入页面的三种情况（对换区足够 / 对换区不足 / UNIX 方式）：同书 5.2.3 节「页面调入策略」，p161–162
• 工作集的定义 $w(t,\mathrm{\Delta })$、窗口尺寸 $\mathrm{\Delta }$、以及"工作集是窗口尺寸 $\mathrm{\Delta }$ 的非降函数，$w(t,\mathrm{\Delta })\subseteq w(t,\mathrm{\Delta }+1)$"：同书 5.4.2 节「工作集」，p171
• 页面缓冲算法 PBA 的两个链表（空闲页面链表保留数据、修改页面链表攒到例如 64 个页面再一起写回）、影响换进换出效率的三个因素、以及"正是由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如 FIFO"：同书 5.3.4 节「页面缓冲算法(PBA)」，p167–168

相关知识

CLOCK 与改进 CLOCK 算法｜内存映射文件｜虚拟存储性能与改进｜虚拟内存基本概念

真题练习

相关真题（8题）

2026Q292分2025Q272分2023Q252分2022Q302分2016Q292分2015Q302分2012Q457分2011Q292分

上一篇页面置换算法对比模拟器下一篇内存映射文件

相关文章

• 内存管理基本概念
• 连续分配（首次/最佳/最坏适应）
• 基本分页（地址变换）
• 基本分段
• 段页式管理
• 虚拟内存基本概念
• 请求页式管理
• FIFO 页面置换算法
• LRU 页面置换算法
• OPT 最佳置换算法
• CLOCK 与改进 CLOCK 算法
• 页面置换算法对比模拟器
• 内存映射文件
• 虚拟存储性能与改进