课程主页：https://courses.cs.washington.edu/courses/cse351/16sp/

课程资料：

实验部分：https://github.com/vuquangtrong/HW-SW_Interface_Course

实验说明：https://courses.cs.washington.edu/courses/cse351/13sp/lab-0.html

课件：http://academictorrents.com/details/b63a566df824b39740eb9754e4fe4c0140306f4b

课程视频：https://www.bilibili.com/video/BV1Zt411s7Gg?from=search&seid=8781593976070799647

这次回顾第九部分，这部分介绍了虚拟内存。

第9节：虚拟内存

概述和动机

进程
  • 定义：进程是正在运行的程序的一个实例。
    • 计算机科学中最重要的思想之一
    • 与“程序”或“处理器”不同
  • 进程为每个程序提供了两个关键抽象：
    • 逻辑控制流
      • 每个进程似乎都独占了CPU
    • 私有虚拟地址空间
      • 每个进程似乎都独占了主内存
  • 这些幻觉是如何维持的？
    • 交错处理执行进程（多任务处理）——上一节
    • 由虚拟内存系统管理的地址空间——本节！
虚拟内存
  • 程序引用虚拟内存地址
    • movl (%ecx),%eax
    • 从概念上讲，内存只是一个非常大的字节数组
    • 每个字节都有自己的地址系统
    • 为特定进程提供专用地址空间
  • 分配：编译器和运行时系统
    • 不同的程序对象应该存储的位置
    • 在单个虚拟地址空间内的所有分配
  • 虚拟内存解决了哪些问题？

问题一：一切都如何适应？

问题二：内存管理

问题三：如何保护

问题四：如何共享

间接

将如何解决如下问题？
  • 将巨大的内存装入微小的物理内存中
  • 多进程内存空间管理
  • 保护处理过程不会干扰到对方的内存
  • 允许进程共享内存的公共部分
间接

  • 间接引用：用名称、引用或容器代替值本身来引用某物的能力。一个名字和事物之间的灵活映射允许改变事物，而不需要通知持有者名字。

  • 无间接

  • 有间接

  • 示例： 域名服务（DNS）名称->IP地址、电话系统（例如，移动电话号码可移植性）、蜗牛邮件（例如，邮件转发）、911 （路由到本地办公室）、DHCP等。

解决方案：分层间接

  • 每个进程都有自己的私有虚拟地址空间
  • 解决之前的问题
地址空间

  • 虚拟地址空间：$N=2^n$个虚拟地址集合

  • 物理地址空间：$M=2^m$个物理地址集合

  • 内存中的每个字节

    • 一个物理地址；零个、一个或多个虚拟地址
映射

虚拟地址可以映射到物理内存或磁盘。

使用物理地址的系统

  • 用于简单的系统，如汽车、电梯和数字相框等设备中的嵌入式微控制器
使用虚拟地址的系统

  • 用于所有现代台式机、笔记本电脑、服务器
  • 计算机科学的伟大思想之一

VM作为缓存工具

VM和内存层次结构
  • 把虚拟内存看成存储在磁盘上的$N = 2^n$个连续字节的数组
  • 然后使用物理主内存（Physical Main Memory,DRAM）作为虚拟内存数组的高速缓存
    • 缓存块称为页（大小为$P = 2^p$字节）

DRAM高速缓存组织
  • DRAM高速缓存组织是由巨大的错过惩罚驱动的
    • DRAM比SRAM慢约10倍
    • 磁盘比DRAM慢约10,000倍
      • （这是指第一个字节；下一个字节更快）
  • 结果
    • 大页（块）大小：一般4-8KB，有时4MB
    • 全关联
      • 任何VP都可以放在任何PP中
      • 需要“大”映射函数——不同于CPU高速缓存
    • 高度复杂、昂贵的替换算法
      • 过于复杂、开放，无法在硬件上实现
    • write-back而不是write-through
索引到“DRAM高速缓存”

如何执行$VA\to PA$的翻译？

地址翻译：页表
  • 页表PT (page table)是将虚拟页映射到物理页的PTE (page table)数组。

使用PT进行地址翻译

在大多数情况下，硬件（MMU）可以自行执行这种转换，而无需软件协助。

页命中(Page Hit)
  • 页命中：对物理内存中的虚拟内存字节的引用

页错误
  • 页错误：对不在物理内存中的VM字节的引用

错误例子：页错误
int a[1000];
main ()
{
    a[500] = 13;
}

  • 用户写入内存位置

  • 用户内存的那部分（页）当前在磁盘上

    80483b7:	c7 05 10 9d 04 08 0d 	movl   $0xd,0x8049d10

  • 页面处理程序必须将页面加载到物理内存中

  • 返回错误指令：mov再次执行！

  • 第二次尝试成功

处理页错误
  • 页面缺失导致页面错误（异常）
  • 页面错误处理程序选择要驱逐的受害者（此处为VP4）
  • 指令重新启动：页面命中！

