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 减一count0 时才释放内存。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有效计算极少。工作集模型工作集一段时间窗口内进程实际访问页面的集合时间区间称为窗口尺寸。 理论依据局部性原理依靠过往访问特征预测未来页面需求。消除抖动核心保证进程工作集完整驻留内存。抖动预防方案采用局部置换策略限制抖动影响范围。调度算法结合工作集模型新进程载入前评估内存容量。持续监控系统缺页率缺页率过高时挂起部分进程释放物理内存。