操作系统物理内存管理：连续和非连续

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

地址空间定义

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

地址生成时机和限制

• 编译时
  • 假设起始地址已知
  • 如果起始地址改变，必须重新编译
• 加载时
  • 如编译时起始位置未知，编译器需生成可重定位的代码(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 )

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

伙伴系统的实现

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

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

非连续分配的设计目标

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

段地址空间

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

段访问机制

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

页式存储管理

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

帧( Frame )

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

页( Page )

• 进程逻辑地址空间被划分为大小相等的页
  • 页内偏移 = 帧内偏移
  • 通常：页号大小 ≠ 帧号大小
  • 进程逻辑地址的表示：二元组 (p, o)
    p: 页号 ( P 位，2^P 个页)
    o: 页内偏移 ( S 位，每页有 2^S 字节)
    虚拟地址 = p * 2^S + 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 冲突

段页式存储管理

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