《计算机操作系统》 第4章 存储器管理

计算机操作系统的第4章“存储器管理”的思维导图

第四章 存储器管理

• 4.1 存储器的层次结构
  • 4.1.1 多层结构的存储器系统
    • 存储器的多层结构：寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质
    • 可/不可执行的存储器
      • 可执行存储器
        • 包括：寄存器、主存储器等
        • 存储管理：存储管理负责对可执行存储器的分配、回收等
      • 不可执行存储器
        • 包括：固定磁盘等
        • 设备和文件管理：根据用户需求，对不可执行存储器进行操作
      • 主要区别在于：是否要通过I/O设备实现访问
  • 4.1.2 主存储器和寄存器
  • 4.1.3 高速缓存和磁盘缓存
    • 高速缓存
      • 位置：介于寄存器和主存储器之间
      • 作用：将主存储器中频繁使用的部分放入高速缓存
    • 磁盘缓存
      • 位置：介于主存与磁盘之间
      • 作用：暂时存放频繁使用的一部分磁盘数据和信息
• 存储器管理功能：主要是如何将外存上的程序装入主存储器上（4.2），如何分配给其空间地址（4.3-4.7）。涉及到可执行存储器，属于存储器管理
• 4.2 程序的装入和链接
  • 程序的完整过程：预编译、编译、汇编、链接、装入
    • 下面只讲述链接与装入
  • 4.2.1 程序的装入
    • 目的：将装入模块装入内存
    • 装入方式
      • 1、绝对装入方式：直接使用目标程序的地址作为物理地址
      • 2、静态可重定位装入方式：在装入时对目标程序中的指令和数据地址的修改过程
      • 3、动态运行时的装入方式：装入模块时并不立即将模块中的逻辑地址转换为物理地址，而是推迟到程序真正被调用时才进行，因此装入内存的所有地址任然是逻辑地址
  • 4.2.2 程序的链接
    • 目的：将所有的目标模块以及所需的库函数链接为一个完整的装入模块
    • 链接方式
      • 1、静态链接
        • 概念上：在程序运行之前，就将目标模块等组装为一个完整的装入模块
        • 链接中的修改
          • 1、对相对地址进行修改，因为链接成了一个整体的装入模块
          • 2、对跳转指令中模块外部调用符号转换为相对地址
        • 缺点
          • 1、整体的装入模块，不可再分割，不够灵活，不便于修改和更新
          • 2、装入模块中，可能含有再实际运行中不使用的部分，浪费了内存
      • 2、装入时动态链接
        • 概念上：在装入时，采取边装入边链接的方式
          • 即在装入一个目标模块时，若发生一个外部模块调用事件，才将其引进到装入模块
        • 优点
          • 不是整体的装入模块，便于修改和更新、实现对目标模块的共享
      • 3、运行时动态链接
        • 概念上：在程序运行时，只有运行到需要某一个目标模块时，才调用目标模块链接进来
        • 优点
          • 高效，节省大量的内存空间。同时，加快程序的装入过程
