内存管理

408王道操作系统的第三章详细思维导图。内存管理是指软件运行时对计算机内存资源的分配和使用的技术。其最主要的目的是如何高效，快速的分配，并且在适当的时候释放和回收内存资源。本图对计算机操作系统部分《内存管理》章节知识点进行了归纳总结，适用于计算机考研考点的复习和记忆~

内存管理

• 1.内存的基础知识
  • 什么是内存，有何作用
    • 存储单元
    • 内存地址
      • 按字节编址
      • 按字编址
  • 进程运行的基本原理
    • 指令的工作原理
      • 操作码+若干参数（可能包含地址参数）
    • 逻辑地址 物理地址
    • 从写程序到程序运行
      • 编辑代码文件
      • 编译
        • 由源代码文件生成目标模块
      • 链接
        • 由目标模块生成装入模块，链接后形成完整的逻辑地址
      • 装入
        • 将装入模块装入内存，装入后形成物理地址
    • 三种链接方式
      • 静态链接
        • 装入前链接成一个完整装入模块
      • 装入时动态链接
        • 运行前边装入边链接
      • 运行时动态链接
        • 运行时需要目标模块才装入并链接
    • 三种装入方式
      • 绝对装入
        • 编译时产生绝对地址
      • 可重定位装入
        • 装入时将逻辑地址转换为物理地址
      • 动态运行时装入
        • 运行时将逻辑地址转换为物理地址，需设置重定位寄存器
• 2.内存管理的概念
  • 内存空间的分配与回收
  • 内存空间的扩充（实现虚拟性）
  • 地址转换
    • 操作系统负责实现逻辑地址到物理地址的转换
    • 三种方式
      • 绝对装入
        • 编译器负责地址转换（单道程序阶段，无操作系统）
      • 可重定位装入
        • 装入程序负责地址转换（早期多道批处理阶段）
      • 动态运行时装入
        • 运行时才进行地址转换（现代操作系统）
  • 存储保护
    • 保证各进程在自己的内存空间内运行，不会越界访问
    • 两种方式
      • 设置上下限寄存器
      • 利用重定位寄存器、界地址寄存器进行判断
• 3.覆盖与交换
  • 覆盖技术
    • 一个固定区
      • 存放最活跃的程序段
      • 固定区中的程序段在运行过程中不会调入调出
    • 若干覆盖区
      • 不可能同时被访问程序段可共享一个覆盖区
      • 覆盖区中的程序段在运行过程中会根据需要调入调出
    • 必须由程序员声明覆盖结构，操作系统完成自动覆盖
    • 缺点：对用户不透明，增加了用户编程负担
  • 交换技术
    • 内存紧张时，换出某些进程以腾出内存空间，再换入某些进程
    • 磁盘分为文件区和对换区，换出的进程放在对换区
  • 覆盖与交换的区别
    • 覆盖是在同一个程序或进程中的
    • 交换是在不同进程（或作业）之间的
• 4.连续分配管理
  • 单一连续分配
    • 只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
    • 无外部碎片，有内部碎片
  • 固定分区分配
    • 支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装入一道作业
    • 无外部碎片，有内部碎片
    • 两种分区方式
      • 分区大小相等
      • 分区大小不等
  • 动态分区分配
    • 支持多道程序，在进程装入内存时，根据进程的大小动态的建立分区
    • 无内部碎片，有外部碎片
    • 外部碎片可用“紧凑”技术来解决
    • 回收内存分区时，可能遇到四种情况
      • 回收区之后相邻的空闲分区
      • 回收区前有相邻的空闲分区
      • 回收区前、后都有相邻的空闲分区
      • 回收区前、后都没有相邻的空闲分区
• 5.动态分区分配算法
  • 首次适应算法
    • 性能最好
  • 最佳适应算法
    • 会产生很多太小的、难以利用的碎片
  • 最坏适应算法
    • 大分区容易被用完，不利于大进程
  • 邻近适应算法
    • 会使高地址的大分区也被用完
• 6.基本分页存储管理的基本概念
  • 基本分页存储管理基本思想
    • 把进程分页，各个页面可离散的放到各个的内存块中
  • 重要概念
    • • 页框
      • 页帧
      • 内存块
      • 物理块
      • 页
      • 页面
    • 页框号
    • 页帧号
    • 内存块号
    • 物理块号
    • 页号
    • 页面号
  • 如何实现地址转换
    • 计算出逻辑地址对应的页号
    • 找到对应页面在内存中的存放位置
    • 算出逻辑地址对应的页内偏移量
    • 物理地址=页面地址+页内偏移量
  • 页号、页内偏移量的计算
    • 页号=逻辑地址/页面大小；页内偏移量=逻辑地址%页面大小
    • 或根据逻辑地址结构计算，逻辑地址=【页号P,页内偏移量W】
  • 页表
    • 页表记录进程页面和实际存放的内存块之间的对应关系
    • 一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由 页号 和块号组成
    • 每个页表项的长度是相同的，页号是 隐含的
