3.1 基本内存管理

3.1.1 内存管理核心功能

1. 内存分配与回收：采用对应分配回收策略，跟踪记录内存使用状态。

2. 地址转换：将进程逻辑地址转换为主存物理地址。

3. 内存逻辑扩充：依托虚拟存储技术，解决大程序无法全部装入内存的问题。

4. 内存共享：多个进程共用一份内存副本，减少内存占用，同时支持进程通信。

5. 内存保护：借助界地址机制、存取访问控制。限制进程仅能访问授权内存区域，防止用户进程干扰操作系统，隔离进程间相互干扰。

3.1.2 多层次存储系统

存储层次距离 CPU 越近，访问速度越快。

• 寄存器：紧邻 CPU，访问速度与 CPU 接近，存放运算操作数，降低访存开销。

• 高速缓存 Cache、快表 TLB：位于 CPU 与主存之间。

• 主存（内存）：直接与 CPU 交互。

• 辅存（外存）：固定磁盘、可移动存储介质，速度最慢。

引入 Cache、寄存器目的：缓解 CPU 与主存之间巨大的速度差异。

3.1.3 内存空间结构与进程内存映像

物理内存从权限维度划分为两大区域，系统区、用户区。系统区专属操作系统内核，用于存放PCB、页表、内核程序等核心系统数据；用户区全部分配给用户进程使用。

进程内存映像：可执行文件载入物理内存后的标准化存储组织形式，是进程得以运行的内存载体。进程初始化时，系统自动为其分配用户内存空间，同时在系统区创建专属PCB（进程控制块）。

用户进程的虚拟地址空间统一划分为四段：

1. 代码段：存放程序指令，具备可重入特性，支持多进程共享。

2. 数据段：存放全局变量、静态变量。

3. 堆：初始为空；C 语言使用malloc/free动态申请、释放空间。

4. 栈：函数调用时创建栈帧，保存参数、返回地址、局部变量。

3.1.4 逻辑地址、物理地址、重定位

• 逻辑地址：程序编译、链接后生成的内部相对地址，以0为起始，是程序员和程序感知的地址，所有进程逻辑地址空间相互独立、完全重合。逻辑地址的整体范围称为逻辑地址空间。

• 物理地址（绝对地址）：CPU 访问内存必须使用物理地址访存。

重定位：当程序装入的物理内存区间，与自身编译生成的逻辑地址空间不一致时，必须修改地址映射关系，该过程即为重定位。重定位可触发于程序装入、内存置换、内存紧凑等场景，根据执行时机分为两类：

1. 静态重定位：程序装入内存时一次性完成地址修改，运行前完成。

2. 动态重定位：运行过程中依靠硬件地址变换机构实时完成地址转换。

3.1.5 编译、链接、装入全过程

源代码 → 编译 → 目标模块（生成逻辑地址）→ 链接 → 装入模块 → 装入内存 → 进程。

装入方式

1. 绝对装入：预先确定装载地址；仅适用于单道程序系统。

2. 可重定位装入（静态装入）：装入阶段完成逻辑地址→物理地址转换；程序运行期间不允许移动。

3. 动态运行时装入：装入内存后依旧保留逻辑地址；地址转换推迟到指令执行时。依靠基址寄存器保存进程起始地址；物理地址 = 基址起始地址 + 逻辑地址。支持程序运行过程中移动位置。

链接方式

1. 静态链接：装入前把所有目标模块、库整合为单一装入模块。

2. 装入时动态链接：边装入边链接。便于单独修改、复用目标模块，无需重新整合整个程序。

3. 运行时动态链接：程序运行需要某模块时，才调入内存完成链接。加快程序初始装入速度，节省内存空间。

3.1.6 内存保护实现方案

1. 上下限寄存器：访存时校验地址是否介于上下限之间。

2. 重定位寄存器 + 界地址寄存器

   1. 重定位寄存器：进程起始地址

   2. 界地址寄存器：进程长度。边界地址 = 起始地址 + 长度，校验访问地址区间。

