4.第四章 内存管理

这是一篇关于4.第四章 内存管理的思维导图。操作系统是用户与硬件之间的接口：操作系统与硬件部分相互作用，并且为运行在计算机上的应用程序提供执行环境 资源的管理理者。

第四章 内存管理：

• 存储器的层次结构：
  • 存储器的层次结构：
    • 【注】：
      • L0-L2都在CPU内
    • 特点：
      • 每一层级的存储器保存来
      • 自下一层级存储器的信息
  • 局部性原理：
    • 定义：
      • 在一段较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域
    • 分类：
      • 时间局部性：
        • 某条指令一旦执行，不久后该指令可能再次执行
      • 空间局部性：
        • 一旦程序访问了某个单元，不久后附近的存储单元也将被访问
• 程序的链接与装入：
  • 【注】：
    • 高级程序语言必须通过【编译】和【链接】的方式才能成为可执行程序
  • 程序的链接：
    • 定义：
      • 将编译后的目标模块装配成一个可执行程序
    • 两种链接方式：
      • 静态链接：
        • 内容：
          • 程序运行前，用【链接程序】将目标模块链接成一个完整的装入模块，【程序运行前完成】
        • 优缺点：
          • 优点：
            • 运行速度快
          • 缺点：
            • 系统开销大
        • 静态链接的任务：
          • 链接前需要对逻辑地址进行修改
          • 变换外部调用符号（0—L+M+N-1）
          • 就是把逻辑地址连接在一起然后重新编号
      • 动态链接：
        • 内容：可将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行
        • 【就是程序一边运行一边连接】
  • 程序的装入：
    • 程序的装入方式：
      • 装入的三个步骤：
        • 编译：把程序编译成0和1的字符串
        • 链接：把0和1整合到一个大的模块
        • 装入：把模块装到可执行程序内
    • 三种装入方式：
      • 绝对装入方式：
        • 编译时产生【物理地址】的目标代码
      • 可重定位装入方式（静态）：
        • 重定位的概念：
          • 程序装入时对目标程序中的指令和数据【地址的修改过程】叫重定位
          • 【编译时】地址是【逻辑地址】，【装入时】通过【重定位】转换为【物理地址】
        • 静态：程序【装入前】算出所有物理地址
        • 【算】物理地址的算法：
          • 公式：物理地址=逻辑地址+程序在内存中的起始地址
          • 
      • 动态运行时装入（动态）：
        • 动态：程序【执行时】通过重定位转换为物理地址
      • 两种方法都属于地址映射
• 连续分配存储管理方式：
  • 单一连续分配：
    • 单一连续分配如图所示：
    • 定义：
      • 任何时刻主存储器最多只有【一个作业】
      • 只适用于【单用户】，【单任务】的操作系统
  • 固定分区分配：
    • 固定分区分配如图所示：
    • 内容：
      • 每个分区大小【固定不变】
      • 每个分区仅可以装入【一个作业】
      • 固定分区设有【上限寄存器】与【下限寄存器】
    • 两种分配方式：
      • 分区大小相等
      • 分区大小不等
    • 固定分区说明表：
      • 
      • 结构：
        • 分区编号
        • 分区大小
        • 分区起始地址
        • 分区状态
  • 动态分区分配：
    • 动态分区分配：
    • 特点：
      • 【分区大小不是预先固定的】，是按【作业的实际需求】来划分的
      • 【分区个数不是预先固定的】，是由【装入的作业数】决定的
    • 空闲分区表与空闲分区链：
      • 空闲分区表：
        • 
        • 结构：
          • 分区编号
          • 分区大小
          • 分区起始地址
      • 空闲分区链：
        • 动态地为每一个分区建立一个【结点】
        • 结点的结构：
          • 分区起始地址：
            • 100KB
          • 分区大小：
            • 10KB
          • 指向前一个空闲分区结点的指针
          • 指向后一个空闲分区结点的指针
    • 【算】动态分区分配算法：
      • 首次适应算法：
        • 步骤：
          • 空闲分区链从【头】开始找
          • 找到满足要求的空闲分区则划分一块内存给进程
          • 接下来仍然从头开始找
        • 例题：
          • P1：
            • T(头)=20+30=50
            • S（剩余大小）=120-30=90
          • P2：
            • T(头)=50+20=70
            • S（剩余大小）=90-20=70
        • 外部碎片与内部碎片：
          • 外部碎片：
            • 分割后没有分配的剩余空间
          • 内部碎片：
            • 分割时分配了的碎片
        • 【注】：不管申请多少个，都得从头开分配
      • 循环首次适应算法：
        • 步骤：
          • 采用【循环首次适应算法】，需要先加一个【循环指针】
          • 空闲分区链从头开始找
          • 找到满足要求的空闲分区则划分一块内存给进程
          • 从下一个空闲分区开始查找
        • 例题：
          • P1：
            • T(头)=20+30=50
            • S（剩余大小）=120-30=90
          • P2：
            • T(头)=200+20=220
            • S（剩余大小）=100-20=80
        • 特点：
          • 空闲区分布均匀
          • 查找开销较小
          • 缺乏大空闲去
        • 【注】：每申请一个之后，往后面的空闲分区分配
      • 最佳适应算法：
        • 空闲分区链从小到大排序
        • 找到满足要求的空闲分区则划分一块内存给进程
        • 接下来仍然从头开始找
        • 例题：
          • P1：
            • T(头)=400+30=430
            • S（剩余大小）=60-30=30
          • P2：
            • T(头)=430+20=450
            • S（剩余大小）=30-20=10
        • 特点：
          • 能提高内存的利用率
        • 先从小到大排序，然后按首次适应算法排序
  • 动态分区的分配与回收：
    • 【背】动态分区分配的流程：
      • 检索空闲分区链
      • 分配空闲分区
      • 将起始地址返回给调用者
      • 修改空闲分配表
    • 动态分区的回收：
      • 【背】动态分区回收的流程：
        • 释放一块连续的内存区域
        • 如果该区域与其他空闲区相邻，则合并
        • 修改空闲分区链
      • 【算】动态分区回收的流程：
        • • 释放后的分区与其他分区不相邻，放在最后
        • • 【注】：括号的内容包括【起始地址】与【结束地址】
          • 空闲区1（20,30）；空闲区2（50,150）；条件2（30,50）
          • 条件2与空闲区1，空闲区2相邻，合并3块空闲区
          • 总长度为10+20+100=130
        • • 【注】：括号的内容包括【起始地址】与【结束地址】
          • 空闲区2（50,150）,条件3（150,170）
          • 条件3与空闲区2相邻，合并2块空闲区
          • 总长度为100+20=120
        • 分区回收的三种情况
