非连续内存分配算法

发表于 分类于

连续内存分配内存利用效率比较低，无法适应动态修改。非连续内存分配通过允许分配非连续物理内存空间来解决问题，其中根据分块标准的不同，分为以段为单位的段式存储管理和以页为单位的页式存储管理。段式内存便于内存保护，而页式内存便于内存转移，将二者折衷又引入了段页式存储管理。

背景

连续内存的缺点：

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

非连续分配的设计目标：提高内存利用效率和管理灵活

  • 允许一个程序使用非连续的物理地址空间
  • 允许共享代码与数据
  • 支持动态加载和动态链接

非连续内存分配的实现

如何实现虚拟地址和物理地址的转换：不同的逻辑地址可能位于不连续的物理区域中

  • 软件实现（灵活，开销大）
  • 硬件实现（够用，开销小）

如何选择非连续分配中的内存分块大小？内碎片、外碎片问题？

段式存储管理（segmentation）：分块大，以段为单位
页式存储管理（paging）：分块小，以页为单位

段式存储管理

段地址空间

进程的段地址空间由多个段组成：
• 主代码段
• 子模块代码段
• 公用库代码段
• 堆栈段（stack）
• 堆数据（heap）
• 初始化数据段
• 符号表等

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

段式地址空间的不连续二维结构

段地址空间的逻辑视图

段访问机制

段的概念

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

段访问：逻辑地址由二元组 段号addr 段内偏移

  • (s，addr)表示s
  • 段号addr 段内偏移

由单地址方案转换为”段基址+段内偏移”

段访问的硬件实现

  1. 首先从逻辑地址中取出段号和偏移量
  2. 在段表中以段号为索引，查找对应的段描述符，得到段基址和段长度
  3. 由MMU判断偏移量是否大于段长度，若大于，则内存异常
  4. 偏移量与段基址相加得到物理地址，根据物理地址访问对应的内容

页式存储管理

基本单位

物理页面

页帧（Page Frame）
• 把物理地址空间划分为大小相同的基本分配单位
• $2$，如512,4096,8192，4k是常用大小

逻辑页面

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

页面到页帧之间的转换

• 逻辑地址到物理地址的转换
• 页表
• MMU/TLB 使转换高效进行

页到页帧

页帧物理地址计算

页逻辑地址计算

页式存储中的地址映射

如何将页映射到帧

  • 逻辑地址中的页号是连续的，物理地址中的页号是不连续的
  • 不是所有页都有对应的帧
  • 页表保存了逻辑地址与物理地址之间的映射关系

页表

页表结构

每个进程都有一个页表

  • 每个页面对应一个页表项
  • 随进程运行状态而动态变化（可以动态调整内存空间大小）
  • 页表基址寄存器：PTBR，Page Table Base Register 存储页表基地址

页表项组成

帧号：f

页表项标志：

  • 存在位(reside bit) 逻辑页面是否存在对应的物理帧
  • 修改位(dirty bit，又称为脏位) 对应页面中内容是否被修改了
  • 引用位(clock/reference bit) 在过去一段事件内是否访问过页中内容

性能问题

  • 访问一个内存单元需要2次内存访问 (内存访问性能问题)
    • 第一次访问获取页表项
    • 第二次访问获取数据
  • 页表大小可能会很大

如何解决页式存储的性能问题

  • 缓存 (Caching) 缓存页表项 ，根据局部性原理，之后极大可能再次访问，从而减少访问次数。例如TLB
  • 间接访问 (Indirection) 将页表项分为多级，逐级访问，比如多级页表

快表

关联存储器：有一组key，可以并行地查找所有表项，得到匹配项

快表(Translation look-aside buffer)位于CPU中，所以速度块，成本高，功耗大。

快表（TLB）与高速缓存（cache）有什么不同？

TLB：缓存页表项

Cache：缓存内存地址对应的数据

多级页表

针对大地址空间，多级页表变得繁琐。

页寄存器和反置页面的思路：

  • 不让页表与逻辑地址空间的大小相对应
  • 让页表与物理地址空间的大小相对应

页寄存器

每个帧与一个页寄存器（Page Register）关联，寄存器内容包括：

  • 使用位（Residence bit）：此帧是否被进程占用
  • 占用页号（Occupier）：对应的页号p
  • 保护位（Protection bits）：设置该页的访问方式，比如可读，可写。

页寄存器示例

  • 物理内存大小：40964096=4K*4KB=16MB
  • 页面大小：4096bytes=4KB
  • 页帧数：4096=4K
  • 页寄存器使用的空间：8*4096=32KB（假定每个页寄存器占8字节）
  • 页寄存器带来的额外开销：32K/16M=0.2%（大约）
  • 虚拟内存的大小：任意

页寄存器特征

优点：

  • 页表大小相对于物理内存而言很小
  • 页表大小与逻辑地址空间大小无关

缺点：

  • 页表信息对调后，需要根据帧号可找页号
  • 在页寄存器中搜索逻辑地址中的页号

页寄存器中的地址转换

以快表缓存页表项的页寄存器为例，

  1. 对逻辑地址进行Hash变换
  2. 在快表中查找对应页表项
  3. 有冲突时遍历冲突项列表
  4. 查找失败时，产生异常

快表的限制

  • 快表的容量限制
  • 快表的功耗限制（StrongARM上快表功耗占27%）

反置页表

查找过程：

  1. 从逻辑地址中得到页号
  2. 根据页号的运行进程pid计算hash值
  3. 在反置页表中查找对应页表项，从中找到相应的物理帧号

可有效应对大地址空间可采用的页表手段是()

  • 多级页表
  • 反置页表
  • 页寄存器
  • 单级页表

页寄存器和反置页表很像，但它们的一个区别是进程ID在地址转换中的使用。没有进程ID（页寄存器方案）时，页表占用的空间仍然是与进程数相关的。反置页表的大小只与物理内存大小，与并发进程数无关。

采用页寄存器的硬件开销会很大。所以现在的通用CPU（包括64位的CPU）没有采用这种方式，大部分还是多级页表。由于有TLB作为缓存，效率还不错。

段页式存储管理

段式内存便于内存保护，页式存储便于内存利用和优化转移，因此引入段页式存储管理。

逻辑地址：段号+页号+页内偏移

物理地址：帧号+页内偏移

地址转换过程

  1. 从逻辑地址中的得到段号s和页号P,偏移o
  2. 根据段基址和段号S查找对应段表项
  3. 访问段S的页表，取出对应的帧号

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

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

在启动页机制后，不可能进行的操作包括（）

  • 取消段机制，只保留页机制
  • 取消页机制，只保留段机制
  • 取消页机制，也取消段机制
  • 保留页机制，也保留段机制