<操作系统>OS3 内存管理

OS3 内存管理

内存 是存放数据的硬件。程序执行前要先放到内存中才能被 CPU 处理。

为对并发执行的程序进行区分，需要给内存的 存储单元 编址。

按字节编址 的计算机，每个存储单元大小为 1 字节。按字编址 的计算机，存储单元的大小取决于其字长。

在一个指令中，要给出操作码和变量的 物理地址（实际存放地址）。但在生成机器指令时不知道该进程数据的地址，因此汇编时使用的是 逻辑地址（相对地址）。

编写的程序需要执行，要经过以下步骤：

1. 编译：由源代码生成若干目标模块（高级语言编译为机器语言）
2. 链接：将目标模块即所需库函数链接，生成装入模块。链接后形成完整的逻辑地址。
3. 装入：将装入模块装入内存，装入后形成物理地址。

操作系统负责对内存进行管理。其主要负责：

• 内存空间的分配与回收：分为 连续分配 和 非连续分配
• 对内存空间的扩充（如虚拟内存技术）
• 地址转换（地址重定位，逻辑地址与物理地址的转换）
• 内存保护（确保各进程在各自存储空间内互不干扰）

OS3.1 地址转换和内存保护

#地址转换

将逻辑地址转换为物理地址的过程称为 装入

装入有三种方式：

• 绝对装入

  在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按装入模块的地址，将程序和数据装入内存。

  绝对装入只适用于单道程序环境。

• 静态重定位（可重定位装入）

  指令中使用相对于初始地址而言的逻辑地址。根据内存的当前情况，将装入模块装入内存合适位置。装入时对地址 “重定位”，将逻辑地址一次性变换为物理地址。

  静态重定位要求作业装入内存时即分配其全部内存空间。一旦作业装入内存后就不能再移动或申请新空间。

• 动态重定位（动态运行时装入）

  装入程序将装入模块载入内存后，不立即进行地址转换，而是等到程序真正执行时再进行。此时装入内存的地址仍是逻辑地址。

  动态重定位需要一个 重定位寄存器 的支持。

  动态重定位可以将程序分配到不连续的存储区中。在程序只需装入部分代码即可运行，在运行期间根据需要动态分配内存。可以向用户提供一个比存储空间大得多的地址空间，以便于程序段的共享。

#内存保护

内存保护，就是要确保各进程在各自存储空间内互不干扰

内存保护有两种方法：

• 在 CPU 中设置一对 上/下限寄存器，存放进程的 上/下限地址。访问地址前检查是否越界。

  比如，采用 重定位寄存器（又称基址寄存器，存放起始物理地址）和 界地址寄存器（又称限长寄存器，存放最大逻辑地址）进行越界检查。合法的地址应满足 $\text{基址寄存器}\le\text{地址}\le\text{限长寄存器}$

• 权限保护

OS3.2 内存空间扩充

内存空间的扩充有三种技术：覆盖技术、交换技术、虚拟内存技术

#覆盖技术

按照程序自身的逻辑结构，使不能被同时访问的程序段共享同一覆盖区。

内存分为一个固定区和若干覆盖区。固定区内存放最活跃的程序段。不能同时访问的程序段共享一个覆盖区，在运行过程中根据需要调入和调出。

由于程序员必须声明覆盖结构，对用户不透明，增加了编程负担，只适用于早期操作系统中。

#交换技术（对换技术）

内存空间紧张时，系统将内存中某些进程换出外存（PCB 常驻内存），将外存中具备运行条件的进程换入内存。进程在内存与外存间动态调度。暂时换出内存的进程进入 挂起状态。

具有交换功能的操作系统中，将磁盘空间分为 文件区 和 对换区。

文件区存放文件，追求存储空间的 利用率，因而采用 离散分配方式 管理空间。

对换区只占磁盘很小部分，存放被换出的进程，追求换入换出的速度，因而采用 连续分配方式 管理空间。

在内存吃紧时进行交换，直至系统负荷降低后暂停。优先换出阻塞进程和优先级低的进程，换出时还会考虑进程在内存的驻留时间。

#虚拟内存技术

传统的存储管理方式存在缺点：作业必须一次性全部装入内存，且装入后会持续驻留内存。

局部性原理：

