ch8 内存管理

8.1 背景

地址绑定
- 指令和数据绑定到内存地址
1. 编译时：编译时就知道进程将在内存中的驻留地址，故在编译的时候生成绝对代码。若开始地址发生改变，需要重新编译。缺点是：不利于程序在内存中的浮动，不支持虚拟内存机制
2. 加载时：绑定在加载时完成。若开始地址改变，只需要重新加载用户代码来引入改变值。缺点：不利于程序的浮动，不支持虚拟内存机制
3. 运行时：进程在执行时可以从一个内存段移动到另一个内存段，则绑定必须延迟到执行时完成。要是有硬件支持，支持虚拟内存机制。
逻辑地址空间和物理地址空间
1. 逻辑地址空间：CPU生成的地址称之为逻辑地址（也称虚拟地址），由程序所有生成的所有逻辑地址的集合叫做逻辑地址空间
  物理地址空间：内存单元的地址叫做物理地址，与程序的逻辑地址空间所对应的为物理地址空间
2. 映射：虚拟地址到物理地址的映射由内存管理单元（MMU）完成，此处先用一个简单的映射方式介绍：利用一个基址寄存器（此处为重定位寄存器）完成映射
  若逻辑地址范围为0~max，基地址为14000，此对应的物理地址为14000~14000+max
3. 动态加载：
  - 定义：主程序装入内存执行，当一个子程序需要被调用的时候将其装入内存
  - 优点：提高了内存的利用率
  - 缺点：管理复杂，执行速度慢
  - 绝对方式加载：在进程执行前将其所有的模块都装入内存。内存利用率低，但是执行速度快，管理简单。
4. 链接：
  - 静态链接：
    - 定义：运行前将所有的程序模块链接在一起，形成可执行文件，运行时直接装入内存
    - 优点：运行速度快
    - 却带你：链接及装入过程费时，可能装入用不到的模块，不利于模块的升级
  - 动态链接：
    - 定义：运行时链接，且仅链接需要的模块
    - 优点：便于模块的升级，减少了链接的时间，节省内存空间
    - 缺点：运行速度慢

8.2 交换

例
概念
- 备份存储一般为快速磁盘
- 就绪队列：在备份存储上火灾内存中准备运行的集合
- 交换限制因素：上下文切换时间较长；若要换出进程，需要保证该进程完全处于空闲状态（尤其时待处理的I/O，若该进程有待处理的I/O，可能导致换出后该I/O会使用已经属于新的进程的内存）

8.3 内存分配

概念
1. 内存主要分为两个区域：一部分用于驻留操作系统（通常位于低内存），另一部分用于用户进程
2. 碎片：
  - 定义：无用的空闲内存空间
  - 分类：内碎片和外碎片。内碎片存在于进程所在区域内部，是属于该进程的。外碎片不属于任何进程，在所有进程外
  - 降低碎片的方法：
    1. 紧缩：移动内存内容，使空闲空间形成一整块。需要重定向是动态的并且在运行时采用
    2. 允许物理空间不连续
连续内存分配（Contiguous Memory Allocation）
1. 特点：为每个调入内存的进程分配一段连续的内存区域
2. 内存映射和保护方法：利用重定位寄存器和界限寄存器实现
3. 内存分配：
  1. 单分区：用户区中只有一个分区，同一时刻只能运行一个程序
  2. 多分区：将用户区分为多个分区，每个分区每一时刻只能运行一个程序，支持多道程序设计
4. 分类：
  1. 固定分区：
    - 特点：用户划分的分区个数固定，大小固定
    - 固定分区表：记录各个分区的位置、大小、使用情况，可用于系统对分区进行管理
    - 碎片：会产生内碎片
  2. 可变分区
    - 特点：初始化分区表只有一个分区，“按需分配”
    - 分区表：对已用分区进行管理
    - 空闲分区表：对空闲分区进行管理
    - 孔（Hole）：空闲分区表中的空闲分区
5. 分区分配算法：为进程在空闲分区表中寻找合适的分区，产生外碎片
  1. 首次适应：分配找到的第一个足够大的分区，寻找的起始位置可以是表头，也可以是上次首次适应结束时的位置
  2. 最佳适应：分配足够大的里面最小的孔。必须要遍历整个表，除非这个表按照大小排序过
  3. 最差适应：分配最大的表，可以产生最大的剩余孔，也必须遍历整个表，除非这个表按照大小排序过
  4. （补充）next-fit：从上次找到合适的孔的位置继续往后找此次合适的孔