• 7.基本地址变换机构
  • 页表寄存器的作用
    • 存放页表起始地址
    • 存放页表长度
  • 地址变换过程
    • 根据逻辑地址算出页号，页内偏移量
    • 页号的合法性检查（与页表长度对比）
    • 若页号合法，再根据页表起始地址、页号找到对应页表项
    • 根据页表项中记录的内存块号、页内偏移量得到最终的地址
    • 访问物理内存对应的内存单元
  • 其它小细节
    • 页内偏移量位数与页面大小之间的关系（要能用其中一个推出另一个条件
    • 页式管理中地址是一维的
    • 实际应用中，通常使用一个页框恰好能放入整数个页表项
    • 为了方便找到页表项，页表一般是放在连续的内存块中的
• 8.具有快表的地址转换机构
  • 局部性原理
  • 什么是快表
  • 引入快表后，地址的变换过程
    • 算页号、页内偏移量
    • 检查页号合法性
    • 查快表，若命中，即可知道页面存放的内存块号，可直接进行5
    • 查页表，找到页面存放的内存块号，并且将页表表项复制到快表中
    • 根据内存块号与页内偏移量得到物理地址
    • 访问目标内存单元
    • 若命中，1次访存，否则2次访存
• 9.两级页表
  • 单级页表存在的问题
    • 所有页表项必须连续存放、页表过大时需要很大的连续空间
    • 在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存
  • 两级页表
    • 将长长的页表在分页
    • 逻辑地址结构：（一级页号，二级页号，页内偏移量）
    • 注意几个术语：页目录表、外层页表、顶级页表
  • 如何实现地址变换
    • 按照地址结构将逻辑地址拆分为三部分
    • 从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
    • 根据二级页号查表，找到最终想访问的内存块号
    • 结合页内偏移量得到物理地址
  • 几个细节
    • 多级页表中，各级页表的大小不能超过一个页面，若两级页表不够，可以分更多级
    • 多级页表的访存次数（假设没有快表机构）-N级页表访问一个逻辑地址需要N+1次
• 10.基本分段存储管理
  • 分段
    • 将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址
    • 每个段在内存中占据连续空间，但各段之间可以不相邻
    • 逻辑地址结构：（段号，段地址）
  • 段表
    • 记录逻辑段到实际存储地址的映射关系
    • 每个段对应一个段表项。各段表项长度相等、由段号、段长、基址组成
  • 地址变换
    • 由逻辑地址得到段号，段内地址
    • 段号与段表寄存器中长度比较，检查是否越界
    • 由段表始址、段号找到对应段表项
    • 根据段表中记录的段长，检查段内地址是否越界
      • 分页不需要这一步
    • 由段表中的“基址+段内地址”得到最终的物理地址
    • 访问目标单元
  • 分段VS分页
    • 分页对用户不可见，分段对用户可见
    • 分页的地址空间是一维的，分段的地址空间是二维的
      • 分页用户只需要给出一个记忆符即可表示一个地址
      • 分段用户在标识一个地址时，既要给出段名，也要给出段内地址
    • 分段更容易实现信息的共享和保护（纯代码/可重入代码可以共享）
    • 分页（单页页表），分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构
• 11.段页式管理方式
  • 分段+分页
    • 将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面
    • 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
    • 逻辑地址结构：（段号 页号 页内偏移量）
  • 段表、页表
    • 每个段对应一个段表项，各段表项长度相同，由段号、页表长度、页表存放地址组成？？？
    • 每个页对应一个页表项，各页表项长度相同，由页号、页面存放的内存块号组成
  • 地址变换
    • 由逻辑地址得到段号、页号、页内偏移量
    • 段号与段表寄存器中华的段长度比较，检查是否越界
    • 由段表始址、段号找到段表项
    • 根据段表中记录的页表长度，检查页号是否越界
    • 由段表中的页表地址、页号得到查询页表、找到页表项
    • 由页面存放的内存块号，页内偏移量得到最终的物理地址
    • 访问目标单元
  • 访问一个逻辑地址所需访存次数
    • 第一次-查段表、第二次-查页表、第三次-访问目标单元
    • 可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存