• 分页存储管理的基本原理：
  • 原理：
    • 基本原理：
      • 页：
        • 将一个进程的【逻辑地址空间】分成若干个大小相同相等的【片】
      • 页框：
        • 将【物理内存空间】分成与页大小相同的若干个【存储块】
      • 分页存储：
        • 将进程中的若干【页】装入多个可以不相邻的【页框】中
      • 页内碎片：
        • 进程最后一页一般【装不满】一个页框，形成【页内碎片】
      • 页表：
        • 实现从【页号】到【页框号】的映射
    • 页与页框：
    • 页表结构图：
      • • 页表：
          • 记录了页和页框的【对应关系】
        • 页：
          • 把【逻辑地址】分成片
        • 页框：
          • 把【物理地址】分成存储块
  • 分页地址结构：
    • 概念：
      • 图1：
      • 先找页，再找页内偏移量
        • 先分页，再分页内偏移量
      • 【例】：
        • 逻辑地址为2049，系统也大小为1KB(1024B)
        • 页号（P）=2049÷1024=2
        • 页内偏移量（W）=2049 ％ 1024=1（取余）
      • 图2：
        • 页号（P）
          • 把逻辑地址分段得到页号
        • 页内偏移量（W）
          • 从页号中分出的地址
          • 【页内偏移量】也称为【页内地址】
    • 分页地址结构计算：
      • 【注】：无论是第一页还是第一片都是从零开始数的
      • 【公式】：
        • 页号：
          • P=INT(A/L)
          • INT表示整除
        • 页内偏移量：
          • W=MOD(A/L)
          • MOD表示取余
        • A表示逻辑地址，L表示页大小
      • 【例】：
        • 4KB=4*1024=4096
        • 页号P=5236÷4096=1
        • 页内偏移量W=5236％4096=1140
      • 【例】：
        • 逻辑地址：
          • 页号：
            • 2^m=8,m=3
          • 页内偏移量：
            • 1KB=1024B=,2^n=1024B
            • n=10
          • 逻辑地址位：
            • 3+10=13
          • 逻辑地址位=页号+页内偏移量
        • 物理地址：
          • 页框号：
            • 2^m=32,m=5
          • 页内偏移量：
            • 1KB=1024B=2^n=1024B
            • n=10
          • 物理地址位：
            • 5+10=15
          • 物理地址位=页框号+页内偏移量
  • 分页地址变换：
    • 定义：
      • 通过【地址变换机构】将【逻辑地址】转换为片【物理地址】
    • 结构图：
    • 【背】分页地址变换的内容：
      • 将PCB中【页表起始地址】和【页表长度】送到CPU的页表寄存器
      • CPU访问某个逻辑单元A
      • 经过分页【地址变换硬件】将A分为【页号】和【页内偏移】两部分
      • 硬件检索【页表】，得到A对应的【页框号】
      • 【页框号】和【页内偏移地址】通过物理地址寄存器，计算出【物理地址】
      • 【注】：物理地址=页框大小*页框号+页内偏移量
    • 【例】物理地址计算：
      • 【算】：物理地址=页框大小*页框号+页内偏移量
      • • 页表左半边是页号，右半边是页框号
      • 计算步骤：
        • 计算页号：
          • P=1025/1024=1
        • 计算页内偏移量：
          • W=1025 MOD 1024=1
        • 观察页表得出1对应的页框号=2
        • 根据公式：物理地址=页框大小*页框号+页内偏移量：
          • 2*1024+1=2049
  • 页大小的选择因素：
    • 管理内存开销
    • 内存的利用率
    • 大小：512B-4KB