3.1.7 内存共享

多个进程需要同一程序时，内存仅保留一份副本。共享内容必须是可重入代码（纯代码），运行过程不会被修改。

系统采用延迟回收机制：当所有共享进程都不再使用该内存副本，才将内容调出内存。

3.1.8 连续分配管理方式

连续分配：将整个程序装入内存一片连续空间。

1. 单一连续分配 适用于单道程序、单用户单任务系统；用户区整体分配给唯一进程，一般无需内存保护。

2. 固定分区分配 内存预先划分为若干分区；分区大小可相等 / 不等。通过分区说明表记录每个分区的大小、起始地址、占用状态。系统为待运行进程匹配合适分区分配。

   1. 优点：无外部碎片，实现简单，系统开销小。

   2. 缺点：存在内部碎片；大程序可能没有匹配分区无法装入。

      内部碎片：内存空间已经分配给进程，但进程无法使用的闲置区域。

3. 动态分区分配 进程到达时，划分大小匹配的连续空闲空间。会产生外部碎片。 可通过紧凑技术移动进程，合并空闲块，消除外部碎片，称为动态可重定位分区分配。

   紧凑需要修改大量地址信息，系统开销很大。

动态分区依靠空闲分区表 / 空闲分区链管理空闲内存。 分配算法：

1. 首次适应算法：空闲分区按地址升序排列，从头查找第一个满足大小的分区。 缺陷：低地址区域频繁分割，堆积大量外部碎片，查找开销大。

2. 循环首次适应算法：从上一次查找终止位置继续检索。 

   1. 空闲分区分布更加均匀；

   2. 容易缺失大尺寸空闲分区。

3. 最佳适应算法：空闲分区按大小升序排列，选择最小能满足需求的分区。

   1. 产生最多外部碎片，持续排序带来额外开销。

4. 最坏适应算法：选择内存中最大空闲分区进行分配。

   1. 减少外部碎片；

   2. 容易耗尽大块空闲分区。

内存回收：进程运行终止后，系统主动释放其占用的内存空间，检索相邻内存区域状态，自动合并相邻空闲分区，更新空闲分区表/空闲分区链，避免碎片化持续堆积，维持内存可用状态。

3.1.9 非连续分配管理方式

不再要求进程整体装入连续内存，可将进程拆分多个块，分散存入内存不相邻的空闲分区。彻底解决外部碎片问题，内存利用率大幅提升，代价是需要页表/段表记录映射关系，内存存储密度略低于连续分配。按照逻辑空间划分特征分为三类：

1. 分页存储管理（页面大小固定）

2. 分段存储管理（段大小可变）

3. 段页式存储管理（分段基础上，每一段再分页）

根据是否支持请求调入、页面置换，分为基本分页 / 分段、请求分页 / 分段（虚拟内存）。

3.2 分页存储管理方式

3.2.1 基础概念

• 页面：逻辑地址空间划分为固定大小块。

• 页框（物理块）：物理内存划分为固定大小块；页面与页框尺寸相等。

• 页表：记录页面→页框映射关系，每个进程独立拥有一张页表；表项为页表项。 页号隐含在页表项相对页表起始位置的偏移量内；页表项存放对应页框号。

3.2.2 地址变换基础

进程PCB中永久存储页表起始地址与页表总长度。当进程被调度上CPU运行时，系统自动将页表起始地址载入页表基址寄存器（PTR），为地址转换提供硬件支撑。多核CPU每个核心拥有独立寄存器组，因此各核心可独立完成页表地址转换，互不干扰。

标准分页地址变换完整流程：

1. 拆分逻辑地址为「页号+页内偏移」，校验页号是否超出页表长度，超出则触发越界中断；

2. 合法页号检索页表项，匹配得到对应的物理页框号；

3. 页框号与页内偏移量拼接，生成最终可被CPU识别的物理地址。

无快表情况下，一次访存需要两次内存访问：第一次访问内存页表，第二次访问目标数据。

3.2.3 快表（TLB，相联存储器）