• 12.虚拟内存的基本概念
  • 传统存储管理方式的特征、缺点
    • 一次性：作业数据必须一次性全部调入内存
    • 驻留性：作业数据在整个运行期间都会常驻内存
  • 局部性原理
    • 时间局部性
      • 现在访问的指令、数据在不久后很可能会被再次访问
    • 空间局部性
      • 现在访问的内存单元周围的内存空间，很可能在不久后会被访问
    • 高速缓冲技术
      • 使用频繁的数据放到更高速的存储器中
  • 虚拟内存的定义个特征
    • 程序不需要全部装入即可运行，运行时根据需要动态的调入数据，若内存不够，还需要换出一些数据
    • 特征
      • 多次性
        • 无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
      • 对换性
        • 无需在作业运行时一直常驻内存，而是允许在作业运行期间，将作业换入，换出
      • 虚拟性
        • 从逻辑上扩充了内存的容量。使用户看到的内存容量，远大于实际的容量
  • 如何实现虚拟内存技术
    • 访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）
    • 内存空间不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）
    • 新增的两个功能
    • 虚拟内存的实现
      • 请求分页存储管理
      • 请求分段存储管理
      • 请求段页式存储管理
• 13.请求分页管理系统
  • 页表机制
    • 在基本分页的基础上增加了几个表项
    • 状态位：表示页面是否已在内存中
    • 访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
    • 修改位：表示页面调入内存后是否被修改过，只有修改过的页面才能在置换时写回内存
    • 外存地址：页面在外存中存放的位置
  • 缺页中断机构
    • 找到页表项后检查页面是否已在内存、若没在内存，产生缺页中断
    • 缺页中断处理中，需要将目标页面调入内存，有必要还要换出页面
    • 缺页中断属于内中断，属于内中断中的故障，即可能被操作系统修复的异常
    • 一条指令在执行过程中可能产生多次缺页中断
  • 地址变换机构（重点关注与基本分页不同的地方）
    • 找到页表项是需要检查页面是否在内存中
    • 若页面不在内存中，需要请求页面
    • 若内存空间不够，还需换出页面
    • 页面调入内存后，需要修改相应页表项
• 14.页面置换算法
  • 最佳置换算法OPT
    • 优先淘汰最长时间内不会被访问的页面
    • 缺页率最小，性能最好，但无法实现
    • 缺页中断未必发生页面置换，只有内存块满后的缺页才会发生页面置换
  • 先进先出置换算法FIFO
    • 优先淘汰最先进入内存的页面
    • 实现简单，但性能很差，可能出现Belady异常
  • 最近最久未使用置换算法LRU
    • 优先淘汰最近最久没访问的页面
    • 性能很好，但需要硬件支持，算法开销大
  • 时钟置换算法（最近未用）CLOCK
    • 循环扫描各页面。第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1.若第一轮没选中，则进行第二轮扫描
    • 实现简单，算法开销小，但未考虑页面是否被修改过
    • 选择一个淘汰页面最多会经历2轮扫描
  • 改进型的时钟置换算法
    • 算法开销小，性能也不错
    • 在其他条件都相同时，优先淘汰没有修改过的页面。修改位为1表示修改过
    • 选择一个淘汰页面最多经历4轮扫描，全是（1,1）
    • 优先级
      • 最近没访问、没修改
      • 最近没访问、修改
      • 最近访问、没修改
      • 最近访问、修改
• 15.页面分配策略
  • 驻留集
    • 指请求分页存储管理中给进程分配的内存块的概念
  • 页面分配、置换策略
    • 固定分配VS可变分配
      • 区别在于进程运行期间驻留集大小是否可变
    • 局部置换VS全局置换
      • 区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
    • 固定分配局部置换
      • 进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页
    • 可变分配全局置换
      • 只要发生缺页就分配新物理块，可能来自空闲物理块，也可能需要换出别的进程页面
    • 可变分配局部置换
      • 频繁缺页的进程，多分配一些物理块，缺页率很低的进程，回收一些物理块，直到缺页率合适
  • 何时调入页面
    • 预调页策略：一般用于进程运行前
    • 请求调页策略：进程运行期间，发生缺页调页
  • 从何处调页
    • 对换区
      • 采用连续存储方式，速度更快；文件区-采用离散存储方式，速度更慢
    • 对换区足够大
      • 运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区调入
    • 对换区不够大
      • 不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
    • UNIX方式
      • 第一次使用的页面都从文件区调入，调出的页面都写回对换区，再次使用时从对换区调入
  • 抖动（颠簸）现象
    • 页面频繁换入换出的现象，主要原因是分配给进程的物理块不够
  • 工作集
    • 在某段时间间隔里，进程实际访问页面的集合，驻留集大小一般不能小于工作集大小。最近k次访问过的页面集合。