内存管理

• 功能
  • 内存分配：解决多道程序或多进程共享内存的问题。
  • 地址转换或重定位：地址变换的方法和相关硬件。
  • 内存保护：访问权限控制。
    • 防止越界
    • 正确地存取：对存储空间的操作进行检查。
  • 内存扩充：允许虚拟内存的使用。
  • 内存共享：允许进程共享内存中的内容。
• 分配机制
  • 单用户单道程序
    • 把单一一块连续内存分配给唯一的运行程序，运行结束后释放。
    • 存储保护容易实现，容易判断是否越界。
  • 分区管理
    • 固定式分区分配
      • 把内存分为若干个不同大小的分区，不同的程序按照大小装入不同分区。
      • 使用的数据结构：分区说明表，包含每个分区的起始位置、分区大小、占用标志（使用的进程）。
      • 多进程队列分配：每个分区一个队列，程序按照大小进入不同队列，按顺序使用。
        • 单个队列容易拥挤。
      • 单进程队列分配：所有进程处于同一队列，有分区空闲时在队列中搜索一个进程并分配。
      • 实现简单，但是每个分区都会造成空间浪费。
      • 使用静态重定位，进程使用物理地址，使用上下界寄存器实现保护。
    • 可变式分区分配
      • 根据作业的大小分配分区，分区大小恰好等于作业的大小。
      • 分区的大小、数量都是不确定的。
      • 使用的数据结构：分区说明表或空闲区链表。
        • 分区说明表：包含两个表，分别表示已分配和未分配内存，内部结构与固定式分区结构相同。
        • 空闲区链表：只记录空闲内存，内存块用指针连接形成双向链表，块首尾都包含块的元信息。
      • 分配算法：
        • 首次适应：按顺序查找内存块，分配第一个满足需求的内存块，剩余空间保留。
        • 最佳适应：查找满足需求的最小内存块并分配。缺点：
          • 需要扫描所有空闲块，可以通过按大小排序空闲块改进。
          • 容易把内存划分很小，造成碎片化。
        • 最坏适应：查找最大内存块并分配。
          • 优点：避免内存碎片。
          • 缺点：大进程的需求可能无法满足。需要扫描所有空闲块。
      • 回收内存块后，需要尝试把此内存块与相邻的空闲块合并。
      • 使用动态重定位，进程使用逻辑地址，使用基址和限长寄存器实现保护。
    • 优缺点
      • 优点：
        • 允许多道程序共享内存。
        • 实现简单。
        • 保护手段简单。
      • 缺点：
        • 容易造成内存碎片。
        • 没有扩充内存，地址空间受限于实际内存大小。
  • 页式管理
    • 把物理内存划分为等大的页框，把地址空间也划分为同样大小的页，进程访问页转换为访问对应的页框。
    • 逻辑地址划分为页号和页内地址，页号位于高位，页内地址位于低位。这种划分对进程是透明的。
    • 不容易产生碎片，每个进程的空间浪费平均为半个页。
    • 地址转换由硬件完成：
      • 每个进程有一个页表，起始地址和长度储存在控制寄存器中。
      • 从页表通过页号查找页框起始地址，再加上页内地址得到物理地址。
      • 如果页号超出长度，则进程中止。
    • 为了加速地址转换，CPU 中设置有联想储存器，用于保持最近地址转换的页表项缓存，即快表。
      • 转换地址时，同时向快表和内存发出转换请求，如果快表缓存命中则立即中止内存请求，否则等待并刷新缓存。
    • 使用的数据结构：
      • 页表：保存页到页框的映射关系和其他信息，每个进程一个。
      • PCB：其中保存此进程的页表起始地址和长度。
      • 存储空间使用情况：记录已分配和空闲的页框。
        • 存储分块表：记录空闲块总数，并将所有空闲块用指针连接成单向链表。
        • 位图：用一个位表示一个块的空闲情况。
    • 内存共享：
      • 对于常用的内容，如代码等，可以通过页指向同一页框实现共享。
      • 对于共享内容，一般需要权限控制，如设置为只读。
  • 段式管理
    • 进程的地址空间划分为二维，需要使用段号和段内地址指定逻辑地址，不同段存放不同内容。
    • 分配内存时按照段为单位分配，每个段是连续的内存，不同段可以不连续，长度可以不同。
    • 地址转换与页式管理类似，使用的是段表，且段表项额外记录段长度。
    • 段氏管理类似于可变分区管理，也可以使用其分配策略，也容易产生碎片。