• 时间局部性：（因为程序中存在大量循环操作）如果执行了程序中的某指令，则该指令可能不久后被再次执行。若某数据被访问过，则该数据可能不久后被再次访问。

• 空间局部性：（因为很多数据在内存中是连续存放的）若程序访问了某个存储单元，则其附近的存储单元也可能在不久后被访问。

基于 局部性原理，人们提出 虚拟内存技术：程序装入时，将程序很快要用到的部分装入内存，用不到的部分留在外存。执行过程中，访问的信息不在内存时，再由操作系统将所需信息调入内存。此外，内存空间不足时，也由操作系统将内存中暂时用不到的信息换出到外存。

虚拟内存的 最大容量 由地址结构决定：若按字节编址的计算机地址结构有 n 位，则其最大容量为 2ⁿB

虚拟内存的 实际容量 是：计算机内外存容量和，与 CPU 寻址范围（最大容量），这两者中的较小值

虚拟内存技术允许作业多次调入内存，这需要非连续分配的内存管理方式。

OS3.3 内存空间的连续分配方式

为用户进程分配一个连续的内存空间，这种内存分配方式就是 连续分配。

内部碎片：分配给某进程的内存区域中，存在未使用的空间。

外部碎片：内存中的某些空闲分区由于太小而难以利用。可以通过 紧凑 技术解决外部碎片问题。

连续分配主要有：单一连续分配、固定分区分配、动态分区分配

#单一连续分配

将内存分为 系统区 和 用户区。

系统区通常位于低地址部分，存放操作系统相关数据。用户区存放用户进程相关数据。

这种情况下，内存中只能有一道用户程序，其独占整个用户区空间。

该方法实现简单，无外部碎片，不一定需要内存保护。但只适用于单用户、单任务的操作系统中，且存在内部碎片，内存利用率低。

#固定分区分配

将用户区分为若干固定大小的分区，每个分区中只装入一道作业。不同的分区大小可能相等，也可能不等。

操作系统需要建立一个 分区说明表 的数据结构，以实现各个分区的分配与回收。每个表项对应一个分区，内容包括分区大小、起始地址、分配状态。

该方法实现简单，无外部碎片。但有时用户程序很大，必须采用覆盖技术，会导致性能降低。且会产生内部碎片，内存利用率低。

#动态分区分配（可变分区分配）

不会预先划分内存分区，而是在进程装入内存时，根据其大小动态建立分区。因此，分区的大小与数量都是可变的。

使用 空闲分区表 或 空闲分区链 的数据结构记录内存使用情况。

将新作业装入内存时，须按照一定的 动态分配算法，从 空闲分区表/链 中选出一个分区分配给该作业。

动态分配算法主要有以下四种：

• 首次适应算法（First fit）

  从低地址起，从低到高，查找第一个满足条件的空闲分区。

• 最佳适应算法（Best fit）

  尽可能留下大片连续空间。在所有满足条件的空闲分区中，选择最小的空闲分区。

  该方法的缺点是会产生大量外部碎片。

• 最坏适应算法（Worst fit）

  又称最大适应算法。在每次分配时优先使用最大的连续空闲分区。

  该方法的缺点是不能留下大片连续空间，可能导致大进程无分区可用。

• 临近适应算法（Next fit）

  首次适应算法查找开销较大。为节省开销，每次都从上次结束位置起开始检索。

  临近适应算法隐含了部分最佳适应算法的优点，和一些最坏适应算法的缺点。但综合来看，临近适应算法在四种算法中效果最好。

回收空间时，若回收区与相邻空闲分区相连，则更新那个空闲分区的 大小 和/或 起始地址。必要时，合并连续的空闲分区。不相连时，增加空闲分区。

动态分区没有内部碎片，但会产生外部碎片。

OS3.4 内存空间的非连续分配方式

为用户分配分散的内存空间，这种内存分配方式称为 非连续分配。

非连续分配主要有：基本分页存储管理、基本分段存储管理、段页式存储管理、请求分段/分页/段页存储管理

#基本分页存储管理方式

将内存空间分为一个个大小相等的分区，每个分区是一个 页框（也称叶帧、内存块、物理块）。每个页框拥有一个 页框号。

将用户进程的地址空间也分成与页框大小相等的一个个区域，称为 页（也称页面），每个页面有一个 页号。页是信息的物理单位，分页是系统行为，对用户是不可见的。

