虚存和地址转换

发表于 更新于 分类于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 10 分钟

计算机存储体系结构

  1. 冯·诺依曼结构

  2. 层次化存储结构

    • 内存DRAM：快、容量小、易丢失、昂贵
    • 外存磁盘：慢、容量大、不易丢失、便宜

需求一：进程保护

  1. 一个进程出错不能影响到其他进程
  2. 需要对每个内存访问都进行检查，保证内存访问都合法

需求二：扩展内存和应用透明

  1. 一个进程必须能运行再不同的物理内存区域上
  2. 一个进程必须能运行在不同的物理内存大小上

问题：如何高效地使用内存空间？

  1. 目标1：同时运行多个进程
    • 系统能够运行的进程越多越好
  2. 目标2：地址空间足够大
    • 一个大进程，其大小超过物理内存
    • 多个小进程，其大小总和超过物理内存
  3. 目标3：保护
    • 一个用户进程不能读取和修改其他用户进程的内存
    • 用户进程不能破坏内核使用的内存空间

解决方案：虚拟内存

  1. 基本内存抽象
    • 地址空间：进程的内存视图 -> 虚拟内存
    • 透明使用、高效访问、安全保护
  2. 虚拟内存 vs 虚拟CPU
    • 虚拟CPU
      • 进程不与CPU绑定，可以迁移到任一CPU
      • 进程执行时，自以为独占了CPU
      • 进程CPU状态与切换：通过上下文
    • 虚拟内存
      • 进程数据不与物理内存绑定，可以迁移到任意的内存/磁盘空间
      • 进程执行时，自以为独占了内存
      • 进程内存状态：通过swap到磁盘上进行保存

虚拟内存

  1. 独立的（进程）地址空间
    • 给每个进程提供一个很大的、静态的"虚拟"内存空间
  2. 虚实地址转换
    • 进程运行时，每次访存通过地址转换获得实际的物理内存地址
  3. 磁盘作为内存的延展（磁盘交换区）
    • 按需加载：只装载部分地址空间到物理内存

地址空间

  1. 独立的进程地址空间 [0,MAX-1]
    • 程序员能够看到的是虚地址
  2. 运行时装载部分地址空间
  3. 每次访存：虚地址->物理地址
    • CPU 和 进程 看到的是虚地址
    • 内存 和 I/O设备 看到的是物理地址
  4. 如果访问到未装载的地址空间
    • 通过OS将它加载进内存

虚存的好处

  1. 灵活
    • 进程在执行时才会被放进内存，另一部分在内存/磁盘中
  2. 简单
    • 进程的内存访问变得简单
  3. 高效
    • 20/80原则：20%的地址空间承担了80%的访问
    • 将20%地址空间放进物理内存
  4. 安全
    • 虚实地址转换时进行安全检查，防止非法访问

地址映射

目标

  1. 隐式：对每个内存访问，转换是隐式的，用户程序不感知
  2. 快速：有转换关系的时候，访存速度非常快
  3. 例外：没有转换关系时会触发一个例外
  4. 保护：能够隔离用户进程的错误

地址映射和粒度

  1. 需要某种"映射"机制
    • 把虚地址空间（大）的内容 放进 物理内存空间（小）
  2. 映射必须有合适的粒度
    • 粒度决定灵活性
    • 大粒度映射可能造成内存浪费
    • 细粒度映射则需要更多的映射信息
  3. 极端情况
    • 字节粒度映射：映射表过大
    • 进程粒度映射：内存浪费

基址 + 长度（Cray-1中采用的方法）

  1. 连续分配
    • 为每个进程分配地址连续的内存空间
    • 用一个二元组来限定其内存区域: <base,bound>
  2. 保护
    • 一个进程只能访问[base,base+bound]区间的内存
  3. 上下文切换
    • 保存/恢复 基址寄存器
  4. 好处
    • 简单：映射时将虚地址和基地址相加
    • 支持换出(swapping)：多进程并发执行
  5. 坏处
    • 外部碎片（进程间的碎片）
    • 难以支持进程增大
    • 难以共享内存

内存碎片：随着进程的换入与换出，内存会产生很多空洞（未使用的小区域）

分段

  1. 不连续分配
    • 把程序逻辑上划分为若干段：代码、全局变量、栈
    • 每个段分配连续内存，段间不必连续
    • 每个进程有一张段表
    • 每个段采用基址 + 长度
  2. 保护
    • 每个段有不同的权限（Read,Write,Exec)
  3. 上下文切换
    • 保存/恢复 段表和指向段表的内核指针
  4. 好处
    • 相比于基址 + 长度，资源使用更高效
    • 易共享
  5. 不足
    • 管理的复杂度增加
    • 仍然存在外部碎片（段间碎片）

虚实地址转换过程

Virtual Address = Seg# + Offset Seg# 通过 Segment Table 映射到 Physical Address

如果 offset > 段Size， 则触发 Memory Violation异常 如果访问地址所在的 Seg# 的 Valid 为0，则触发 Segment Fault异常

分页

  1. 分页机制
    • 使用固定大小的映射单元
    • 把虚存划分成固定大小的单元（称为页 Page）
    • 把物理内存划分成同样大小的单元（称为页框 Page Frame）
    • 按需加载（On-Demand Paging）
  2. 用页表来记录映射
    • 虚页 -> 物理页
  3. 每个表项都有若干个控制位
    • 按页进行保护（Read,Write,Exec)
  4. 上下文切换
    • 与分段类似，保存/恢复页表及其地址
  5. 好处
    • 分配简单
    • 易共享
  6. 坏处
    • 页表很大
    • 进程地址空间有很多空洞：对应的页表项没用

