第三章内存管理¶

补充反置页表

【考纲内容】¶

Note

（一）内存管理基础

内存管理概念：逻辑地址与物理地址空间，地址变换，内存共享，内存保护，内存分配与回收
连续分配管理方式；
页式管理；
段式管理；
段页式管理

（二）虚拟内存管理

虚拟内存基本概念；
请求页式管理；
页框分配与回收；(回收是25考纲的新增考点)
页置换算法
内存映射文件（Memory-Mapped Files）；
虚拟存储器性能的影响因素及改进方式

【本章学习建议】¶

Note

程序的链接与装入这块要理解逻辑地址与物理地址的形成时间，以及静态链接与动态链表的区别，三种装入方式的区别 2.

【考频统计】¶

年份	考点	分值
2009	选择题：内存保护、分段存储管理的地址转换应用题：请求分页管理、访存时间分析、页面置换算法、驻留集、虚实地址转换	4+8=$12$分
2010	选择题：动态分区分配存储管理、动态分配分区算法、两级页表地址转换应用题：地址转换、页面置换算法($FIFO$、$CLOCK$)	4+8=$12$分
2011	选择题：缺页处理、抖动、地址变换、程序的连接与装入应用题：计组那里考了虚拟存储，涉及了虚实地址转换与$TLB$	3*2=$6$分
2012	选择题：虚拟存储的基本概念、虚拟存储容量应用题：请求分页存储管理、驻留集、页面置换算法、局部性原理	2+8=$10$分
2013	选择题：缺页中断、内存保护应用题：基本分页存储管理（二级页表、地址转换）	2+8=$10$分
2014	选择题：虚实地址转换、$TLB$、页面置换算法、多级页表	3*2=$6$分
2015	选择题：页面置换算法($LRU$)、【页面分配策略、页面置换策略】(可变/固定分配、全局/局部置换) 应用题：基本分页存储、二级页表、虚实地址转换	2*2+6=$10$分
2016	选择题：页面置换算法(改进型$CLOCK$)、分段存储管理的地址转换、工作集应用题：计组部分考察到了页式虚拟存储管理、$TLB$等	3*2=$6$分
2017	选择题：动态分区分配存储管理及回收、动态分配分区算法应用题：二级分页虚拟存储管理、地址转换	2+4=$6$分
2018	应用题：计组考察了与虚拟存储有关的问题，TLB、虚拟地址分析、页面置换算法(改进型$CLOCK$)、地址转换	$9$分
2019	选择题：分段存储管理、页置换算法、局部置换策略。二级分页存储管理地址转换、动态分区分配算法	4*2=$8$分
2020	选择题：请求分页存储管理访存时间分析应用题：请求分页存储管理、二级页表、地址转换、局部性原理	2+8=$10$分
2021	选择题：地址转换、页面置换算法(改进型$CLOCK$)、页表基址寄存器应用题：计组的存储系统部分考察了虚拟地址转换、$TLB$、页面置换算法	4+8=$12$分
2022	选择题：缺页处理、缺页率、页面置换算法、工作集	2*2=$4$分
2023	选择题：虚拟地址空间、页与页框号	2*2=$4$分

3.1 内存管理基础¶

3.1.1 程序的链接与装入¶

程序运行基本原理：

创建进程首先要将程序和数据装入内存，一般需要以下几个步骤

编译：由编译程序将用户源代码编译成为若干目标模块（就是把高级语言翻译成机器语言）
链接：由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块（即可执行文件）
装入：由装入程序将装入模块装入内存运行

【注】：

编译后，每个目标模块都从0号单元开始编址，但是这仅仅是相对于该模块的逻辑地址；

当链接程序将各个模块链接成一个完整的可执行目标程序时，将顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间(即虚拟地址空间)。（即链接后形成整个程序的完整逻辑地址空间）

操作系统通过内存管理部件MMU将进程使用的逻辑地址转换为物理地址。

【2011-30】在虚拟内存管理中，地址变换机构将逻辑地址变为物理地址，形成该逻辑地址的阶段是（）。

A. 编辑

B. 编译

C. 链接

D. 装载

解析

本题选C。

A错误。

B错误。编译：编译器将源代码转换为目标代码。

C正确。链接：在链接阶段，编译器将生成的目标代码与程序所需的库函数和其他目标文件进行链接，生成最终的可执行文件和该文件的逻辑地址（虚拟地址）。

D错误。装载：在装载阶段，操作系统将可执行文件从磁盘加载到物理内存中，并将程序的逻辑地址（虚拟地址）转换为物理地址。这个过程由地址变换机构（如页表或段表）完成。

程序的装入¶

装入模块在装入内存时有如下三种方式（重定位，完成逻辑地址到物理地址的转化）

装入方式	绝对装入	可重定位装入	动态运行时装入
适用场景	只适用于单道程序环境	多道	多道
物理地址生成时机	+ 编译时生成 + 如果起始地址改变，必须重新编译	+ 加载（装入）时生成 + 如果编译时起始地址未知，则编译器需要生成可重定位的代码 + 加载时，生成绝对(物理)地址	+ 执行时生成 + 执行时代码可移动 + 需要地址转换（映射）硬件的支持；
装入方式	在编译时，若知道程序将驻留在内存的某个位置，则编译程序将产生`绝对地址`的目标代码，装入时不需要对程序和数据的地址进行修改	根据内存的情况，将装入模块装入内存的适当位置，地址变化通常是在装入时一次完成的，所以又称之为`静态重定向`	装入程序把装入模块装入内存后，并不立即进行重定向，而是把这种地址转换推迟到程序真正要开始执行时才进行，所以又称为`动态重定向`
装入要求		1. 在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。 2. 作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。	+ 可以将程序分配到不连续的存储区 + 便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间（虚拟存储技术） + 在程序运行之前可以只装入部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；
适用的内存分配策略	与单一连续分配搭配（整个内存空间只有一道作业，无需移动地址）	固定分区分配；	动态分区分配；(请求)分页；(请求)分段、段页式都可以
备注	程序中所用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时再转换为绝对地址	必须要有足够的物理内存空间确保进程的物理地址连续（与连续分配配合使用）	+ 装入内存后的所有地址均为相对地址； + 允许程序在内存中发生移动；（在运行过程中程序在内存中的位置可能经常要改变，例如，在具有对换功能的系统中，一个进程可能被多次换出，又多次被换入，每次换入后的位置通常是不同的，这时就应该用动态重定位）

程序的链接¶

其中程序的链接有如下三种方式（该阶段生成完整的逻辑地址）

静态链接：在程序运行开始之前，先将各目标模块及他们所需要的库函数链接成一个完整的装入模块，以后不再拆开。
装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。其优点是便于修改和更新，便于实现对目标模块的共享（将一个目标模块链接到几个应用模块上）。

例如在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要修改目标模块中的相对地址。

运行时动态链接：在程序执行中需要某目标模块时，才对它进行链接。凡在程序执行中未用到的目标模块，都不会被调入内存和链接到装入模块上。其优点是能加快程序的装入过程，还可节省内存空间。

链接指的是把标准库连入程序的虚拟地址空间，静态链接在磁盘中就完成这一步，而动态链接在OS修改页表的一瞬间才链入主程序的虚拟地址空间；

装入时动态链接在装入模块的时候修改页表，具体来说，是主程序装入内存的时候看需要哪个动态库，就一起装入内存并修改页表；而运行时动态链接是主程序在执行的时候，运行到了某个函数发现是某个动态库里面的，就去把这个动态库调入内存并且修改页表。

关于静态链接与运行时动态链接的更详细说明：

假设你在编写一段代码，需要使用加法函数，考虑到这个函数可能其它入也需要，因此单独放到一个源文件中，其它类似的函数也一样。
接下来是编译过程，先编译成目标文件，链接器把目标文件打包成最终的可执行程序。

由于你实现的加减乘除等函数非常好用，广受其它程序员的欢迎，因此你写的代码渐渐的变成了一种标准，所有程序员都遵循，标准库就是这么诞生的。

当然，你写的代码也可能根本没有其它入用，只能当做你自己使用的普通库，实际上这才是入生常态，这样的非标准库还是留着自己用吧。
不管是标准库还是非标准库对后续的讲解都是一样的，因此我们以标准库为例来讲解。
现在有了标准库，所有入都很开心，终于不用重复造轮子了。但是很快你会发现，及时写一个最简单的hello world程序，也不得不重新编译一堆标准库代码。

由于标准库编译耗时很长，这显然是难以接受的（对老板来说），该怎么解决重复编译标准库的问题呢。很简单，可以提前把标准库编译出来。

这样我们再次编译自己的项目时直接跳过标准库的编译过程，直接把标准库链接到最终的可执行程序中。

接下来我们来到了第二阶段，链接。
链接器从表面看实际上是一个打包器，把各种目标文件，也就是你的代码和标准库打包起来，如果还有其它库也是一样的道理，经过链接会生成最终的可执行程序。

注意看最终的可执行程序中，包含了你的代码和使用的库，这种将所有代码打包到可执行程序的链接方式叫做静态链接。

执行程序当然是保存在磁盘中的，接下来我们双击运行这个程序。
此时会在内存中划分出一块区域，这就是进程内存映像里的堆区、栈区、数据和代码区等。

这时会把可执行程序中的指令都拷贝到代码区，这就是程序运行的最基本原理。显然计算机系统里不会只有一个程序。可能会有很多个，如果所有程序都采用静态链接会怎样呢？
如果都是静态链接，那么这些程序都保存一份标准库，由于是标准库，因此它们的内容都是一样的，最终这些程序都保存在磁盘上，占据磁盘空间：

而在运行起来后同样会占用内存空间。注意看这里和这里，它们的内容都是一样的，这显然是在浪费宝贵的存储资源。

问题出在哪里呢？注意看这里，每个可执行程序都包含有一份标准库。

这就像什么呢？这就像一本非常厚的书，这本书把引用到的所有内容到装订在一起。好处当然是更方便读者阅读引用到的内容，但问题就是这样的书太厚重了，更好的方法是把引用到内容放在一页参考文献中而不要打包在一起，这样一本书就很轻量了。

可执行程序也是一样的道理，我们不再打包一切而是使用参考文献。
这就是所谓的动态链接。
这时提前编译好的库就是动态库，linux下以.so为结尾，windows中是dll文件。

这时的可执行程序中不再包含完整的动态库代码，而是只有一份参考文献，你可以想象一下，这里肯定保存了两项基本信息，依赖了哪个库，这个库保存在了哪里。

这样及时有再多的可执行程序也不怕，因为我们只需要保存一份标准库。动态链接的程序该怎么运行呢？依然是把可执行程序拷贝到代码区，然后根据参考文献把动态库加载进来，这时才是真正的链接，也就是所谓的动态链接，我们把链接这个过程从编译期推迟到了运行时。

如果是其它程序运行呢？道理也一样。动态链接下每个程序中不会有一份标准库，而是大家共享内存中的同一份标准库。
这样利用动态链接我们不但节省了磁盘空间也节省了内存空间。

3.1.2 内存管理的主要功能：¶

内存空间的分配与回收。由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率。
地址转换。在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址。
内存空间的扩充。利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。
内存共享。指允许多个进程访问内存的同一部分。例如，多个合作进程可能需要访问同一块数据，因此必须支持对内存共享区域进行受控访问。
存储保护。保证各道作业在各自的存储空间内运行，互不干扰。

3.1.2.1 内存空间的分配与回收¶

操作系统需要负责内存空间的分配与回收，例如

如何标记哪些区域已经被划分出去了，哪些又还是空闲的？
当进程运行结束之后，如何将进程占用的内存空间回收？
进程应该放在内存哪个位置？

内存分配策略的演化：

单一连续分配→固定分区分配 → 动态分区分配 → 离散分配方式（页式管理存储、分段管理存储）

3.1.2.2 内存空间的扩展¶

我们知道，运行一个程序时，需要将该程序调入内存，然后根据局部性原理，内存中的部分相关数据会调入Cache以提高性能。那么现在的问题是，一个程序调入内存时需要全部调入吗，还是只需要调入一部分就可以了呢？答案是部分即可。这一点大家可以联系我们日常使用的手机就能明白，手机内存有限，但是可以同时运行多个大体积程序。这就是虚拟存储系统：实际物理内存很有限，但是运行时似乎很大很大

tips：游戏开局（比如英雄联盟）前面，会有一段加载资源的过程，也就是“loading”其实其中绝大部分的工作就是将相关数据从辅存调入主存

其实操作系统仍然会将程序分页，程序加载进主存时，会加载一部分，也就是说有的页已经加载进了主存，有的页还留在辅存中

内存空间的扩展主要有三种方式：（运行在多道程序环境下）

覆盖技术
交换技术
虚拟存储技术（后面单独详细介绍）

Note

覆盖与交换均不在大纲，了解即可

覆盖技术：主要用来解决程序大小超过物理内存总和的问题¶

性质：同一作业，进程内部进行覆盖。

基本思想：将程序分为多个段（多个模块）,要求段与段之间相对独立，没有直接的联系，不能相互之间交叉访问(虚拟存储技术则没有这种要求)

需要常驻内存的段放在固定区，调入后不再调出
当需要访问其他段时，将其调入内存中的覆盖区，替换覆盖区的原有段。而固定区的段不被覆盖。

示例：如下有一段程序，其中A模块会依次调用B模块和C模块（也就是说A不会同时调用B和C），B模块会调用D模块，而C模块又会依次调用E模块和F模块。因此

对于A模块来说，它要单独占用空间
对于B模块和C模块来说，他们不会同时被调入，因此同一时间只开辟一片空间即可，大小依最大的模块而定
对于D、E和F模块他们也不会被同时调入，因此只需要一片空间即可

优点：打破了必须将一个进程的全部信息装入内存后才能运行的限制，而且内存中能够更新的地方只会是在覆盖区的段

缺点：必须由程序员声明覆盖结构，操作系统完成自动覆盖。对用户不透明，增加编程难度。只适用于早期的OS，已成为历史.

交换¶

交换技术：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已经具备运行条件的进程换入内存

中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。

性质：不同作业，进程之间进行交换

注意问题

1：具有对换功能的操作系统中，通常会把磁盘空间划分为文件区和对换区两部分：

其中文件区主要用于存放文件，追求存储空间利用率，因此对文件区空间的管理采用离散分配方式；
对换区空间仅占一小部分。被换出的进程数据就存放在对换区。由于对换的速度直接影响系统的整体速度，因此对换区空间的管理主要追求换入换出速度，所以对换区采用连续分配方式。
总之，对换区的I/O速度要远快于文件区
注意：交换技术有个要求，所有的应用程序要支持动态重定位。

2：一般来说，在许多进程运行且内存吃紧的时候就要进行交换

3：以下进程可以优先考虑换出

阻塞进程
优先级较低进程
驻留时间短的进程\ …

需要注意PCB是会常驻内存的，并不会被换出

4：为了有效使用CPU，需要每个进程的执行时间比交换时间长；

5：交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用起来很快；

3.1.2.3 地址转换¶

为了使编程更加方便，程序员写程序时应该只需要关注指令、数据和逻辑地址，而逻辑地址到物理地址的转换（这个过程称为地址重定位）应该由操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况。（上面介绍的三种装入方式就是用来完成地址转换的）

地址生成过程

3.1.2.4 内存保护¶

为避免主存中多道程序相互干扰,防止某程序出错而破坏其他程序的正确性,或某程序不合法地访问其他程序或数据区,应该对每个程序进行存储保护,包括操作系统程序和用户程序。为了对操作系统存储保护提供支持,硬件必须具有以下3种基本功能。

支持至少两种特权模式：即内核态和用户态
使部分CPU状态只能由操作系统内核程序进行读写而用户进程不能读写；

特权模式位、页表首地址、TLB内容等都只能由操作系统内核程序通过特殊的指令(一般称为管态指令或特权指令)进行访问。常用的管态指令(特权指令)包括刷新cache、刷新TLB、改变特权模式、输入/输出、停止处理器执行等。

提供让CPU在管理模式和用户模式之间相互转换的机制。

执行系统调用指令、响应异常和中断、异常和中断处理后的“返回”指令\ 硬件通过提供相应的专用寄存器、专门的指令、专门的状态/控制位等,和操作系统一起实现上述3个功能。通过这些功能,并把页表保存在操作系统的地址空间,操作系统就可更新页表,并防止用户进程改变页表,以确保用户进程只能访问由操作系统分配给的存储空间。

所谓内存保护，就是保证各个进程在各自的存储空间内运行，互不干扰

存储区域保护
方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令在访问地址时，CPU进行越界检查

方法二：采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址；界地址寄存器存放的是进程的最大逻辑地址

一般来说重定位寄存器整个系统就一个，因为CPU同一时刻只执行一条指令或访问数据。而且寄存器成本高，设置多了也不现实。

