操作系统 第四章 非连续式内存分配

> 清华大学 陈渝老师 操作系统教程

• 连续内存分配的缺点
• 分配给一个程序的物理内存是连续的
• 内存利用率较低
• 有外碎片、内碎片的问题
• 非连续分配的优点
• 一个程序的物理地址空间是非连续的
• 更好的内存利用和管理
• 允许共享代码与数据（共享库……）
• 支持动态加载和动态链接

• 如何建立虚拟地址和物理地址之间的转换
• 软件方案
• 硬件方案
• 分段（Segmentation）：更好的分离和共享
• 程序的分段地址空间
• 
  
• 
  
• 分段寻址方案
• 段访问机制
• 一个段：一个内存“块”
• 一个逻辑地址空间
• 程序访问内存地址需要
• 一个二维的二元组
• 段号
• 段内偏移
• 实现方案
• 段寄存器+地址寄存器
• 单地址
• 
  
• 分页（Paging）
• 划分物理内存至固定大小的帧
• 大小是2的幂
• 划分逻辑地址空间至相同大小的页
• 大小是2的幂
• 建立方案：转换逻辑地址为物理地址（pages to frames）
• 页表
• MMU（内存管理单元，CPU重要组成部分）/TLB（块表，对页表的缓存）
• 页帧
• 物理内存被分割为大小相等的帧
• 一个内存物理地址是一个二元组（f，o）
• f——帧号（F位，共2的F次方个帧）
• o——帧内偏移（S位，每帧有2的S次方字节）
• 
  
• 页
• 一个程序的逻辑地址空间被划分为大小相等的页
• 页内偏移的大小 = 帧内偏移的大小
• 页号大小<>帧号大小
• 一个逻辑地址是一个二元组（p，o）
• p——页号（P位，2的P个页）
• o——页内偏移（S位，每页有2的S次方字节）
• 
  
• 页表是由操作系统创建的
• 页寻址机制
• 页映射到帧
• 页是连续的虚拟内存
• 帧是非连续的物理内存
• 不是所有的页都有对应的帧

• 页表概述
• 页表结构
• 每个运行的程序都有一个页表
• 属于程序运行状态，会动态变化
• PTBR：页表基址寄存器
• 页表项的内容
• Flags（标志位）
• dirty bit
• resident bit
• 0
• 页帧在内存中不存在，没有这个映射关系
• 1
• clock/reference bit
• 帧号
• 地址转换实例
• 分页机制的性能问题
• 访问一个内存单元需要2次内存访问
• 一次用于获取页表项
• 一次用于访问数据
• 页表可能非常大
• 64位机器如果每页1024字节，那么一个页表的大小会是多少？
• 解决方法
• 缓存（Caching）
• 间接（Indirection）访问
• 转换后备缓冲区（TLB）
• 解决页表的时间问题
• 缓存近期访问的页帧转换表项
• TLB使用associative memory(关联内存)实现,具备快速访问性能
• 如果TLB命中,物理页号可以很快被获取
• 如果TLB未命中,对应的表项被更新到TLB中
• TLB缺失不会很大
• 写程序时注意使程序具有局部性,把平时的访问集中在一个区域可以减少TLB的缺失
• 二级/多级 页表
• 二级页表
• 多级页表
• 通过把页号分为k各部分来实现多级间接页表
• 反向页表
• 大地址空间问题
• 有大地址空间（64-bits），前向映射页表变得繁琐
• eg.5级页表
• 不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应
• 逻辑（虚拟）地址空间增长速度快于物理地址空间
• 基于页寄存器（Page Registers）的方案
• 
  
• 每一个帧和寄存器关联，寄存器内容包括
• Residence bit：此帧是否被占用
• Occupier：对应的页号p
• Protection bits：保护位
• 利弊
• 利
• 转换表的大小相对于物理内存来说很小
• 转换表的大小跟逻辑地址空间的大小无关
• 弊
• 需要的信息对调了，即根据帧号可找到页号
• 如何转换回来？即根据页号找到帧号
• 需要在反向页表中搜索想要的页号
• 基于关联内存（associative memory）的方案
• 在反向页表中搜索一个页对应的帧号
• 如果帧数较少，页寄存器可以被放置在关联内存中
• 在关联内存中查找逻辑页号
• 成功：帧号被提取
• 失败：页错误异常（page fault）
• 限制因素
• 大量关联内存非常昂贵
• 难以在半个时钟周期内完成
• 耗电
• 基于哈希（hash）查找的方案
• 子主题 1
• 在反向页表中通过哈希算法来搜索一个页对应的帧号
• 对页号做哈希计算，为了在“帧表”（每帧拥有一个表项）中获取对应的帧号
• 页i被放置在表中f（i）位置，其中f是设定的哈希函数
• 为了查找页i，执行下列操作
• 计算哈希函数f（i）并且使用它作为页寄存器表的索引
• 获取对应的页寄存器
• 检查寄存器标签是否包含i，如果包含，则代表成功
• 否则失败