操作系统学习笔记 | 第三章 内存管理

第三章 内存管理

该笔记基于 B 站 Up主 无涯的小丑 的 408 笔记：15万字408笔记分享！在学习后添加了自己的理解。

3.1 内存管理功能

3.1.1 基本概念

​ 内存可存放数据，数据执行前需要先放到内存中才能被 CPU 处理。因为 CPU 读取数据的速度非常快，单位是纳秒级，而磁盘读取数据非常慢，单位是毫秒级。因此，把数据预先加载到内存，CPU 可以非常快速地从内存读取数据，大大缓解了等待的时间。

​ 内存的存储单元地址格式为如下三种：

1. 按字节编址，每个存储单元大小为 1 字节，1B，8个二进制位。

   ​ 假设内存地址如下：

   地址	存储内容
   0	A
   1	B
   2	C
   3	D

   ​ 地址 0 指向 A，地址 1 指向 B，地址 2 指向 C，地址 3 指向 D，每个地址存储 1 字节。每个地址指向 1 字节，地址连续，每次地址 + 1 就是下一个字节。现代计算机基本都是按字节编址。

2. 按字编址，字长 16 位，每个存储单元大小为 1 个字，16 个二进制位。

   ​ 假设内存地址如下：

   地址	存储内容
   0	A B
   1	C D
   2	E F

   ​ 地址 0 指向 2 个字节（A 和 B），地址 1 指向 2 个字节（C 和 D），地址 2 指向 2 个字节（E 和 F）。每次地址+1，跳过2字节。老式16位计算机使用较多。

​ 需要注意的是，指令的工作基于地址，每个地址对应一个数据的存储单元。地址又分为逻辑地址和物理地址，程序经过编译、链接后生成的指令中指明的是逻辑地址，即：相对于进程的起始地址而言的地址——与之相反的是物理地址。

​ 不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存不同位置。逻辑地址转换成物理地址的过程，称为地址重定位。

​ 从写程序到程序运行需要三个步骤：

1. 编译：由编译程序将用户源代码编译成若干个目标模块，就是把高级语言翻译为机器语言。
2. 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块，链接时要修改相对地址。
3. 装载：由装入程序将装入模块装入内存运行，装入后形成物理地址。

Q：什么是“若干个目标模块”？

​ 当你编写一个较大的程序，比如一个完整的APP，通常会分成多个源代码文件，比如 main.c、math.c 和 display.c 等，每个源文件通常编译成一个目标模块，也称为目标文件。所谓 “若干个目标模块”即为每个源代码文件单独编译，生成一个对应的目标模块，比如，main.c 编译成 main.o，math.c 编译成 math.o。

​ 这样做的目的在于，如果程序很大，改了一个小文件，没必要整个项目重新编译，只需要重新编译改动的源文件，其他目标模块可以复用。比如只改了 math.c，只需要重新生成 math.o，其他文件的目标模块不动。

Q：如何理解逻辑地址和物理地址？

​ 逻辑地址是程序自己看到和使用的地址，物理地址是实际内存条上的物理位置。可以类比家庭住址，我的门牌号是 A 栋 301，这是逻辑地址，而物理地址是实际的 GPS 坐标。

​ 需要注意的是，每个进程都有独立的地址空间，彼此完全隔离。进程 A 的变量 X 的逻辑地址是 0x00001000，进程 B 的变量 Y 的逻辑地址也是 0x00001000。看起来这两个地址一样，实际上对进程 A 来说，0x00001000 可能映射到物理内存的 0x7FFB1000，对进程 B 来说，0x00001000 可能映射到物理内存的 0x80002000。

3.2 连续分配管理方式

3.2.1 三种分配管理方式

​ 连续分配指的是为用户进程的分配必须是一个连续的内存空间。

1. 单一连续分配

   ​ 在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。

   ​ 内存中只能有一道用户程序，用户程序独占整个用户区空间。如图 3-2 所示，用户进程 A 尽管只有那么大，但是它会独占整一个用户区。优点是实现简单，无外部碎片，缺点是只能用于单用户、单任务的操作系统中，有内部碎片。

   ​ 内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。外部碎片，是指内存中的某些空闲分区由于太小而难以利用。

   

   图3-2 单一连续分配示意图.