• 关于程序如何装入内存有两种手段，分别是连续分配（4.3）和离散分配（4.5、4.6）
• 4.3 连续分配存储管理方式
  • 4.3.1 单一连续分配
    • 适用系统：适用于单道程序环境
    • 概念：将内存分为系统区和用户区，其中用户区仅装有一道用户程序
  • 4.3.2 固定分区分配
    • 概念
      • 固定：指分区大小是固定不变的
      • 分区：将用户区划分为多个分区
      • 分配：将分区分配给进程
    • 划分分区方法
      • 1、全等式：所有分区的大小相等，缺点是缺乏灵活性
      • 2、不等式：分区大小不相等，将内存区划分为多个较小的分区、适量的中等分区以及少量的大分区
    • 内存分配：使用分区使用表
  • 4.3.3 动态分区分配
    • 动态分区数据结构
      • 空闲分区表：包括分区号、分区大小、分区始址、状态
      • 空闲链表结构：每个空闲分区的前后设置设置一个指针指向前/后一个空闲分区
    • 动态分区算法
      • 1、基于顺序搜索的动态分区分配算法
        • 基于顺序搜索的概念：依次搜索空闲分区链上的空闲分区，去寻找一个其能满足要求的分区
        • 1、首次适应算法FF
          • 过程：按照空闲分区链地址递增的次序寻找第一个满足要求的空闲分区
          • 优缺点：有效的利用内存的低地址的空闲分区。缺点是低地址部分不断被划分，会留下许多碎片
        • 2、循环首次适应算法NF
          • 过程：为进程寻找空闲分区时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区查找
        • 3、最佳适应算法BF
          • 过程：指每次为作业分配内存空间时，总是把满足要求、又是最小的空闲分区和分配给作业
        • 4、最坏适应算法WF
          • 过程：与最佳适应算法相反
      • 2、基于索引搜索的动态分区分配算法
        • 索引搜索，能够加快搜查速度
        • 1、快速适应算法
          • 别名：分类搜索法
          • 基本思想： 将空闲分区按照其容量大小进行分类，对于每一类相同容量的所有空闲分区设立一个空闲分区链表
          • 过程：按照需求的空闲分区的大小从索引表中找到能容纳的最小空闲区的双向链表，然后从该链表中取下一块分配即可
        • 2、伙伴系统
          • 规定：分区的大小必须均为2的k次幂,也需要进行按大小分类，并同时设置空闲区的双向链表
          • 分配过程观察
            • 过程描述：基于分割将空闲区分割为适合的大小
            • 过程结果
              • 最好的结果：第一次就完成了分配
              • 最坏的结果：最坏的情况下，可能需要对2^k的空闲分区进行k次分割
          • 伙伴的由来：由于2^(i+1)分割为2个2^i的空闲区，二者被称为伙伴
        • 3、哈希算法：进一步加快搜索的过程
    • 分配操作
      • 分配内存：按照分配算法，从数据结构中找到合适大小的进行分配
      • 回收内存
        • 不用建立新表项的情况：回收区的前后有相邻的空闲区，可以直接合并
        • 建立新表项的情况：回收区的前后无空闲区，必须建立新表项
  • 4.3.4 动态可重定位分区分配
    • 紧凑操作+动态重定位
      • 紧凑操作：通过移动内存中作业的位置，将原来的多个分散的小分区拼接为大分区
        • 带来的问题：碎片合并后，用户程序也会发生移动，导致地址变化，必须重定位
      • 动态重定位：通过重定位寄存器实现程序在运行中，地址的重新定位
        • 重定位寄存器：存储着程序在内存中的物理开始地址
    • 动态重定位分区分配算法
• 4.4 对换
  • 4.4.1 多道程序环境下的对换技术
    • 对换的概念：指将内存空间中暂时不使用的程序和数据换出到外存上，以便腾出足够的内存空间
    • 对换的目的：改善内存利用率，直接提高处理机的利用率和系统的吞吐量
    • 对换的实现：通过对换进程来实现
    • 对换的类型
      • 1、页面（分段）对换
        • 别名：统称为部分对换
        • 目的：为了支持虚拟存储系统
        • 单位：以进程的一个页面或段作为基础单位
      • 2、整体对换
        • 别名：统称为进程对换
        • 目的：为了缓解内存紧张问题，进程对换实际上就是处理机中级调度
        • 单位：以进程作为基础单位
  • 4.4.2 整体对换实现，系统需要具备两方面功能
    • 1、对换空间的管理
      • 磁盘空间的分类
        • 文件区
          • 归属：文件区管理
          • 作用：存放各种文件，占用磁盘空间的大部分，操作频率低
          • 管理目标：文件区管理的目标是提高文件存储空间的利用率
          • 管理方式：采取离散分配方式
        • 对换区
          • 归属：对换空间管理
          • 作用：存放从内存中换出的进程，占用磁盘空间的小部分，操作频率高
          • 管理目标：对换空间管理的目标是提高进程的换入和换出
          • 管理方式：采取连续分配方式
      • 对换空间管理
        • 基本单位：盘块
        • 空闲盘块的数据结构：分区表、分区链
        • 分配与回收
    • 2、进程的换出与换入
      • 进程的换出
        • 1、选择被换出的进程：选择运行内存中的阻塞或睡眠状态的进程中优先级最低
        • 2、开始进程换出进程
      • 进程的换入
        • 1、对换程序定期检查并执行换入操作，查看PCB集合中所有进程的状态，找出就绪状态但已换出的进程
