3.2.2 请求分页管理方式
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 3.2.2 请求分页管理方式
请求分页系统建立在基本分页系统的基础之上，为支持虚拟存储器功能而增加了请求调页和页面置换功能。在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可启动作业运行。在作业执行过程中，当所访问的页面不在内存时，再通过请求调页功能将其从外存调入内存；当内存空间不够时，通过页面置换功能将内存中暂时用不到的页面换出到外存。
为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。
### 1. 页表机制
相比于基本分页系统，在请求分页系统中，为了实现请求调页功能，操作系统需要知道每个页面是否已调入内存；若未调入，则还需要知道该页在外存中的存放地址。为了实现页面置换功能，操作系统需要通过某些指标来决定换出哪个页面；对于要换出的页面，还要知道其是否被修改过，以决定是否写回外存。为此，在请求页表项中增加了4个字段，如图3.20所示。
[tbl-93.md](tbl-93.md)
图3.20 请求分页系统中的页表项
增加的4个字段说明如下：
- 状态位 $P$。标记该页是否已调入内存，供程序访问时参考。
- 访问字段 $A$。记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考。
- 修改位 $M$。标记该页在调入内存后是否被修改过，以决定换出时是否写回外存。
- 外存地址。记录该页在外存的存放地址，通常是物理块号，供调入该页时参考。
### 2. 缺页中断机构
图3.21 缺页处理的过程及效率分析（2011、2013、2014、2020、2022）
图3.22 缺页异常导致进程状态的变化（2023）
在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，请求操作系统的缺页中断处理程序处理。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。若内存中有空闲页框，则为进程分配一个页框，将所缺页面从外存装入该页框，并修改页表中相应的表项。若内存中没有空闲页框，则由页面置换算法选择一个页面淘汰，若该页在内存期间被修改过，则还要将其写回外存。未被修改过的页面不用写回外存。
缺页中断作为中断，同样要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等几个步骤。但与一般的中断相比，它有以下两个明显的区别：
- 在指令执行期间而非一条指令执行完后产生和处理中断，属于内部异常。
<!-- page: 227 -->
- 一条指令在执行期间，可能产生多次缺页中断。
## 3. 地址变换机构
在基本分页系统地址变换机构的基础上，为实现虚拟内存，增加了产生和处理缺页中断，及从内存中换出一页的功能，请求分页系统中的地址变换过程如图3.21所示。
图3.21 请求分页中的地址变换过程
**创建规程** ▶ 分页系统的地址变换过程及分析（2009、2010、2014、2024）
请求分页系统的地址变换过程如下：
① 先检索快表，若命中，则从相应表项中取出该页的物理块号，并修改页表项中的访问位，以供置换算法换出页面时参考。对于写指令，还需要将修改位置为1。
② 若快表未命中，则要到页表中查找，若找到，则从相应表项中取出物理块号，并将该页表项写入快表，若快表已满，则需采用某种算法替换。
③ 若在页表中未找到，则需要进行缺页中断处理，请求系统将该页从外存换入内存，页面被调入内存后，由操作系统负责更新页表和快表，并获得物理块号。
④ 利用得到的物理块号和页内地址拼接形成物理地址，用该地址去访存。
## 3.2.3 页框分配
### 1. 驻留集大小
对于分页式的虚拟内存，在进程准备执行时，不需要也不可能将一个进程的所有页都读入主存。因此，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。给一个进程分配的页框的集合就是这个进程的驻留集。需要考虑以下两点：
1）驻留集越小，驻留在内存中的进程就越多，可以提高多道程序的并发度，但分配给每个进程的页框太少，会导致缺页率较高，CPU需耗费大量时间来处理缺页。
<!-- page: 228 -->
2）驻留集越大，当分配给进程的页框超过某个数量时，再为进程增加页框对缺页率的改善是不明显的，反而只能是浪费内存空间，还会导致多道程序并发度的下降。
## 2. 内存分配策略
在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局和局部置换。于是可组合出下面三种适用的策略。
### 附属建议
**页面分配与置换策略的名称（2015）**
#### （1）固定分配局部置换
为每个进程分配固定数量的物理块，在进程运行期间都不改变。所谓局部置换，是指若进程在运行中发生缺页，则只能从分配给该进程在内存的页面中选出一页换出，然后再将所缺页面调入，以保证分配给该进程的内存空间不变。实现这种策略时，难以确定应为每个进程分配的物理块数量：太少会频繁出现缺页中断，太多又会降低CPU和其他资源的利用率。
**注意**
全局置换意味着一个进程拥有的物理块数量必然会变，因此不可能与固定分配组合。
#### （2）可变分配全局置换
先为每个进程分配一定数量的物理块，在进程运行期间可根据情况适当地增加或减少。所谓全局置换，是指若进程在运行中发生缺页，则系统从空闲物理块队列中取出一块分配给该进程，并将所缺页面调入。这种方法比固定分配局部置换更加灵活，可以动态增加进程的物理块，但也存在弊端，如它会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降。
#### （3）可变分配局部置换
为每个进程分配一定数量的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，因此不会影响其他进程的运行。若进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直至该进程的缺页率趋于适当程度；反之，若进程在运行中的缺页率特别低，则可适当减少分配给该进程的物理块，但不能引起其缺页率的明显增加。这种方法在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力。当然它需要更复杂的实现，也需要更大的开销，但对比频繁地换入/换出所浪费的计算机资源，这种牺牲是值得的。
页面分配策略在2015年的统考选择题中出现过，考查的是这三种策略的名称。往年很多读者看到这里时，由于认为不是重点，复习时便一带而过，最后在考试中失分。在这种基础题上失分是十分可惜的。再次提醒读者，考研成功的秘诀在于“全面”和“反复多次”。
## 3. 物理块调入算法
采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法。
1）平均分配算法，将系统中所有可供分配的物理块平均分配给各个进程。
2）按比例分配算法，根据进程的大小按比例分配物理块。
3）优先权分配算法，为重要和紧迫的进程分配较多的物理块。通常采取的方法是将所有可分配的物理块分成两部分：一部分按比例分配给各个进程；一部分则根据优先权分配。
## 4. 调入页面的时机
为确定系统将进程运行时所缺的页面调入内存的时机，可采用以下两种调页策略：
1）预调页策略。根据局部性原理，一次调入若干个相邻的页面会比一次调入一页更高效。但若提前调入的页面中大多数都未被访问，则又是低效的。因此，可以预测不久之后可能被
<!-- page: 229 -->
访问的页面，将它们预先调入内存，但目前预测成功率仅约 50%。因此这种策略主要用于进程的首次调入，由程序员指出应先调入哪些页。
2）请求调页策略。进程在运行中需要访问的页面不在内存，便提出请求，由系统将其所需页面调入内存。由这种策略调入的页一定会被访问，且比较易于实现，因此目前的虚拟存储器大多采用此策略。其缺点是每次仅调入一页，增加了磁盘 I/O 开销。
预调页实际上就是运行前的调入，请求调页实际上就是运行期间的调入。
## 5. 从何处调入页面
请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区，也称交换区。对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘 I/O 速度比文件区的更快。这样，当发生缺页请求时，系统从何处将缺页调入内存就分为三种情况：
1）系统拥有足够的对换区空间。可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
2）系统缺少足够的对换区空间。凡是不会被修改的文件都直接从文件区调入；当换出这些页面时，由于它们不会被修改而不必再换出。但对于那些可能被修改的部分，在将它们换出时必须放在对换区，以后需要时再从对换区调入（因为读比写的速度快）。
3）UNIX方式。与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面，因为放在对换区，所以在下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则不需要再从对换区调入。
## 6. 如何调入页面
当进程所访问的页面不在内存中时（存在位为 0），便向 CPU 发出缺页中断，中断响应后便转入缺页中断处理程序。该程序通过查找页表得到该页的物理块，此时，若内存未满，则启动磁盘 I/O，将所缺页调入内存，并修改页表。若内存已满，则先按某种置换算法从内存中选出一页准备换出；若该页未被修改过（修改位为 0），则不需要将该页写回磁盘；但是，若该页已被修改（修改位为 1），则必须将该页写回磁盘，然后将所缺页调入内存，并修改页表中的相应表项，置其存在位为 1。调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址。
## 3.2.4 页面置换算法
进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页，换出到外存。选择调出哪个页面的算法就称为页面置换算法。页面的换入、换出需要磁盘 I/O，开销较大，因此好的页面置换算法应该追求更低的缺页率。
**前言简介** 各种页面置换算法的特点：哪种可能导致 Belady 异常（2014）
常见的页面置换算法有以下四种。
### 1. 最佳（OPT）置换算法
最佳置换算法选择淘汰的页面是以后永不使用的页面，或是在最长时间内不再被访问的页面，以便保证获得最低的缺页率。然而，人们目前无法预测进程在内存的若干页面中哪个是未来最长时间内不再被访问的，因此该算法无法实现。但可利用该算法去评价其他算法。
假定系统为某进程分配了三个物理块，并考虑有页面号引用串：
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
进程运行时，先将 7,0,1 三个页面依次装入内存。当进程要访问页面 2 时，产生缺页中断，
<!-- page: 230 -->
根据最佳置换算法，选择将第18次访问才需调入的页面7淘汰。然后，访问页面0时，因为它已在内存中，所以不必产生缺页中断。访问页面3时，又会根据最佳置换算法将页面1淘汰……以此类推，如图3.22所示，从图中可以看出采用最佳置换算法时的情况。
[tbl-94.md](tbl-94.md)
图3.22 利用最佳置换算法时的置换图
可以看到，发生缺页中断的次数为9，页面置换的次数为6。
最长时间不被访问和以后被访问次数最小是不同的概念，在理解OPT算法时不要混淆。
## 2. 先进先出（FIFO）页面置换算法
FIFO 算法选择淘汰的页面是最早进入内存的页面。该算法实现简单，将内存中的页面根据调入的先后顺序排成一个队列，需要换出时选择队头的页面。但该算法没有利用局部性原理，与进程实际运行的规律不相适应，最早进入内存的页面也可能经常被访问，因此性能较差。
**前图3.22** FIFO算法的应用分析（2010）
这里仍用上面的例子采用FIFO算法进行置换。当进程访问页面2时，将最早进入内存的页面7换出。然后访问页面3时，将2,0,1中最先进入内存的页面0换出。由图3.23可以看出，利用FIFO算法时进行了12次页面置换，比最佳置换算法正好多一倍。
[tbl-95.md](tbl-95.md)
图3.23 FIFO置换算法时的置换图
FIFO算法还会产生当为进程分配的物理块增多，缺页次数不减反增的异常现象，称为Belady异常。例如，页面访问顺序为3,2,1,0,3,2,4,3,2,1,0,4，当分配的物理块为3个时，缺页次数为9次；当分配的物理块为4个时，缺页次数为10次，如图3.24所示。
[tbl-96.md](tbl-96.md)
图3.24 Belady异常
只有FIFO算法可能出现Belady异常，LRU和OPT算法永远不会出现Belady异常。
<!-- page: 231 -->
## 3. 最近最久未使用（LRU）置换算法
LRU算法选择淘汰的页面是最近最长时间未使用的页面，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的页面。
### 创建测验
**LRU算法的应用分析（2009、2015、2019）**
再对上面的例子采用LRU算法进行置换，如图3.25所示。进程第一次访问页面2时，将最近最久未使用的页面7换出。然后在访问页面3时，将最近最久未使用的页面1换出。
访问页面 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
[tbl-97.md](tbl-97.md)
图3.25 LRU页面置换算法时的置换图
在图3.25中，前5次置换的情况与最佳置换算法相同，但两种算法并无必然联系。实际上，LRU算法根据各页以前的使用情况来判断，是“向前看”的；而最佳置换算法则根据各页以后的使用情况来判断，是“向后看”的。而页面过去和未来的走向之间并无必然联系。
OPT算法性能最好，但无法实现。FIFO算法实现简单，但性能较差。LRU算法性能较好，但实现起来需要寄存器和线的硬件支持，开销较大。
## 4. 时钟（CLOCK）置换算法
LRU算法的性能接近OPT算法，但实现起来的开销大。因此，操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU算法的性能，这类算法都是CLOCK算法的变体。
### （1）简单的CLOCK置换算法
**创建测验** 类CLOCK置换算法的过程分析（2012）
为每个页面设置一个访问位，当某页首次被装入或被访问时，其访问位被置为1。算法将内存中的页面链接成一个循环队列，并有一个替换指针与之相关联。当某一页被替换时，该指针被设置指向被替换页面的下一页。在选择淘汰一页时，只需检查页面的访问位；若为0，就选择该页换出；若为1，则将它置为0，暂不换出，给予该页第二次驻留内存的机会，再依次顺序检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则返回到队首去循环检查。因为该算法是循环地检查各个页面的使用情况，所以称为CLOCK算法。但是，因为该算法只有一位访问位，而置换时将未使用过的页面换出，所以也称最近未用（NRU）算法。
**创建测验** CLOCK算法的应用分析（2010）
假设页面访问顺序为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 3, 2，采用简单CLOCK置换算法，分配4个页帧，每个页对应的结构为（页面号，访问位），置换过程如图3.26所示。
访问顺序 7 0 1 2 0 3 0 4 2 3 0 3 2 1 3 2
[tbl-98.md](tbl-98.md)
图3.26 CLOCK算法时的置换图
<!-- page: 232 -->
首次访问7,0,1,2时，产生缺页中断，依次调入主存，访问位都置为1。访问0时，已存在，访问位置为1。访问3时，产生第5次缺页中断，替换指针初始指向帧1，此时所有帧的访问位均为1，则替换指针完整地扫描一周，将所有帧的访问位都置为0，然后回到最初的位置（帧1），替换帧1中的页（包括置换页面和置访问位为1），如图3.27(a)所示。访问0时，已存在，访问位置为1。访问4时，产生第6次缺页中断，替换指针指向帧2（上次替换位置的下一帧），帧2的访问位为1，将其修改为0，继续扫描，帧3的访问位为0，替换帧3中的页，如图3.27(b)所示。然后依次访问2,3,0,3,2，均已存在，每次访问都将其访问位置为1。访问1时，产生缺页中断，替换指针指向帧4，此时所有帧的访问位均为1，又完整扫描一周并置访问位为0，回到帧4，替换之。访问3时，已存在，访问位置为1。访问2时，产生缺页中断，替换指针指向帧1，帧1的访问位为1，将其修改为0，继续扫描，帧2的访问位为0，替换帧2中的页。
图3.27 缺页中断时替换指针扫描示意图
（2）改进型 CLOCK 置换算法
**套装追尾**> 改进 CLOCK 算法的思想（2018）
**套装追尾**> 改进 CLOCK 算法的应用分析（2016、2021）
将一个页面换出时，若该页已被修改过，则要将该页写回磁盘，若该页未被修改过，则不必将它写回磁盘。可见，对于修改过的页面，替换代价更大。在改进型 CLOCK 算法中，除考虑页面使用情况外，还增加了置换代价——修改位。在选择页面换出时，优先考虑既未使用过又未修改过的页面。由访问位 $A$ 和修改位 $M$ 可以组合成下面四种类型的页面：
- 1 类 $A = 0, M = 0$：最近未被访问，且未被修改，是最佳的淘汰页。
- 2 类 $A = 0, M = 1$：最近未被访问，但已被修改，是次佳的淘汰页。
- 3 类 $A = 1, M = 0$：最近已被访问，但未被修改，可能再被访问。
- 4 类 $A = 1, M = 1$：最近已被访问，且已被修改，可能再被访问。
内存中的每页必定都是这四类页面之一。在进行页面置换时，可采用与简单 CLOCK 算法类似的算法，差别在于该算法要同时检查访问位和修改位。算法执行过程如下：
1）从指针的当前位置开始，扫描循环队列，寻找 $A = 0$ 且 $M = 0$ 的1类页面，将遇到的第一个1类页面作为选中的淘汰页。在第一次扫描期间不改变访问位 $A$。
2）若第1）步失败，则进行第二轮扫描，寻找 $A = 0$ 且 $M = 1$ 的2类页面。将遇到的第一个2类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
3）若第2）步也失败，则将指针返回到开始的位置，并将所有帧的访问位复0。重复第1）步，并且若有必要，重复第2）步，此时一定能找到被淘汰的页。
改进型 CLOCK 算法优于简单 CLOCK 算法的地方在于，可减少磁盘的 I/O 操作次数。但为了找到一个可置换的页，可能要经过几轮扫描，即实现算法本身的开销将有所增加。
操作系统中的页面置换算法都有一个原则，即尽可能保留访问过的页面，而淘汰未访问过的页面。简单的 CLOCK 算法只考虑页面是否被访问过；改进型 CLOCK 算法对这两类页面做了细
<!-- page: 233 -->
分，分为修改过和未修改过的页面。因此，若有未使用过的页面，则当然优先将其中未修改过的页面换出。若全部页面都使用过，还是优先将其中未修改过的页面换出。
## *3.2.5 抖动和工作集
### 1. 抖动
在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出内存，这种频繁的页面调度行为称为抖动或颠簸。
#### 问题解答 ➔ 抖动的处理措施（2011）
系统发生抖动的根本原因是，分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页，必须请求系统将所缺页面调入内存。显然，对磁盘的访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，进而导致发生CPU利用率急剧下降并趋于零的情况。
抖动是进程运行时出现的严重问题，必须采取相应的措施解决它。由于抖动的发生与系统为进程分配物理块的多少（驻留集）有关，于是又提出了关于进程工作集的概念。
### 2. 工作集
工作集是指在某段时间间隔内，进程要访问的页面集合。一般来说，工作集 $W$ 可由时间 $t$ 和工作集窗口尺寸 $\Delta$ 来确定。例如，某个进程对页面的访问次序如下：
$$
1, 4, \boxed{2, 3, 5, 3, 2}, 2, 1, 1, 1, 3, 4, 5, 4, \boxed{4, 2, 1, 1, 3}, 3
$$
$$
t_1
$$
$$
t_2
$$
#### 问题函数 ➔ 工作集的应用分析（2016）
假设工作集窗口尺寸 $\Delta$ 设置为 5，则在 $t_1$ 时刻，进程的工作集为 $\{2,3,5\}$，$t_2$ 时刻，进程的工作集为 $\{1,2,3,4\}$。实际应用中，工作集窗口会设置得很大，对于局部性好的程序，工作集大小一般会比工作集窗口 $\Delta$ 小很多。工作集反映了进程在接下来的一段时间内很有可能频繁访问的页面集合，因此驻留集大小不能小于工作集大小，否则进程在运行过程中会频繁缺页。
## 3.2.6 页框回收
本节是2025年大纲新增考点，2012年统考真题45题实际上已涉及页框回收，该题对页框回收过程的描述是“被系统回收的页框，放入空闲页框链尾，其中内容在下一次分配之前不清空”，该描述便是对页面缓冲算法中空闲页面链表的定义，因此本节主要介绍页面缓冲算法。页框回收算法较复杂，且常见的操作系统教材中也未介绍页框回收算法的内容，而主要存在于一些深入讲解Linux系统的图书中，408考查的概率也很低，因此本书不做介绍。