注意两个寄存器的区别，一个用来“比”，一个用来“加”；加载这两个寄存器时必须使用特权指令，只有操作系统内核才可以加载这两个存储器，因此允许OS内核对其修改，而不允许用户程序修改。

以上提到的内存保护属于存储区域保护，就是看是否发生了“地址越界”，即是否访问了不该访问的区域。

【2009-26】分区分配内存管理方式的主要保护措施是（）。

A. 界地址保护

B. 程序代码保护

C. 数据保护

D. 栈保护

解析

本题选A。

界地址保护是分区分配内存管理方式的主要保护措施之一。界地址保护的目的是确保每个分配的内存区域不会超出其分配的边界。在分区分配内存管理方式中，内存被划分为不同的区域或分区，每个分区用于分配给不同的进程或任务使用。界地址保护通过在每个分区的边界处设置特定的地址值或标记来实现。当一个进程试图访问其分配的内存区域之外的地址时，界地址保护机制会触发一个异常或错误，阻止进程越界访问。这可以防止进程意外修改或访问其他进程的内存，保护了进程间的数据隔离性和安全性。通过界地址保护，每个进程的内存访问范围被限制在其分配的边界内，防止了内存越界操作和非法访问，从而提高了系统的稳定性和安全性。

还有一种保护即访问方式保护，就是看是否发生了“访问越权”，若实际访问操作与访问权限不符，则发生存储保护错。

例如，即使进程访问的逻辑地址未越界，但是如果该进程在用户态下访问了内核空间或者访问了未被授权的地址，则会触发地址越界异常。

Note

通常通过在页表或段表中设置访问权限位来实现这种保护。一般规定：

各程序对本程序所在的存储区可读可写;
对共享区或已获授权的其他用户信息可读不可写;
而对未获授权的信息(如操作系统内核、页表等)不可访问。
通常,数据段可指定为可读可写或只读;程序段可指定只可执行或只读。（2023年28题）

3.1.2.5 内存共享¶

并不是所有的进程内存空间都适合共享，只有那些只读的区域才可以共享。
可重入代码的共享：可重入代码又称为纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码。但在实际执行时，也可以为每个进程配以局部数据区，把在执行中可能改变的部分复制到该数据区，这样，程序在执行时只需对该私有数据区中的内存进行修改，并不去改变共享的代码。

可重入代码示例

可重入代码（Reentrant Code）是指在某个执行线程中可以中断并且被另一线程调用，同时能正确地完成操作的代码。它的主要特点包括：

无共享数据：可重入代码不依赖于在多个调用之间共享的静态或全局变量。这些变量会在每次调用时重新初始化，或者通过参数传递。
无副作用：可重入代码不会在执行过程中修改静态或全局变量，不会引发不可预期的副作用。
局部数据：所有需要在多次调用中保持的数据，都必须通过函数参数传递或在函数内部以局部变量的形式存在。

示例代码：

一个典型的可重入代码示例如下：

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

这个递归函数计算阶乘。它是可重入的，因为：

它不使用静态或全局变量。
它仅依赖于参数 n 和局部变量。
每次调用都是独立的，没有共享状态。

不可重入代码示例：

相对地，一个不可重入的代码示例如下：

int counter = 0;

void increment_counter() {
counter++;
}

这个代码不可重入，因为：

它使用了全局变量 counter。
如果在中断中或多个线程同时调用 increment_counter，可能导致竞争条件，从而导致不可预期的结果。

不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）;

【应用实例】考虑一个可以同时容纳40个用户的多用户系统，他们同时执行一个文本编辑程序，若该程序有160KB代码区和40KB数据区，则共需8000KB的内存空间来支持 40 个用户。如果160KB代码是可分享的纯代码，则不论是在分页系统中还是在分段系统中，整个系统只需保留一份副本即可，此时所需的内存空间仅为40KBx40+160KB=1760KB。

对于分页系统，假设页面大小为 4KB，则代码区占用40个页面、数据区占用10个页面。为实现代码共享，应在每个进程的页表中都建立40个页表项，它们都指向共享代码区的物理页号。此外，每个进程还要为自己的数据区建立10个页表项，指向私有数据区的物理页号。

对于分段系统，由于是以段为分配单位的，不管该段有多大，都只需为该段设置一个段表项（指向共享代码段始址，以及段长160KB)。由此可见，段的共享非常简单易行。

3.1.3 连续分配管理方式¶

连续分配方式是指为一个用户程序分配一个连续的内存空间，主要有：

分配方式	单一连续分配	固定分区分配	动态分区分配
作业道数	内存中仅有一道用户程序	多道，<= N(用户空间划为N块)	多道
内存分配	系统区：位于内存低地址处，用于存放操作系统相关数据；用户区：位于内存高地址处，用于存放用户程序相关数据。	`系统区`：操作系统用； `用户区`：整个用户空间划分为若干固定大小的分区，在每个分区中只装入一道作业,进程与分区一一对应.；	`系统区`：操作系统用； `用户区`：不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区。因此系统分区的大小和数目是可变的

优点	实现简单；可以采用覆盖技术扩充内存；不一定需要采取内存保护（单道不冲突）	实现简单，无外部碎片；可采用静态重定位，适合嵌入式微型设备；
缺点	只能用于单道批处理；有内部碎片；存储器利用率低	当用户程序太大时，可能所有分区都无法满足，因此不得不采用覆盖解决，但是又会降低性能；会产生内部碎片，内存利用率低	随着时间的推移，会有越来越多的碎片，内存利用率下降；（解决：`紧凑技术`，对进程进行移动和整理，需要重定向寄存器支持）
碎片问题	有内部碎片，无外部碎片(只有一个区块)	有内部碎片，无外部碎片	无内部碎片，有外部碎片（动态分配才存在）
		分区说明表：利用一种数据结构，来实现各个分区的分配与回收。每个表项对应一个分区（通常按照大小排列），记录分区的大小、起始地址、状态；当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将其分配给该程序，然后修改状态为已分配	常考点：在回收分区后注意有可能需要合并的分区，包括了与上块合并、与下块合并、与上下块一起合并这三种情况，注意分区数目的变化

Note

内存碎片：空闲内存不能被利用
外部碎片：分配单元之间的未被使用内存
内部碎片：分配单元内部的未被使用内存（取决于分配单元大小是否与所需内存大小相等）

内部碎片是因为，因为分区大小固定，最后一块分区虽然分配给进程，但是总是装不满，所以产生内部碎片；

外部碎片是因为，因为分区大小等于段大小，所以每一段都填充满，没有内部碎片，但是因为段与段之间存在碎片，所以存在外部碎片；

“过量分配”，无法保证需要多少分配多少，但是被分配的空间之间没有缝隙，因此可能产生内部碎片而不会产生外部碎片。段式分配属于“按需分配”，需要多少分配多少，分配空间之间可能出现小的无法被利用的缝隙，因此会产生外部碎片而不会产生内部碎片。

动态分区分配的其他介绍：

采用的数据结构（主要有两种）¶

空闲分区表	空闲分区链
每个空闲分区对应一个表项；表项包含分区号、分区大小、分区起始地址等信息	每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可以记录分区大小等信息

基于顺序搜索的动态分区分配算法（顺序分配算法）¶

算法	首次适应算法(`First Fit`)	邻近适应算法(`Next Fit`)	最佳适应算法(`Best Fit`)	最坏适应算法(`Worst Fit`)
算法思想	从头到尾找到适合的分区	基于First Fit算法，如果每次都从上次查找结束位置开始检索，就能解决First Fit算法的缺点	优先适用更小的分区，以保留更多大分区	优先使用更大的分区，以防止产生太小的不可用的碎片
具体操作	+ 空闲分区以地址递增的次序排列，每次分配内存时都`从首地址开始` + 顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区	空闲分区以地址递增的次序排列（可以排成一个循环链表），每次分配内存时`从上次查找结束位置开始` 查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区	+ 空闲分区按容量递增次序链接 + 分配时顺序查找第一个大小能满足要求的`最小空间`的空闲分区 + 释放时，查找并且合并临近的空闲分区	+ 空闲分区按容量递减次序链接 + 分配时顺序查找第一个满足要求的`最大空间`的空闲分区 + 释放时，查找并且合并临近的空闲分区，并调整空闲分区列表顺序
优点	+ 综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序。 + 可以在高地址空间保留大内存块	不用每次都从低地址的小分区开始检索；算法开销小	+ 会有更多的大分区被保留下来，更能满足大进程需求 + 相对简单	+ 可以减少难以利用的小碎片 + 中等大小的分配较多时，效果最好
缺点	+ 每次都从链头开始查找，可能导致低地址部分出现很多小的空闲区（外部碎片），而每次分配查找时，又需要经过这些分区，所以增加了查找的开销	无论低地址、高地址他们被使用的概率是相同的。这样就导致了高地址部分的大分区可能会被划分为小分区，最终又导致了无分区可用。也就是说它隐含了最佳适应算法的缺点	+ 每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的外部碎片； + 算法开销大，回收分区后可能需要对空闲分区队列重新排序	+ 大分区容易被用完，不利于大进程； + 算法开销大，回收分区后可能需要对空闲分区队列重新排序
效果	$Simplest/Quickest/Best$	比首次适应差一点	性能通常很差	性能非常差

【2010-28】某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空闲），采用最佳适配 (Best Fit) 算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是（）。

A. 7MB

B. 9MB

C. 10MB

D. 15MB

解析

本题选B。

该算法全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。

分配过程如下图所示。

初始时主存空闲容量为55MB。

第一步分配15MB后有一个40MB的空闲分区。

第二步分配30MB后有一个10MB的空闲分区。

第三步释放15MB后有一个15MB的空闲分区和一个10MB的空闲分区。

第四步分配8MB，因为采用最佳适配算法，所以选择10MB的空闲分区分配8MB，之后有一个15MB的空闲分区和一个2MB的空闲分区。

第四步分配8MB，此时只有15MB的空闲分区能够分配8MB，所以选择15MB的空闲分区分配8MB，之后有一个9MB的空闲分区和一个2MB的空闲分区。此时主存中最大空闲分区的大小是9MB。

【2017-25】某计算机按字节编址，其动态分区内存管理采用最佳适应算法，每次分配和回收内存后都对空闲分区链重新排序。当前空闲分区信息如下表所示。

分区起始地址	20K	500K	1000K	200K
分区大小	40KB	80KB	100KB	200KB

回收起始地址为60K、大小为140KB的分区后，系统中空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是（）。

A. 3、20K、380KB

B. 3、500K、80KB

C. 4、20K、180KB

D. 4、500K、80KB

解析

本题选B。

回收起始地址为60K、大小为140KB的分区后，起始地址为20K、和起始地址为200K的空闲分区合并为一个40KB+140KB+200KB=380KB的新空闲分区，如下图所示：

此时系统中还剩3个空闲分区，空闲分区信息如下表所示。

分区起始地址500K1000K20K分区大小80KB100KB380KB

空闲分区链第一个分区的起始地址和大小分别是500K、80KB。

【2019-32】在下列动态分区分配算法中，最容易产生内存碎片的是（）。

A. 首次适应算法

B. 最坏适应算法

C. 最佳适应算法

D. 循环首次适应算法

解析

本题选C。

首次适应算法：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法的目的在于减少查找时间。

最佳适应算法：从全部空闲区中找出能满足作业要求的，且大小最小的空闲分区，这种方法能使碎片尽量小。

最差适应算法：它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使空闲链表中的结点大小趋于均匀。

循环首次适用算法：每次查找的起始位置是从上次查找位置的下一个位置开始，把最先能够满足要求的空闲区分配给作业。

当系统中存在多个不同大小的空闲分区时，如果选择最佳适应的方式去分配内存，会导致许多小的空闲分区被保留下来，而较大的分区被分割成较小的部分，从而增加了内存碎片的数量和总碎片的大小。相比而言，首次适应算法、最坏适应算法和循环首次适应算法相对来说更容易获得较大的连续空闲区，减少了内存碎片的发生。因此，最容易产生内存碎片的算法是最佳适应算法。

【2024-27】下列算法中，每次回收分区时仅合并大小相等的空闲分区的是

A. 伙伴算法

B. 最佳适应算法

C. 最坏适应算法

D. 首次适应算法

解析

本题选A。

A正确。伙伴算法即伙伴分配算法 (Buddy Allocation Algorithm) 将可用内存分割成大小相等、成对的“伙伴”块。当请求内存时，系统会找到大于等于请求大小的最小块，并分配给请求的大小，将剩余部分形成新的伙伴块。这种方法有利于减少外部碎片，但可能会生成一定量的内部碎片。

B错误。最佳适应算法 (Best Fit Algorithm) 是指在内存分配时，选择能够恰好满足需求并且剩余空间最小的可用空闲分区进行分配。

C错误。最坏适应算法 (Worst Fit Algorithm) 是指在内存分配时，选择能够满足需求的最大的可用空闲分区进行分配。

D错误。首次适应算法 (First Fit Algorithm) 是指在内存分配时，选择第一个能满足要求的空闲分区进行分配。

基于索引搜索的分配算法¶

基于顺序搜索的动态分区分配比较适用于不太大的系统，当系统很大时系统中的内存分区可能会很多，空闲分区链就可能很长，这时采用顺序搜索分区方法可能会很慢。为了提高搜索空闲分区的速度，在大、中型系统中往往会采用基于索引搜索的动态分区分配算法。

快速适应(quick fit)算法（我觉得不会考）¶

  又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。同时在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。该算法在搜索时先根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表，然后从链表中取下第一块进行分配即可

关于是否产生碎片的问题：

汤书的说法认为既不会产生内部碎片也不会产生外部碎片；

当进程请求内存时，系统根据进程长度，通过索引表直接找到能完全满足其大小的最小空闲分区链表，并取下第一块分配给进程。

无内部碎片：分配时直接给出刚好契合进程需求的完整块，不留多余空间。

无外部碎片：分配时不分割连续分区，也就是说不会把一个大块切碎留下用不掉的“边角料”。

2. 实际上内部碎片和外部碎片都会有 1. 如果系统只准备了固定几种常用规格的链表：进程请求了一个非标准的规格（例如 7KB），而系统中只有 4KB 和 8KB 的链表。为了保证算法的高效性，系统不会去实时拆分块，而是直接将一个 8KB 的完整分区分配给该进程。进程只用了 7KB，剩下的 1KB 被白白浪费在分区内部，这就产生了内部碎片。 2. 当一个进程释放内存时，它所占用的块需要归还到对应的空闲链表中。如果此时它的物理邻居（前后的内存块）也是空闲的，最理想的操作是将它们合并成一个更大的块。由于相邻的空闲块可能属于完全不同的尺寸分类（存放在不同的链表中），要找到并合并它们需要遍历其他链表，这会极大地破坏 Quick Fit 的速度优势。如果系统为了追求速度选择不合并（或者很少合并），内存中就会充斥着大量离散的、无法拼凑成大块的空闲分区。当一个大进程请求内存时，虽然空闲总容量够，但没有一块连续空间足够大，这就演变成了严重的外部碎片。

伙伴系统(buddy system)¶

伙伴系统(buddy system)算法规定无论已分配分区或空闲分区，其大小均为 2的$u$次幂($u$ 为整数，$1 ≤ u ≤ m$)。将这些空闲分区按分区的大小进行分类，对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。\ \ \ 整个可分配的分区大小 $2^U$\ 需要的分区大小为$2^{U-1} < s ≤ 2^U$ 时，把整个块分配给该进程

- 如$ s ≤2^{i－1} $，将大小为$ 2^i $ 的当前空闲分区划分成两个大小为$ 2^{i－1} $的空闲分区
- 重复划分过程，直到$ 2^{i－1} < s ≤ 2^i $ ，并把一个空闲分区分配给该进程

多选题

描述伙伴系统(Buddy System)特征正确的是()

A 多个小空闲空间可合并为大的空闲空间

B 会产生外碎片

C 会产生内碎片

D 都不对

正确答案 ABC

【实现】：

数据结构
空闲块按大小和起始地址组织成二维数组
初始状态：只有一个大小为$2^U$的空闲块
分配过程
由小到大在空闲块数组中找最小的可用空闲块
如空闲块过大，对可用空闲块进行二等分，直到得到合适的可用空闲块
释放过程
把释放的块放入空闲块数组
合并满足合并条件的空闲块
合并条件
大小相同$2^i$
地址相邻
低地址空闲块起始地址为$2^{i＋1}$的位数

Hash算法¶

哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律建立哈希函数。构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小通过哈希函数计算，从中得到相应的空闲分区链表，实现最佳分配策略。\

4.紧凑技术

动态分区分配没有内部碎片，但有外部碎片

比如下面就产生了外部碎片，内存中剩余空间是可以满足该进程的，但是他们却割裂开来，导致每个分区都很小，因而无法利用

