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

地址空间定义

  • 物理地址空间：硬件支持的地址空间
    • 起始地址0，直到 MAXsys
  • 逻辑地址空间：在 CPU 运行的进程看到的地址
    • 起始地址0，直到 MAXprog

地址生成时机和限制

  • 编译时
    • 假设起始地址已知
    • 如果起始地址改变，必须重新编译
  • 加载时
    • 如编译时起始位置未知，编译器需生成可重定位的代码(relocatable code)
    • 加载时，生成绝对地址
  • 执行时
    • 执行时代码可移动
    • 需地址转换(映射)硬件支持

地址生成过程

  • CPU
    • ALU：需要逻辑地址的内存内容
    • MMU：进行逻辑地址和物理地址的转换
    • CPU 控制逻辑：给总线发送物理地址请求
  • 内存
    • 发送物理地址的内容给 CPU
    • 或接受 CPU 数据到物理地址
  • 操作系统
    • 建立逻辑地址 LA 和物理地址 PA 的映射

连续内存分配和内存碎片

  • 连续内存分配
    • 给进程分配一块不小于指定大小的连续的物理内存区域
  • 内存碎片
    • 空闲内存不能被利用
  • 外部碎片
    • 分配单元之间的未被使用内存
  • 内部碎片
    • 分配单元内部的未被使用内存
    • 取决于分配单元大小是否要取整

连续内存分配：动态分区分配

  • 动态分区分配
    • 当程序被加载执行时，分配一个进程指定大小可变的分区(块、内存块)
    • 分区的地址是连续的
  • 操作系统需要维护的数据结构
    • 所有进程的已分配分区
    • 空闲分区(Empty-blocks)
  • 动态分区分配策略
    • 最先匹配(First-fit)
    • 最佳匹配(Best-fit)
    • 最差匹配(Worst-fit)

最先匹配(First Fit Allocation)策略

  • 思路：分配 n 个字节，使用功能第一个可用的空间比 n 大的空闲块
  • 原理 & 实现
    • 空闲分区列表按地址顺序排序
    • 分配过程中，搜索一个合适的分区
    • 释放分区时，检查是都可与临近的空闲分区合并
  • 优点
    • 简单
    • 在高地址空间有大块的空闲分区
  • 缺点
    • 外部碎片
    • 分配大块时较慢

最佳匹配(Best Fit Allocation)策略

  • 思路：分配 n 字节分区时，查找并使用不小于 n 的最小空闲分区
  • 原理 & 实现
    • 空闲分区列表按照大小排序
    • 分配时，查找一个合适的分区
    • 释放时，查找并且合并临近的空闲分区(如果找到)
  • 优点
    • 大部分分配的尺寸较小时，效果很好
      • 可避免大的空闲分区被拆分
      • 可减少外部碎片的大小
      • 相对简单
  • 缺点
    • 外部碎片
    • 释放分区比较慢
    • 容易产生很多无用的小碎片

最差匹配(Worst Fit Allocation)策略

  • 思路：分配 n 字节，使用尺寸不小于 n 的最大空闲分区
  • 原理 & 实现
    • 空闲分区列表按由大到小排序
    • 分配时，选最大的分区
    • 释放时，检查是否可与临近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序
  • 优点
    • 中等大小的分配比较多时，效果最好
    • 避免出现太多的小碎片
  • 缺点
    • 释放分区较慢
    • 外部碎片
    • 容易破坏大的空闲分区，因此后续难以分配大的分区

碎片整理：紧凑( compaction )

  • 碎片整理
    • 通过调整进程占用的分区位置来减少或避免分区碎片
  • 碎片紧凑
    • 通过移动分配给进程的内存分区，以合并外部碎片
    • 碎片紧凑的条件：所有的应用程序可动态重定位
    • 需要解决的问题：
      • 什么时候移动？
      • 开销

碎片整理：分区兑换( Swapping in/out )

  • 通过抢占并回收处于等待状态进程的分区，以增大可用内存空间
  • 需要解决的问题
    • 交换哪个(些)程序？