2. 固定分区分配

   ​ 为了能在内存中装入多道程序，且这些程序之间又不会互相干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这就是固定分区分配方式。其中，图 3-3 所示的左图是分区大小相等的类别，右图则是分区大小不等的类别。

   ​ 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合。比如，钢铁厂有 n 个相同的炼钢炉，就可把内存分为 n 个大小相等的区域存放 n 个炼钢炉控制程序。

   ​ 分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分。比如，划分多个小分区、适量中等分区、少量大分区。

   ​ 固定分区分配的优点是实现简单，无外部碎片。但缺点是当用户程序太大时，可能所有的分区都不能满足需求，且会产生内部碎片，内存利用率低。

   

   图3-3 固定分区分配示意图.

3. 动态分区分配

   ​ 动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

   ​ 动态分区分配没有内部碎片，但是有外部碎片。如果内存中空闲空间的总和本来可以满足某进程的要求但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑技术来解决外部碎片。

   Q：系统要用什么样的数据结构记录内存的使用情况？

   ​ 主要有两种数据结构：空闲分区表和空闲分区链。空闲分区表会记录当前用户空间中的分区号、分区大小、起始地址以及分区状态。空闲分区链会将每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息。

   Q：当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

   ​ 首次适应算法（First Fit）、最佳适应算法（Best Fit）、最坏适应算法（Worst Fit）以及临近适应算法（Next Fit）。

   

   图3-4 动态分区分配示意图.

3.2.2 动态分区分配算法

1. 首次适应算法

   ​ 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

   ​ 空闲分区以地址递增的次序排列。，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   ​ 如图 3-5 所示，进程 5 会对空闲分区链进行扫描，可见第一个分区就是满足大小的分区，因此进程 5 会被分配到第一个分区中。

   

   图3-5 首次适应算法示意图.

2. 最佳适应算法

   ​ 由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区即，优先使用更小的空闲区。

   ​ 空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   ​ 如图 3-6 所示，空闲分区表 / 链按分区大小增序排列，因此进程 6 会被分配到第二个分区中，分配完第二个分区剩下 1 MB，此时又会重新排序，第二个分区变成第一个分区。

   ​ 这种方法的缺点是，每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

3. 最坏适应算法

   ​ 为了解决最佳适应算法容易留下太多难以利用的小碎片，最坏适应算法在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

   ​ 和最佳适应算法同理，空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   ​ 这种方法的缺点是，每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了

4. 邻近适应算法

   ​ 首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

   ​ 空闲分区以地址递增的顺序排列（可排成一个环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

   ​ 首次适应算法每次都要从头查找，每次都需要检索低地址的小分区但是这种规则也决定了当低地址部分有更小的分区可以满足需求时会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来。邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用。

   

   图3-7 邻近适应算法示意图.

3.3 非连续分配管理方式

3.3.1 基本分页存储管理

3.3.1.1 基本分页存储管理的概念

​ 对于主存，将内存空间分为一个个大小相等的分区，每个分区就是一个“页框”，每个页框有一个编号，即“页框号”，从 0 开始编号。对于进程，将逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页面” 。每个页面也有一个编号，即“页号”，从 0 开始编号。操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。

​ 那么，操作系统如何知道进程的每个页面在内存中存放的位置呢？操作系统为每个进程建立一张页表，通常存在于 PCB 中。如图 3-8 所示，一个进程对应一张页表，进程的每个页面对应一个页表项，每个页表项由“页号”和“块号”组成，页表记录进程页面和实际存放的内存块之间的映射关系。

Q：每个页表项占多少字节？

​ 假设某系统物理内存大小为 4GB，页面大小为 4KB，则内存块大小 = 页面大小 = 4KB = $2^{12}$ B，故 4GB的内存总共会被分为 $2^{32}/2^{12}=2^{20}$ 个内存块。内存块号至少要用 20 bit 来表示，即至少需要 3B 来表示块号。

​ 此外，页号是不需要存储空间的，类似于数组下标。

Q：如何实现地址的转换？

​ 重定位寄存器指明了进程在内存中的起始位置，逻辑地址可以理解为相对于起始位置的偏移量。如果要访问逻辑地址 A，则首先需要确定逻辑地址 A 对应的页号 P，通过页表找到 P 号页面在内存中的起始位置，确定逻辑地址 A 的页内偏移量 W。那么，逻辑地址 A 对应的物理地址等于，P 号页面在内存中的起始位置，加上业内偏移量 W。