为什么有效？局部性
  • 虚拟内存由于局部性而工作良好
    • L1/L2/L3缓存工作的原因相同
  • 程序在任意时刻主动访问的虚拟页面集合称为工作集。
    • 具有较好时间局部性的程序将具有较小的工作集
  • if (工作集大小<主内存大小)：
    • 强制miss后，单进程表现良好
  • 如果(SUM(工作集大小)>主内存大小)：
    • Thrashing：连续交换（复制）页面的性能崩溃

内存管理/保护和地址转换

VM用于多进程管理
  • 关键抽象：每个进程都有自己的虚拟地址空间
    • 它可以把内存看成简单的线性数组
  • 有了虚拟内存，这个简单的线性虚拟地址空间不必在物理内存中连续
    • 进程是否需要将数据存储在另一个VP中？只要把它映射到任何PP!

VM用于保存和共享
  • VP到PP的映射为保护内存和共享内存提供了一种简单的机制
    • 共享：只需将单独的地址空间中的虚拟页映射到同一个物理页（这里： PP 6）
    • 保护：进程无法访问它没有映射的物理页（此处：进程2不能访问PP2）

单进程内存保护
  • 对PTE拓展权限位
  • MMU在每次访问内存时检查这些权限位
    • 如果违反，则引发异常，操作系统发送SIGSEGV信号进行处理

地址翻译：页命中

  • 1)处理器向MMU（内存管理单元）发送虚拟地址
  • 2-3)MMU从缓存/内存中的页表获取PTE
  • 4)MMU将物理地址发送到cache/memory
  • 5)高速缓存/内存向处理器发送数据字
地址翻译：页面错误

  • 1)处理器向MMU发送虚拟地址
  • 2-3)MMU从缓存/内存中的页表获取PTE
  • 4)有效位为0，MMU触发页面错误异常
  • 5)处理程序识别受害者（如果dirty，则将其分页到磁盘）
  • 6)新页面中的Handler页面和内存中更新PTE
  • 7)处理程序返回原进程，重新启动故障指令
翻译听起来很慢！
  • MMU访问内存两次：第一次是首先获取PTE进行转换，然后再次获取来自CPU的实际内存请求。
    • PTE可以像任何其他存储字一样缓存在L1中
      • 但是它们可能会被其他数据引用所淘汰
      • L1高速缓存中的命中仍然需要1-3个周期
  • 我们能做什么来加快速度呢？
使用TLB加速翻译
  • 解决办法：添加另一个缓存！
  • Translation Lookaside Buffer（TLB）：
    • MMU中的小硬件缓存
    • 将虚拟页号映射到物理页号
    • 包含用于少量页的完整页表项
      • 现代英特尔处理器： TLB中的128或256个条目
TLB命中

TLB命中消除内存访问。

TLB缺失

TLB缺失会导致额外的内存访问(PTE)。幸运的是，TLB的缺失很少。

虚拟内存示例

简单内存系统例子
  • 寻址
    • 14比特虚拟地址
    • 12比特物理地址
    • 页面大小= 64字节

简单内存系统页表

仅显示前16个项（256个项中的16个）

简单内存系统TLB
  • 16项
  • 4-way关联

简单内存系统高速缓存
  • 16行，4字节块大小
  • 物理地址
  • 直接映射

缓存/表的当前状态

地址转换示例

虚拟地址：0x03D4

  • VPN：直接读取
  • TLBI：直接读取
  • TLBT：直接读取
  • TLB Hit：TLB表中存在Set为3，Tag为3的项，PPN为0D
  • PPN：由上一项可得
  • Page Fault：PT中存在VPN=0F，PPN=0D，Valid=1的项

物理地址

  • CO：直接读取
  • CI：直接读取
  • CT：直接读取
  • Hit：CI为Cache中Idx，CT为Cache中Tag，显然Cache中存在对应项
  • Byte：从Cache中读取
总结
  • 程序员视角的虚拟内存
    • 每个进程都有自己的私有线性地址空间
    • 不会被其他进程损坏
  • 系统视角的虚拟内存
    • 通过缓存虚拟内存页，有效使用内存
      • 仅因局部性才高效
    • 简化内存管理和共享
    • 通过提供方便的插入点来检查权限，简化了保护

内存系统总结

  • L1/L2内存高速缓存
    • 纯加速技术
    • 应用程序人员和（大部分）操作系统不可见的行为
    • 硬件完全实现
  • 虚拟内存
    • 支持多种操作系统相关功能
      • 进程创建、任务切换、保护
    • 软件
      • 在进程间分配/共享物理内存
      • 维护跟踪内存类型、来源、共享的高级表
      • 处理异常，填写硬件定义的映射表
    • 硬件配置
      • 通过映射表转换虚拟地址，强制执行权限
      • 通过翻译缓存（TLB）加速映射