伙伴系统( Buddy System )

  • 整个可分配的分区大小 2U
  • 需要的分区大小为 2U-1 < s <= 2U 时，把整个块分配给该进程
    • 如 s <= 2i-1 ，将大小为 2i 的当前空闲分区划分成两个大小为 2i-1 的空闲分区
    • 重复划分过程，直到 2i-1 < s <= 2i ，并把一个空闲分区分配给该进程

伙伴系统的实现

  • 数据结构
    • 空闲块按大小和起始地址组织成二维数组
    • 初始状态：只有一个大小为 2U 的空闲块
  • 分配过程
    • 由小到大在空闲块数组中找最小的可用空闲块
    • 如空闲块过大，对可用空闲块进行二等分，知道得到合适的可用空闲块
  • 释放过程
    • 把释放的块放入空闲块数组
    • 合并满足合并条件的空闲块
  • 合并条件
    • 大小相同 2i
    • 地址相邻
    • 起始地址较小的块的起始地址必须是 2^(i+1) 的倍数

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

非连续分配的设计目标

  • 连续分配的缺点
    • 分配给程序的物理内存必须连续
    • 存在外碎片和内碎片
    • 内存分配的动态修改困难
    • 内存利用率较低
  • 非连续分配的设计目标：提高内存利用效率和管理灵活性
    • 允许一个程序的使用非连续的物理地址空间
    • 允许共享代码与数据
    • 支持动态加载和动态链接
  • 非连续分配需要解决的问题
    • 如何实现虚拟地址和物理地址的转换?
      • 软件实现 (灵活，开销大)
      • 硬件实现 (够用，开销小)
  • 非连续分配的硬件辅助机制
    • 如何选择非连续分配中的内存分块大小？
      • 段式存储管理( segmentation )
      • 页式存储管理( paging )

段地址空间

  • 进程的段地址空间由多个段组成
    • 主代码段
    • 子模块代码段
    • 公用库代码段
    • 堆栈段( stack )
    • 堆数据( heap )
    • 初始化数据段
    • 符号表等
  • 段式存储管理的目的
    • 更细粒度和灵活的分离与共享

段访问机制

  • 段的概念
    • 段表示访问方式和存储数据等属性相同的一段地址空间
    • 对应一个连续的内存”块”
    • 若干个段组成进程逻辑地址空间
  • 段访问：逻辑地址由二元组 (s,addr) 表示
    • s: 段号
    • addr: 段内偏移

页式存储管理

  • 页帧(帧，物理页面，Frame，Page Frame)
  • 页面(页，逻辑页面，Page)
  • 页面到页帧
    • 逻辑地址到物理地址的转换
    • 页表
    • MMU/TLB

帧( Frame )

  • 物理内存被划分成大小相等的帧，内存物理地址的表示：二元组 (f,o)
    f: 帧号( F 位，共有 2F 个帧)
    o: 帧内偏移 ( S 位，每帧有 2S 字节)
    物理地址 = f * 2S + o
  • 基于页帧的物理地址计算实例
    • 假定
      • 16-bit 的地址空间
      • 9-bit (512 byte) 大小的页帧
    • 物理地址计算
      • 物理地址表示 = (3, 6)
      • 物理地址 = f * 2S + o

      • F = 7，S = 9，f = 3，o = 6
    • 实际物理地址 = 2^9 * 3 + 6 = 1536 + 6 = 1542

页( Page )

  • 进程逻辑地址空间被划分为大小相等的页
    • 页内偏移 = 帧内偏移
    • 通常：页号大小 ≠ 帧号大小
    • 进程逻辑地址的表示：二元组 (p, o)
      p: 页号 ( P 位，2P 个页)
      o: 页内偏移 ( S 位，每页有 2S 字节)
      虚拟地址 = p * 2S + o
  • 页式存储中的地址映射
    • 页到帧的映射
    • 逻辑地址中的页号是连续的
    • 物理地址中的帧号是不连续的
    • 不是所有的页都有对应的帧