快表（TLB）由高速相联存储器实现，缓存进程高频访问的页表项副本，核心目的是减少内存访问次数、加速地址转换。地址转换优先检索快表，流程极简：

• 快表命中：直接读取页框号，仅需一次访存，效率极高；

• 快表未命中：跳转访问内存页表获取页框号，同时将当前页表项写入快表，更新缓存，供后续访问使用。

3.2.4 多级页表

普通单级页表存在局限性：大型进程的页表体量极大，自身会占用多个物理页面，且这些页面在内存中离散分布。PCB仅能存储一个基址地址，无法定位离散的页表页面，因此引入多级页表嵌套机制。

以二级页表为例，逻辑地址拆分为「页目录号（一级页号）+页号（二级页号）+页内偏移」，层级分工明确：

• 外层（一级）页表：存储内层页表的物理页框号，仅用于索引下级页表；

• 内层（二级）页表：存储进程程序页面的物理页框号，最终映射用户数据。

多级页表可无限嵌套延伸，核心设计原则：保证最高层页表仅占用一个物理页面，让PCB仅需存储一个顶层页表基址即可完成全部地址映射，完美适配大进程场景。

3.3 分段存储管理方式

3.3.1 分段特点

段大小不固定，对用户透明性差，设计面向程序员需求：

1. 便于编程：程序按照逻辑功能天然划分为多个段。

2. 便于信息共享：段是独立逻辑单元。

3. 便于信息保护：可以针对独立逻辑段设置访问权限。

4. 支持段动态增长。

5. 利于动态链接：动态链接以功能模块为单位，与分段思想契合。

3.3.2 地址结构与段表

逻辑地址由段号 + 段内地址组成。 段表：保存段映射信息；段表项包含：段起始地址、段长。段号隐含在段表项偏移位置。

3.3.3 地址越界判断（两次校验）

1. 段号 ≥ 段表长度 → 段号越界。

2. 段内偏移 ≥ 段长 → 段内地址越界。

分页仅需要一次越界判断；分页页内偏移不会越界。

3.3.4 段的保护与共享

1. 保护方式：界地址保护、存取权限控制（只读、读写、不可访问）。

2. 共享机制：系统设置共享段表。 共享段在内存仅有一份物理副本；不同进程段表中各自保存该共享段的映射项。 同一共享段在各个进程内逻辑地址、段号互不相关。 共享段维护引用计数 count：进程释放段时 count 减一；count=0 时才释放内存。

3.4 段页式存储管理方式

先对进程地址空间分段，每一段内部再分页。 每个进程仅有一张段表；每一段对应一张独立页表。 段表项记录对应段的页表起始地址。

3.5 虚拟内存管理

3.5.1 虚拟存储器基础

传统内存管理（连续 / 非连续基本分配）要求程序整体装入内存；并发进程数量受物理内存容量限制。

虚拟存储器：在非连续存储基础上，具备请求调入、置换功能。

• 请求调入：仅载入程序部分页面；访问不在内存页面时，从外存调入。

• 置换：内存已满时，选出暂时不用页面调出，腾出空间加载新页面。

容量特性：

• 理论最大容量：CPU 寻址范围决定。

• 实际可用容量：min (CPU 寻址范围，内存容量 + 外存交换区容量)。 实现基础：局部性原理

1. 时间局部性：近期访问的指令 / 数据，短期内会再次访问（典型：循环）。

2. 空间局部性：访问某地址，相邻地址大概率会被访问。

3.5.2 请求分页存储管理

在基本分页之上增加请求调入、置换。需要三大硬件支撑：请求页表机制、缺页中断机构、地址变换机构。

1. 请求页表新增字段 在原有页表项基础上增加 4 项：

• 状态位：标记页面是否驻留内存。

• 访问字段：记录页面近期访问情况，置换算法使用。

• 修改位：页面载入内存后是否发生修改；修改页面换出时需要写回磁盘。

• 外存地址：页面在外存磁盘上的位置。