操作系统以页框为单位分配内存空间，进程的每个页面对应一个页框。各个页面不需要连续存放，也不需要保持存放顺序。

计算物理地址时，先计算那个页号，再根据该页号在内存中的 起始地址，加上那个 页面内的偏移量，就是物理地址。

为方便计算页号和偏移量，页面大小通常为 2 的整数幂，此时末尾 k 尾为页内偏移量，其余部分为页号。如：页面大小为 2¹⁰，实际地址 3028（0000 1011 1101 0100），对应页号为 3（000010），页内偏移量为 980（1111010100）

若页面偏移量有 m 位，则说明页面大小是 2^m 个内存单元。若页号有 n 位，则说明该系统内一个进程最多有 2ⁿ 个页面。

操作系统为每个进程建立一张 页表，以建立页面与页框的对应关系。进程每一页对应一个 页表项，页表项由 页号 和 块号 组成。由于每个页表项长度相同，故页号实际上是 “隐含” 的。

分页的用户进程地址空间是一维的。程序员使用一个助记符就能表示一个地址。

• 基本地址变换机构

  系统使用 基本地址变换机构 以将逻辑地址变换为物理地址。

  • 在系统中设置一个 页表寄存器（PTR），其存放页表在内存中的起始地址 F 和页表长度 M。

    进程未执行时，页表起始地址 F 和页表长度 M 放在进程控制块（PCB）中。

    进程被调度时，操作系统内核将数据导入页表寄存器。

  • 若页面大小为 L（L 是 2 的整数幂），对于逻辑地址 A，计算其页号 P（P = A / L）和偏移量 W（W = A % L）。若页号 P≥M 则产生越界中断。

  • 从指定页表项中取出内存块号 b（页表项位置 = 页表起始地址 F + 页号 P * 页表项长度）

    根据那个内存块号，得到物理地址 E（E = b * L + W）。把内存块号、页面偏移量的二进制表示拼接就是那个物理地址。

  基本地址变换机构每次变换须访问两次内存（查询页表、访问物理地址），占用较大。

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

  根据 局部性原理，提出了 基本地址变换机构 的改进版，即 具有快表的地址变换机构

  • 在系统中设置一个 联想寄存器（TLB，也称 快表，是一种访问速度比内存快很多的高速缓冲寄存器），存放当前访问的若干页表项，以加速地址变换过程。与之对应的内存中的页表被称为 慢表。

  • 计算页号、偏移量，检查页号是否越界。

  • 在快表中查找页号对应的页表项。快表中未找到该页号时，再访问内存查找页表项，并在快表中记录该页表项。若在快表中找到页表项，则可以直接访问那个物理地址，此时只需一次内存访问。

  由于局部性原理，快表的命中率能达到 90% 以上，大幅节省了系统开销。

  还能通过 散列访问快表 从而对快表进行进一步优化。

• 两级页表

  单级页表必须连续存放，页表很大时须占用多个页框。此外，也没必要让页表始终常驻内存。为解决这些问题，又提出了 两级页表：

  • 将页表进行分组，使每个页框恰能存放一组。

  • 为离散分配的页表再建立一张页表，称为 页目录表（也称 外层页表、顶层页表）。页目录表中存放对应页表组所在的页框号。

  • 原先的页号被分为两部分。较高位部分为 一级页号，对应页目录表中查询的页表组号。较低位部分为 二级页号，对应页表组中目标页表的序号。

  以此类推，也能形成多级页表。采用多级页表时，各级页表的大小都不要超过一个页面。但是，页表的级数越多，内存访存次数就越多。

#基本分段存储管理方式

按程序自身逻辑关系，将地址空间划分为若干 段。每段有一个段名，从 0 开始编址。段是信息的逻辑单位，由用户划分，对用户可见。用户编程时显式给出段名。

内存以段为单位进行分配。每个段在内存中占用连续空间，但段与段可以不相邻。

该方式以逻辑功能模块划分段，用户编程方便，程序可读性高。

分段系统的逻辑地址由 段号 和 段内地址 组成。段号长度决定了进程最多划分的段数，段内地址长度决定了每段的最大长度。

操作系统要为每个进程建立一张段映射表，即 段表。每个段对应一个 段表项，其中记录了该段在内存的 起始位置 和 段长。段表项的长度相同，故 段号 也能隐含。