Q：如何确定一个逻辑地址对应的页号、业内偏移量？

​ 假设在某计算机系统中，页面大小是 50B。某进程逻辑地址空间大小为 200B，则逻辑地址 110 对应的页号、页内偏移量是多少？计算过程如图 3-9 所示。

图3-9 页号和业内偏移量的计算示意图.

3.3.1.2 基本地址变换机构

​ 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址 F 和页表长度 M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

1. 计算页号 P 和页内偏移量 W，如果用十进制数手算，则 $P=A/L$，$W=A\%L$，A 表示逻辑地址，L 表示页面大小。
2. 比较页号 P 和页表长度 M，若 $P\ge M$，则产生越界中断，否则继续执行。
3. 页表中页号 P 对应的页表项地址 = 页表起始地址 F + 页号 P * 页表项长度，取出该页表项内容 b，即为内存块号。
4. 计算 $E=b\ast L+W$，用得到的物理地址 E 去访存。

3.3.1.3 具有快表的地址变换机构

​ 快表又称为联想寄存器，是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常被称为慢表。此外，快表是一种专门的硬件，当进程切换的时候，快表的内容也会被清除。

1. CPU 给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。
3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。

3.3.1.4 两级页表

​ 在单级列表中，页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。此外，进程在一段时间内只需要访问某几个页面就可以正常运行了，因此没有必要让整个页表都常驻内存。

​ 两级页表的地址转换过程如下：

1. 按照地址结构将逻辑地址拆分成三部分。
2. 从 PCB 中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置。
3. 根据二级页号查表，找到最终想访问的内存块号。
4. 结合页内偏移量得到物理地址。

3.3.2 基本分段存储管理

​ 分段指的是进程的地址空间按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从 0 开始编址。

​ 程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。段表由段号、段长、段基址（段在内存中的起始位置，就是实际的物理地址）组成，如图 3-12 所示。

​ 分页和分段是两种常见的内存管理方式，页是物理单位，操作系统为了内存管理而划分的固定大小的内存块。页大小固定且由操作系统决定，分页的用户地址空间是一维的，程序员只需提供一个逻辑地址，系统自动分离页号和页内偏移。

​ 段是逻辑单位，用于满足用户的程序结构和需求，一个段通常表示一组逻辑相关的数据或代码（例如函数、数组等）。用户可见，程序员在编程时需要显式指定段名，且段长度不固定，依据程序设计而定。分段的用户地址空间是二维的，程序员在访问地址时，必须同时给出段号和段内地址。

3.3.3 请求分页管理方式

​ 缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断（故障）。

​ 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

​ 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

3.4 五种页面置换算法

1. 最优页面置换算法

   ​ 每次置换时，总是选择未来最长时间不会被访问或者永远不会再被访问的页面进行置换。优点是理论上缺页率最低，缺点是需要知道未来的访问序列，实际中无法实现，只能作为衡量其他算法的参照标准。

2. 先进先出页面置换算法

   ​ 总是置换最早进入内存的页面，即排在队列最前的页面。缺点是容易出现 Belady 异常：增加物理块数量，缺页次数反而可能增加。

3. 最近最久未使用算法

   ​ 每次置换时，选择距离当前时刻最近最久没有被访问的页面。需要记录每个页面上一次被访问的时间，或用时间栈、时间链表等结构来模拟。优点是缺页率比较低，实际效果接近最优算法，缺点是实现复杂，开销较大。

4. 时钟置换算法

   ​ 最近最久未使用算法的近似实现，每个页面设置一个访问位（0 或 1），页面被访问时，访问位置为 1。页面置换时，页面按循环队列检查：如果访问位是 0，直接置换。如果访问位是 1，清 0，继续检查下一个页面。优点是简单，性能接近最近最久未使用算法，硬件支持良好。

5. 改进型时钟算法

   ​ 在时钟置换算法的基础上，增加一个 修改位（M 位），考虑页面是否被修改过。优先置换访问位和修改位为 0 的页面，如果没有，依次考虑访问位为 0，和修改位为 1，如果还是没有，继续扫描并清零访问位。优点是进一步降低误判，减少页面写回次数。