2.5 本章疑难点
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 2.5 本章疑难点
### 1. 进程与程序的区别与联系
1）进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序，离开程序的进程没有存在的意义。从静态角度看，进程是由程序、数据和进程控制块（PCB）三部分组成的。而程序是一组有序的指令集合，是一种静态的概念。
2）进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命周期，是暂时存在的；而程序则是一组代码的集合，是永久存在的，可长期保存。
3）一个进程可以执行一个或几个程序，一个程序也可构成多个进程。进程可创建进程，而程序不可能形成新的程序。
4）进程与程序的组成不同。进程的组成包括程序、数据和PCB。
### 2. 银行家算法的工作原理
银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行试分配，并对分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免了死锁现象的发生。
### 3. 进程同步、互斥的区别和联系
并发进程的执行会产生相互制约的关系：一种是进程之间竞争使用临界资源，只能让它们逐个使用，这种现象称为互斥，是一种竞争关系；另一种是进程之间协同完成任务，在关键点上等待另一个进程发来的消息，以便协同一致，是一种协作关系。
<!-- page: 188 -->
视频讲解
# 【考纲内容】
## （一）内存管理基础
内存管理概念：逻辑地址与物理地址空间，地址变换，内存共享，内存保护，内存分配与回收
连续分配管理方式：页式管理；段式管理；段页式管理
## （二）虚拟内存管理
虚拟内存基本概念：请求页式管理；页框分配与回收；页置换算法
内存映射文件（Memory-Mapped Files）：虚拟存储器性能的影响因素及改进方式
# 【复习提示】
内存管理和进程管理是操作系统的核心内容，需要重点复习。本章围绕分页机制展开：通过分页管理方式在物理内存大小的基础上提高内存的利用率，再进一步引入请求分页管理方式，实现虚拟内存，使内存脱离物理大小的限制，从而提高处理器的利用率。
# 3.1 内存管理概念
在学习本节时，请读者思考以下问题：
1）为什么要进行内存管理？
2）多级页表解决了什么问题？又会带来什么问题？
在学习经典的管理方法前，同样希望读者先思考，自己给出一些内存管理的想法，并在学习过程中和经典方案进行比较。注意本节给出的内存管理是循序渐进的，后一种方法通常会解决前一种方法的不足。希望读者多多思考，比较每种方法的异同，着重掌握页式管理。
# 3.1.1 内存管理的基本原理和要求
内存管理（Memory Management）是操作系统设计中最重要和最复杂的内容之一。虽然计算机硬件技术一直在飞速发展，内存容量也在不断增大，但仍然不可能将所有用户进程和系统所需要的全部程序与数据放入主存，因此操作系统必须对内存空间进行合理的划分和有效的动态分配。操作系统对内存的划分和动态分配，就是内存管理的概念。
有效的内存管理在多道程序设计中非常重要，它不仅可以方便用户使用存储器、提高内存利用率，还可以通过虚拟技术从逻辑上扩充存储器。内存管理的主要功能有：
- 内存空间的分配与回收。由操作系统负责内存空间的分配和管理，记录内存的空闲空间、内存的分配情况，并回收已结束进程所占用的内存空间。
<!-- page: 189 -->
- 地址转换。程序的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，将逻辑地址转换成相应的物理地址。
- 内存空间的扩充。利用虚拟存储技术从逻辑上扩充内存。
- 内存共享。指允许多个进程访问内存的同一部分。例如，多个合作进程可能需要访问同一块数据，因此必须支持对内存共享区域进行受控访问。
- 存储保护。保证各个进程在各自的存储空间内运行，互不干扰。
在进行具体的内存管理之前，需要了解进程运行的基本原理和要求。
## 1. 逻辑地址与物理地址
### 附图图表 ▶ 进程虚拟地址空间的特点（2023）
编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址（或逻辑地址）。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间（或虚拟地址空间），对于32位系统，逻辑地址空间的范围为 $0\sim 2^{32} - 1$ 。进程在运行时，看到和使用的地址都是逻辑地址。用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的。不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。
物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。
操作系统通过内存管理部件（MMU）将进程使用的逻辑地址转换为物理地址。进程使用虚拟内存空间中的地址，操作系统在相关硬件的协助下，将它“转换”成真正的物理地址。逻辑地址通过页表映射到物理内存，页表由操作系统维护并被处理器引用。
## 2. 程序的链接与装入
创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：
### 附图图表 ▶ 编译、链接和装入阶段的工作内容（2011）
- 编译。由编译程序将用户源代码编译成若干目标模块。
- 链接。由链接程序将编译后形成的一组目标模块，以及它们所需的库函数链接在一起，形成一个完整的装入模块。
- 装入。由装入程序将装入模块装入内存运行。
将用户程序变为可在内存中执行的程序的步骤如图3.1所示。
图3.1 将用户程序变为可在内存中执行的程序的步骤
<!-- page: 190 -->
将一个装入模块装入内存时，有以下三种装入方式。
（1）绝对装入
绝对装入方式只适用于单道程序环境。在编译时，若知道程序将放到内存的哪个位置，则编译程序将产生绝对地址的目标代码。装入程序按照装入模块的地址，将程序和数据装入内存。程序中的逻辑地址与实际内存地址完全相同，因此不需对程序和数据的地址进行修改。
程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时再转换为绝对地址。
（2）可重定位装入
可重定位装入也称静态重定位。经过编译、链接后的装入模块的始址（起始地址）通常都是从0开始的，程序中使用的指令和数据的地址都是相对于始址而言的逻辑地址。可根据内存的当前情况，将装入模块装入内存的适当位置。在装入时对目标程序中的相对地址的修改过程称为重定位，地址转换通常是在进程装入时一次完成的，如图3.2(a)所示。
当一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则无法装入。作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。
（3）动态运行时装入
动态运行时装入也称动态重定位。程序若要在内存中发生移动，则要采用动态的装入方式。装入程序将装入模块装入内存后，并不会立即将装入模块中的相对地址转换为绝对地址，而是将这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器（存放装入模块的起始位置）的支持，如图3.2(b)所示。
动态重定位的优点：可以将程序分配到不连续的存储区；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享。
(a) 静态重定位
图3.2 重定位类型
(b) 动态重定位
对目标模块进行链接时，根据链接的时间不同，分为以下三种链接方式。
（1）静态链接
在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装入模块，以后不再拆开。将几个目标模块装配成一个装入模块时，需要解决两个问题：①修改相对地址，编译后的所有目标模块都是从0开始的相对地址，当链接成一个装入模块时要修改相对地址。②变换外部调用符号，将每个模块中所用的外部调用符号也都变换为相对地址。
（2）装入时动态链接
将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。其优点是便于修改和更新，便于实现对目标模块的共享。
<!-- page: 191 -->
## （3）运行时动态链接
在程序执行中需要某目标模块时，才对它进行链接。凡在程序执行中未用到的目标模块，都不会被调入内存和链接到装入模块上。其优点是能加快程序的装入过程，还可节省内存空间。
## 3. 进程的内存映像
不同于存放在硬盘上的可执行程序文件，当一个程序调入内存运行时，就构成了进程的内存映像。一个进程的内存映像一般有几个要素：
- 代码段：即程序的二进制代码，代码段是只读的，可以被多个进程共享。
- 数据段：即程序运行时加工处理的对象，包括全局变量和静态变量。
- 进程控制块（PCB）：存放在系统区。操作系统通过PCB来控制和管理进程。
- 堆：用来存放动态分配的变量。通过调用malloc函数动态地向高地址分配空间。
- 栈：用来实现函数调用。从用户空间的最大地址往低地址方向增长。
代码段和数据段在程序调入内存时就指定了大小，而堆和栈不一样。当调用像malloc和free这样的C标准库函数时，堆可以在运行时动态地扩展和收缩。用户栈在程序运行期间也可以动态地扩展和收缩，每次调用一个函数，栈就会增长；从一个函数返回时，栈就会收缩。
图3.3是一个进程在内存中的映像。其中，共享库用来存放进程用到的共享函数库代码，如printf()函数等。在只读代码段中，init是程序初始化时调用的_init函数；text是用户程序的机器代码；rodata是只读数据。在读/写数据段中，data是已初始化的全局变量和静态变量；bss是未初始化及所有初始化为0的全局变量和静态变量。
图3.3 一个进程在内存中的映像
## 4. 内存保护
### 的最短篇 分区分配内存保护的措施（2009）
确保每个进程都有一个单独的内存空间。内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。内存保护可采取两种方法：
1）在CPU中设置一对上、下限寄存器，存放用户进程在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。
2）采用重定位寄存器（也称基地址寄存器）和界地址寄存器（也称限长寄存器）进行越界
<!-- page: 192 -->
检查。重定位寄存器中存放的是进程的起始物理地址，界地址寄存器中存放的是进程的最大逻辑地址。内存管理部件将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元，如图3.4所示。
图3.4 重定位寄存器和界地址寄存器的硬件支持
实现内存保护需要重定位寄存器和界地址寄存器，因此要注意两者的区别。重定位寄存器是用来“加”的，逻辑地址加上重定位寄存器中的值就能得到物理地址；界地址寄存器是用来“比”的，通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界。
加载重定位寄存器和界地址寄存器时必须使用特权指令，只有操作系统内核才可以加载这两个存储器。这种方案允许操作系统内核修改这两个寄存器的值，而不允许用户程序修改。
## 5. 内存共享
并不是所有的进程内存空间都适合共享，只有那些只读的区域才可以共享。可重入代码也称纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码。但在实际执行时，也可以为每个进程配以局部数据区，将在执行中可能改变的部分复制到该数据区，这样，程序在执行时只需对该私有数据区中的内存进行修改，并不去改变共享的代码。
下面用一个例子来说明内存共享的实现方式。考虑一个可以同时容纳40个用户的多用户系统，他们同时执行一个文本编辑程序，若该程序有160KB代码区和40KB数据区，则共需8000KB的内存空间来支持40个用户。若160KB代码是可分享的纯代码，则不论是在分页系统中还是在分段系统中，整个系统只需保留一份副本即可，此时所需的内存空间仅为 $40\mathrm{KB}\times 40 + 160\mathrm{KB} = 1760\mathrm{KB}$ 。对于分页系统，假设页面大小为4KB，则代码区占用40个页面、数据区占用10个页面。为实现代码共享，应在每个进程的页表中都建立40个页表项，它们都指向共享代码区的物理页号。此外，每个进程还要为自己的数据区建立10个页表项，指向私有数据区的物理页号。对于分段系统，由于是以段为分配单位的，不管该段有多大，都只需为该段设置一个段表项（指向共享代码段始址，以及段长160KB）。由此可见，段的共享非常简单易行。
此外，在第2章中我们介绍过基于共享内存的进程通信，由操作系统提供同步互斥工具。在本章的后面，还将介绍一种内存共享的实现——内存映射文件。
## 6. 内存分配与回收
存储管理方式随着操作系统的发展而发展。在操作系统由单道向多道发展时，存储管理方式便由单一连续分配发展为固定分区分配。为了能更好地适应不同大小的程序要求，又从固定分区分配发展到动态分区分配。为了更好地提高内存的利用率，进而从连续分配方式发展到离散分配方式——页式存储管理。引入分段存储管理的目的，主要是满足用户在编程和使用方面的要求，其中某些要求是其他几种存储管理方式难以满足的。
## 3.1.2 连续分配管理方式
连续分配方式是指为一个用户程序分配一个连续的内存空间，譬如某用户需要100MB的内
<!-- page: 193 -->
存空间，连续分配方式就在内存空间中为用户分配一块连续的100MB空间。连续分配方式主要包括单一连续分配、固定分区分配和动态分区分配。
## 1. 单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；用户区内存中仅有一道用户程序，即用户程序独占整个用户区。
这种方式的优点是简单、无外部碎片；不需要进行内存保护，因为内存中永远只有一道程序。缺点是只能用于单用户、单任务的操作系统中：有内部碎片；内存的利用率极低。
## 2. 固定分区分配
固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的分区，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。在划分分区时有两种不同的方法。
- 分区大小相等。程序太小会造成浪费，程序太大又无法装入，缺乏灵活性。
- 分区大小不等。划分为多个较小的分区、适量的中等分区和少量大分区。
为了便于分配和回收，建立一张分区使用表，通常按分区大小排队，各表项包括对应分区的始址、大小及状态（是否已分配），如图3.5所示。分配内存时，便检索该表，以找到一个能满足要求且尚未分配的分区分配给装入程序，并将对应表项的状态置为“已分配”；若找不到这样的分区，则拒绝分配。回收内存时，只需将对应表项的状态置为“未分配”即可。
[tbl-68.md](tbl-68.md)
(a) 分区使用表
(b) 存储空间分配情况
图3.5 固定分区说明表和内存分配情况
这种方式存在两个问题：①程序太大而放不进任何一个分区；②当程序小于固定分区大小时，也要占用一个完整的内存分区，这样分区内部就存在空间浪费，这种现象称为内部碎片。固定分区方式无外部碎片，但不能实现多进程共享一个主存区，所以内存的利用率低。
## 3. 动态分区分配
### （1）动态分区分配的基本原理
动态分区分配也称可变分区分配，是指在进程装入内存时，根据进程的实际需要，动态地为之分配内存，并使分区的大小正好适合进程的需要。因此，系统中分区的大小和数量是可变的。
如图3.6所示，系统有64MB内存空间，其中低8MB固定分配给操作系统，其余为用户可用内存。开始时装入前三个进程，它们分别分配到所需的空间后，内存仅剩4MB，进程4无法装入。在某个时刻，内存中没有一个就绪进程，CPU出现空闲，操作系统就换出进程2，换入进程4。由于进程4比进程2小，这样在主存中就产生了一个6MB的内存块。之后CPU又出现空闲，需要换入进程2，而主存无法容纳进程2，操作系统就换出进程1，换入进程2。
动态分区在开始时是很好的，但是随着时间的推移，内存中会产生越来越多的小内存块，内存的利用率也随之下降。这些小内存块被称为外部碎片，它存在于所有分区的外部，与固定分区中的内部碎片正好相对。外部碎片可通过紧凑技术来克服，即操作系统不时地对进程进行移动和
<!-- page: 194 -->
整理。但是，这需要动态重定位寄存器的支持，且相对费时。紧凑过程实际上类似于 Windows 系统中的磁盘碎片整理程序，只不过后者是对外存空间的紧凑。
图3.6 动态分区分配
## 前期测试 ▶ 动态分区分配的内存回收方法（2017）
在动态分区分配中，与固定分区分配类似，设置一张空闲分区链（表），可以按始址排序。分配内存时，检索空闲分区链，找到所需的分区，若其大小大于请求大小，则从该分区中按请求大小分割一块空间分配给装入进程（若剩余部分小到不足以划分，则不需要分割），余下部分仍然留在空闲分区链中。回收内存时，系统根据回收分区的始址，从空闲分区链中找到相应的插入点，此时可能出现四种情况：①回收区与插入点的前一空闲分区相邻，此时将这两个分区合并，并修改前一分区表项的大小为两者之和；②回收区与插入点的后一空闲分区相邻，此时将这两个分区合并，并修改后一分区表项的始址和大小；③回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，并取消后一分区表项；④回收区没有相邻的空闲分区，此时应该为回收区新建一个表项，填写始址和大小，并插入空闲分区链。
以上三种内存分区管理方法有一个共同特点，即用户程序在主存中都是连续存放的。
## （2）基于顺序搜索的分配算法
将作业装入主存时，需要按照一定的分配算法从空闲分区链（表）中选出一个分区，以分配给该作业。按分区检索方式，可分为顺序分配算法和索引分配算法。顺序分配算法是指依次搜索空闲分区链上的空闲分区，以寻找一个大小满足要求的分区，顺序分配算法有以下四种。
## 前期测试 ▶ 各种动态分区分配算法的特点（2019、2024）
1）首次适应（First Fit）算法。空闲分区按地址递增的次序排列。每次分配内存时，顺序查找到第一个能满足大小的空闲分区，分配给作业。首次适应算法保留了内存高地址部分的大空闲分区，有利于后续大作业的装入。但它会使内存低地址部分出现许多小碎片，而每次分配查找时都要经过这些分区，因此增加了开销。
2）邻近适应（Next Fit）算法。也称循环首次适应算法，由首次适应算法演变而成。不同之处是，分配内存时从上次查找结束的位置开始继续查找。邻近适应算法试图解决该问题。它让内存低、高地址部分的空闲分区以同等概率被分配，划分为小分区，导致内存高地址部分没有大空闲分区可用。通常比首次适应算法更差。
## 前期测试 ▶ 最佳适应算法的分配过程（2010）
3）最佳适应（Best Fit）算法。空闲分区按容量递增的次序排列。每次分配内存时，顺序查找到第一个能满足大小的空闲分区，即最小的空闲分区，分配给作业。最佳适应算法虽然称为最佳，能更多地留下大空闲分区，但性能通常很差，因为每次分配会留下越来越多很小的难以利用的内存块，进而产生最多的外部碎片。
<!-- page: 195 -->
4）最坏适应（Worst Fit）算法。空闲分区按容量递减的次序排列。每次分配内存时，顺序查找到第一个能满足要求的空闲分区，即最大的空闲分区，从中分割一部分空间给作业。与最佳适应算法相反，最坏适应算法选择最大的空闲分区，这看起来最不容易产生碎片，但是把最大的空闲分区划分开，会很快导致没有大空闲分区可用，因此性能也很差。
综合来看，首次适应算法的开销小，性能最好，回收分区也不需要对空闲分区重新排序。
（3）基于索引搜索的分配算法
当系统很大时，空闲分区链可能很长，此时采用顺序分配算法可能很慢。因此，在大、中型系统中往往采用索引分配算法。索引分配算法的思想是，根据其大小对空闲分区分类，对于每类（大小相同）空闲分区，单独设立一个空闲分区链，并设置一张索引表来管理这些空闲分区链。当为进程分配空间时，在索引表中查找所需空间大小对应的表项，并从中得到对应的空闲分区链的头指针，从而获得一个空闲分区。索引分配算法有以下三种。
1）快速适应算法。空闲分区的分类根据进程常用的空间大小进行划分。分配过程分为两步：①首先根据进程的长度，在索引表中找到能容纳它的最小空闲分区链表；②然后从链表中取下第一块进行分配。优点是查找效率高、不会产生内存碎片；缺点是回收分区时，需要有效地合并分区，算法比较复杂，系统开销较大。
**附图图2** ▷ 伙伴关系的概念（2024）
2）伙伴系统。规定所有分区的大小均为 2 的 $k$ 次幂（$k$ 为正整数）。当需要为进程分配大小为 $n$ 的分区时（$2^{n-1} < n \leqslant 2^i$），在大小为 $2^i$ 的空闲分区链中查找。若找到，则将该空闲分区分配给进程。否则，表示大小为 $2^i$ 的空闲分区已耗尽，需要在大小为 $2^{i+1}$ 的空闲分区链中继续查找。若存在大小为 $2^{i+1}$ 的空闲分区，则将其等分为两个分区，这两个分区称为一对伙伴，其中一个用于分配，而将另一个加入大小为 $2^i$ 的空闲分区链。若不存在，则继续查找，直至找到为止。回收时，需要要将相邻的空闲伙伴分区合并成更大的分区。
3）哈希算法。根据空闲分区链表的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应空闲分区链的头指针。分配时，根据所需分区大小，通过哈希函数计算得到哈希表中的位置，从中得到相应的空闲分区链表。
在连续分配方式中，我们发现，即使内存有超过1GB的空闲空间，但若没有连续的1GB空间，则需要1GB空间的作业仍然是无法运行的；但若采用非连续分配方式，则作业所要求的1GB内存空间可以分散地分配在内存的各个区域，当然，这也需要额外的空间去存储它们（分散区域）的索引，使得非连续分配方式的存储密度低于连续分配方式。非连续分配方式根据分区的大小是否固定，分为分页存储管理和分段存储管理。在分页存储管理中，又根据运行作业时是否要将作业的所有页面都装入内存才能运行，分为基本分页存储管理和请求分页存储管理。
3.1.3 基本分页存储管理
固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想：将内存空间分为若干固定大小（如4KB）的分区，称为页框、页帧或物理块。进程的逻辑地址空间也分为与块大小相等的若干区域，称为页或页面。操作系统以页框为单位为各个进程分配内存空间。
从形式上看，分页的方法像是分区相等的固定分区技术，分页管理不产生外部碎片。但它又有本质的不同点：块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申
① 本章后面的内容与《计算机组成原理考研复习指导》一书的3.6节高度相关，建议结合复习。
<!-- page: 196 -->
请主存可用空间并执行。这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但这种碎片相对进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片（也称页内碎片）。