地址转换时，流程与分页存储基本相同。但由于段长不定，在获取物理地址时，分段存储要求额外检查地址是否越界。

分段的用户进程地址空间是二维的。程序员标识地址时，需要给出段名及段内地址。

由于段是按照逻辑划分的，所以分段存储比分页更便于实现 信息的共享和保护。可以更好地将 纯代码（也称可重入代码，即不能修改的代码）进行共享。

基本分段存储管理与分页管理一样，也能使用 快表 进行优化。

#段页式管理方式

分页式管理不便于信息的共享和保护，而分段式管理可能产生外部碎片。

先将进程 按逻辑模块分段，再 将各段分页，这就是段页式管理方式。分段对用户可见，但分页由操作系统完成，用户不可见。

段页式管理方式的逻辑地址分为三部分：段号、页号、页内偏移量。段号位数决定了进程最多分段数，页号位数决定了每段最大分页数，页内偏移量的位数决定页框大小。

系统为每个进程建立 段表，段表项由 段号（段表项长度固定，段号是隐含的）、页表长度、页表起始地址 组成。此外，还建立数个二级 页表，页表项由 页号（页表项长度固定，页号是隐含的）、页框起始地址 组成。

段页式管理方式需要进行三次访存，也能引入 快表 机制，用段号和页号作为关键字进行优化。

#请求分页管理方式

非连续管理方式中，可以引入 虚拟内存技术。由此派生出了 请求分页管理方式（基本分页+虚拟内存）、请求分段管理方式（基本分段+虚拟内存）、请求段页管理方式（段页+虚拟内存）

程序执行期间，当访问信息不在内存时，由操作系统将所需信息调入内存。若内存空间不够，由操作系统将暂时用不到的信息换出外存。

为实现 “请求调页”，操作系统须记录每个页面是否已调入内存，以及该页面在外存的位置。

为实现 “页面换出”，操作系统要通过某些指标决定换出的页面。还要记录页面是否修改，以节省调出时间。

由于以上原因，请求分页管理方式的 页表 中添加了四个字段：状态位（是否已调入）、访问字段（最近访问次数/时间，供置换算法参考）、修改位（是否修改）、外存地址

在请求分页管理中，访问页面不在内存中时，会产生一个 缺页中断，之后操作系统的中断处理程序将处理该中断。此时，缺页进程阻塞，待调页完成后将唤醒。页表调入后，修改慢表，并会导入快表项。

在请求分页管理方式中，决定换入、换出页面的算法是 页面置换算法。

页面置换算法主要有以下几类：

• 最佳置换算法（OPT，optimal）

  每次选择淘汰的页面是以后再不使用，或最长时间内不再被使用的页面。

  比如有如下页面号引用串：1,4,3,2,1,3,0,3,0,3，则其访问情况如下

  访问页面	1	4	3	2	1	3	0	3	0	3
  内存块 1	1	1	1	1	1	1	0	0	0	0
  内存块 2		4	4	2	2	2	1	1	1	1
  内存块 3			3	3	3	3	3	3	3	3
  缺页状态	缺页	缺页	缺页	缺页			缺页

  最佳置换算法能保证最低缺页率。但实际情况下，只有执行过程中才能直到接下来访问的页面。该算法只是理想化的算法，实际无法实现。

• 先入先出置换算法（FIFO）

  每次选择淘汰最早进入内存的页面。

  调入内存的页面按进入顺序形成队列，置换时弹出队头页面。

  比如有如下页面号引用串：1,4,3,2,1,3,0,3,0,3，则其访问情况如下

  访问页面	1	4	3	2	1	3	0	3	0	3
  内存块 1	1	1	1	2	2	2	2	3	3	3
  内存块 2		4	4	4	1	1	1	1	1	1
  内存块 3			3	3	3	3	0	0	0	0
  缺页状态	缺页	缺页	缺页	缺页	缺页		缺页	缺页

  该算法的缺点是当内存块增多时，缺页次数可能不减反增。这种现象称为 Belady 异常。

  只有该算法会产生 Belady 异常，算法性能差。