要解决外部碎片，可以使用拼凑(Compaction)技术解决，通过移动分配给进程的内存分区，以合并外部碎片；

前提：所有的应用程序支持动态重定位

非连续分配管理方式¶

在连续分配管理方式中，程序被装入时是需要连续的空间的。也就是说一个1GB的进程想要装入内存就必须要找到连续的1GB空间，即便有1GB的空间，但只要是不连续的，那也无能为力

固定分区分配：缺乏灵活性，会产生大量内部碎片，内存利用率低
动态分区分配：会产生很多外部碎片，虽然可以用紧凑技术处理，但是相应也会提高时间代价

于是我们不禁提出一个疑问：如果允许将一个进程分散地装入到许多不相邻的分区中，那内存的利用率不就能得到很大的提升了吗？这也就是本节所涉及的主要内容——非连续分配方式，主要有以下三种

基本分页存储管理
基本分段存储管理
段页式存储管理

3.1.4 基本分页存储管理¶

3.1.4.1 基本概述¶

基本思想：把主存空间划分为大小相等且固定的物理页面，作为主存的基本单位，每个进程也以页面划分，在执行过程中以页为单位进行申请。
分页存储管理基本概念
页框（页帧、帧、物理页面、Frame、Page Frame ）：将物理地址空间划分为大小相同的基本分配单位，称其为页框，每个页框有一个编号，叫做页框号，页框号从0开始。
页面（页、逻辑页面、Page）：将逻辑地址空间也划分为大小相同的基本分配单位，称为“页”或“页面” 。每个页面也有一个编号，即“页号”，页号也是从0开始。
操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中，也即它们是一一对应的关系。各个页面不必连续存放，也不必遵循先后顺序，可以放到不相邻的各个页框中
分页的优点\ 分页的方法从形式上看像分区相等的固定分区技术，但它们有本质的区别。分页管理和固定分区一样不会产生外部碎片，进程在运行时按照页框申请空间，这样进程只会在为最后一个不完整的页申请一个页框时才会产生内部碎片，尽管会有碎片产生，但足以忽略其影响.
页表：为了能获得每个页面在内存中存放的位置，操作系统会为每个进程建立一张页表。具体来说：
一个进程对应一张页表

在多个进程并发执行时，所有进程的页表大多数驻留在内存中，在系统中只设置一个页表寄存器（PTBR），它存放页表在内存中的始址和长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的 PCB 中，当调度到某进程时，才将这两个数据装入页表寄存器中。每个进程都有一个单独的逻辑地址，有一张属于自己的页表。

进程的每个页面对应一个页表项
每个页表项由页号和块号组成 （由于页表是一个数组，因此页号可隐含）
页表记录进程页面和实际存放的内存块之间的映射关系

因此利用页表得到页号对应的物理页号后（例如页框号为M），那么M号内存页的起始地址就是M×内存页框大小，得到起始地址后再加上偏移量就是真实的物理地址了\

页目录项大小的计算：

假设上面左图中的系统物理内存为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？

内存块大小=页面大小=4KB= 2¹²B

4GB 的内存总共会被分为 2³²/2¹²= 2²⁰个内存块

内存块号的范围应该是0 ~ 2²⁰-1

内存块号至少要用 20 bit 来表示

所以至少要用3B来表示块号（3*8=24bit）(计算机中内存块的数量→页表项中块号至少占多少字节)

页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）

由于页号是隐含的，因此每个页表项占3B，存储整个页表至少需要 3*2²⁰B

【注】：页表记录的只是内存块号，而不是内存块的起始地址！J 号内存块的起始地址 = J * 内存块大小

对页表项大小的进一步探讨：

各页表项会按顺序连续地存放在内存中,如果该页表在内存中存放的起始地址为 X ，则M 号页对应的页表项是存放在内存地址为 X + 3 * M

一个页面为 4KB，则每个页框可以存放 4096/3 = 1365个页表项，但是这个页框会剩余 4096 % 3 = 1 B页内碎片

因此，1365 号页表项存放的地址为 X + 3*1365 + 1

如果每个页表项占4字节，则每个页框刚好可存放 1024个页表项,1024号页表项虽然是存放在下一个页框中的，但是它的地址依然可以用 X + 4*1024得出.

【结论】：理论上，页表项长度为3B即可表示内存块号的范围，但是，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。

3.1.4.2 地址转换¶

分页存储管理如何实现地址转换

采用分页管理，每个进程会被分为若干页，然后离散的存储在各个页框中。这样的管理方式的最大的难点就是实现逻辑地址到物理地址的转换

基本思想：可以把进程中所有的页看作一个个连续存放的模块，当页面分配到页框中后，虽然页面彼此之间是离散存放的，但是每个页面之内却是连续的。因此如果知道一个模块（一个页）的起始地址，并且知道某逻辑地址相对于该起始地址的偏移量，那么物理地址自然很容易得到。关键分为以下几步
要算出逻辑地址对应的页号
要算出某逻辑地址在页面内的偏移量
要知道该页号对应页面在内存中的起始地址（需要查页表）
物理地址=页框的起始地址+偏移量
分页存储管理逻辑地址结构：前一部分为页号，后一部分为页内偏移量
如果用k位表示页内偏移量，那么说明该系统一个页面的大小为2^k个内存单元
如果用m位表示页号，那么说明该系统中一个进程最多允许有2^m个页面
具体计算方式：为了方便计算页号，页内偏移量，页面大小一般是2的整数次幂。其中如果每个页面大小为2^kB，那么末尾k位表示页内偏移量，其余部分为页号
分页存储管理系统中的基本地址变换机构
地址变换机构可以借助进程的页表将逻辑地址转化为物理地址。通常会在系统中设置一个页表寄存器(PTR)，它存放了页表在内存中的起始地址F和页表长度M
进程未在执行时，页表的起始地址和页表长度存放在PCB中，当进程被调度时，系统内核会把它们放到PTR中
地址变换机构的过程演示和手算步骤
首先将PCB中的页表的起始地址F和页表长度M装入页表寄存器PTR中；
变换过程：假设页面大小为L，逻辑地址A到物理地址E的变换过程如下（页面大小为2的整数次幂）
计算页号P = A / L；计算偏移量W = A % L
若P ≥ M，也即页号大于等于页表长度，产生越界中断，否则继续执行
页表中页号P对应的页表项地址=页表起始地址F+页号P×页表项长度，取出该页表项内容b ，即为内存块号
最终：E = b ∗ L + W,用得到的物理地址E去访存

Note

在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

Note

注意：

页表在内核区中，页表负责逻辑地址到物理地址的映射及内存权限管理（如读、写、执行）。若页表位于用户区，用户进程可能篡改其内容，导致非法内存访问或系统崩溃。内核区受硬件保护（如CPU特权级），仅内核可修改页表，确保安全性。
进程上下文切换时，内核需更新CPU的页表基址寄存器（如x86的CR3），指向新进程的页表。这些页表的物理地址由内核维护在进程控制块（PCB）中，PCB位于内核区。

具有快表的地址变换机构

上面那种基本的地址变换机构，每次要访问一个逻辑地址都需要先查询内存中的页表，第二次访问才能访问到所需要的数据。由局部性原理可知，在一定时间内可能连续多次查到的都是同一个页表项，既然如此，能否利用此特性减少访问页表的访问次数呢——快表

快表(TLB, Translation Lookaside Buffer)：这是一种访问速度快于内存的高速缓冲器，用来存放当前访问的若干页表项，以加速地址变化过程。与之对应，内存中的页表就称之为慢表。引入快表后，地址变换过程如下

CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较
如果找到匹配的页号，说明要访问的页表在快表中有副本，则直接从中取出该页对应的内存块号，再将其与页内偏移量拼接形成物理地址然后访存；因此如果快表命中，则访问某个逻辑地址仅需一次访存即可
如果没有找到匹配的页号，则需要访问内存中的页表，找到对应的页表项，得到页面存放的内存块号，再将其与页内偏移量拼接形成物理地址访存；因此，若快表未命中，则访问某个逻辑地址需要两次访存

Note

注意：

TLB里的页号是显式保存的；
TLB位于CPU之中，使用相联存储器实现，具备快速访问性能；
如果快表未命中，在页表中找到页表项后，基于局部性原理，应同时将其存入快表，以便后面可能再次访问；同时如果页表已满，则必须按照一定的算法对旧的页表项进行替换（页面置换算法）

3.1.4.3 多级页表¶

简单的分页有什么缺陷吗？有空间上的缺陷。

因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。

在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2¹²），那么就需要大约 100万 (2²⁰)个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。

那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。

要解决上面的问题，就需要采用一种叫作多级页表（Multi-Level Page Table）的解决方案。

在前面我们知道了，对于单页表的实现方式，在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 多万个「页表项」，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用4MB大小的空间。

我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。如下图所示：

逻辑地址结构:我们规定，页目录表最多只能有一个页面，所以页目录表总共可以容纳4KB/4B=1K（占用10位）个页表项。这样在32位的结构中，低12位仍然是页内偏移量，高20位中更高的10位作为一级页号，更低的10位作为二级页号。一级页号用于查询小页表的存放位置，由一级页号查找到小页表后再由二级页号查询得到最终想要访问的块号

你可能会问，分了二级表，映射 4GB 地址空间就需要 4KB（一级页表）+ 4MB（二级页表）的内存，这样占用空间不是更大了吗？

当然如果 4GB 的虚拟地址全部都映射到了物理内存上的话，二级分页占用空间确实是更大了，但是，我们往往不会为一个进程分配那么多内存。

其实我们应该换个角度来看问题，还记得计算机组成原理里面无处不在的局部性原理么？

每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页面，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。

如果使用了二级分页，一级页表就可以覆盖整个 4GB虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

那么为什么不分级的页表就做不到这样节约内存呢？

我们从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

我们把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用。

Note

原理：也就是说单级页表其最大的问题就在于存储了很多无用的页表项，并且查询页表时也是无脑式地顺序查询。如果不采用单级页表，那么我们可以像引入分页管理一样，为页表分页，从而形成多张页表，查询时我们还需要一张索引表来告诉系统第几张页表应该上哪里去找，这样就不需要把所有的页表都调入内存，只在需要它时查询调入。因此两级页表实则就是页表的页表。具体来说，将长长的页表分组，使每个内存块刚好放入一个分组。同时为离散分配的页表再建立一张页表，称之为页目录表（外层页表/顶层页表）

对于更高位系统，两级分页自然不够，就需要采用多级页表，但是不管是几级页表，必须满足各级页表的大小不能超过一个页面

【2010】某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为$2^{10}$B，页表项大小为2B，逻辑地址结构为

逻辑地址空间大小为 $2^{16}$页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（）。

A. 64 B. 128 C. 256 D. 512

解析

本题选B。

页大小为 210 B，页表项大小为2B，一页可以存放个页表项，逻辑地址空间大小为页，即至少有个页表项，存放这些页表项至少需要页组成页目录。

【2014-32】下列选项中，属于多级页表优点的是（）。

A. 加快地址变换速度

B. 减少缺页中断次数

C. 减少页表项所占字节数

D. 减少页表所占的连续内存空间

解析

本题选D。

A错误。多级页表并不能直接加快地址变换的速度。事实上，由于多级页表需要多次间接查表，地址变换的速度可能会稍微变慢。

B错误。多级页表与缺页中断没有直接关系。缺页中断是由于页面不在内存中，需要进行页面调度和置换的过程中产生的。多级页表在页表管理方面有一些优势，但并不直接减少缺页中断次数。

C错误。因为多级页表需要更多的页表项，而页表项大小是固定的，所以级页表会增加页表项所占的字节数。

D正确。多级页表的一个显著优点是减少页表所占用的连续内存空间。传统的单级页表需要一次性分配整个页表，因此需要连续的内存空间。而多级页表可以将页表分为多个级别，每个级别只需要分配一部分页表，从而减少了连续内存空间的需求。

【2019-31】某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：

虚拟地址20501225H对应的页目录号、页号分别是（）。

A. 081H、101H

B. 081H、401H

C. 201H、101H

D. 201H、401H

解析

本题选A。

【2021-29】在采用二级页表的分页系统中，CPU页表基址寄存器中的内容是（）。

A. 当前进程的一级页表的起始虚拟地址

B. 当前进程的一级页表的起始物理地址

C. 当前进程的二级页表的起始虚拟地址

D. 当前进程的二级页表的起始物理地址

解析

本题选B。

在二级页表的分页系统中，页表被划分为两级结构：一级页表和二级页表。一级页表包含多个页表项，每个页表项对应一个二级页表的起始物理地址。每个二级页表也包含多个页表项，用于映射虚拟页到物理页。CPU页表基址寄存器 (Page Table Base Register, PTBR) 存储的是当前进程的一级页表的起始物理地址。通过在物理地址空间中访问该寄存器中的内容，CPU可以获取当前进程的一级页表，进而进行页表查找和地址映射操作。

【2023-30】进程R和S共享数据data，若date在R和S中所在页的页号分别为p1和p2，两个页所对应的页框号分别为f1和f2，则下列叙述中，正确的是（）。

A. p1 和 p2 一定相等，f1 和 f2 一定相等

B. p1 和 p2 一定相等，f1 和 f2 不一定相等

C. p1 和 p2 不一定相等，f1 和 f2 一定相等

D. p1 和 p2 不一定相等，f1 和 f2 不一定相等

解析

本题选C。

每个进程的虚拟地址空间是独立的，它们使用的页号是相对于各自的地址空间的。对于进程 R 和 S 共享的数据 data，可能位于不同的页面中，因此其对应的页号 p1 和 p2 不一定相等。

一段数据物理地址空间是确定的，对应的起始页框号是唯一的。对于进程 R 和 S 共享的数据 data，位于同一个页框中，因此两个页所对应的页框号分别为 f1 和 f2 一定相等。

【2024-25】在支持页式存储管理的系统中，进程切换时操作系统要执行的操作是

Ⅰ. 更新程序计数器的值

Ⅱ. 更新栈基址寄存器的值

Ⅲ. 更新页基地址寄存器的值

A. 仅Ⅲ

B. 仅I、Ⅱ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

解析

本题选D。

进程切换除了要切换CPU现场信息，还需要切换地址空间相关的信息，前者包括了PC SP（堆栈指针寄存器）通用寄存器等，与后者相关的有页表基址寄存器的值。

具体切换过程见第二章进程调度与切换，有详细全流程解析。

I 正确。程序计数器指示了将要执行的指令的地址，因此在进程切换时需要更新程序计数器以指向新进程的指令地址。

II 正确。栈基址寄存器用于指向栈帧的底部，通常用于保存函数调用的局部变量和参数。在进程切换时，当前进程的栈基址寄存器值需要被保存，而新进程的栈基址寄存器值则需要被加载，以确保新进程的栈环境正确。

III 正确。在页式存储管理中，不同的进程可能拥有不同的页表，因此在进程切换时，需要更新页基地址寄存器的值，以便将内存访问转向新进程的页表。

综上所述，Ⅰ、Ⅱ、Ⅲ正确。

【2013-46】（8分）某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题。

(1) 若使用一级页表的分页存储管理方式，逻辑地址结构为：

$\begin{array}{|c|}\hline 页号（20\ 位）&页内偏移量（12\ 位）\\\hline \end{array}$

则页的大小是多少字节？页表最大占用多少字节？

(2) 若使用二级页表的分页存储管理方式，逻辑地址结构为：

$\begin{array}{|c|}\hline 页目录号（10\ 位）&页表索引（10\ 位）&页内偏移量（12\ 位） \\\hline \end{array}$

设逻辑地址为 LA，请分别给出其对应的页目录号和页表索引的表达式。

(3) 采用 (1) 中的分页存储管理方式，一个代码段起始逻辑地址为 0000 8000H，其长度为 8KB，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面 2 的起始物理地址。

解析

(1) 第一问，因为该计算机主存按字节编址，页内偏移量是12位，所以页大小是。第二问，页号占20位，说明最多有个页面，一个页表项占4B，一级页表最大占用。

(2) 我们通过观察对二进制串进行分割可以直接提取目标字段，但计算机只能通过运算获取。由于为了节约内存，内存地址存储为由比特位构成的整型，而不是由字符型构成字符串，所以LA中内容无法通过字符串分割获取，必须通过整型的运算获取。这里用C语言进行模拟。二级页表的分页存储管理方式逻辑地址占10+10+12=32位，恰好用一个32位的unsigned int表示。

页目录号占高10位，第一步通过逻辑右移移动到低10位，同时去除了比页目录号位数低的内容，逻辑地址为无符号数，右移22位后得((unsigned int)(LA)) >> 22（C 语言中右移运算为算术右移，需要先将LA强转为无符号整型），第二步需要用掩码 (mask) 截取低10位内容，掩码为 1111111111B=0x3FF，进行按位与操作，得到最终表达式 (((unsigned int)(LA)) >> 22) & 0x3FF。由于此时有效数值位全在低10位，其它有效数值位均已通过右移运算被过滤掉，也可无需用掩码提取，得到最终 C 语言表达式 (((unsigned int)(LA)) >> 22)。结果如图 (b) 所示。

