OS——内存管理
3.1 基本内存管理
3.1.1 内存管理核心功能
内存分配与回收：采用对应分配回收策略，跟踪记录内存使用状态。
地址转换：将进程逻辑地址转换为主存物理地址。
内存逻辑扩充：依托虚拟存储技术，解决大程序无法全部装入内存的问题。
内存共享：多个进程共用一份内存副本，减少内存占用，同时支持进程通信。
内存保护：借助界地址机制、存取访问控制。限制进程仅能访问授权内存区域，防止用户进程干扰操作系统，隔离进程间相互干扰。
3.1.2 多层次存储系统
存储层次距离 CPU 越近，访问速度越快。
寄存器：紧邻 CPU，访问速度与 CPU 接近，存放运算操作数，降低访存开销。
高速缓存 Cache、快表 TLB：位于 CPU 与主存之间。
主存（内存）：直接与 CPU 交互。
辅存（外存）：固定磁盘、可移动存储介质，速度最慢。
引入 Cache、寄存器目的：缓解 CPU 与主存之间巨大的速度差异。
3.1.3 内存空间结构与进程内存映像
物理内存划分为系统区、用户区；系统区供操作系统使用。
进程内存映像：程序载入内存后的存储组织形式。进程创建时，系统分配内存，并在系统区创建 PCB。PCB 保存进程控制信息，包含进程页表起始地址。 进程地址空间分为四段：
代码段：存放程序指令，具备可重入特性，支持多进程共享。
数据段：存放全局变量、静态变量。
堆：初始为空；C 语言使用
malloc/free动态申请、释放空间。栈：函数调用时创建栈帧，保存参数、返回地址、局部变量。
3.1.4 逻辑地址、物理地址、重定位
逻辑地址：程序内部地址，范围称为逻辑地址空间。
物理地址（绝对地址）：CPU 访问内存必须使用物理地址访存。
重定位：程序装入内存的目标地址与自身内部地址不一致时，执行地址修改工作。可发生在程序装入、内存置换、紧凑操作时。
静态重定位：程序装入内存时一次性完成地址修改，运行前完成。
动态重定位：运行过程中依靠硬件地址变换机构实时完成地址转换。
3.1.5 编译、链接、装入全过程
源代码 → 编译 → 目标模块（生成逻辑地址）→ 链接 → 装入模块 → 装入内存 → 进程。
装入方式
绝对装入：预先确定装载地址；仅适用于单道程序系统。
可重定位装入（静态装入）：装入阶段完成逻辑地址→物理地址转换；程序运行期间不允许移动。
动态运行时装入：装入内存后依旧保留逻辑地址；地址转换推迟到指令执行时。依靠基址寄存器保存进程起始地址；物理地址 = 基址起始地址 + 逻辑地址。支持程序运行过程中移动位置。
链接方式
静态链接：装入前把所有目标模块、库整合为单一装入模块。
装入时动态链接：边装入边链接。便于单独修改、复用目标模块，无需重新整合整个程序。
运行时动态链接：程序运行需要某模块时，才调入内存完成链接。加快程序初始装入速度，节省内存空间。
3.1.6 内存保护实现方案
上下限寄存器：访存时校验地址是否介于上下限之间。
重定位寄存器 + 界地址寄存器
重定位寄存器：进程起始地址
界地址寄存器：进程长度。边界地址 = 起始地址 + 长度，校验访问地址区间。
3.1.7 内存共享
多个进程需要同一程序时，内存仅保留一份副本。共享内容必须是可重入代码（纯代码），运行过程不会被修改。 当所有共享进程都不再使用该内存副本，才将内容调出内存。
3.1.8 连续分配管理方式
连续分配：将整个程序装入内存一片连续空间。
单一连续分配适用于单道程序、单用户单任务系统；用户区整体分配给唯一进程，一般无需内存保护。
固定分区分配内存预先划分为若干分区；分区大小可相等 / 不等。依靠分区说明表记录分配状态。
优点：无外部碎片，实现简单，系统开销小。
缺点：存在内部碎片；大程序可能没有匹配分区无法装入。
内部碎片：内存空间已经分配给进程，但进程无法使用的闲置区域。
动态分区分配进程到达时，划分大小匹配的连续空闲空间。会产生外部碎片。 可通过紧凑技术移动进程，合并空闲块，消除外部碎片，称为动态可重定位分区分配。
紧凑需要修改大量地址信息，系统开销很大。
动态分区依靠空闲分区表 / 空闲分区链管理空闲内存。 分配算法：
首次适应算法：空闲分区按地址升序排列，从头查找第一个满足大小的分区。 缺陷：低地址区域频繁分割，堆积大量外部碎片，查找开销大。
循环首次适应算法：从上一次查找终止位置继续检索。
空闲分区分布更加均匀；
容易缺失大尺寸空闲分区。
最佳适应算法：空闲分区按大小升序排列，选择最小能满足需求的分区。
产生最多外部碎片，持续排序带来额外开销。
最坏适应算法：选择内存中最大空闲分区进行分配。
减少外部碎片；
容易耗尽大块空闲分区。
内存回收：进程结束释放内存，系统将回收区域合并，加入空闲分区表 / 空闲分区链。
3.1.9 非连续分配管理方式
程序拆分后存放于互不相邻的内存分区。缓解内存碎片问题，但需要额外索引表，存储密度低于连续分配。 按照逻辑空间划分特征分为三类：
分页存储管理（页面大小固定）
分段存储管理（段大小可变）
段页式存储管理（分段基础上，每一段再分页）
根据是否支持请求调入、页面置换，分为基本分页 / 分段、请求分页 / 分段（虚拟内存）。
3.2 分页存储管理方式
3.2.1 基础概念
页面：逻辑地址空间划分为固定大小块。
页框（物理块）：物理内存划分为固定大小块；页面与页框尺寸相等。
页表：记录页面→页框映射关系，每个进程独立拥有一张页表；表项为页表项。 页号隐含在页表项相对页表起始位置的偏移量内；页表项存放对应页框号。
3.2.2 地址变换基础
PCB 中保存页表起始地址；进程调度到 CPU 运行时，将页表起始地址载入页表基址寄存器 PTR。 多核 CPU 每个核心拥有独立寄存器组，因此每个核心都具备独立页表基址寄存器。
基础地址变换流程：
对比页号与页表长度，超出则越界中断。
通过页号检索页表项，得到页框号。
页框号拼接页内偏移量，生成物理地址。
无快表情况下，一次访存需要两次内存访问：第一次访问内存页表，第二次访问目标数据。
3.2.3 快表（TLB，相联存储器）
存放部分页表项副本。地址变换优先检索快表：
命中：直接获得页框号。
未命中：访问内存页表；同时把本次页表项写入快表。
3.2.4 多级页表
进程规模较大时，页表本身占用多个页面，页表内存空间离散。PCB 仅保存最高层外层页表起始地址。 二级页表逻辑地址分为：页目录号、页号、页内偏移。
外层页表（一级页表）：指向内层页表的页框。
内层页表（二级页表）：指向程序页面的页框。 多级页表持续向上嵌套分层，保证最高层页表仅占用一页。
3.3 分段存储管理方式
3.3.1 分段特点
段大小不固定，对用户透明性差，设计面向程序员需求：
便于编程：程序按照逻辑功能天然划分为多个段。
便于信息共享：段是独立逻辑单元。
便于信息保护：可以针对独立逻辑段设置访问权限。
支持段动态增长。
利于动态链接：动态链接以功能模块为单位，与分段思想契合。
3.3.2 地址结构与段表
逻辑地址由段号 + 段内地址组成。段表：保存段映射信息；段表项包含：段起始地址、段长。段号隐含在段表项偏移位置。
3.3.3 地址越界判断（两次校验）
段号 ≥ 段表长度 → 段号越界。
段内偏移 ≥ 段长 → 段内地址越界。
分页仅需要一次越界判断；分页页内偏移不会越界。
3.3.4 段的保护与共享
保护方式：界地址保护、存取权限控制（只读、读写、不可访问）。
共享机制：系统设置共享段表。 共享段在内存仅有一份物理副本；不同进程段表中各自保存该共享段的映射项。 同一共享段在各个进程内逻辑地址、段号互不相关。 共享段维护引用计数 count：进程释放段时 count 减一；count=0 时才释放内存。
3.4 段页式存储管理方式
先对进程地址空间分段，每一段内部再分页。 每个进程仅有一张段表；每一段对应一张独立页表。 段表项记录对应段的页表起始地址。
3.5 虚拟内存管理
3.5.1 虚拟存储器基础
传统内存管理（连续 / 非连续基本分配）要求程序整体装入内存；并发进程数量受物理内存容量限制。
虚拟存储器：在非连续存储基础上，具备请求调入、置换功能。
请求调入：仅载入程序部分页面；访问不在内存页面时，从外存调入。
置换：内存已满时，选出暂时不用页面调出，腾出空间加载新页面。
容量特性：
理论最大容量：CPU 寻址范围决定。
实际可用容量：min (CPU 寻址范围，内存容量 + 外存交换区容量)。 实现基础：局部性原理
时间局部性：近期访问的指令 / 数据，短期内会再次访问（典型：循环）。
空间局部性：访问某地址，相邻地址大概率会被访问。
3.5.2 请求分页存储管理
在基本分页之上增加请求调入、置换。需要三大硬件支撑：请求页表机制、缺页中断机构、地址变换机构。
请求页表新增字段在原有页表项基础上增加 4 项：
状态位：标记页面是否驻留内存。
访问字段：记录页面近期访问情况，置换算法使用。
修改位：页面载入内存后是否发生修改；修改页面换出时需要写回磁盘。
外存地址：页面在外存磁盘上的位置。
缺页中断特点普通中断在指令执行周期结束后响应；缺页中断在指令执行周期内触发（异常），保证及时调入页面，指令能够顺利完成。
请求分页地址变换流程优先查询快表
快表命中：直接获取页框号。
快表未命中：访问内存页表 ✔页面在内存：取出页框号，更新快表。 ✘页面不在内存：触发缺页中断，执行页面调入；载入后更新页表、快表。 最终页框号拼接页内偏移得到物理地址。
3.5.3 内存分配与置换策略
驻留集：分配给进程的物理页框集合。缺页率与驻留集大小直接相关。 分配大类：固定分配、可变分配。
固定分配局部置换预先分配固定数量页框；缺页置换仅在进程自身驻留集内进行。
可变分配局部置换根据进程运行情况动态增减页框；置换局限于本进程，进程间相互干扰小。
可变分配全局置换系统维护空闲页框队列；缺页优先分配空闲页框；无空闲页框时，从整个系统所有进程页面中选择换出。
全局置换会改变进程持有的页框数量，不存在固定分配全局置换。
3.5.4 页面调入策略
两大问题：何时调入页面、从何处调入页面。
何时调入
请求调页：缺页中断时仅调入缺失页面。IO 频率高，实现简单，现代虚拟内存主流方案。
预调页：缺页时同时载入目标页面与相邻页面，依托空间局部性。
从何处调入页面系统外存分为文件区、交换区。 交换区采用连续分配，读写效率更高；优先把易修改页面存放交换区，减少随机 IO 开销。
3.5.5 页面置换算法
最佳置换 OPT淘汰未来最长时间不会访问的页面。理想算法，无法实现，用作理论对比基准。
先进先出 FIFO淘汰最早载入内存的页面；使用队列实现。存在Belady 异常：分配页框数量增加，缺页率反而上升。未利用局部性原理。
LRU 最近最久未使用淘汰最长时间没有访问的页面；依托时间局部性。
软件实现：双向链表，表头最近访问，表尾最先淘汰；每次访问更新链表。
硬件实现：页面配备计数器，每条指令计数器自增；置换选择计数值最小页面。
LFU 最少使用置换淘汰一段时间访问频次最低的页面；侧重访问频率，区别于 LRU 的访问时间。
Clock 时钟算法（简单时钟）每个页面设置访问位；页面被访问，访问位置 1。 置换时指针循环扫描：访问位 = 0 直接淘汰；访问位 = 1 则清零，指针前进。一轮最多两次扫描。
改进 Clock 算法增加修改位区分页面。未修改页面置换无需写磁盘，置换代价更低，优先淘汰。
3.5.6 内存映射文件
普通 IO：磁盘数据 → 交换缓冲区 → 用户内存。 内存映射文件：进程调用系统调用，将磁盘文件映射至虚拟地址空间；初始不加载物理内存。访问对应地址触发缺页异常，直接载入物理内存，跳过交换缓冲区。 进程使用指针直接操作文件；产生脏页后，系统后台自动回写磁盘。大幅简化文件读写流程。
3.5.7 抖动与工作集
抖动（颠簸）系统多道程序度持续升高，CPU 利用率上升至峰值后急剧下降。分配给进程的物理块过少，页面频繁换入换出，系统大量时间消耗在磁盘 IO，有效计算极少。
工作集模型工作集：一段时间窗口内，进程实际访问页面的集合；时间区间称为窗口尺寸。 理论依据局部性原理：依靠过往访问特征预测未来页面需求。消除抖动核心：保证进程工作集完整驻留内存。
抖动预防方案：
采用局部置换策略，限制抖动影响范围。
调度算法结合工作集模型，新进程载入前评估内存容量。
持续监控系统缺页率；缺页率过高时挂起部分进程，释放物理内存。