• 最近最久未使用算法（LRU，Least recently used）

  每次淘汰最近最久未使用的页面。

  在每个页表项中，用一个访问字段记录自上次被访问以来经历的时间，以供算法参考。

  比如有如下页面号引用串：1,4,3,2,1,3,0,3,0,3，则其访问情况如下

  访问页面	1	4	3	2	1	3	0	3	0	3
  内存块 1	1	1	1	2	2	2	0	0	0	0
  内存块 2		4	4	4	1	1	1	1	1	1
  内存块 3			3	3	3	3	3	3	3	3
  缺页状态	缺页	缺页	缺页	缺页	缺页		缺页

  该算法最接近 OPT 算法，性能最好，但开销大，实现困难。

• 时钟置换算法（CLOCK）

  也称 最近未用算法（NRU，not recently used）

  为每个页面添加一个访问位。页面被访问后，该访问位置为 1。

  检查页面访问位时，将访问位为 0 的换出，访问位为 1 的置 0。

  查找时的具体流程：

  1. 第一轮扫描：检查访问位为 0 的页面。同时，将所有页面访问位置为 0。
  2. 第二轮扫描：第一轮扫描未找到合适页面时执行。检查访问位为 0 的页面。此时必定能找到页面。

  比如有如下页面号引用串：1,4,3,2,1,3,0,3,0,3，则其访问情况如下

  访问页面	1	4	3	2	1	3	0	3	0	3
  内存块 1	1(1)	1(1)	1(1)	2(1)	2(0)	2(0)	0(1)	0(1)	0(1)	0(1)
  内存块 2		4(1)	4(1)	4(0)	1(1)	1(1)	1(0)	1(0)	1(0)	1(0)
  内存块 3			3(1)	3(0)	3(0)	3(1)	3(0)	3(1)	3(1)	3(1)
  缺页状态	缺页	缺页	缺页	缺页	缺页		缺页

  时钟置换算法最多经过两轮扫描就能找到淘汰页面。

• 改进型时钟置换算法

  如果被淘汰的页面未被修改，置换时就不必将其写回外存。

  在时钟置换算法的基础上，为每个页面添加一个修改位。页面被修改后，该修改位置为 1。

  在其他条件相同时，优先选择未被修改的页面进行淘汰。

  查找时的具体流程：

  1. 第一轮扫描：检查访问位为 0、修改位为 0 的页面。
  2. 第二轮扫描：检查访问位为 0、修改位为 1 的页面。同时，将所有页面访问位置为 0。
  3. 第三轮扫描：检查访问位为 0、修改位为 0 的页面。
  4. 第四轮扫描：检查访问位为 0、修改位为 1 的页面。

  因此，改进型时钟置换算法最多四轮扫描就能找到淘汰页面。

有时刚换出的页面马上又要换入内存，刚换入的页面又要立刻换出。这种现象称为 抖动（颠簸）。发生抖动的原因是频繁访问的页面数高于可用的内存块数（分配给进程的内存块不够）

请求分页管理方式分配给进程的所有内存块的集合称为 驻留集。驻留集要有合适的大小，这个大小一般小于进程总大小。

在某段时间间隔内，进程实际访问页面的集合称为 工作集。系统会根据 窗口尺寸（进程访问的连续几个页面中，不同页面的数量）来算出工作集大小，再根据工作集大小分配内存块。

为进程 分配内存块的策略 分为三种：

• 固定分配局部置换：为进程分配的内存块数量在整个运行期间不变

  要求在最开始就确定最佳的分配数量。这点很难做到

• 可变分配全局置换：每当进程缺页时，即将一空闲内存块，或其他进程的未锁定物理块分配给缺页进程

  只要进程发生缺页，就能获得新的内存块。

• 可变分配局部置换：当进程频繁缺页时，才为其分配新内存块。进程缺页率很低时，系统会适当减少其内存块

  系统会动态调节，使各进程缺页率保持在合适水平。

调入页面的时机 也有以下策略：

• 预调页策略：由于 局部性原理，可以预测并提前进行多个调页。

  目前预测成功率不高，故该策略多用于进程的 首次调入。

• 请求调页策略：发生缺页时再进行调页。该方法 I/O 开销较大。

外存可被分为 对换区（读写速度快，采用连续分配方式）和 文件区（读写速度慢，采用离散分配方式）。

调入、调出页面时，优先在对换区进行。对换区空间不足时，只将需修改的文件换出对换区。

UNIX 情况下，运行前进程所有数据存放在文件区，使用过的页面换出时换出至对换区。