页表索引占中间10位，第一步通过逻辑右移移动到低10位，同时去除了比页表索引位数低的内容，逻辑地址为无符号数，右移12位后得((unsigned int)(LA)) >> 12（C 语言中右移运算为算术右移，需要先将LA强转为无符号整型），第二步需要用掩码截取低10位内容（由于剩余有效数值既包含页目录号和页表索引），掩码为 1111111111B=0x3FF，进行按位与操作，得到最终表达式 (((unsigned int)(LA)) >> 12) & 0x3FF。当然，先用掩码进行按位与操作然后进行逻辑右移操作也是可以的，掩码为 0000 0000 0011 1111 1111 0000 0000 0000B=3FF000H，然后右移12位，得到最终表达式 (LA & 0x3FF000) >> 12。结果如图 (c) 所示。

(3) 因为采用 (1) 中的分页存储管理方式，根据问题(1)给出的一级页表逻辑地址格式，代码起始逻辑地址为 00008000 H ，页内偏移量为0，代码长度为 8KB，根据问题 (1) 的结论，一个页面占4KB，恰好需要连续8KB/4KB = 2个页面存放。页表起始地址为0020 0000H，一个页表项占4B，该计算机主存按字节编址，一个页表项占4H个地址单元。页表项的物理地址 = 页表起始地址+页号×页表项的字节数。

页面1的逻辑地址为 00008000 H，页号为8H=8，对应页表中的页表项8，得到页面1的页表项的物理地址 = 0020 0000H+8×4H=0020 0020H。页面2的逻辑地址为 00009000H，页号为9H=9，对应页表中的页表项9，得到页面2的页表项的物理地址 = 0020 0000H+9×4H=0020 0024H。

该代码被主存空间起始物理地址为 00900000 H ，页内偏移量为0，连续存储，同样地，恰好需要连续两个页框存放，代码页面1的物理地址为 00900000 H，代码页面2的物理地址为 00901000H。

综上，页框号1是00900H，页框号2是00901H，物理地址1是0020 0020H，物理地址2是0020 0024H，物理地址3是0090 1000H。

【2015-46】（6分）某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：

$\begin{array}{|c|}\hline \text{页目录号（10位）}& \text{页表索引（10位）}& \text{页内偏移量（12位）}\\\hline \end{array}$

请回答下列问题。

(1) 页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？

(2) 假定页目录项和页表项均占4个字节，则进程的页目录和页表共占多少页？要求写出计算过程。

(3) 若某指令周期内访问的虚拟地址为0100 0000H和0111 2048H，则进行地址转换时共访问多少个二级页表？要求说明理由。

解析

(1) 页大小：页内偏移量为12位，故页大小 = 字节 = 4KB；

页框大小：页框大小 = 页大小 = 4KB（4096字节）；

虚拟地址空间页数：虚拟地址共位，虚拟地址空间大小 = 字节，

(2) 页目录占用页数：

页表占用页数：

每个页目录项指向一个二级页表，共有个二级页表
每个页表项数 = 个
每个页表大小 = 页
全部页表共占页

合计：

(3) 共访问 1 个二级页表。

理由： 将两个虚拟地址分解为页目录号和页表索引：

两个虚拟地址的页目录号相同（均为4），因此它们都通过页目录第4项找到同一个二级页表（只是在该页表中访问不同的页表项）。

所以，地址转换过程中只访问了 1 个二级页表。

3.1.5 基本分段管理方式¶

3.1.5.1 基本概述¶

由进程的地址映像我们可以看到，进程地址空间可由多个逻辑分段组成，例如代码分段、数据分段、栈段、堆段等，不同的段是有不同的属性，所以可以用分段的形式把这些段分离出来。

什么是段：段表示访问方式和存储数据等属性相同的一段逻辑地址空间，若干个段组成进程的逻辑地址空间，段的大小不等。
基本思想：按照用户进程自身的逻辑关系划分为若干段。每个段有一个段名，每段从0开始编址。内存分配时，以段为单位进行分配，段内连续，段间可以不连续
段访问的逻辑地址是由二元组（s,addr）表示，s即段号，addr为段内偏移量。
段表：为了能获得每个段在内存中存放的位置，操作系统会为每个进程建立一张段映射表，简称为“段表”.具体来说，
一个进程对应一张段表
进程的每一段对应一个段表项
由于段与段之间的大小不相同，因此想要记录一个段的信息必须要有两个变量，即段长和段基址（在内存中的起始地址）；
各个段表项的长度是相同的，因此段号可以隐含；

如图，如果要访问段2中偏移量为200的虚拟地址，我们可以通过段表计算出物理地址为段2基地址3000+偏移量200=3200

分段存储管理的特点
方便编程：汇编程序编写通常按照自身逻辑关系被划分为几个段，这与分段管理方式十分契合，所以分段极大便利了程序员的程序编写工作；
信息共享：分段中的段不同于分页的页面，这里的段是一个有内容共性的逻辑单位体，这个特性有效提高了程序段的可复用性，多个进程可以方便地共享某段内存文件的内容。

将段称为有内容共性的逻辑单位体是指每一个段都有其明确的完整作用，而不会像分页一样，完成某个内容的程序文件可能被分割在不同页中。

信息保护：同样是因为程序段是一个个逻辑单位的这一特性，系统可以方便地对特定的函数、数据等逻辑单位设定其读写方式和权限列表，有效保证进程的信息安全。
动态增长：进程在运行的过程中，有部分内容会随着运行而增长，较为明显的就是数据段。这种情况下，分页存储管理方式比较适合预先分配，不利于应对这一状况，而分段系统中段长度可变，不需要确定各个段共同的固定大小，从而容易实现动态分配，可以较好地解决这一问题。
动态链接：动态链接中，为了提高内存的利用率，系统只将进程当前需要用到的程序内容装入内存。对于实现这种动态链接的程序而言，该程序是一边运行一边进行链接的，其链接单元应当是一个个实现某一功能的独立逻辑单位，这恰符合分段管理方式中段的划分原则。所以分段管理方式十分利于实现动态链接。

段的共享与保护：

段的保护：由于分页与分段的保护方式大致相同，在此做统一说明。分页和分段的主要保护方式都为界地址保护和存取控制保护。

界地址保护通过逻辑地址与段（页）表信息的比较来防止进程的越界访问。在分页方式中，将页号与页表的长度做比较，若页号>=页表长度则产生越界中断。需要说明的是分页方式的页内偏移量与页表大小严格对应，不会造成越界。

在分段方式中，段号和段内偏移量需要同时显性给出，判断访问是否越界也需要进行两次：

1. 若段号 ⩾段表长度，则产生越界中断
2. 查询段表时，若段内偏移量 ⩾段长，则产生越界中断。

存取访问控制通过对进程段（页）进行访问权限设置以保护其信息。系统内存中的段页设置只读、读/写、不可访问等限制，访问相关页面时进行权限检查。

段的共享：实现段共享时，除了每个进程自身的段表外，系统还设置了一个供相关进程共同使用的共享段表。如图所示，共享段表的表项中除记录该共享段的物理地址等相关信息外，还设置了一个count字段用于记录共享该段的进程数。

当P1进程与P2进程共享段S时，段S在内存中只有一份，P1与P2的段表中对该共享段的记录与正常段相同，二者分别有一个段表项记录该段的物理地址。同时共享段表中也会有一个表项记录段S的物理地址等信息，并记录共享段S的进程数及相关信息。需要注意的是，段S的物理地址是唯一的，但其在P1和P2中的逻辑地址是不同的。自然，段S在P1段表、P2段表与共享段表中的段号是不一定相同的，三者没有必然关联。由于共享段被多个进程共享，在其中某一个进程释放该段时，系统并不会直接调出该段，而是将共享段表中的count减去1。只有当共享段的count减至0时，系统才会将该段调出内存。

对于段共享的实现，在汤小丹老师的旧版教材中采用的方法是配置共享段表：但是，在新版教材中采用的方法是在每个进程的段表中设置一个段表项，指向被共享的同一个物理段。如下图所示。2019年的统考真题考查的是前述方法。

为什么分段相较于分页来说更容易实现信息的共享与保护？

因为如果被共享的内容占N个页框的大小，则每个进程的页表中都要建立N个页表项，指向被共享的N个页框。而在分段管理中，不管该共享段有多大，都只需要为该段设置一个段表项，因此更容易实现共享。保护同理。

【2009-27】一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（）。

A. $2^8B$

B. $2^{16}B$

C. $2^{24}B$

D. $2^{32}B$

解析

本题选C。

分段存储管理系统中逻辑地址的格式为段号段内地址，地址长度为32位，其中段号占8位，则段内地址占32-8=24位，默认按字节编址，最大段长是 B。

【2016-28】某进程的段表内容如下所示。

当访问段号为2、段内地址为400的逻辑地址时，进行地址转换的结果是（）。

A. 段缺失异常

B. 得到内存地址4400

C. 越权异常

D. 越界异常

解析

本题选D。

查表访问段号2，先查该段状态，该段在内存中，再查该段段长，该段长300，段内地址范围为[0, 299]，段内地址400>299，越界。

【2019-28】在分段存储管理系统中，用共享段表描述所有被共享的段。若进程P1和P2共享段S，下列叙述中，错误的是（）。

A. 在物理内存中仅保存一份段S的内容

B. 段S在P1和P2中应该具有相同的段号

C. P1和P2共享段S在共享段表中的段表项

D. P1和P2都不再使用段S时才回收段S所占的内存空间

解析

本题选B。

分段存储管理系统是一种操作系统中的内存管理方式，通过将程序和数据划分为不同大小的段 (segment)，并分配给它们特定的内存区域，来管理内存的使用。每个段都代表了程序或数据的逻辑单元，有自己的起始地址和长度。分段系统的一个突出优点，是易于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。

A正确。当多个进程共享同一个段时，为了节省内存空间，物理内存中只需要保存一份该段的内容，而不是为每个进程都保存一份。

B错误。在分段存储管理系统中，每个进程都有自己的段表，段表中的段号是由该进程自己管理的。如果进程P1和P2共享段S，它们可以分别在它们的段表中有不同的段号来表示段S。实际上，共享段的段号可以不同，只要在段表中的其他属性（例如段的基地址、段的长度等）相同即可。这样可以确保进程通过不同的段号访问同一个共享段。

C正确。共享段表中的段表项会记录共享段S的相关信息，比如段号、段长度、共享权限等。P1和P2可以通过共享段表中的段表项来获取段S的描述信息，以便访问和使用共享段S。

D正确。当进程P1和P2都结束运行或者显式释放共享段S时，操作系统会检查共享段S的使用计数器或引用计数器。如果计数器的值为零，表示没有任何进程在使用该共享段，操作系统会将该段的内存空间回收。

3.1.5.2 分段存储管理的地址转换¶

进程在未执行时，段表的起始地址F和段表长度M存放在PCB中，当进程被调度时，系统会将其存放在段表寄存器中。具体变换步骤如下：

根据逻辑地址得到段号S和段内地址W
判断段号是否越界，若S ≥ M，产生越界中断，否则继续执行
查询段表，找到对应段表项。（对应段基址b实则可以由F+S×段表项长度得到)
判断段内地址是否超过段长，若W ≥ C，产生越界中断，否则继续执行
计算：物理地址=段基址b+段内地址W
访存

3.1.5.3 分段和分页管理比较¶

页是信息的物理单位，分页的目的是为了实现离散分配。分页仅仅是系统管理上的需要，完全是系统行为，对用户不可见(透明)。页的大小固定且由系统决定.
段是信息的逻辑单位，分段的目的是为了更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息，对用户可见(不透明)。段的长度不固定，用户编程时需要显式地给出段名
分页的用户进程地址空间是一维的，程序员只需要给出一个记忆符即可表示一个地址
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，又要给出段内地址

为什么分页与分段的地址结构都被分为页（段）号和页（段）内偏移量两个部分，而二者的空间维度却不同？
从这两种方式的地址结构来看，它们都由两个变量组合而成，所以看上去都是二维空间。而之所以分页的地址空间为一维，是由于页号和页内偏移量并不是两个独立变量。我们可以只给出某一数据在逻辑地址空间中的相对位置这一个变量，根据页面大小来直接计算出数据处于的页号和页内偏移量。而分段系统中的段大小不等，所以段号和段内偏移量这两个变量是独立的，必须显性给出。
例如，8086CPU就使用了分段式内存管理，其程序计数器PC就保存在CS和IP两个寄存器中，写作CS:IP。CS（CodeSegment，代码段寄存器）存储代码段的地址，IP（InstructionPointer,指令指针寄存器）存储下一条指令在代码段中的段内偏移。这就是“二维”的体现。

访问一个逻辑地址需要几次访存？
分页（单级页表）：第一次访存——查内存中的页表，第二次访存——访问目标内存单元。总共两次访存
分段：第一次访存——查内存中的段表，第二次访存——访问目标内存单元。总共两次访存
与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度

3.1.6 段页式管理方式¶

分段和分页管理优缺点

	优点	缺点
分页管理	空间利用率高，仅有少量页内碎片，不会产生外部碎片	不利于实现信息的共享保护
分段管理	利于实现逻辑模块间信息的共享和保护	段长过大，导致分配连续空间不方便，会产生外部碎片

3.1.6.1 段页式管理基本概念¶

基本思想:将进程先按照逻辑模块分段，再将各段分页。对内存空间的管理仍然和分页管理一样，将其分成若干和页面大小相同的存储块，对内存块的分配以存储块为单位

段页式存储管理兼有页式管理和段式管理的优点，采用分段方法来分配和管理用户地址空间，采用分页方法来管理物理存储空间。但它的开销要比段式和页式管理的开销大。

逻辑地址结构:由段号、页号和页内地址(或页内偏移量)组成
如果用k位表示页内偏移量，那么说明一个页面的大小为2^k个内存单元
如果用m位表示页号，那么说明每个段最大有2^m 个页面
如果用n位表示段号，那么说明每个进程最多可以分为2ⁿ个段

Note

【注】“分段”对用户是可见的，程序员编程时需要显示地给出段号、段内地址。而给各段“分页”的过程对用户却是不可见的，系统会自动进行。所以段页式管理的地址结构是二维的

段表和页表
在段页式管理中，根据段表可以获得该段对应的页表在内存中的存放位置，然后根据页表可以获得每一页对应的页框号。
每个进程只会对应一个段表，它拥有多个段，然后每个段又会对应一个页表，所以一个进程会对应多个页表
每个段对应一个段表项，每个段表项由段号、页表长度、页表存放的块号组成。由于段表项长度是固定的，所以段号可以隐含
每个页面对应一个页表项，每个页表项由页号，块号组成，由于页表项长度是固定的，所以页号可以隐含

3.1.6.2 段页式管理的地址转换¶

地址变换过程：进程在未执行时，段表的起始地址F和段表长度M存放在PCB中，当进程被调度时，系统会将其存放在段表寄存器中。具体变换步骤如下：

根据逻辑地址得到段号S、页号P、页内偏移量W
如果段号S ≥ 段表长度M，则产生越界中断，否则继续执行
查询段表，找到对应段表项。（段表项的存放地址为F+S×段表项长度）
检查页号，如果页号≥ 页表长度，则发生越界中断，否则继续执行
依据页表存放的块号和页号查询页表，找到对应页表项
根据内存块号和页内偏移量得到物理地址
访存

未引入快表时，访问一个逻辑地址需要访存3次，一次查段表、一次查页表、一次访问目标单元。

可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后如果命中仅需一次访存。

段页式管理当然也可以实现内存共享，具体方式是让共享段指向相同的页表，从而实现进程间的段共享；

【例题】在段页式存储管理系统中，进程R和S共享数据段data，若进程R和S都想访问该data段里的某个内存单元x，若x在R和S的段表中的段号分别为p1和p2，x所在页对应的页框号分别为f1和f2，则下列叙述中，正确的是（）。

A. p1 和 p2 一定相等，f1 和 f2 一定相等

B. p1 和 p2 一定相等，f1 和 f2 不一定相等

C. p1 和 p2 不一定相等，f1 和 f2 一定相等

D. p1 和 p2 不一定相等，f1 和 f2 不一定相等

答案

本题选C

3.2 虚拟内存管理¶

3.2.1 虚拟内存的基本概念¶

内存管理需要完成内存空间扩充的功能，主要有三种，其中覆盖和交换在前文已经介绍过了：

覆盖技术
交换技术
虚拟内存技术

一：传统存储管理方式的弊端