• 基于分页存储管理方式：
  • 快表（TLB）：
    • 定义：
      • 快表也称“转换后援缓冲”，是为了【提高CPU访存速度】而采用的【专用缓存】，用来【存放最近被访问过的页表项】
    • 块表结构图：
    • 引入快表后的地址变换过程：
      • CPU产生分页的逻辑地址页号和页内偏移地址后，【将页号提交给快表】
      • 【查找快表】，如果找到页号，得到该页所对应的页框号；否则，继续查找【内存页表】，得到页框号
      • 如果查找的页表项不在快表中，访问完内存页表后，把【该页表项写到快表中】
    • TLB命中率：
      • 两个时间：
        • 能在TLB找到页表：
          • 有效访存时间 = 一次访问TLB的时间 + 一次访问内存的时间
        • 不能在TLB找到页表：
          • 有效访存时间 = 一次访问TLB的时间 + 两次访问内存的时间
      • 【例】：
        • 【注】：有效访存时间=命中时间+未命中时间
        • 命中：85%*（210+30）=204
        • 未命中：15%（30+210*2）=67.5
        • 204+67.5=271.5
  • 两级和多级表：
    • 将页表再分页，形成两级或多级页表，将页表离散地存放在物理内存中
• 基于分页的虚拟存储系统：
  • 虚拟存储器：
    • 内容：
      • 定义：
        • 指具有请求【调入功能】和【置换功能】，能从【逻辑上对内存容量进行扩充】的一种存储器系统
      • 请求调入：
        • 先将进程的一部分装入内存，其余的部分什么时候需要，什么时候请求系统装入
      • 置换：
        • 如果请求调入时，没有足够的内存，则由操作系统选择一部分内存中的进程内容移到外存，以腾出空间把当前需要装入的内存调入
    • 优点：
      • 提高内存利用率
      • 提高多道程序度
      • 把逻辑地址空间和物理地址空间分开
    • 特征：
  • 分页：
    • 请求分页：
      • 定义：
        • 请求分页系统是最基本、最常用的虚拟存储系统的实现方式
      • 分页的结构：
        • 特殊的页表：
          • 页号：
            • 将进程的逻辑地址空间分成若干页,每个页的编号就是页号
          • 页框号：
            • 在物理内存空间也相对应的划分成若干个块，每个页框的编号就是页框号
          • 状态位P：
            • 标识页是否在内存中
          • 访问字段A：
            • 记录页最近被访问的情况
          • 修改位M：
            • 标识页最近是否被修改过
          • 保护位：
            • 标识页的访问权
        • 缺页异常机构：
          • 在访问内存过程中发现缺页时产生缺页异常信号
        • 【背】地址变换机构：
          • 分页地址变换机构计算出页号和页内偏移地址
          • 【查找快表】，若找到页号，读出页框号，计算物理地址
          • 若未找到页号，查找内存【页表】，若该页已调入，读出页框号，计算物理地址
          • 若内存中无页号，则产生【缺页异常】，请求调入该页，修改页表，重新执行因缺页被中断的指令
    • 页分配策略：
      • 最少页框数：
        • 定义：
          • 保证进程运正常运行的所需要的最少页框数
        • 最少页框数与进程的大小没有关系，它与计算机的【硬件结构】有关
        • 取决于指令的【格式】、【功能】和【寻址方式】
      • 置换：
      • 三种分配算法：
        • 平均分配算法
        • 按比例分配算法
        • 考虑优先权的分配算法
    • 页置换算法：
      • 三种常用置换算法：
        • 先进先出置换算法（FIFO）：
          • 内容：
            • 最简单的页置换算法
            • 为每个页记录该页调入内存的时间，选择换出页时，选择进入内存时间最早的页
          • 具体算法：
            • 算法：
              • 【替换】【最早进入】内存的页
            • 答案：
              • 缺页次数：12次
              • 缺页率：12/15=80%
              • 页置换：9次
        • 最近最久未置换算法（LRU）：
          • 内容：
            • 实现最佳算法的近似算法
            • 选择最近最久未使用的页换出
          • 具体算法：
            • 算法：
              • 往左边数，数【3个不相等的数】，【替换】被数到的数字
            • 答案：
              • 缺页次数：10次
              • 缺页率：10/15=66.7%
              • 页置换：7次
        • 最佳置换方法：
          • 内容：
            • 主要用于理论研究
            • 选择以后永远不会被访问的页&在未来最长时间内不再被访问的页作为换出页
          • 具体算法：
            • 两种情况：
              • 未访问到：
                • 序列2 0 1，从队列号3往后数，查找没有被访问到的页号（1）
                • 用页号3替换页号1
              • 最后访问：
                • 序列2 0 3，从队列号4往后数，查找最晚被访问到的页号（0）
                • 用页号4替换页号0
            • 答案：
              • 缺页次数：7次
              • 缺页率：=7/13=53.85%
              • 页置换：4次
      • 其他置换算法:
    • 请求分页系统的性能：
      • 有效访问时间：
        • 公式：
          • 有效访问时间=0.1+24999.9*P
          • P：缺页率
        • 有效访问时间与缺页率成正比，【缺页率越高，有效访问时间越长，访问效率越低】
      • 工作集：
        • 作用：
          • 降低缺页率，提高访问内存效率
        • 含义：
          • 某段时间间隔里，进程实际要访问的页的集合
      • 抖动：
        • 定义：
          • 运行进程的大部分时间都用于页的换入换出几乎不能完成任何有效果工作的状态
        • 产生原因：
          • 进程数量太多
          • 分配页框太少
        • 预防方法：
          • 采取局部置换策略
          • 引入工作集
          • 挂起若干进程