页表项

  1. 表达一个映射关系（Page Table Entry，PTE）
    • 虚页号 -> 物理页号
  2. 包含如下信息：
    • 物理页框号
    • 有效位：标志该页是否在内存中
    • 保护位：标志该页的访问权限(Read,Write,Exec)
    • 修改位：标志该页是否被修改过
    • 访问位：标志该页是否被访问过
    • 缓存位
  3. PTE的数量
    • 假设一页是 4K（12位页内偏移Offset）
    • 32位虚拟地址空间：2^32 = 4G = 4K * 1024
      • 一个PTE的大小为32位 = 4B，故总共为 4MB
      • 如果有10K个进程，那么可能内存连页表都放不下
    • 64位虚拟地址空间：2^64 = 16EB = 4K * 1024 * 1024 * 1024
      • 一个PTE的大小为64位 = 8B，故总共为 8TB
      • 内存连一个页表的大小都放不下

分段 + 分页

  1. 先将进程划分为若干段
  2. 每个段采用分页
  3. 段表记录它的页表地址
  4. 不足：仍然存在分段的不足

多级页表

  1. 虚地址除去 offset 之外的部分划分为多个段
    • 每段对应一级页表
    • 多个页表
  2. 好处：节省空间

示例：二级页表

  1. 虚地址：32位，前10位为一级页表索引，中间10位为二级页表索引，后12位为页内偏移
  2. 每个页表4KB，共有1024个页表项，下级页表每一项映射1页(4KB)，上级页表映射1024页(4MB)
  3. 对于大地址空间，大部分程序都只需要几个页表

反向页表

  1. 基本逻辑
    • 64位地址空间，4K页，共有252个页；256MB物理内存，总共有216个页框
    • 按物理页索引，记录每个物理页对应的进程ID及虚页
  2. 主要思想
    • 每个物理页对应一个PTE
    • 通过Hash查找进行地址转换（Hash(Vpage,pid) -> Ppage#）
  3. 好处
    • 页表大小与地址空间大小无关，只与物理内存大小有关
    • 对于大地址空间，页表较小
  4. 坏处
    • 查找困难（Hash冲突）
    • 管理哈希链需要大量开销

MMU 和 TLB

地址转换实现

  1. 地址类别
    • CPU发出的是虚地址
    • 内存和IO设备接收的是物理地址
  2. MMU（Memory Management Unit，内存管理单元）职责
    • 负责虚地址到物理地址转换的硬件单元，通常在片内实现
    • 虚存地址转换到物理地址（每条Load 和 Store指令都需要地址转换）
    • 内存保护，检查地址是否有效
    • 特殊指令操作对应寄存器，记录Base/Bound，或者页目录
  3. 操作系统职责
    • 内存管理：新进程分配空间，结束的进程回收空间
    • 进程切换时上下文管理（RISC-V satp寄存器等）
    • 异常处理：内存越界访问、无效地址等

加速地址转换

  1. 程序只知道虚地址
    • 每个程序或进程的地址空间是[0,max-1]
  2. 每个虚地址必须要进行转换
    • 可能需要逐级查找多级页表
    • 页表保存在内存中，一个内存访问可能变成多个内存访问
  3. 解决办法
    • 用速度更快的部件来缓存使用最频繁的那部分页表项

TLB（Translation Look-aside Buffer，地址转换旁路缓冲）

TLB是一种页表的缓冲机制

  1. 共有的（必须的）位
    • VP#（虚页号）：与虚地址进行匹配
    • PP#（物理页号）：转换后的实际地址
    • Valid位：标志此表项是否有效
    • 访问控制位：运行内核/用户访问，以及允许何种访问（Read,Write）
  2. 可选的（有用的）位
    • 进程标签（pid）
    • 访问标签位（R位）
    • 修改标志位（M位）
    • 缓存标志位

TLB具体流程（硬件和软件不同）

  1. CPU先把一个虚地址VA给MMU进行转换
  2. MMU先查TLB: VA = VP# || offset
    • 将该虚页号同时与TLB中所有的表项进行比较（硬件支持）
  3. TLB hit：TLB里找到含 VP# 的表项
    • 如果有效（TLB的Valid位=1），取表项中的物理页号
    • 如果无效（TLB的Valid位=0），则等同于TLB miss
  4. 如果TLB miss（不命中）：TLB中没有含有 VP# 的表项
    • MMU硬件在页表中进行查找，得到PTE / 进入内核异常处理程序，软件在页表中进行查找，得到PTE
    • 将找到的PTE加载进TLB
      • 如果没有空闲表项，则替换一个TLB表项
    • 获取TLB表项中的物理页号 / 重新执行TLB不命中的指令

硬件控制 vs 软件控制

  1. 硬件控制
    • 高效
    • 不灵活
  2. 软件控制
    • 简化 MMU 的逻辑，是的 CPU芯片上有更多面积可以用于缓存
    • 软件控制更加灵活
    • 可以使用反向页表进行映射，处理大的虚地址空间

TLB 设计问题

  1. 替换哪个TLB表项
    • 伪随机 或 LRU算法
  2. 上下文切换时需要做什么
    • 有进程标签：修改TLB寄存器和进程寄存器的内容
    • 无进程标签：将整个TLB的内容置于无效
  3. 修改一个页表项时需要做什么
    • 修改内存中的PTE
    • 将对应的TLB表项置于无效（刷新TLB）
  4. TLB的大小
    • 很小的TLB（64项），能够有很好的TLB命中率
    • 不能太大（不超过256项），CPU的面积有限