前面我们花费了很大的精力叙述了内存的分配与回收方式，他们都具有以下特征，或者说是弊端

一次性：作业必须一次性全部装入内存后，才能开始运行，这就导致两种情况
当作业很大而不能全部装入内存时，将导致作业无法运行
当大量作业要求运行时，由于内存不足以容纳所有作业，所以只能使少数作业先运行，无疑降低了多道程序的并发度
驻留性：作业被装入内存后，就会一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。运行中的进程会因为等待I/O而被阻塞，长期处于等待状态

二：虚拟内存的定义和特征

（1）定义：基于局部性原理，可以这样控制程序

程序装入时：将程序中很快会用到的部分先装入内存，暂时用不到的留在外存
程序执行时：如果所访问的信息不在内存，则由操作系统负责将所需要的信息从外存调入内存
发现内存不够时：由操作系统负责将内存中暂时用不到的信息换出外存

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

虚拟存储技术基于程序的局部性原理。局部性越好，虚拟存储系统越能更好地发挥作用

操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充。

【易混知识点】：

虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的

虚拟内存的实际容量是min(“内存和外存容量之和”，“CPU寻址范围”)

如：某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB。

则虚拟内存的最大容量为 2³² B = 4GB

虚拟内存的实际容量 = min (2³²B, 512MB+2GB) = 2GB+512MB

（2）特征

多次性：作业运行时无需一次全部装入内存，而是允许分批次调入内存
对换性：作业运行时无需一直常驻内存，而是允许在运行时进行换入和换出
虚拟性：从逻辑上扩充了内存的容量

三：虚拟内存实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。主要有以下三种

请求分页存储管理
请求分段存储管理
请求段页式存储管理

与传统的非连续存储管理方式相比，区别在于

所访问信息不在内存时，由操作系统负责将信息从外存调入内存——请求调页（或请求调段）功能
如果内存空间不够，由操作系统负责将内存中暂时用不到的信息换出外存——页面置换（或段置换）功能

不管哪种方式，都需要有一定的硬件支持，一般需要的支持有以下几个方面：

一定容量的内存和外存
页表机制(或段表机制)，作为主要的数据结构；
中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断；
地址变换机构，实现逻辑地址到物理地址的转换；

【2012-25】下列关于虚拟存储器的叙述中，正确的是（）。

A. 虚拟存储只能基于连续分配技术

B. 虚拟存储只能基于非连续分配技术

C. 虚拟存储容量只受外存容量的限制

D. 虚拟存储容量只受内存容量的限制

解析

本题选B。

A错误，B正确。非连续分配技术则可以将虚拟地址空间中的不同部分映射到内存或外存的任意位置。根据所用的存储器映像算法，虚拟存储器管理方式主要有段式、页式、和段页式三种。

C和D错误。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。

【2023-28】对于采用虚拟内存管理方式的系统，下列关于进程虚拟地址空间的叙述中，错误的是（）。

A. 每个进程都有自己独立的虚拟地址空间

B. C语言中malloc( )函数返回的是虚拟地址

C. 进程对数据段和代码段可以有不同的访问权限

D. 虚拟地址的大小由主存和硬盘的大小决定

解析

本题选D。

A正确。每个进程在运行时都被分配了独立的虚拟地址空间。

B正确。C语言中malloc()函数用于动态内存分配，返回的是一个指向分配内存的虚拟地址。

C正确。操作系统可以对进程的不同部分设置不同的权限，例如只读、可读写等。

D错误。虚拟地址空间的大小由操作系统决定。计算机系统一般按字节编址，32位操作系统的虚拟地址空间的大小为，64位操作系统的虚拟地址空间大小为。

【2014-28】下列措施中，能加快虚实地址转换的是（）。

I. 增大快表 (TLB) 容量

II. 让页表常驻内存

III. 增大交换区 (swap)

A. 仅 I

B. 仅 II

C. 仅 I、II

D. 仅 II、IIII

解析

本题选C。

快表 (Translation Lookaside Buffer, TLB) 是缓存页表项的高速缓存，用于加速虚实地址的转换。

I正确。通过增大TLB的容量，可以存储更多的页表项，减少了需要访问内存的次数，从而提高虚实地址转换的速度。

II正确。将页表常驻内存是指将页表始终保留在内存中，而不将其置换到磁盘上的交换区。当页表在内存中时，虚实地址转换的速度更快，因为访问内存比访问磁盘要快得多。通过确保页表常驻内存，可以加快虚实地址转换的速度。(单级页表中，页表一般常驻内存中的内核区，多级页表除顶级页表常驻内存，别的可以在外存)

III错误。增大交换区的容量并不直接加快虚实地址转换的速度。交换区是用于将内存中不活跃的页调出到磁盘的区域。增大交换区可以提供更多的存储空间，以便支持更多的进程运行，但它并不直接影响虚实地址转换的速度。

综上所述，能加快虚实地址转换的措施是仅 I、II。

3.2.2 请求分页管理方式的硬件支持¶

本节以请求分页管理方式为例，相比传统分页管理，区别主要在于以下三种硬件支持

请求页表机制
缺页中断机构
地址变换机构

请求页表机制¶

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置。

当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。

所以请求分页系统的页表机制不同于基本分页系统，需要增加如下字段

存在位（状态位）：表示该页是否在内存
1表示该页位于内存中，该页表项是有效的，可以使用
0表示该页当前在外存中，访问该页表项将导致缺页异常
访问位：表示该页面是否被访问过（读或写），供页面置换算法选择页面时进行参考

汤书描述：访问字段：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供页面置换算法（程序）在选择换出页面时参考。

保护位：表示该页的允许访问方式(只读、可读写、可执行等)
修改位（脏位）：表示在内存中的该页是否被修改过

回收该物理页面时，据此判断是否要把它的内容写回外存（供页面置换算法使用）

外存地址：指向该页在外存中的地址

发生缺页时缺页异常处理程序根据该地址去外存中交换页面

缺页中断机构¶

在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断（内中断，属于异常中的故障），请求操作系统将所缺页调入内存。此时，缺页的进程将会被阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列

内存若有空闲块：分配一个块，将要调入的页装入该块，并修改页表中的页表项
内存若没有空闲块：由页面置换算法淘汰一个页面。而且如果被淘汰的页面在内存期间被修改过，还要写回外存

需要注意以下两点

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断
一条指令在执行期间，可能会发生多次缺页中断。

某条指令需要访问的操作数可能在不同的页面，若这些页面均未调入内存，则在一条指令的执行周期就会发生多次缺页中断。

【2011-28】在缺页处理过程中，操作系统执行的操作可能是（）。

Ⅰ. 修改页表

Ⅱ. 磁盘I/O

Ⅲ. 分配页框

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ

C. 仅Ⅲ

D. Ⅰ、Ⅱ和Ⅲ

解析

本题选D。

在缺页处理过程中，当访问的页面不在主存中，会触发缺页异常。为了处理该异常，操作系统需要进行以下操作：

分配页框：当页面缺失时，操作系统需要为该页面分配一个合适的物理页框，以供页面调入主存。这包括从空闲页框池中选择一个可用页框。III正确。

磁盘 I/O：由于缺失的页面不在内存中，操作系统需要通过磁盘 I/O 将该页面读取到主存中。这涉及到磁盘读取操作，将页面从磁盘加载到主存。II正确。

修改页表：操作系统需要修改页表，将缺失页面映射到主存中的合适页框。这样，当页面再次被访问时，就可以直接从主存中获取而不触发缺页异常。I正确。

综上，Ⅰ、Ⅱ和Ⅲ正确。

【2013-30】若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是（）。

I. 处理越界错

II. 置换页

III. 分配内存

A. 仅 I、II

B. 仅 II、III

C. 仅 I、III

D. I、II 和 III

解析

本题选B。

I错误。处理越界错误（即访问超出进程地址空间范围的内存）是一种不合法或无效的内存访问错误，缺页处理程序不会遇到。

II正确。页面置换是将一个当前驻留在物理内存中的页面替换出去以腾出空间，从而将所需的页面加载到物理内存中。这个过程涉及到选择要替换的页面和载入所需的页面。常见的页面置换算法包括FIFO、LRU算法等。

III正确。操作系统通过分配内存的方式腾出空间，从而将所需的页面加载到物理内存中。

综上，仅 II、III正确。

【2022-29】某进程访问的页b不在内存中，导致产生缺页异常，该缺页异常处理过程中不一定包含的操作是（）。

A. 淘汰内存中的页

B. 建立页号与页框号的对应关系

C. 将页b从外存读入内存

D. 修改页表中页b对应的存在位

解析

本题选A。

缺页异常处理过程是指在访问某个页时，发现该页不在内存中而需要从外存中调入的情况。

A正确。淘汰内存中的页并不是缺页异常处理的必要步骤。淘汰页是在内存空间不足时，为了给新的页腾出空间而选择淘汰一些旧的页。在处理缺页异常时，并不一定需要进行淘汰操作。

B错误。在处理缺页异常时，需要建立页号与页框号之间的对应关系，以便将对应的页调入内存或者进行其他操作。这是确保后续内存访问可以正确映射的步骤，是缺页异常处理过程中一定包含的操作。

C错误。当发生缺页异常时，需要将缺失的页从外存读入到内存中，以满足进程的访问需求。是缺页异常处理过程中一定包含的操作。

D错误。在页表中，通常会使用一位存在位来表示该页是否在内存中，当发生缺页异常处理完成时，需要修改页表中相应页的存在位，将其置为1，表示该页已经调入内存。

地址变换机构¶

与基本分页存储管理相比，请求分页管理方式需要额外进行以下几个步骤

请求调页，查找到页表项时进行判断
页面置换，需要调入页面，但没有空闲内存块时进行
修改请求页表中的新增表项
快表中有的页面一定是在内存中的。若某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面

Note

注意：缺页异常执行后需要重新执行该指令，一般来说只会修改页表，不会修改快表，只有重新执行该指令后TLB缺失之后，才会更新快表。

不过如果题目有提示，例如09年的处理缺页的过程中会更新TLB和页表，那么要根据题目条件来，随机应变，不能死板。

3.2.3 页框分配（请求分页中的内存分配）¶

驻留集：指请求分页存储管理中给一个进程分配的页框的集合。

驻留集往时间前进的反方向(过去)读取窗口大小，去掉重复以后就是工作集。

若还有空闲页框，则再调入进程来增加多道并发度，若所有进程的驻留集大小和超过系统的页框数之和，则应暂停进程，空出页框以避免颠簸。

驻留集太大和太小都会对进程或系统产生一定影响，经常被访问的页面要留在驻留集中，长期不被使用的页面应从驻留集中丢弃！

驻留集越小，系统的并发程度越高，CPU利用率提高，但是每个进程的缺页率也越高，导致缺页频繁，发生抖动现象，系统需要花费大量时间来处理缺页，实际用于推进进程的时间很少。
驻留集越大，导致多道程序并发度下降，资源(如CPU)利用率降低

Note

在为进程分配内存（物理页框）时，需要考虑以下问题

为保证进程能正常运行，所需要的最少页框数的确定；
在为每个进程分配页框时，应采取什么样的内存分配策略，即所分配的页框数是固定的，还是可变的；
在为不同进程分配页框时，是采取平均分配算法分配，还是根据进程的大小按比例分配。

进程所需最少页框数的确定（考过，重要难理解）¶

最小页框数的定义

核心概念：保证进程正常执行所需的最少物理页框数量。若分配数量不足，进程会因无法加载必要页面而无法运行（例如缺页中断无法完成）。
区分以下两个概念：
“有效工作”的页框数：通常大于最小值，以减少缺页率、提升性能。

随着为每个进程所分配的页框数的减少，进程在执行过程中的缺页率将会上升，从而会降低进程的执行速度。为使进程能有效地工作，应为它分配一定数目的页框，但这并不是最小页框数的概念。

“最小页框数”：硬件强制要求的底线，与指令和寻址方式直接相关。

硬件结构如何影响进程所需最小页框数？

指令格式与内存访问模式（下面举例说明）
单地址指令 + 直接寻址：需要至少 2 个页框。指令页：存放当前执行的指令； 数据页：存放指令操作数（直接寻址的目标地址所在页）。
示例：指令 LOAD R1, 0x1000（从地址 0x1000 加载数据）需指令页和数据页同时驻留内存。
间接寻址（单级）：需要至少 3个页框。指令页；间接地址页：存放间接地址（如指令 MOV AX, [BX] 中，BX 指向的地址所在页）；数据页：存放最终操作数（间接地址指向的数据所在页）。
多级间接寻址：需要的页框数逐级增加。例如指令 MOV AX, [[BX]]： * 第一级：BX 指向的页（获取下一级地址）。 * 第二级：该地址指向的页（获取最终数据）。 * 若跨页访问，每级需独立页框。
指令隐含的多页面访问
同时访问多页面：
示例 1：x86 的 MOV [A], [B] 需同时访问源地址 B 和目标地址 A。若两者跨页，需 2 个数据页 + 1 个指令页，共 3 个页框。
示例 2：函数调用 CALL 0x2000 若跨页（如指令末尾在 0x1000FFC，目标地址在 0x2000000），需 2 个代码页。

典型架构所需最小页框数对比

架构特性	最小页框需求示例	原因
简单单地址指令	2 个页框（指令页 + 数据页）	直接寻址无需间接访问
x86 复杂指令	3+ 个页框（代码 + 数据 + 堆栈页）	指令可能同时操作代码、数据和堆栈段
RISC-V 精简指令	2~3 个页框（显式加载/存储设计）	减少隐式跨页访问，但需显式寻址支持

4. 总结

最坏情况覆盖：最小页框数由最复杂指令执行时的最大页面需求决定。例如，若某条指令需同时访问 4 个页，则最小页框数至少为 4。
硬件不可绕过：指令格式、寻址方式、对齐规则等硬件特性直接约束最小页框数，软件无法通过优化绕过。
实际应用意义：操作系统需为不同架构的进程分配不同最小页框数。编写高效代码时，应减少跨页访问（如内存对齐、紧凑数据结构），以降低对最小页框数的依赖。

页框分配/置换策略¶

根据驻留集大小是否可变，可以有如下两种分配方式

固定分配： 操作系统为每个进程分配一组固定数目的页框，进程运行期间不再改变
可变分配： 先为每个进程分配一定数目的页框，在进程运行期间，可以根据情况做适当的增加或者减少

根据置换时置换的范围不同，可以有两种置换方式

局部置换： 发生缺页时只能选进程自己的页框进行置换
全局置换：可以将操作系统保留的空闲页框分配给进程；也可以将别的进程持有的页框置换到外存，然后再分配给缺页进程

将上面不同的分配方式和置换方式搭配起来，就可以得到下面三种页面分配策略

	局部置换	全局置换
固定分配	✅	❎
可变分配	✅	✅

注意：没有固定分配全局置换这种分配策略，因为全局置换意味着一个进程拥有的页框数必定会改变，因此不可能采用固定分配

固定分配局部置换： 系统为每个进程分配一定数量的内存块，在整个运行期间都不改变；若进程在运行期间发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面

缺点：难以在一开始就确定每个进程所需的驻留集大小(分配的页框数)，太少会导致频繁缺页，太多会导致CPU和其他资源利用率下降，降低并发度。

可变分配全局置换：刚开始会为每个进程分配一定数量的内存块,同时操作系统自身会保持一个空闲页框队列，当进程发生缺页时，从空闲页框中取出一块分配该进程；若已经没有空闲页框了，则可以选择一个未锁定（被锁定的可能是很重要的页面）的页面换出外存，再将该页框分配给缺页的进程

使用该策略，只要进程发生缺页，都将会获得新的页框；仅当空闲页框用完时，系统才会选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程的页，因此被选中的进程拥有的页框会减少，缺页率会增加

优点：灵活、动态

缺点：盲目地给进程添加页框会导致多道并发度降低

可变分配局部置换：刚开始会为每个进程分配一定数量的页框。当进程发生缺页时，只允许从该进程自己的页框中选出一个换出外存。
如果进程在运行中频繁缺页，系统会为该进程多分配几个页框，直至该进程缺页率趋势变得适当且平稳；
反之如果缺页率很低，则可以适当减少分配给该进程的页框

使用该策略，要根据发生缺页的频率来动态地增加或减少进程的页框，保证了系统的多道并发能力。

【2015-30】在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（）。

A. 可变分配，全局置换

B. 可变分配，局部置换

C. 固定分配，全局置换

D. 固定分配，局部置换

解析

本题选C。

页框分配算法¶

在采用固定分配策略时，为了将系统中可供分配的所有页框分配给各个进程，一般可采用下列几种算法。

平均分配算法。将系统中所有可供分配的页框，平均分配给各个进程。（未考虑进程之间的大小不同，可能有的分配多了，有的不够用总是缺页）
按比例分配算法。根据进程的大小按比例分配物理页框；
考虑优先级的分配算法：为高优先级的进程分配更多的页框；