• 虚拟内存
  • 页式虚拟内存管理
    • 管理方法
      • 进程的信息默认不载入内存，而是存放在外存上，在调度时，再把需要的页加载。
      • 需要额外使用一个外页表，用于记录页与外存空间的映射关系。
      • 页表中需要增加：
        • 有效位：记录页是否被加载到内存中，如果没有，访问时会发生缺页中断。
        • 修改位：记录页加载后是否被修改过，如果没有，换页时可以直接丢弃，否则需要写回外存。
      • 产生缺页中断时，CPU 自动转向运行 OS 提供的中断处理程序，尝试装入需要的页。
    • 页面淘汰算法
      • OPT：理论上的最优方法，但无法泛用地实现。
      • FIFO：淘汰最先加载的页。
        • 效率低，容易缺页。
        • Belady 异常：如果分配给进程的页增加，缺页次数反而增加。
      • LRU：淘汰上一次使用距今间隔时间最长的页面。
        • 可以使用一个计数器记录访问内存的次数，访问每个页面时写入计数器值，淘汰时选择值最小的页面。
        • 可以使用栈，访问页面后就把此页面移动到栈顶，淘汰时选择栈底页面。
      • 时钟页面置换：
        • 所有页面连接为循环链表，页面有一个引用位，表示最近是否使用过。
        • 维护一个指针，淘汰页面时，不断重复：
          • 如果引用位为 1，则清除，向前移动指针。
          • 如果引用位为 0，则淘汰此页面并更换，停止扫描。
        • 指针的位置不重置。
    • 页面大小
      • 小页面可以减少内存碎片，并且装入页面可以更灵活，权限控制更精细。
      • 大页面可以减小页表大小，从外存加载可以更快。
      • 使用多级页表时，可以支持不同尺寸的页表。
      • 定量确定页面大小 $p$：
        • 设进程平均占用 $s$，单个页表项占用 $e$。
        • 单个进程的碎片和页表占用开销约为 $\dfrac{se}{p} + \dfrac{p}{2}$。
        • 最优值为 $p = \sqrt{2se}$。
  • 段式虚拟内存管理
    • 管理方法
      • 段表需要额外增加：
        • 有效位：段是否加载到内存中。
        • 访问位、修改位：用于确定要淘汰的段以及是否需要写回外存。
        • 动态增长位：段的长度是否允许动态增长。
      • 发生缺段中断时，自动执行 OS 的中断处理程序：
        • 检查是否有足够空闲空间加载段，如果没有则尝试整理现有段，如果还没有再淘汰段。
        • 加载后，检查是否越界：
          • 如果不允许动态增长，则如果发生越界就中止进程。
          • 如果允许动态增长，先确认是否可以增长到请求的地址，如果不行也同样中止。
    • 动态链接
      • 间接编址字：包含动态链接标志位 L 和直接地址。
        • 如果 L 为 0，则直接调用或跳转到直接地址。
        • 如果 L 为 1，则先找到直接地址指向的符号，根据符号进行链接，并替换直接地址为真实地址，设置 L 为 0。
      • 编译后符号实际上是目标段名和段内地址，链接后转换为真实的段号和真实的段内地址。
      • 动态链接过程中，也可能加载目标段到内存。
  • 段页式虚拟内存管理
    • 将段式和页式管理结合，程序仍然使用段式地址，地址先进行段式转换为线性，再页式地址转换为物理地址。
    • x86 架构使用段页式管理：
      • 访问段时给出的是段选择符，包括段号（13 位）、全局（GDT）或局部（LDT）、特权级（2 位）。
      • 页表分为两级，支持 4 KiB 和 4 MiB 页表。