考研笔记

页框分配

上一节解决了”缺页了怎么办”，但回避了一个前置问题：每个进程到底该分几个页框？

这个数字影响巨大：给少了缺页频繁，给多了又挤占别人。本节讲的就是分多少和在哪个范围里换。

机制

驻留集

驻留集指请求分页存储管理中，给进程分配的物理页框的集合（即该进程在内存中的页面集合）。

驻留集大小的影响非常直接：

  • 驻留集太小 → 缺页频繁，进程大部分时间在等待调页，执行效率骤降，严重时导致抖动。
  • 驻留集太大 → 单个进程的缺页率确实降低了，但内存中能容纳的进程数减少，多道程序度下降，CPU 可能因为无进程可调度而空闲，系统整体吞吐量反而下降。

这是一个典型的”局部最优 vs 全局最优”的矛盾：对单个进程好的，未必对系统整体好。

而且驻留集与缺页率的关系不是线性的——增大到一定程度后，继续增加页框对降低缺页率的效果会急剧减弱（因为该进程当前活跃的那部分页已经全在内存里了）。这个”够用的大小”就是工作集要回答的问题。

两组正交的策略

页框分配涉及两个互相独立的决定，务必分开理解：

第一个决定：分配策略——驻留集大小是否可变？

  • 固定分配：进程运行期间驻留集大小保持不变。
  • 可变分配：驻留集大小可以动态调整。

第二个决定：置换策略——换出的页从哪个范围里选？

  • 局部置换：只能从该进程自己的页面中选择淘汰对象。
  • 全局置换：可以从内存中所有可换出的页面里选（包括别的进程的）。

两两组合本应有四种，但其中一种在逻辑上不成立：

局部置换全局置换
固定分配✅ 固定分配局部置换❌ 不存在
可变分配✅ 可变分配局部置换✅ 可变分配全局置换

为什么”固定分配全局置换”不存在：

全局置换意味着可以抢占别的进程的页框。一旦发生抢占，被抢者的驻留集就变小了，抢占者的驻留集就变大了——这直接违背了”固定分配”（大小不变）的定义。

两者在定义上互相矛盾，所以这个组合不可能成立。 这是本节最常考的一个点。

三种可行策略的对比

① 固定分配局部置换

进程一开始分到固定数目的页框，缺页时只能淘汰自己的页。

  • 优点：实现简单，各进程互不干扰。
  • 缺点：难以在一开始就确定合适的数目。给少了这个进程一直缺页，给多了浪费——而且无法根据运行情况调整。

② 可变分配全局置换

系统维护一个空闲页框队列。进程缺页时先从空闲队列取；队列空了，就从内存中任选一页换出（可能属于别的进程）。

  • 优点：实现简单，缺页的进程总能立刻得到页框。
  • 缺点：盲目性大。被抢走页框的那个进程完全无辜，它的驻留集莫名其妙变小了，缺页率随之上升。一个进程的缺页可能引发另一个进程的缺页，容易连锁。

③ 可变分配局部置换

进程缺页时只能淘汰自己的页；但系统会根据缺页率动态调整它的驻留集大小：

  • 缺页率过高 → 说明页框不够 → 多分配几个

  • 缺页率过低 → 说明分多了 → 适当收回几个

  • 优点：既避免了抖动，又保持了较高的多道程序度，是三者中最合理的。

  • 缺点：实现复杂，开销较大（要持续统计各进程的缺页率）。

物理页框的分配算法

在多个进程之间分配总页框数，有三种做法：

平均分配：所有进程平分。问题是没考虑进程大小差异——一个 10 页的小进程和一个 200 页的大进程分到同样多页框，对大进程极不公平。

按比例分配：按各进程的页面数（大小）比例分配。比平均分配合理。

优先权分配：按优先级分配，重要进程多分。实际系统常用折中方案——一部分按比例分，一部分按优先级分。

边界

分配策略与置换策略是两个维度

初学时最容易把”固定/可变”和”局部/全局”混为一谈。它们回答的是完全不同的两个问题：

  • 固定 / 可变问的是：驻留集的大小会不会变？
  • 局部 / 全局问的是：淘汰对象从哪个集合里选？

只有认清这是两个正交维度，才能理解为什么”固定分配 + 全局置换”是自相矛盾的——全局置换必然改变驻留集大小，而固定分配禁止改变。

全局置换必然导致驻留集变化

这条是上一条的推论，但值得单独记：

只要采用全局置换，驻留集大小就一定会变。 抢别人的页框，自己的驻留集变大；被别人抢，自己的驻留集变小。

因此全局置换只能配可变分配。

驻留集大小与系统吞吐量不成正比

这是个反直觉点。给每个进程更多页框，单个进程的缺页率下降，但系统吞吐量可能反而下降——因为内存中放得下的进程变少了，CPU 更容易无事可做。

系统追求的是全局最优：找到那个让”缺页开销”和”多道程序度”取得平衡的驻留集大小。这正是工作集模型要解决的问题。

可变分配局部置换 vs 可变分配全局置换

两者都会调整驻留集，但调整的时机和方式完全不同：

  • 可变分配局部置换：主动调整。系统持续监测缺页率，有依据地增减页框。
  • 可变分配全局置换：被动变化。谁缺页谁抢，没有任何评估，被抢的那个只能自认倒霉。

一句话：前者是”按需调控”，后者是”先到先得”。 所以前者效果好但复杂，后者简单但盲目。

对照速查

分配策略置换策略
回答的问题驻留集大小变不变从哪个范围选淘汰页
两个取值固定 / 可变局部 / 全局
组合是否成立特点
固定分配 + 局部置换✅简单；初始数目难确定，无法调整
固定分配 + 全局置换❌ 不存在全局置换必然改变驻留集，与固定矛盾
可变分配 + 全局置换✅简单；盲目，易连锁引发他人缺页
可变分配 + 局部置换✅最合理；按缺页率调控，实现复杂
分配算法依据问题
平均分配进程数未考虑进程大小差异
按比例分配进程页面数较合理
优先权分配优先级常与按比例折中使用

考点

  • 驻留集的定义，以及太大太小各自的后果
  • “固定分配全局置换”不存在及其原因（定义互相矛盾）
  • 三种可行组合的优缺点，可变分配局部置换最合理
  • 可变分配局部置换按缺页率调控（主动），全局置换是先到先得（被动）
  • 三种分配算法，平均分配未考虑进程大小

链接

反向链接