3.2.4 页面调入策略¶

为了让进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。

什么时候调入页面¶

主要有以下两种调页策略，实际场景中，两种策略会结合使用

预调页策略：根据局部性原理，一次调入若干相邻的页面可能要比一次只调入一个页面更加高效，但如果调入的一批页面中大多数都没有被访问，效率就会很低。因此，需要采用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存，但目前预测成功率平均不超过50%

应用场景：

- 在第一次将进程调入内存时，此时可将程序员指出的那些页先调入内存。
- 在采用工作集的系统中，每个进程都具有一张表，表中记录有运行时的工作集，每当程序被调度运行时，就将工作集中的所有页调入内存。

2. 请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。该策略下，调入的页面一定会被访问到，但是由于一次只能调入一页，所以 I/O开销较大

从哪里调入页面¶

具有对换功能的操作系统中，通常会把磁盘空间划分为文件区和对换区两部分：其中文件区主要用于存放文件，追求存储空间利用率,采用离散分配方式；对换区空间仅占一小部分。被换出的进程数据就存放在对换区。由于对换的速度直接影响系统的整体速度，因此对换区空间的管理主要追求换入换出速度，所以对换区采用连续分配方式。总之，对换区的I/O速度要远快于文件区

由于对换区磁盘I/O速度要快于文件区，因此就有如下三种情况

若系统拥有足够的对换区空间： 页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，将相关数据从文件区复制到对换区，之后把需要的页面从对换区调入内存；如图1所示。

若系统缺少足够的对换区空间： 凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下一次需要时再从文件区调入即可。对于可能被修改的部分，换出时需要写回对换区，下次需要时再从对换区调入；如图2所示
UNIX方式： 运行之前进程有关的数据全部放在文件区，所以未使用过的页面，都可以从文件区调入；被使用过页面的换出时，则写回对换区，下次需要直接从对换区调入

unix方式

如何调入页面¶

每当程序所要访问的页面未在内存时（存在位为“0”），便会触发缺页异常，执行关中断、保存断点、异常服务程序寻址，然后跳转到缺页异常处理程序执行；
该程序通过查找页表得到该页的外存地址后
如果此时内存能容纳新页，则启动磁盘I/O，将所缺之页调入内存，然后修改页表。
如果内存已满，则须先按照某种页面置换算法，从内存中选出一页准备换出；
- 如果该页未被修改过（修改位为“0”），则不必将该页写回磁盘；
- 但如果该页已被修改（修改位为“1”），则必须将该页写回磁盘；
然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”。
至此缺页处理完成，重新执行发生缺页的那条指令；

3.2.5 页面置换算法¶

在进程运行过程中，当其所要访问的页面不在内存中，而须把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，并将其送入磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。

页面置换算法的好坏将直接影响系统的性能。不适当的算法可能会导致进程发生“抖动”，即刚被换出的页，很快又要被访问，因此需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页，很快又被访问，又需要将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在了页面置换工作上，我们称该进程发生了“抖动”。

一个好的页面置换算法应具有较低的页面置换频率。从理论上讲，应将那些以后不再会访问的页面或那些在较长时间内不会再访问的页面换出。

Note

置换本质上不改变页框号，只改变页号，因为替换是把同一页框号的内容覆盖，而不是另找页框。
页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率
在408范围内，页面置换算法通常指局部置换的算法；

最佳置换算法（`OPT，Optimal`）¶

每次淘汰的页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证最低的缺页率

如下，假设系统为某个进程分配了三个内存块，然后会依次访问某些页面，顺序为：7-0-1-2-0-3-0-4-2-3-0-3-2。其置换过程大致如下

Note

【注】：缺页时不一定发生页面置换！！！若还有可用的空闲内存块，就不用进行页面置换。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

先进先出算法（FIFO）¶

算法思想：每次淘汰的页面是最早进入内存的页面。

实现方法：可以把调入内存的页面根据调入先后顺序排成一个队列（链表也可），需要换出页面时选择队头即可，队列的最大长度取决于系统为进程分配了多少个内存块

Note

会出现随着为进程分配的页框数（驻留集、工作集）增大时，缺页次数不减反增的现象，这种现象称之为Belady异常

另外，FIFO算法实现虽然实现简单，但是该算法与进程实际运行时的规律不相适应，因为先进入的页面也有可能是需要经常访问的，所以性能差

最近最久未使用置换算法(`LRU，least recently used`)¶

算法思想：每次淘汰的页面是最近最久未使用的页面。

实现方法：在每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t，需要淘汰页面时，选择t值最大的那个页面。大致流程如下

可以看出,LRU算法性能非常好，但是实现困难，开销也比较大

Note

技巧：若需要淘汰页面，可以逆向检查访问序列。假设某进程分配了n个内存块，则逆向找到第n个不同且在内存中的页号(即逆向扫描过程中最后一个出现的页号)，该页号就是要淘汰的页面。

lru算法的软件方法实现：内核维护一个双向页面链表，如图所示，表头是最近刚使用过的页面，表尾是最近最久没有使用的页面。该链表在每次该进程访问内存时都要进行更新，即遍历链表找到该页面，把它摘下来，移动到表头；每次缺页异常需要置换页面时，选择表尾页面淘汰，新页面挂到表头；因此开销很大。

时间	1	2	3	4	5	6	7	8	9	10	11	12
访问请求	a	c	b	d	e	b	c	a	b	c	e	d
链尾	a	a	a	a	c	c	d	e	e	e	a	b
		c	c	c	b	d	e	b	c	a	b	c
			b	b	d	e	b	c	a	b	c	e
链首				d	e	b	c	a	b	c	e	d
缺页？	✔	✔	✔	✔	✔	❌	❌	✔	❌	❌	❌	✔

硬件实现：为每个页面配置一个移位寄存器，记录页面使用情况（汤书的说法，不切实际）
给页面打上时间戳，需要置换时，选择时间戳最大的页面（需要排序）置换出去（每一次访问页面需要更新时间戳）

Note

需要了解上述算法实现的页面访问更新和页面置换的逻辑，这样才能更好地理解为什么它的实现开销大，以及理解到后面的clock算法是它的近似。

时钟置换算法（`CLOCK`）¶

虽然lru算法性能接近于OPT算法，但是实现起来的开销太大，为此，在实际应用中大多数采用LRU置换算法的近似算法。CLOCK置换算法就是其中一种。

简单时钟置换算法,又称最近未使用算法(`NRU,Not Recently Used`)¶

lru的近似算法，并不追求严格的最近最久未使用，可以认为是将最近较久未访问的页面换出；实现起来较简单，开销小一些；

算法思想：

访问页面时，在对应页表项记录页面使用情况；
缺页时，从指针处开始顺序查找未被访问的页面进行置换；

实现方法：

为每个页面设置一个访问位（页表项里），再将内存中的页面通过链接指针链接成一个循环队列，指针指向最先调入的页面。
页面刚开始被装入内存时，访问位被初始化为0；
当某页被访问（读或写）时，访问位置设置为1。
当缺页并且需要淘汰页面时，从指针当前位置顺序检查循环队列
如果访问位为0，表示最近没有访问过，选择该页换出
如果是1，表示最近访问过，将其访问位置为0，并将指针移动到下一个页面
若第一轮扫描中所有页面均为1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面）。

【注】第二轮扫描中一定会有访问位为 0 的页面，因此简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描。

访问位部分为“0”选择第一个为“0”的页号，访问位全为“1”选择第一个页号。\ 大致流程如下

改进型时钟置换算法¶

简单时钟置换算法仅仅考虑到了一个页面是否被访问过，但访问不一定修改，而页面一旦遭到修改就需要写回至外存，涉及I/O操作，所以在淘汰页面时不止要考虑是否被访问过而且要考虑是否被修改过
算法规则：为每个页面再设置一个修改位，淘汰页面时优先淘汰没有被修改过的页面
如果修改位为0：表示页面没有被修改过
如果修改位为1：表示页面被修改过

同时为了方便讨论，可以使用（访问位，修改位）这样二元组的形式表示各页面的状态

具体规则：将所有可能被置换的页面排成一个循环队列
第一轮：从当前位置开始扫描到第一个(0,0){最近未被访问，未被修改}的帧用于替换。本轮扫描不修改任何标志位
第二轮：若第一轮失败，则重新扫描，查找第一个(0,1){最近未被访问，已修改}的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮：若第二轮失败，则重新扫描，查找第一个（0,0）的帧用于替换。本轮扫描不修改任何标志位
第四轮：若第三轮失败，则重新扫描，查找第一个（0,1）的帧用于替换

由于第二轮已将所有帧的访问位设置为了0，所以经过第三轮、第四轮扫描一定有一个帧被选中，所以改进型CLOCK算法选择一个淘汰页面至多进行四轮扫描

该算法仅修改访问位，不修改修改位。

