鲤鱼笔记

物理内存管理：非连续内存分配

2021-07-18 操作系统 uCore

# 一、需求背景

连续内存分配给内存分配带来了很多不便，可能所有空闲片区大小都无法满足需求大小，这个分配就会失败。基于这种现状，就有了非连续内存分配的需求。

非连续分配成功的几率更高，但也面对更多的问题，比如分配时是不是 1 个字节的空间也可以进行分配？显然 1 个字节为单位分配太短了。因此我们需要选择不同尺度的基本块进行分配管理。

实际操作系统中出现了两种基本块，一种是段式，一种是页式。段式分的块比较大，页式分配的块比较小。分配的块越小，逻辑地址与物理地址之间的映射关系就越复杂。根据这种映射关系形成了页表。还有一种结合的方式段页式管理。

# 1.1 连续分配的缺点

  • 分配给程序的物理内存必须连续
  • 存在外碎片和内碎片
  • 内存分配的动态修改困难
  • 内存利用率较低

# 1.2 非连续分配的设计目标

  • 允许一个程序使用非连续的物理地址空间
  • 允许共享代码与数据
  • 支持动态加载和动态链接
  • 提高内存利用效率和管理灵活性

# 1.3 非连续分配需要解决的问题

  • 如何实现逻辑地址和物理地址的转换
    • 软件实现（灵活，开销大）
    • 硬件实现（够用，开销小）
  • 如何选择非连续分配的内存分块大小
    • 段式存储管理（segmentation），内存基本块较大；
    • 页式存储管理（paging），内存基本块较小。

# 二、段式存储管理

段式存储管理的目的：更细粒度和灵活的分离与共享。

# 2.1 段地址空间

进程的段地址空间由多个段组成，具体表现形式如下图所示，我们可以将不同类型的数据在物理地址上分离开。

# 2.2 段访问机制

段的概念：

  • 段表示访问方式和存储数据等属性相同的一段地址空间
  • 对应一个连续的内存“块”
  • 若干个段组成进程逻辑地址空间

段访问：逻辑地址由二元组 (s, addr) 表示，其中 s 为段号，addr 为段内偏移。

上图是段访问的硬件实现，具体流程为：

  1. 程序在 CPU 上执行，要访问一个存储单元的时候，首先得到它的逻辑地址，将其分为段号和段内偏移；
  2. 根据段号去查进程的段表，得到段描述符（记录段起始地址和长度）；
  3. 存储管理单元（MMU）将长度与偏移进行比较：
    • 若越界，则内存异常，访问结束；
    • 若未越界，将基址与偏移相加，得到实际物理地址，从而读取数据。

# 三、页式存储管理

# 3.1 页式存储管理的概念

页帧（帧、物理页面，Frame，Page Frame）

  • 把 物理地址空间 划分为大小相同的基本分配单位
  • 2 的 n 次方，如 512，4096，8192

内存物理地址的表示：二元组 (f, o)，其中 f 表示帧号（F 位，共有 2F2^F 个帧），o 表示帧内偏移（S 位，每帧有 2S2^S 个字节）。因此，物理地址 = 帧号 * 帧长度 + 帧内偏移 = f * 2S2^S + o

下图是一个基于页帧的物理地址计算实例：

页面（页、逻辑页面，Page）

  • 把 逻辑地址空间 也划分为相同大小的基本分配单位
  • 帧和页的大小必须是相同的

进程逻辑地址的表示：二元祖 (p, o)，其中 p 表示页号（P 位，共有 2P2^P 个页），o 表示页内偏移（S 位，每页有 2S2^S 个字节）。因此，逻辑地址 = 页号 * 页长度 + 页内偏移 = p * 2S2^S + o

# 3.2 页式存储管理的地址转换

  • 逻辑地址中的页号是连续的
  • 物理地址中的帧号是不连续的
  • 不是 所有的页都有对应的帧

上图是通过页表实现的逻辑地址到物理地址的转换，具体流程为：

  1. 程序在 CPU 上执行，要访问一个存储单元的时候，首先得到它的逻辑地址，将其分为页号和页内偏移；
  2. 根据页号去查页表，得到对应的帧号；
  3. 由于页内偏移与帧内偏移相等，因此根据得到的帧号和偏移就可以计算出物理地址。

# 3.3 页表结构

每个进程都有一个页表，其中：

  • 每个页面对应一个页表项，用于完成逻辑页号到物理帧号的转换；
  • 页表中的内容会随着进程运行而动态变化，使得我们可以动态调整分配给一个进程的内存空间的大小；
  • 在页表基址寄存器（PTBR：Page Table Base Register）中记录页表的起始位置。

页表项的组成：

  • 帧号：f；
  • 页表项标志位：
    • 存在位（resident bit）：是否有一个物理帧与当前页号相对应；
    • 修改位（dirty bit）：当前页面里的内容是否被修改；
    • 引用位（clock / reference bit）：当前页面在过去一段时间内是否有过对它的引用。

# 3.4 页表地址转换实例

# 3.5 页式存储管理机制的性能问题

内存访问性能问题

访问一个内存单元需要 2 次内存访问：

  • 第一次访问：获取页表项；
  • 第二次访问：访问数据。

页表大小问题

页表可能非常大。

64 位机器如果每页 1024 字节，那么一个页表的大小会超过 264−10×(64/8)=2572^{64-10} \times (64 / 8) = 2^{57} 个字节（未计算标志位）。

解决方法

  • 缓存（Caching）：快表；
  • 间接（Indirection）访问：多级页表。

# 3.6 快表（Translation Look-aside Buffer, TLB）

用于缓存近期访问的页表项。

  • TLB 使用关联存储（associative memory）实现，具备快速访问性能；
  • 如果 TLB 命中，物理页号可以很快被获取；
  • 如果 TLB 未命中，对应的表项被更新到 TLB 中。

# 3.7 多级页表

通过间接引用将页号分成 k 级，最多访问次数 k + 1 次。

  • 建立页表“树”；
  • 减少每级页表的长度（根据存在位将不需要的页表项删除）。

二级页表实例

  • 从 PTBR 中获取第一级页表的基址；
  • 根据第一级页号 p1 与基址相加定位到对应页表项，获取到第二级页表的基址；
  • 根据第二级页号 p2 与基址相加定位到对应页表项，获取到实际的物理帧号；
  • 根据得到的物理帧号与偏移得到实际的物理地址。

# 四、段页式存储管理

# 4.1 段页式存储管理的需求

  • 段式存储在内存保护方面有优势；
  • 页式存储在内存利用和优化转移到后备存储方面有优势。

那么段式存储、页式存储能否结合？

# 4.2 段页式存储管理

在段式存储管理基础上，给每个段加一级页表。

# 4.3 段页式存储管理中的内存共享

通过指向相同的页表基址，实现进程间的段共享。

# 五、参考资料

Last Updated: 2023-01-28 4:31:25

虚拟存储概念