• 分页存储管理
• 分段存储管理：
  • 分段机制的引入：
    • 分段机制：
      • 定义：
        • 在分段存储管理的系统中，程序员使用【二维】的逻辑地址，一个数用来表示【段】，另一个数用来表示【段内偏移量】
      • 目的：
        • 部分存储空间动态增长
        • 信息共享
        • 信息保护
    • 内容：
      • 进程的地址空间被划分成【若干个段】
      • 每个段定义了一组逻辑信息，每个段的大小由相应的逻辑信息组的长度确定，【段的大小不一样，每个段的逻辑地址从0开始，采用一段连续的地址空间】
      • 系统为每个段分配一个【连续的物理内存区域】，各个【不同的段可以离散】地放入物理内存不同的区域
      • 系统为每个进程建立【一张段表】，段表的每一个表项纪录的信息包括【段号、段长和该段的基址】，段表存放在内存中
    • 分段的逻辑地址结构：
    • 段表：
      • 段表是由操作系统维护的用于支持分段存储管理地址映射的数据结构
      • 段表由段表项构成，每个段表象包括：【段号】【段基址】【段长】
      • 段表图：
      • 公式：
        • S号段表项=段表起始地址+段号S*段表项长度
  • 分段系统的基本原理：
    • 分段系统的地址变换：
      • 若已知逻辑单元的地址为s:d，求相应物理地址的步骤如下：
      • 以段号作索引，从段表中找到段号为s的段表项；
      • 从找到的段表项中读出s段的基地址和段大小；
      • 如果d<=段大小，则将段基址与段内偏移d相加，得到与逻辑单元s:d相应的物理单元地址
    • 分页与分段的相同与区别：
      • 相同：
        • 分页与分段都属于离散分配方式，都是为了实现逻辑地址到物理地址映射的
      • 区别：
        • 页式按物理单位划分的，段是按逻辑单位划分的
        • 页的大小固定的，段的大小是不固定的
        • 分页的地址空间是一维的，分段的地址空间是二维的
• 段页式存储管理：
  • 原理：
    • 将用户进程的逻辑空间【先划分成若干个段，每个段再划分成若干个页】
    • 进程以页为单位在物理内存中离散存放，每个段中被离散存放的页具有逻辑相关性
    • 为了实现地址映射，操作系统为【每个进程建立一个段表】，再为【每个段建立一个页表】
    • 进程段表的每一个【段表项】存放某个段的【页表起始地址和页表长度】
    • 图：
  • 地址变换过程：
    • 以段号s作索引，找到【段s的段表项】，得到该段页表的【起始地址】
    • 通过分页机制从段内偏移d中分离出【页号P和页内偏移W】
    • 以段内页号P作索引，从段s的页表中搜索页号P对应的页表项
    • 从页表项得到页所在的【页框号】
    • 由【页框号与页内偏移W】得到对应的物理地址
• Linux的伙伴系统：
  • 伙伴：
    • 【两个块具有相同的大小】，记作b
    • 它们的【物理地址是连续的】，【起始地址是2b的整数倍】
• 连续与离散：
  • 连续分配存储管理方式：
    • 单一连续分配
    • 固定分区分配
    • 动态分区分配
  • 离散分配存储管理方式：
    • 分页存储管理
    • 分段存储管理
    • 段页式存储管理