该算法的本质是将页面划分为了四个优先级，淘汰优先级：(0，0）> (0,1) > (1,0) > (1,1),首先考虑最近是否被访问过，再考虑页面是否被修改过。

可以将其类比于二进制的1，2，3，4进行记忆来选择淘汰顺序。

Note

会发生Belady现象的算法：FIFO CLOCK 以及改进版CLOCK

不会发生Belady现象的算法：LRU OPT

$belady$现象是指局部置换算法中，发现某进程缺页率变高，于是操作系统给它又分了几个物理页，原以为缺页率的增高是由于工作集变大，物理页帧不够用，结果增加了物理页以后，缺页率不降反而升高。

$belady$现象的出现，是由于置换算法将需要经常访问的页面置换了出去导致的。例如$FIFO$算法，即便最开始进入内存的那个页面是最近以及未来要经常访问的，但是$FIFO$还是选择把它换出去。

$FIFO$选择替换最早进入内存的页面，没有考虑到这个页面未来是否可能会经常访问，所以导致了$belady$现象。

类似的算法还有简单$clock$算法，$clock$算法本质跟$FIFO$一样，假如物理页帧数为$4$，并且页面$p1、p2、p3、p4$先后被访问并被载入物理页帧，从$p4$被载入内存的时刻$t_1$开始，直到下一次发生缺页的时刻$t_2$为止这段时间内最经常访问的页是$p1$，根据局部性原理，未来$p1$有很大可能要继续访问。但是$clock$算法给这四个页面都设置了访问位，而且很遗憾的是，这个访问位只有一个比特，它根本区分不了这个四个页面中谁被访问最频繁，这4个页面的访问位都是1，根据$clock$算法，$t_2$时候发生缺页，$clock$算法按照被载入内存的时间先后扫描所有页帧，将第一个访问位为0的页面置换出去，但是显然这四个页面的访问位都是1，所以$clock$算法会将这4个页面的访问位依次置为0，然后循环扫描，将$p1$置换出去。所以$clock$算法是存在$belady$现象的。

$clock$算法的提出就是因为觉得$LRU$为了维持对访问局部性（谁是最近第一个被访问的、谁是最近第2个被访问的、...）的感知开销太大，$LRU$需要经常修改页面链表，确保是按照最近访问时间排序。$FIFO$不需要费这种功夫，所以开销比较小，但是缺点是$FIFO$感知不了访问局部性。

$clock$算法是$LRU$和$FIFO$的折中，但是还是偏向于$FIFO$，它不像$LRU$那样能够区分页面的访问时间的先后顺序，它只能够区分有没有被访问过，至于在那些都被访问过的页面中，谁是最频繁被访问的、谁是最近被访问的，$clock$算法区分不了。所以导致它经过一轮扫描以后退化成为$FIFO$。

该部分真题¶

【2014-30】在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是（）。

I. LRU算法

II. FIFO算法

III. OPT算法

A. 仅 II

B. 仅 I、II

C. 仅 I、III

D. 仅 II、III

解析

本题选A。

【2016-26】某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位。A=0表示页最近没有被访问，A=1表示页最近被访问过。M=0表示页没有被修改过，M=1表示页被修改过。按 (A, M) 所有可能的取值，将页分为四类：(0, 0)、(1, 0)、(0, 1) 和 (1, 1)，则该算法淘汰页的次序为（）。

A. (0, 0), (0, 1), (1,0), (1, 1)

B. (0, 0), (1, 0), (0, 1), (1, 1)

C. (0, 0), (0, 1), (1, 1), (1, 0)

D. (0, 0), (1, 1), (0, 1), (1, 0)

解析

本题选A。

改进型CLOCK置换算法会优先尝试淘汰不会影响数据一致性的页，然后淘汰可能会导致数据一致性问题的页。其算法规则为将所有可能被置换的页面排成一个循环队列，然后进行至多四轮扫描：

第一轮：从当前位置开始扫描到第一个 (0, 0) 的帧用于替换。本轮扫描不修改任何标志位；

第二轮：若第一轮扫描失败，则重新扫描，查找第一个 (0, 1) 的帧用于替换。本轮将所有扫描过的帧访问位设为0；

第三轮：若第二轮扫描失败，则重新扫描，查找第一个 (0, 0) 的帧用于替换。本轮扫描不修改任何标志位；

第四轮：若第三轮扫描失败，则重新扫描，查找第一个 (0, 1) 的帧用于替换。

所以该算法淘汰页的次序为：

(0, 0)：选择(A, M)为(0, 0)的页进行淘汰。这表示页最近没有被访问过且没有被修改过。
(0, 1)：选择(A, M)为(0, 1)的页进行淘汰。这表示页最近没有被访问过，但已经被修改过。
(1, 0)：选择(A, M)为(1, 0)的页进行淘汰。这表示页最近被访问过，但没有被修改过。
(1, 1)：选择(A, M)为(1, 1)的页进行淘汰。这表示页最近被访问过且已经被修改过。

【2015-27】系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 4, 8, 4, 5。若进程要访问的下一页的页号为7，依据LRU算法，应淘汰页的页号是（）。

A. 2

B. 3

C. 4

D. 8

解析

本题选A。

根据题意，模拟过程如下（红色标记未命中，绿色标记命中）：

【2019-29】某系统采用LRU页置换算法和局部置换策略，若系统为进程P预分配了4个页框，进程P访问页号的序列为0, 1, 2, 7, 0, 5, 3, 5, 0, 2, 7, 6，则进程访问上述页的过程中，产生页置换的总次数是（）。

A. 3

B. 4

C. 5

D. 6

解析

本题选C。

根据题意，模拟过程如下（红色表示未命中，蓝色表示未命中且置换，绿色表示命中）：

产生页置换的总次数是5。

【2021-28】某请求分页存储系统的页大小为4KB，按字节编址。系统给进程P分配2个固定的页框，并采用改进型Clock置换算法，进程P页表的部分内容如下表所示。

若P访问虚拟地址为02A01H的存储单元，则经地址变换后得到的物理地址是（）。

A. 00A01H

B. 20A01H

C. 60A01H

D. 80A01H

解析

本题选C。

分页存储系统的虚拟地址格式为页号页内偏移，页大小为4KB，按字节编址，页内偏移占12位，虚拟地址为 02A01 H的页号为02H=2，查表得，页号2对应的表项中存在位为0，系统给进程P分配2个固定的页框，已经有两个表项中存在位为1，需要执行页面置换算法，题目要求采用改进型Clock置换算法，改进型Clock算法的替换顺序为：

选择访问位为0且修改位为0的页进行淘汰。这表示页最近没有被访问过且没有被修改过。
选择访问位为0且修改位为1的页进行淘汰。这表示页最近没有被访问过，但已经被修改过。
选择访问位为1且修改位为0的页进行淘汰。这表示页最近被访问过，但没有被修改过。
选择访问位为1且修改位为1的页进行淘汰。这表示页最近被访问过且已经被修改过。

页号3对应的表项(访问位, 修改位)为(1, 0)，页号4对应的表项(访问位, 修改位)为(1, 1)，页号2选择替换页号3，此时页号2对应的页框号为60H，将页框号为60H拼接页内偏移A01H得到变换后得到的物理地址60A01H。

【2012-45】（7分）某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是：

<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。请回答下列问题。

(1) 访问<0, 4>时，对应的页框号是什么？

(2) 访问<1, 11>时，对应的页框号是什么？说明理由。

(3) 访问<2, 14>时，对应的页框号是什么？说明理由。

(4) 该策略是否适合于时间局部性好的程序？说明理由。

【2010-46】（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页 (Page) 数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框 (Page Frame)。在时刻260前该进程访问情况见下表（访问位即使用位）。

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：

(1) 该逻辑地址对应的页号是多少？

(2) 若采用先进先出 (FIFO) 置换算法，该逻辑地址对应的物理地址？要求给出计算过程。

(3) 采用时钟 (CLOCK) 置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针按顺时针方向移动，且指向当前2号页框，示意图如下图）。

【2009-46】（8分）请求分页管理系统中，假设某进程的页表内容见下表。

页面大小为4KB，一次内存的访问时间为100ns，一次快表（TLB）的访问时间为10ns，处理一次缺页的平均时间为 $$10^8$$ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页面不在内存中，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：

(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。

(2) 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。

【例题】：在某个请求分页管理系统中，假设某进程的页表内容如下表所示。

页号	页框（Page Frame）号	有效位（存在位）
0	120H	1
1	—	0
2	850H	1

页面大小为 4KB，一次内存的访问时间是 200ns，一次快表（TLB）的访问时间是 20ns，处理一次缺页的平均时间为 10⁹ns（已含更新 TLB 和页表的时间），进程的驻留集大小固定为两页，采用最近最久未使用置换算法（LRU）和局部置换策略。

假设：（a）TLB 初始为空；（b）地址转换时先访问 TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）；（c）有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。

现设有虚地址访问序列 2345H、1876H、258FH，请问：

（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。

（2）基于上述访问序列，虚地址 1876H 的物理地址是多少？请说明理由。

【解】（1）页面大小为 4KB，页内偏移量为 12 位，则虚地址的剩余部分为页号。

2345H：页号为 2，在 TLB 寻找，没有找到；再去页表寻找，有效位为 1，找到了；此时将页号 2 和对应的页框号 850H 写入 TLB 中，然后访存。因此所花时间为：查 TLB + 访存 + 访存 = 20ns + 200ns + 200ns = 420ns。

1876H：页号为 1，在 TLB 寻找，没有找到；再去页表寻找，有效位为 0，缺页；发生缺页中断，调入页面，此时将页号 1 和对应的页框号写入 TLB 和页表中；返回被中断的指令，重新查询 TLB，然后访存。因此所花时间为：查 TLB + 访存 + 缺页中断 + 查 TLB + 访存 = 20ns + 200ns + 10⁹ns + 20ns + 200ns

258FH：页号为 2，在 TLB 寻找，找到了；然后访存。因此所花时间为：查 TLB + 访存 = 20ns + 200ns = 220ns。

【注】很多同学在第二次访存时没有多加一次快表的查询时间，这是不对的。请注意，执行完缺页中断后 CPU 将返回到被中断的位置，然后重新执行被中断的指令，这时 CPU 还是跟之前一样去快表查记录，这时肯定能找到对应记录。如上图为整个地址翻译的过程，做错的同学应该是对上面流程不太熟悉。建议每次做这种题时都把上图画出来，这样就不会错了！

【2011-44】（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB：Cache采用直接映射方式，共8行：主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题 44-a 图、题 44-b 图所示，图中页框号及标记字段的内容为十六进制形式。

请回答下列问题∶

(1) 虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？

(2) 使用物理地址访问Cache时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。

(3) 虚拟地址001C60H所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？要求说明理由。

(4) 假定为该机配置一个4路组相连的TLB，该TLB共可存放8个页表项，若其当前内容（十六进制）如题 44-c 图所示，则此时虚拟地址024BACH所在的页面是否在主存中？要求说明理由。

【2016-45】（14分）某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB；TLB采用全相联映射；Cache数据区大小为64KB，按2路组相联方式组织，主存块大小为64B。存储访问过程的示意图如下。

请回答下列问题。

(1) 图中字段A～G的位数各是多少？TLB标记字段B中存放的是什么信息？

(2) 将块号为4099的主存块装入到Cache中时，所映射的Cache组号是多少？对应的H字段内容是什么？

(3) Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？

(4) 为什么Cache可以采用直写 (Write Through) 策略，而修改页面内容时总是采用回写 (Write Back) 策略？

3.2.6 页框回收¶

前面我们学习了页框分配，也就是给进程分配物理页框，我们当时学习了固定分配以及可变分配，所谓的可变分配就是先为每个进程分配一定数目的页框，在进程运行期间，可以根据情况做适当的增加或者减少，这里的减少就是页框回收。但是这个页面如果在调入内存后内容发生更改了，那就得写回磁盘，不能直接清空当成空页框。一般来说，这种被系统回收的页框，会被放入空闲页框链尾，里面的内容在下一次分配之前不会被清空。这也是12年真题的说法。下面将介绍与之相关的内容，选自汤小丹mooc版操作系统p186《页面缓冲算法》。

影响页面换入换出的影响因素¶

Note

这部分也可以归入虚拟存储器的性能影响因素

页面置换算法：这是最重要的影响因素，因为一个好的页面置换算法，可以使得进程在运行过程中具有较低的缺页率，从而减少页面换入换出的次数。
将已修改页面写回磁盘的频率：对于已经被修改过的页面，在将其换出时，应当写回磁盘。如果采取每当有一个页面要被换出时，就将它写回磁盘的策略，则意味着每换出一个页面就需要启动一次磁盘。但如果在系统中已建立了一个已修改换出页面链表，则针对每个要被换出的页面（已修改），系统可暂不把它们写回磁盘，而是将它们挂在已修改换出页面链表上，仅当被换出页面数目达到一定值（如64）时，再将它们一起写回到磁盘上，这样就显著地减少了磁盘I/O的操作次数，或者说，减少了已修改页面换出的开销。
将磁盘内容读入内存的频率：在设置了已修改换出页面链表后，在该链表上就暂时有了一批装有数据的页面，如果有进程在这批数据还未写回磁盘时需要再次访问这些页面，则无须从磁盘上调入，而可直接从已修改换出页面链表中获取，这样不仅可以降低将页面从磁盘读入内存的频率，而且可以减少页面换入的开销。或者说，只须花费很小的开销，便可使这些页面又回到该进程的驻留集中。

页面缓冲算法¶

页面缓冲算法就是采用上述思想，在原页面置换算法的基础上增设已修改页面链表，保存已修改且需要被换出的页面，等被换出的页面数目达到一定值时，再一起换出至磁盘，以达到减少页面换出开销的目的。页面缓冲算法的主要特点是：

显著地降低了页面换入/换出的频率，使磁盘I/O的操作次数大为减少，因而减小了页面换入/换出的开销；
正是由于换入/换出的开销大幅度减小，其采用一种较简单的置换策略（如FIFO页面置换算法）时不需要特殊硬件的支持，实现起来非常简单。

页面缓冲算法已在不少系统中被采用，下面介绍VAX/VMS系统中所使用的页面缓冲算法。在该系统的内存分配策略中采用了可变分配局部置换方式，系统为每个进程分配一定数目的物理页框，系统自己保留一部分空闲物理页框。为了能显著地降低页面换入/换出的频率，在内存中设置了以下两个链表。

空闲页面链表。实际上空闲页面链表是一个空闲物理页框链表，这些系统掌握的空闲物理页框用于分配给频繁发生缺页的进程，以降低这些进程的缺页率。当这些进程需要读入一个页面时，它们便可利用空闲物理页框链表中的第一个物理页框来装入该页。当有一个未被修改的页面要换出时，实际上并不将它换出到磁盘，而是将它所在的物理页框挂在空闲链表的末尾。应当注意，这些挂在空闲链表中的、未被修改的页面中是有数据的，如果以后某进程需要这些页面中的数据，则可从空闲链表上将它们取下，这免除了从磁盘读入数据的操作，减少了页面换入的开销。
修改页面链表。修改页面链表是由已修改的页面所形成的链表。设置该链表的目的是减少已修改页面换出的次数。当进程需要将一个已修改的页面换出时，系统并不会立即把它换出到磁盘上，而是会将它所在的物理页框挂在修改页面链表的末尾。这样做的目的是降低将已修改页面写回磁盘的频率，进而降低将磁盘内容读入内存的频率。

哪些页框可以被回收¶

页框回收算法按照页框所含内容的不同，将页框区分为以下几种类型，并以不同的方式处理：

不可回收页：包括空闲页、内核空间使用的页、临时锁定的页等。

可交换页：用户态进程的匿名页或与其他进程共享的页，这些页在硬盘上没有对应的区域，需要写入交换区（swap区）

可同步页：如文件映射到内存的页(例如程序的代码段、数据段等)，这些页在硬盘中有备份，系统只需检查页是否被修改过，如果被修改过则写回硬盘

系统内存紧张的时候，就会进行回收内存（页框）的工作，主要有两类内存可以被回收，而且它们的回收方式也不同。

文件页(File-backed Page)：内核缓存的磁盘数据(Buffer)和内核缓存的文件数据(Cache)都叫作文件页。大部分文件页，都可以直接释放内存，以后有需要时，再从磁盘重新读取就可以了。而那些被应用程序修改过，并且暂时还没写入磁盘的数据(也就是脏页)，就得先写入磁盘，然后才能进行内存释放。所以，回收干净页的方式是直接释放内存，回收脏页的方式是先写回磁盘后再释放内存（如上，可能先挂到修改页面链表，暂时不写入磁盘）。
匿名页(Anonymous Page)：这部分内存没有实际载体,不像文件缓存有硬盘文件这样一个载体，比如堆、栈数据等。这部分内存很可能还要再次被访问，所以不能直接释放内存，它们回收的方式是通过Linux 的 Swap 机制，Swap 会把不常访问的内存先写到磁盘中,然后释放这些内存，给其他更需要的进程使用。再次访问这些内存时，重新从磁盘读入内存就可以了。

文件页和匿名页的回收都是基于 LRU 算法，也就是优先回收不常访问的内存。

连续页框分配算法--伙伴算法的页框回收¶

Linux系统采用“伙伴算法”对内存中具有不同长度的连续空闲页框进行统计和记录。将内存中连续的空闲页框视为空闲页框块，并根据它们的大小（连续页框的数量）分组。分配页框是一个化整为零的过程，会产生很多碎片，而系统也必须有把零碎的页框合并成大的连续页框块的机制，Linux使用伙伴算法的逆操作进行页框的回收。回收页框时，算法先检查是否有大小相等的伙伴页框块存在，若有，则将它们合并成一个大小为原来两倍的新空闲页框块，每次合并完后，还要检查是否可以继续合并成更大的页框块。

【2022-30】下列选项中，不会影响系统缺页率的是（）。

A. 页面置换算法

B. 工作集的大小

C. 进程的数量

D. 页缓冲队列的长度

解析

本题选D。

A错误。页面置换算法的选择会直接影响到系统的缺页率。不同的页面置换算法具有不同的策略和性能指标，会对缺页率产生影响。

B错误。工作集是指进程在其过去的t个虚拟执行时间中访问的页的集合。如果工作集较小，可以更容易将常用页面保留在内存中，从而减少缺页率。因此工作集的大小会对缺页率产生影响。

C错误。较多的进程意味着可能会有更多的内存页被占用，如果这些进行被分配的内存有限，则对内存资源的竞争会更加激烈，从而增加了发生页面置换的机会，导致更高的缺页率。

D正确。页缓冲队列是为了减少磁盘IO频率的，即减少已修改页写回磁盘的频率，具体内容见页框回收那边的介绍。

3.2.7 虚拟存储器性能影响因素¶

“抖动和工作集”一节原本是2017年统考大纲中已删除的考点，但是2022年的统考大纲中新增了考点“虚拟存储器性能影响因素及改进方式”。缺页率（缺页率高即为抖动）是影响虚拟存储器性能的主要因素，且缺页率又受到页面大小、分配给进程的页框数（取决于工作集页面置换算法以及程序的编制方法的影响。因此，该考点也与本节的内容相关。

缺页率¶

假设一个进程的逻辑空间为n页，系统为其分配的内存物理页框数为m（m\<n）。如果在进程运行过程中，访问页面成功（即所访问页面在内存中）的次数为S，访问页面失败（即所访问页面不在内存中，需要从外存调入）的次数为F，则该进程总的页面访问次数为：A=S+F，该进程在其运行过程中的缺页率为：f=F/A。

通常，缺页率会受到以下几个因素的影响。

①页面大小：根据局部性原理，页面较大则缺页率较低，页面较小则缺页率较高。页面较小时，一方面减少了内存碎片，有利于提高内存利用率；另一方面，也会使每个进程要求较多的页面，导致页表过长，占用大量内存。页面较大时，虽然可以减少页表长度，但会使页内碎片增大。

②进程所分配物理页框的数目：所分配的页框数目越多，缺页率越低；反之，缺页率越高。

但是当页框超过某个数目时，再为进程增加一个页框对缺页率的改善是不明显的。可见，此时已没有必要再为它分配更多的页框，否则也只能是浪费内存空间。只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可。

③页面置换算法：算法的优劣决定了进程执行过程中缺页中断的次数，因此缺页率是衡量页面置换算法的重要指标。

④程序固有特性：程序本身的编制方法对缺页中断次数有影响，根据程序执行的局部性原理，程序编制的局部化程度越高，相应执行时的缺页程度就越低。

事实上，在缺页中断处理时，当由于空间不足而需要置换部分页面到外存时，选择被置换页面还需要考虑置换的代价，例如页面是否被修改过。没有修改过的页面可以直接放弃，而已

被修改过的页面则必须进行保存，因此处理这两种情况时的耗时是不同的。假设被置换的页面被修改的概率是β，其缺页中断处理时间是$t_a$，被置换页面没有被修改的缺页中断时间是$t_b$，那么，缺页中断处理时间的计算公式可表示为：$t=β×t_a+(1-β)×t_b$

CPU利用率与并发进程数的关系及“抖动”¶

由于虚拟存储器可以从逻辑上扩充内存，只要装入一个进程的部分程序和数据，进程便可以运行，因此人们便增加并发进程的道数以提高CPU的利用。然而

CPU利用率与并发进程数存在相互促进和制约的关系

进程数少时，提高并发进程数，可提高CPU利用率
并发进程导致内存访问增加
并发进程的内存访问会降低了访存的局部性特征
局部性特征的下降会导致缺页率上升和CPU利用率下降（发生了抖动）

产生“抖动”的根本原因：同时在系统中运行的进程太多，导致分配给每个进程的页框数太少，不能满足进程正常运行的基本要求，进程运行时频繁缺页，进而导致在系统中排队等待页面换入/换出的进程数量增加。显然，对磁盘的有效访问时间也会随之急剧增加，造成每个进程的大部分时间都用于页面的换入换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降而趋于0的情况。我们称此时的进程处于“抖动”状态。

由于“抖动”的发生与系统为进程分配的页框数（驻留集）有关，因此有人提出了“工作集”这个概念。

工作集¶

工作集：指在某段时间间隔里，进程实际访问页面的集合

基于局部性原理，可以用最近访问过的页面来确定工作集。工作集W可以由时间t和工作集窗口大小Δ来确定

如下，假设系统为该进程设定的工作集窗口大小为Δ =5，那么在t₁进程工作集为{2,3,5}；在t₂进程工作集为{1,2,3,4}

工作集大小可能小于窗口尺寸。实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。比如窗口尺寸为5，经过一段时间监测后发现某进程的工作集最大为3，那么说明该进程具有良好的局部性，所以可以给该进程分配三个以上的内存块即可满足运行时的需要。

一般来说，驻留集大小不能小于工作集大小，否则将导致频繁换页（“抖动”）

【2016-29】某进程访问页面的序列如下所示。

若工作集的窗口大小为6，则在t时刻的工作集为（）。

A. {6, 0, 3, 2}

B. {2, 3, 0, 4}

C. {0, 4, 3, 2, 9}

D. {4, 5, 6, 0, 3, 2}

抖动的预防方法¶

页框分配与置换时采取局部置换策略：当某进程发生缺页时，只能在分配给它的内存空间内进行置换，而不允许从其他进程的内存空间中去获得新的物理块。这样，即使该进程发生了“抖动”，也不会对其他进程产生影响；
作业调度时考虑工作集因素：从外存调入作业之前，必须先检查每个进程在内存中的驻留页面是否足够。若都足够，则可以调入新作业并为其分配页框，此时不会因为新作业的调入导致缺页率的增加；若有些进程的内存页面不够，则应该为这些进程优先分配页框，暂时不会调入新作业。
当并发进程数目已经影响到CPU的利用率时，为了预防“抖动”，会主动调出优先级低（或剩余执行时间最多）的进程，将其挂起，换出到磁盘，腾出页框分配给其他进程；

请求分页系统的内存有效访问时间¶

Note

以下讨论的前提：考虑一级页表，且设访问内存的时间为$t$，处理缺页异常的时间为 $\varepsilon$，查询TLB的时间为$\lambda$；由于CPU处理速度远高于其访存速度，因此分析逻辑地址、获取页号和页内偏移量等CPU处理时间忽略不计；

被访问页在内存中，且其对应的页表项在TLB里

$EAT=\lambda + t$

被访问页在内存中，但是不在TLB里

流程为查找TLB、去内存查找页表、更新TLB、访存

$EAT=\lambda + t +\lambda+t=2\times （\lambda + t）$

注意查找TLB和页表也可以并行进行，一切根据题目要求来

被访问页不在内存
访问TLB未命中，用时$\lambda$
访问页表缺失，用时$t$，触发缺页
缺页异常处理耗时$\varepsilon$（一般来说缺页异常只会修改页表，但是不排除题目告诉你同时修改页表和TLB，这里假设仅修改页表）
重新执行缺页的指令，访问TLB缺失，用时$\lambda$
页表命中，用时$t$
修改TLB，用时$\lambda$
使用获得的物理地址访存，用时$t$

$EAT=3\lambda + \varepsilon +3t$，考虑快表命中率$\alpha$和缺页率$f$后，该计算公式变为

$EAT=\alpha \times （\lambda + t）+（1-\alpha ）\times （1-f）\times (2（\lambda + t）)+（1-\alpha ）\times f\times (3\lambda + \varepsilon +3t)$，

化简得$EAT=[(2+f)−α(1+f)]λ+[(2−α)+f(1-α)]t+f(1−α)ε$

Note

在做这类题目时，一定不能死板，要看清楚题目要求，尤其注意以下两点

缺页异常处理，是只修改页表还是同时修改页表和TLB
缺页异常处理将页面调入内存以后，是重新执行发生缺页的那条指令，还是直接拿到的物理地址去访存；

一切根据题目要求计算，我所分析的只是最经典的一种情况；

【2011-29】当系统发生抖动 (thrashing) 时，可以采取的有效措施是（）。

Ⅰ. 撤销部分进程

Ⅱ. 增加磁盘交换区的容量

Ⅲ. 提高用户进程的优先级

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅱ

解析

本题选A。

“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页又很快被访问，必须换入，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，引起系统性能下降甚至崩溃。

引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的，只能增加内存容量。增加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情况下增加物理内存条），或者，降低进程数量，相对地增加内存。

I正确。撤销部分进程可以相对地增加内存。

II错误。增加交换区容量(位于磁盘)并不能解决内存不足的问题。

Ⅲ错误。提高用户进程的优先级并不能解决内存不足的问题。

综上，仅I正确。

【2020-28】下列因素中，影响请求分页系统有效（平均）访存时间的是（）。

Ⅰ. 缺页率

Ⅱ. 磁盘读写时间

Ⅲ. 内存访问时间

Ⅳ. 执行缺页处理程序的CPU时间

A. 仅Ⅱ、Ⅲ

B. 仅Ⅰ、Ⅳ

C. 仅Ⅰ、Ⅲ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ和Ⅳ

解析

本题选D。

I正确。较低的缺页率意味着较少的页面置换操作，从而减少了系统的I/O开销和额外的访存开销，从而减少平均访存时间。

Ⅱ正确。在请求分页系统中，当发生缺页时，需要从磁盘读取相应的页面到内存中。磁盘读写时间是影响有效访存时间的重要因素之一。较低的磁盘读写时间可以加快页面的加载和替换操作，从而减少平均访存时间。

Ⅲ正确。内存访问时间指的是从CPU发出一个访存请求到得到相应数据的时间。较低的内存访问时间能够提高请求分页系统的响应速度，从而减少平均访存时间。

Ⅳ正确。执行缺页处理程序所需的CPU时间会影响有效访存时间。较低的CPU时间可能导致请求分页系统的响应速度变慢，从而增加平均访存时间。

综上，Ⅰ、Ⅱ、Ⅲ和Ⅳ正确。

【2022-30】下列选项中，不会影响系统缺页率的是（）。

A. 页面置换算法

B. 工作集的大小

C. 进程的数量

D. 页缓冲队列的长度

解析

本题选D。

A错误。页面置换算法的选择会直接影响到系统的缺页率。不同的页面置换算法具有不同的策略和性能指标，会对缺页率产生影响。

B错误。工作集是指进程在其过去的t个虚拟执行时间中访问的页的集合。如果工作集较小，可以更容易将常用页面保留在内存中，从而减少缺页率。因此工作集的大小会对缺页率产生影响。

C错误。较多的进程意味着可能会有更多的内存页被占用，如果这些进行被分配的内存有限，则对内存资源的竞争会更加激烈，从而增加了发生页面置换的机会，导致更高的缺页率。

D正确。页缓冲队列是为了减少磁盘IO频率的，即减少已修改页写回磁盘的频率，具体内容见页框回收那边的介绍。

3.2.8 内存映射文件(`Memory-Mapped Files`)¶

需要先了解文件IO相关的知识后才能理解这部分内容

Note

关键点：

虚拟内存管理是在物理内存与进程虚拟地址空间建立映射关系，而内存映射文件mmap()是在磁盘上的文件与进程虚拟地址空间之间建立映射关系；
没有mmap()之前，访问磁盘上的文件数据需要通过read()/write()等系统调用，学习了IO相关的知识我们知道，这需要先将磁盘上的文件复制到内核缓冲区，再将其复制到用户缓冲区；而mmap()由于建立了磁盘文件与进程虚拟地址空间的映射，在缺页中断IO的过程中，直接将该文件读取进内存中的用户空间，不需要拷贝；

一句话，mmap是一种将文件或设备直接映射到进程虚拟地址空间的机制，使得进程可以像访问内存一样读写文件，从而避免频繁的系统调用（如 read/write）和数据拷贝。

内存映射文件的工作原理：

用户使用open()打开映射文件，返回一个文件描述符fd；
通过mmap(*addr,length,fd...)系统调用发起请求，内核会在进程的虚拟地址空间分配一段连续的虚拟内存区域，用于映射磁盘上的文件，如图页表所示；
正如上图所示，此时并没有立即加载文件数据到内存之中；
按需加载：当进程首次访问这段虚拟内存的某个页面时，发现存在位为0，触发缺页中断，内核找到该页面对应的文件数据后，为其分配一个物理页框，然后将其加载到里面，并更新页表，此时才真正建立了虚拟内存到物理内存的映射；
至此，该页框里的数据即为磁盘中该文件在内存中的副本，后续对这段虚拟内存的读写会直接作用于内存中的该页（文件缓存页），修改该内存的内容会标记脏位，内核会在适当时机（如内存不足将该页面换出、或者关闭文件时）将修改写回磁盘。

多个进程还可以允许并发地内存映射同一文件，以便允许数据共享。任何一个进程的写入会修改虚拟内存的数据，并且其他映射同一文件部分的进程都可看到。根据虚拟内存的相关知识可以清楚地看到内存映射部分的共享是如何实现的：每个共享进程的虚拟内存映射指向物理内存的同一页面，而该页面有磁盘块的复制。这种内存共享如下图所示。内存映射系统调用还可以支持写时复制功能，允许进程既可以按只读模式来共享文件，也可以拥有自己修改的任何数据的副本。为了协调对共享数据的访问，有关进程可以使用同步与互斥中描述的实现互斥访问的机制。

注意，在多个进程共享某一个磁盘文件时，某个进程关闭文件，并不会触发文件同步并且解除映射，因为这个文件描述符会有个引用计数，此时只会引用计数--；一般来说，解除映射需要调用 munmap(addr, length)

内存映射文件的优点：

减少数据拷贝：传统 read/write 需要数据在内核缓冲区和用户缓冲区之间拷贝，而 mmap 直接操作页缓存，零拷贝。
方便程序员访问磁盘文件：对于已经建立映射的文件，可以像访问内存一样读写，尤其是频繁随机访问大文件的场景，无需多次 lseek移动读写指针。
文件的读入读出全部由操作系统内核实现（缺页异常服务程序读入数据，内核负责将脏数据写回磁盘），不需要用户使用read()、write()等各种系统调用；
方便多个进程共享同一个文件：多个进程映射同一文件时，共享内存中的同一份页缓存，既可提升效率，也能够实现进程间通信；
文件按需加载进内存，节约物理内存占用；（访问到哪一页，从磁盘调入哪一页，不需要将整个文件读入内存）
可以显著提升IO密集型进程的效率；

传统的文件访问访问方式需要经历以下几个步骤：open()——打开文件、seek()——将读写指针移到某个位置、read()——从读写指针所指位置读入若干数据（从磁盘读入内存）、write()——将内存中的指定数据，写回磁盘（根据读写指针确定要写回什么位置），这样访问文件的话需要经历一系列系统调用和磁盘I/O,系统调用需要切换到内核态，磁盘I/O也很耗时，这样看来时间开销属实很大；

如果我们采用虚拟内存技术，将文件I/O作为常规内存访问,这种方法称为内存映射文件，允许一部分虚拟内存与文件进行逻辑关联,这将会大大方便程序员访问文件数据。

为什么read/write()需要数据在内核缓冲区和用户缓冲区之间拷贝，而mmap()缺页时就可以直接写到用户空间？

Note

首先，对于read/write(fd,*buf,count)，os内核会根据进程打开文件表里的读写指针和需要读写的文件长度(count)，确定所读区域位于fd所指的文件中的哪些磁盘块，然后依次将这些磁盘块通过dma读入内存中的内核缓冲区（注意，文件系统与主存的交换单位是磁盘块，一次只能读入一整块，不存在说只读入自己需要的部分像是半块这样子），之后再将自己需要的指定字长的数据复制到用户指定空间buf里面；（用户没有权限读入一整个磁盘块到用户空间，因为这一整块里面除了用户需要的数据，剩下的数据可能是敏感数据，不能放到用户空间）；注意，在将磁盘块读入到内核缓冲区时，发起该系统调用的进程会阻塞，直到I/O完成才会将其唤醒，等待其被调度程序选择上处理机时才会继续执行剩下的部分，也就是把数据复制到buf里面；

而缺页异常处理的时候，也会发生阻塞，只不过这里跟磁盘交换的单位是页面，因此在DMA预处理的时候，直接将分配给该页的页框(内存)物理地址写到DMA控制器里的主存地址寄存器(相当于锁定了物理地址，无所谓阻塞引起进程切换发生的进程地址空间切换)，之后DMA控制器负责直接将所需页面加载到指定页框里面(用户地址空间)；你可能会问，为什么这里就可以直接写到用户空间，不用先写到内核缓冲区？这是因为缺页处理程序读入的是一整个页面，这个页面都是属于这个进程的，进程有权限访问这个页面的所有内容，不存在读入不该读的敏感数据，所以可以直接把整个页调入用户空间；

注意这里提到的磁盘块和页面，二者是没有关系的，操作系统以页为单位进行内存和磁盘的交换，而文件系统以块为单位管理磁盘存储。如果一个页面大小是磁盘块大小的n倍，那么一次缺页异常，文件系统可能需要读取多个块，只不过页面和块大小对齐更方便而已，二者的大小并没有实质上的关系；

补充：内存映射I/O（即在I/O控制器那一节提到的I/O端口的统一编址方式）

在I/O的情况下，我们知道每个I/O控制器包括保存命令和传输数据的寄存器，通常专用I/O指令允许在这些寄存器和系统内存之间进行数据传输。为了更方便地访问I/O设备，许多计算机体系结构提供了内存映射|/O。在这种情况下，一组内存地址专门映射到设备寄存器。对这些内存地址的读取和写入，导致数据传到或取自设备寄存器。这种方法适用于具有快速响应时间的设备，例如视频控制器。对于IBM PC,屏幕上的每个位置都映射到一个内存位置。在屏幕上显示文本几乎和将文本写入适当内存映射位置一样简单。内存映射I/O也适用于其他设备，如用于联结modem和打印机的计算机串口和并口。通过读取和写入这些设备寄存器（即I/O端口)，CPU可以对这些设备传输数据。

年份	考点	分值
2009	选择题：内存保护、分段存储管理的地址转换应用题：请求分页管理、访存时间分析、页面置换算法、驻留集、虚实地址转换	4+8=\(12\)分
2010	选择题：动态分区分配存储管理、动态分配分区算法、两级页表地址转换应用题：地址转换、页面置换算法(\(FIFO\)、\(CLOCK\))	4+8=\(12\)分
2011	选择题：缺页处理、抖动、地址变换、程序的连接与装入应用题：计组那里考了虚拟存储，涉及了虚实地址转换与\(TLB\)	3*2=\(6\)分
2012	选择题：虚拟存储的基本概念、虚拟存储容量应用题：请求分页存储管理、驻留集、页面置换算法、局部性原理	2+8=\(10\)分
2013	选择题：缺页中断、内存保护应用题：基本分页存储管理（二级页表、地址转换）	2+8=\(10\)分
2014	选择题：虚实地址转换、\(TLB\)、页面置换算法、多级页表	3*2=\(6\)分
2015	选择题：页面置换算法(\(LRU\))、【页面分配策略、页面置换策略】(可变/固定分配、全局/局部置换) 应用题：基本分页存储、二级页表、虚实地址转换	2*2+6=\(10\)分
2016	选择题：页面置换算法(改进型\(CLOCK\))、分段存储管理的地址转换、工作集应用题：计组部分考察到了页式虚拟存储管理、\(TLB\)等	3*2=\(6\)分
2017	选择题：动态分区分配存储管理及回收、动态分配分区算法应用题：二级分页虚拟存储管理、地址转换	2+4=\(6\)分
2018	应用题：计组考察了与虚拟存储有关的问题，TLB、虚拟地址分析、页面置换算法(改进型\(CLOCK\))、地址转换	\(9\)分
2019	选择题：分段存储管理、页置换算法、局部置换策略。二级分页存储管理地址转换、动态分区分配算法	4*2=\(8\)分
2020	选择题：请求分页存储管理访存时间分析应用题：请求分页存储管理、二级页表、地址转换、局部性原理	2+8=\(10\)分
2021	选择题：地址转换、页面置换算法(改进型\(CLOCK\))、页表基址寄存器应用题：计组的存储系统部分考察了虚拟地址转换、\(TLB\)、页面置换算法	4+8=\(12\)分
2022	选择题：缺页处理、缺页率、页面置换算法、工作集	2*2=\(4\)分
2023	选择题：虚拟地址空间、页与页框号	2*2=\(4\)分

第三章内存管理¶

【考纲内容】¶

【本章学习建议】¶

【考频统计】¶

3.1 内存管理基础¶

3.1.1 程序的链接与装入¶

程序的装入¶

程序的链接¶

3.1.2 内存管理的主要功能：¶

3.1.2.1 内存空间的分配与回收¶

3.1.2.2 内存空间的扩展¶

覆盖技术：主要用来解决程序大小超过物理内存总和的问题¶

交换¶

3.1.2.3 地址转换¶

3.1.2.4 内存保护¶

3.1.2.5 内存共享¶

3.1.3 连续分配管理方式¶

采用的数据结构（主要有两种）¶

基于顺序搜索的动态分区分配算法（顺序分配算法）¶

基于索引搜索的分配算法¶

快速适应(quick fit)算法（我觉得不会考）¶

伙伴系统(buddy system)¶

Hash算法¶

非连续分配管理方式¶

3.1.4 基本分页存储管理¶

3.1.4.1 基本概述¶

3.1.4.2 地址转换¶

3.1.4.3 多级页表¶

3.1.5 基本分段管理方式¶

3.1.5.1 基本概述¶

3.1.5.2 分段存储管理的地址转换¶

3.1.5.3 分段和分页管理比较¶

3.1.6 段页式管理方式¶

3.1.6.1 段页式管理基本概念¶

3.1.6.2 段页式管理的地址转换¶

3.2 虚拟内存管理¶

3.2.1 虚拟内存的基本概念¶

3.2.2 请求分页管理方式的硬件支持¶

请求页表机制¶

缺页中断机构¶

地址变换机构¶

3.2.3 页框分配（请求分页中的内存分配）¶

进程所需最少页框数的确定（考过，重要难理解）¶

页框分配/置换策略¶

页框分配算法¶

3.2.4 页面调入策略¶

什么时候调入页面¶

从哪里调入页面¶

如何调入页面¶

3.2.5 页面置换算法¶

最佳置换算法（OPT，Optimal）¶

先进先出算法（FIFO）¶

最近最久未使用置换算法(LRU，least recently used)¶

时钟置换算法（CLOCK）¶

简单时钟置换算法,又称最近未使用算法(NRU,Not Recently Used)¶

改进型时钟置换算法¶

该部分真题¶

3.2.6 页框回收¶

影响页面换入换出的影响因素¶

页面缓冲算法¶

哪些页框可以被回收¶

连续页框分配算法--伙伴算法的页框回收¶

3.2.7 虚拟存储器性能影响因素¶

缺页率¶

CPU利用率与并发进程数的关系及“抖动”¶

工作集¶

抖动的预防方法¶

请求分页系统的内存有效访问时间¶

3.2.8 内存映射文件(Memory-Mapped Files)¶

最佳置换算法（`OPT，Optimal`）¶

最近最久未使用置换算法(`LRU，least recently used`)¶

时钟置换算法（`CLOCK`）¶

简单时钟置换算法,又称最近未使用算法(`NRU,Not Recently Used`)¶

3.2.8 内存映射文件(`Memory-Mapped Files`)¶