页表

  • 页表概述
    • 页表保存了逻辑地址与物理地址之间的映射关系
  • 页表结构
    • 每个进程都有一个页表
      • 每个页面对应一个页表项
      • 随进程运行状态而动态变化
      • 页表基址寄存器( PTBR: Page Table Base Register )
    • 页表项的组成
      • 帧号：f
      • 页表项状态
        • 存在位( register bit )
        • 修改位( dirty bit )
        • 引用位( clock/reference bit )
  • 页式存储管理机制的性能问题
    • 内存访问性能问题
      • 访问一个内存单元需要2次内存访问
      • 第一次访问：获取页表项
      • 第二次访问：访问数据
    • 页表大小问题
      • 页表可能非常大
      • 64位机器如果每页1024字节，那么一个页表的大小会是多少
    • 如何处理？
      • 缓存 ( Caching )
      • 间接 ( Indirection ) 访问

解决页表问题

  • 快表 ( Translation Look-aside Buffer, TLB )
    • 缓存近期访问的页表项
      • TLB 使用关联存储 ( association memory ) 实现，具备快速访问性能
      • 如果 TLB 命中，物理页号可以很快被获取
      • 如果 TLB 未命中，对应的表项被更新到 TLB 中
  • 多级页表
    • 通过间接引用将页号分成 k 级
      • 建立页表”树”
      • 减少每级页表的长度
  • 反置页表
    • 大地址空间问题
      • 对于大地址空间 ( 64-bits ) 系统，多级页表变得繁琐
        • 比如：5级页表
        • 逻辑(虚拟)地址空间增长速度快于物理地址空间
      • 页寄存器和反置页面的思路
        • 不让页表与逻辑地址空间的大小相对应
        • 让页表与物理地址空间的大小相对应
    • 页寄存器( Page Registers )
      • 每个帧与一个页寄存器( Page Register )关联，寄存器内容包括：
        • 使用位( Register bit )：此帧是否被进程占用
        • 占用页号( Occupier )：对应的页号 p
        • 保护位 ( Protection bits )
      • 页寄存器示例
        • 物理内存大小：4096 4096 = 4 K 4 KB = 16 MB
        • 页面大小：4096 bytes = 4 KB
        • 页帧数：4096 = 4 K
        • 页寄存器使用的空间(假设每个页寄存器占8字节)：8 * 4096 = 32 Kbytes
        • 页寄存器带来的额外开销：32K / 16M = 0.2%(大约)
        • 虚拟内存的大小：任意
      • 页寄存器方案特征
        • 优点
          • 页表大小相对于物理内存而言很小
          • 页表大小与逻辑地址空间大小无关
        • 缺点
          • 页表信息对调后，需要依据帧号可找页号
          • 在页寄存器中搜索逻辑地址中的页号
      • 页寄存器中的地址转换
        • CPU 生成的逻辑地址如何找对应的物理地址？
          • 对逻辑地址进行 Hash 映射，以减少搜索范围
          • 需要解决可能的冲突
        • 用快表缓存页表项后的页寄存器搜索步骤
          • 对逻辑地址进行 Hash 变换
          • 在快表中查找对应页表项
          • 有冲突时遍历冲突项链表
          • 查找失败时，产生异常
        • 快表的限制
          • 快表的容量限制
          • 快表的功耗限制( StrongARM 上快表功耗占 27% )
    • 反置页表
      • 基于 Hash 映射值查找对应页表项中的帧号
        • 进程标识与页号的 Hash 值可能有冲突
        • 页表项中包括保护位、修改位、访问位和存在位等标识
      • 反置页表的 Hash 冲突

段页式存储管理

  • 需求
    • 段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势。
    • 段式存储，页式存储能否结合？
  • 做法
    • 在段式存储管理基础上，给每个段加一级页表
  • 段页式存储管理中的内存共享
    • 通过指向相同的页表基址，实现进程间的段共享