存储器管理

这是一篇关于存储器管理的思维导图，主要内容有内存的基础知识、连续分配管理、覆盖与对换、非连续分配管理。

内存管理

• 内存的基础知识
  • 什么是内存、有何作用
    • 存储单元、内存地址的概念和联系
    • 按字节编址VS按字编址
  • 进程运行的基本原理
    • 从写程序到程序运行
      • 编辑源代码文件
      • 编译
        • 由源代码文件生成目标模块
      • 链接
        • 由目标模块生成装入模块，链接形成完整的逻辑地址
      • 装入
        • 将装入模块装入内存，形成物理地址
    • 三种链接方式
      • 静态链接
        • 装入前链接成一个完整装入模块
      • 装入时动态链接
        • 运行前边装入边链接
      • 运行时动态链接
        • 运行时需要目标模块才装入并链接
    • 三种装入方式
      • 绝对装入
        • 编译时产生绝对地址（单道程序阶段，无操作系统）
      • 可重定位装入
        • 装入时逻辑地址转换为物理地址（早期多道批处理系统）
      • 动态运行时装入
        • 运行时将逻辑地址转换为物理地址，需要设置重定位寄存器（现代操作系统）
    • 存储保护
      • 设置上下限寄存器
      • 利用重定位寄存器、界地址寄存器判断
• 连续分配管理
  • 单一连续分配
    • 只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
    • 无外部碎片，有内部碎片
  • 固定分区分配
    • 支持多道程序，内存用户空间分为若干个固定大小的分区，每一个分区只能装一道作业
    • 无外部碎片，有内部碎片
    • 两种分区方式
      • 分区大小相等
      • 分区大小不等
  • 动态分区分配
    • 支持多道程序，在程序装入内存时，根据进程大小动态建立分区
    • 无内部碎片，有外部碎片（可用“紧凑”技术解决）
  • 基于顺序搜索的动态分区分配算法
    • 首次适应算法
      • 按地址从低到高排序，从链首开始查找，找到第一个满足要求的空闲分区
      • 最简单，通常是最好和最快的
    • 循环首次适应算法
      • 按地址从低到高排序，从上次找到的空闲分区的下一个空闲分区查，找到第一个满足要求的空闲分区找
    • 最佳适应算法
      • 按容量从小到大排序，找到第一个满足要求的空闲分区
    • 最坏适应算法
      • 按容量从大到小排序，只要看第一个是否满足要求即可
• 覆盖与对换
  • 覆盖技术
    • 一个固定区
      • 存放最活跃的程序段
      • 固定区的程序段在运行过程中不会调入调出
    • 若干覆盖区
      • 覆盖区的程序段在运行过程中会根据需要调入调出
    • 必须由程序员申明覆盖结构，操作系统完成自动覆盖
    • 缺点：对用户不透明，增加了用户编程负担
  • 换对技术
    • 内存紧张时，换出某些进程以腾出内存空间，再换入某些进程（中级调度采用的就是对换技术）
    • 磁盘分为文件区和对换区，换出的进程在对换区
  • 区别
    • 覆盖在同一个程序或进程中的
    • 对换是在不同进程或作用之间的
• 非连续分配管理
  • 分页存储管理
    • 原理：把进程分页，把内存分块，各个页面离散地放到各个内存块
    • 易混概念
      • “页框、页帧、内存块、物理块、物理页”VS“页、页面”
    • 页表
      • 页表记录了页面和实际存放的内存块之间的映射关系
      • 一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由“页号”和“块号”组成
      • i号页表项存放地址=页表始址+i*页表项大小
    • 逻辑地址结构<页号P,页内偏移量W>
      • 页号=逻辑地址/页面大小；页内偏移量=逻辑地址%页面大小
    • 如何实现地址转换
      • 1.计算出逻辑地址对应的页号和页内偏移量
      • 2.找到页面对应的块号（通过查找页表)
      • 3.物理地址=页面始址（相当于块号*内存块大小）+页内偏移量
    • 基本地址变换机构
      • 页表寄存器作用
        • 存放页表起始地址
        • 存放页表长度
      • 地址变换过程
        • 1.根据逻辑地址计算出页号和页内偏移量
        • 2.页号的合法性检查（页号与页表长度对比）
        • 3.若合法，再根据页表起始地址、页号找到对应的页表项（第一次访问内存）
        • 4.根据页表项中记录的内存块号、页内偏移量得到最终物理地址
        • 5.访问物理地址对应的内存单元（第二次访问内存）
      • 注意
        • 分页存储管理中地址是一维的
    • 具有快表的地址变换机构
      • 地址变换过程
        • 1.2.5.6同上1.2.4.5
        • 3.查快表，若命中，即可知道页面存放的内存块号，直接进行5.；若未命中则进行4.
        • 4.查页表，找到页面存放的内存块号，并且将页表复制到块表中
      • 内存访问次数
        • 命中则一次
        • 未命中则两次
    • 多级页表
      • N级页表访问一个逻辑地址需要N+1次访存
  • 分段存储管理
    • 分段
      • 将地址空间按照程序的自身逻辑关系划分为若干个段，每段从0开始编址
      • 每个段在内存中占据连续空间，但各段之间可以不相邻
      • 逻辑地址结构<段号，段内地址>
    • 段表
      • 记录逻辑段到实际存储地址的映射关系
      • 每个段对应一个段表项。各段表项长度相同，由段号（隐藏）、段长、基址组成
    • 地址变换
      • 1.由逻辑地址得到段号、段内地址
      • 2.段号与段表寄存器中的段表长度比较，检查是否越界
      • 3.由段表始址、段号找到对应段表项
      • 4.根据段表中记录的段长，检查段内地址是否越界
      • 5.由段表中的“基址+段内地址”得到最终的物理地址
      • 6.访问目标单元
    • 分段与分页的区别
      • 分页对用户不可见，逻辑地址的划分由系统、硬件完成，分段对用户可见，段的长度不固定，决定于用户所编写的程序，通常编译时划分。
      • 分页地址空间是一维，分段地址空间是二维的
      • 分页存在少量页内碎片（碎片比分段少），分段存在外部碎片
      • 分页（单级页表）、分段访问一个逻辑地址都需要两次访存，都可以引入快表
  • 段页存储管理
    • 分段+分页
      • 将地址空间按照程序自身的逻辑关系划分为若干个段，再将各段分为大小相等的页面
      • 将内存空间划分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
      • 逻辑地址结构<段号，页号，页内偏移量>
    • 段表+页表
      • 每一个段对应一个段表项。各段表项长度相同，由段号（隐含）、页表长度、页表始址组成
      • 每个页对应一个页表项。各页表项长度相同，由页号（隐含）、块号组成
    • 地址变换
      • 1.由逻辑地址得到段号、页号、页内偏移量
      • 2.段号与段表寄存器中的段长度比较，检查是否越界
      • 3.由段表始址、段号找到对应段表项
      • 4.根据段表中记录的页表长度，检查页号是否越界
      • 5.由段表中的页表始址、页号得到对应的页表项
      • 6.由页面存放的内存块号、页内偏移量得到最终物理地址
      • 7.访问目标单元
    • 访问一个逻辑地址所需访存次数
      • 第一次查找段表，第二次查找页表，第三次访问目标单元
      • 可引入快表机构，命中仅需一次访存