• 4.5 分页存储管理方式
  • 4.5.1 分页存储管理的相关概念
    • 1、基本单位
      • 页面：进程的逻辑地址空间被分为若干个固定大小的页
      • 物理块：内存的物理地址空间被分为若干个块
      • 进程分配内存时，可以将进程的多个页面装入不相邻的物理块中
    • 2、地址
      • 地址的结构：页号P+位移量W（页内地址）
        • 各自的位数：决定了页的数目、每一页的大小
      • 含义：进程的逻辑地址空间中第P页的第W个的地址
    • 3、页表
      • 表项内容：记录了相应页的页号在内存中的对应物理块号
      • 作用：实现从页号到物理块号的映射
  • 4.5.2 地址变换机构
    • 作用：进组页表来完成将进程的逻辑地址转换为内存的物理地址
    • 实际任务：就是将逻辑地址的页号转换为物理块号
    • 基本的地址变换机构
      • 组成：页表寄存器、页表、输入的用户的逻辑地址、输出的物理地址
        • 页表寄存机器：含有页表始址与页表长度
        • 页表：含有页号与对应的物理块号
          • 页表存放在内存中
        • 逻辑地址：页号+页内地址
        • 物理地址：物理块号+页内地址
      • 地址变换过程
        • 1、判断：先比较页表长度和对应页号
        • 2、查找物理块号：将页表始址与页号和页表项长度的乘积相加，得到该表项在页表的位置，找出对应的物理块号
        • 3、拼接：将物理块号与页内地址进行拼接
      • 问题：页表是存放在内存中，CPU每次读取数据要访问两次内存
        • 1、第一次访问：访问内存中的页表，从中找到指定页的物理块号，再将物理块号与页内偏移量拼接
        • 2、第二次访问：真正的访问这个内存中的数据
      • 改进：具有快表的地址变换机构
        • 快表也叫“联想寄存器”，作用在于存储最近使用的页号和对应的物理地址，由此避免了第一次访问的要求（快表一般16-512个表项）
        • 相应的地址变换过程
          • 1、快表查询：查询快表中，是否有对应的页号，如果有，可以直接查找到直接对应的物理地址
          • 2、快表中没有对应页号的表项，则与基本的地址变换机构一样的过程：判断、查找、拼接
          • 3、添加快表表项：将本次查找的物理地址和页号放入快表中
  • 4.5.3 访问内存的有效时间EAT
    • 概念：指进程发出逻辑地址的访问请求后，经过地址变换，到找到对应的物理地址单元中的数据的时间
    • 计算EAT
      • 1、基本的地址变换机构：两次访问内存的时间之和
      • 2、引入快表的地址变换机构：以概率p访问快表的成功的时间、以概率1-p访问失败的时间加上后两次访问内存的时间
        • 命中率越高，CPU访问数据所耗费的时间越短
  • 4.5.4 两级和多级页表
    • 页表带来的问题：页表占据的内存空间是相当大的，且需要连续的内存空间。解决办法
      • 1 、离散分配：对于页表需要的内存空间，可采用离散分配方式--解决连续分配的
      • 2、部分调入：只将部分页表项调入到内存中--解决占用大量的内存空间
    • 两级页表：就是采用了离散分配方式，并创建了一个外层页表
      • 1、离散分配：二级页表可以分散在内存空间的不同位置上
      • 2、部分调入：一级页表（外层页表）必须位于内存上，而二级页表（内层页表）按需调入即可
  • 4.5.5 反置页表：将页表中的表项跌倒过来，为每一个物理块设置一个页表项
    • 内容
      • 序号：对应物理块号
      • 页号：该物理块对应的页号
      • 进程的标识符：该页号下的进程的标识符
    • 检索：根据进程的标识符与页号来查找对应的物理块
      • 注意：加入了进程的标识符
    • 优点：极大的减少了页表占用内存的问题
      • 原因：页表是为每一个进程都创建页表，而反置页表仅仅只需要为一个内存创建反置页表
• 4.6 分段存储管理方式
  • 4.6.1 分段存储管理方式
    • 目的：满足用户在编程和使用上的多方面要求
    • 符合用户和程序员的如下多方面需要：方便编程、信息共享、信息保护、动态增长、动态链接
    • 段的特征
      • 每个段的都是从0开始编址，属于相对地址
      • 数据段还可以动态增加
      • 段时信息的逻辑单位
      • 每个段的段名、长度都不一样
  • 4.6.2 分段系统的相关概念
    • 分段：作业的地址空间被划分为若干个段，每个段都定义了一组逻辑信息
    • 分段的地址结构：段号+段内地址
    • 段表
      • 内容
        • 1、段号：从0到n
        • 2、段长与对应的物理地址的基地址
      • 作用：将段的逻辑地址映射到内存的物理地址上
    • 分段与分页的主要区别
      • 1、单位属性、目的：
        • 页是信息的物理单位，作用是为了提高内存的利用率
        • 段是信息的逻辑单位，包含了一组意义完整的信息，作用是为了更好的满足用户需求
      • 2、 大小：
        • 页的大小是固定的，由系统决定，主要取决地址结构中页内地址的位数
        • 段的大小是不固定的，取决于用户编写的程序
      • 3、行为上：
        • 分页是系统行为，是单一的线性地址空间
        • 分段式用户的行为，用户程序的地址空间是二维，即有段名与段内地址
  • 4.6.3 信息共享
    • 分页系统中对程序和数据的共享
      • 不方便
    • 分段系统中对程序和数据的共享
      • 方便
    • 例如一个40kb的程序段，分段系统只需读取该段一次，而读取一个只有4kb的页时，需要读取至少10次