6. 分区式内存管理特点：作业/进程放在一段连续的内存区域；管理简单；比较大的作业要找到足够大的内存区域比较困难
分页（Paging）
- 引入：连续内存分配存在的碎片化问题很严重，而且为较大的作业分配足够大的内存区域比较困难（在对换时的交换区也有此问题），故引入分页
1. 基本概念
  1. 页（Page）：将逻辑内存分成固定大小的块
  2. 帧（Frame）：将物理内存分成固定大小的块
  3. 页表：将页和帧完成映射（逻辑地址到物理地址的映射）。由于页号是从0开始按顺序排列的，所以页表中忽略页号只留帧号
  4. 逻辑地址格式：页号+页内偏移量
  5. 帧表（Frame Table）：内存分配的细节，如哪些帧已用，哪些帧可用，总帧数等。每个条目代表一个帧，表示该帧空闲/占有（被哪个进程的哪个页占用）
2. 基本思想：一个作业在内存的各个页面可分配到不同帧中，但是每个页面时连续的。用户视角的内存和实际的物理内存分离，内存分帧作业分页，帧的大小和页的大小相同。内存分配以页为单位，会产生内碎片
3. 地址映射解析：
- 进一步看地址映射
1. 地址变换
- Memory Address Register (MAR)：指存储器地址寄存器，用于存储要访问的内存地址。当计算机需要读取或写入内存中的数据时，它会将要访问的内存地址加载到MAR中。
1. 硬件支持：页表的硬件实现：
  1. 作为一组专用寄存器来实现：寄存器的访问速度快，所以地址变换的速度快，但是页表较大时成本太大
  2. 将页表放入内存
  3. 使用转换表缓冲区（translation lookaside buffer，TLB），类似Cache的策略
2. 内存保护
  1. 设置valid/invalid标志位来区分有效/无效位。当系统调用一个进程的时候，将该进程的PCB中的页表信息放入系统页表中，并控制相应的控制寄存器和标志位
  2. 将逻辑地址的页号部分和页表长度比较，若比页表长度大则判断无效
3. 共享页
  - 实质：利用页表指向统一部分帧实现共享
  - 条件：
    1. 代码是可重入代码（运行多次结果不变，也叫纯码）
    2. 共享的代码应该完全一样（在逻辑地址空间里面的地址也一样）
分段（Segmentation）
- 引入：分页内存管理存在缺点：物理内存和用户想象的内存不一致；内存共享的时候可能将一个模块分成了多个页面，分享有困难
1. 主体思想
  - 支持用户视角的内存管理方案
  - 作业分段，内存按照动态分区管理
  - 内存分配以段为单位，每段都有段名和长度
  - 作业在内存中不连续，但是在段中要连续
  - 逻辑地址格式：段号+段内偏移量
  - 会产生外碎片
  - 段表描述段之间的内存位置关系，每个条目包含该段的起始位置和长度，段表基址寄存器（Segment-table base resister，STBR）保存段表在内存中的地址，段长度寄存器（Segment-length register，STLR）保存一个程序使用的段的长度
2. 基本结构如下
3. 内存保护方法：
  1. 设置valid/invalid标志位保护位
  2. 利用段表长度与段号进行比较判断段号是否有效，然后根据段表判断段内偏移量是否有效
4. 共享：
  1. 条件：代码可重入；逻辑地址必须相同
  2. 示例，进程P1，P2共享了0号段
5. 分段与分页的区别
分段和分页结合：
1. 主题思想：
  - 作业先分段，段内分页，内存划为与页相同大小的帧
  - 每个段有一个段名
  - 内存分配以页为单位
  - 每个作业有一个段表，记录段在内存中的起始地址和段长
  - 每个段还对应一个页表
  - 逻辑地址的格式：段号+段内偏移量（页号+页内偏移量）
  - 会产生内碎片
2. 地址转换

8.4 页表结构

层次页表（Hierarchical Paging）
- 引入：页表可能非常大，内存中可能找不到如此之大的连续空间，所以将表划分为更小的部分进行存放，即将表再分页。
- 例：二级分页算法
哈希页表（Hash Paging）
- 地址映射：虚拟地址的虚拟页号根据哈希函数找到哈希表的某一条目（哈希表的每一条目都存在一个链表元素处理哈希碰撞，链表的每个元素都包含三个部分：虚拟页号，帧号，指向下一个元素的指针），将虚拟页号与链表中的每个元素的虚拟页号比较，找到匹配的元素即获得对应帧号，即可形成物理地址。
反向页表
- 逻辑页号确定物理帧号的位正向列表，而由物理帧确定对应的页号为反向列表。反向列表的每个条目包括对应页号以及拥有该页的进程信息。
- 地址形成：其中pid用来表示地址空间的标识符