1. 缺页中断特点 普通中断在指令执行周期结束后响应；缺页中断在指令执行周期内触发（异常），保证及时调入页面，指令能够顺利完成。

2. 请求分页地址变换流程 优先查询快表

• 快表命中：直接获取页框号。

• 快表未命中：访问内存页表

  • 页面在内存：取出页框号，更新快表。

  • 页面不在内存：触发缺页中断，执行页面调入；载入后更新页表、快表。 最终页框号拼接页内偏移得到物理地址。

3.5.3 内存分配与置换策略

驻留集：分配给进程的物理页框集合。缺页率与驻留集大小直接相关。

固定与可变指的是系统为进程分配的页框数是否可发生变化，局部和全局指的是当发生缺页是可从哪里进行调页。

1. 固定分配局部置换 预先分配固定数量页框；缺页置换仅在进程自身驻留集内进行。

2. 可变分配局部置换 根据进程运行情况动态增减页框；置换局限于本进程，进程间相互干扰小。

3. 可变分配全局置换 系统维护空闲页框队列；缺页优先分配空闲页框；无空闲页框时，从整个系统所有进程页面中选择换出。

全局置换会改变进程持有的页框数量，不存在固定分配全局置换。

3.5.4 页面调入策略

两大问题：何时调入页面、从何处调入页面。

1. 何时调入

• 请求调页：缺页中断时仅调入缺失页面。IO 频率高，实现简单，现代虚拟内存主流方案。

• 预调页：缺页时同时载入目标页面与相邻页面，依托空间局部性。

1. 从何处调入页面 系统外存分为文件区、交换区。 交换区采用连续分配，读写效率更高；优先把易修改页面存放交换区，减少随机 IO 开销。

3.5.5 页面置换算法

1. 最佳置换 OPT 淘汰未来最长时间不会访问的页面。理想算法，无法实现，用作理论对比基准。

2. 先进先出 FIFO 淘汰最早载入内存的页面；使用队列实现。存在Belady 异常：分配页框数量增加，缺页率反而上升。未利用局部性原理。

3. LRU 最近最久未使用 淘汰最长时间没有访问的页面；依托时间局部性。

   1. 软件实现：双向链表，表头最近访问，表尾最先淘汰；每次访问更新链表。

   2. 硬件实现：页面配备计数器，每条指令计数器自增；置换选择计数值最小页面。

4. LFU 最少使用置换 淘汰一段时间访问频次最低的页面；侧重访问频率，区别于 LRU 的访问时间。

5. Clock 时钟算法 每个页面设置访问位；页面被访问，访问位置 1。 置换时指针循环扫描：访问位 = 0 直接淘汰；访问位 = 1 则清零，指针前进。一轮最多两次扫描。

6. 改进 Clock 算法 增加修改位区分页面。未修改页面置换无需写磁盘，置换代价更低，优先淘汰。

3.5.6 内存映射文件

普通 IO：磁盘数据 → 交换缓冲区 → 用户内存。

内存映射文件：进程调用系统调用，将磁盘文件映射至虚拟地址空间；初始不加载物理内存。访问对应地址触发缺页异常，直接载入物理内存，跳过交换缓冲区。

进程使用指针直接操作文件；产生脏页后，系统后台自动回写磁盘。大幅简化文件读写流程。

3.5.7 抖动与工作集

抖动（颠簸） 系统多道程序度持续升高，CPU 利用率上升至峰值后急剧下降。分配给进程的物理块过少，页面频繁换入换出，系统大量时间消耗在磁盘 IO，有效计算极少。

工作集模型 工作集：一段时间窗口内，进程实际访问页面的集合；时间区间称为窗口尺寸。

理论依据 局部性原理：依靠过往访问特征预测未来页面需求。

消除抖动核心：保证进程工作集完整驻留内存。

抖动预防方案：

1. 采用局部置换策略，限制抖动影响范围。

2. 调度算法结合工作集模型，新进程载入前评估内存容量。

3. 持续监控系统缺页率；缺页率过高时挂起部分进程，释放物理内存。