Part I:TLB命中示例
1、存储器层次结构
因此,现代计算机系统通常把各种不同存储容量、存取速度和价格的存储器按照一定的体系组成多层结构,以解决存储器容量、存取速度和价格之间的矛盾。
分层存储(Tiered Storage)的理论基础是:局部性原理,其中包括时间局部性与空间局部性 2 类:
上图为 MIT 6.004 Computation Structures 课程中非常经典的一张存储器层次结构图:从上到下,容量更大,访问速度更慢、价格更便宜。
在计算机系统中:内存/DRAM 被称为主存(Primary Storage),磁盘/Disk 被称为辅助存储器/次级存储器(Secondary Storage)。
2、物理内存与物理寻址
计算机系统的主存(Primary Storage)被组织成一个由 M 个连续的字节(bytes)大小的单元组成的数组。每字节都有一个唯一的物理地址(Physical Address,PA)。
CPU 访问内存的最自然的方式就是使用物理地址。我们把这种方式称为物理寻址(physical addressing)。
Part I:物理寻址的3个问题
在一个 32-bit 的操作系统中,CPU 能够提供 2^32(bytes)= 4GB 的程序地址空间,如果该操作系统只有 1GB DRAM 物理内存。如果采用物理寻址,当应用程序的访问地址空间(4GB)超过物理内存的实际地址空间(1GB DRAM)范围时,就会导致程序崩溃。
在一个 32-bit 的操作系统中,如果该操作系统同时拥有 4 GB 的 DRAM,首先运行程序 1(占用 1GB 连续 DRAM)与程序 2(占用 2GB 连续 DRAM),此时程序 3 无法正常运行(占用 2GB 连续 DRAM)。
此时程序 1 退出,剩余 2 GB RAM,程序 3 依然无法运行。因为剩余的 2 GB RAM内存空间不是连续的。
每个程序都可以访问 4GB 的物理内存地址空间,如果多个程序访问相同的物理地址,会导致数据污染或崩溃。
3、虚拟内存
怎么才能解决物理寻址的 3 个问题?
计算机领域有一句名言:“All problems in computer science can be solved by another level of indirection."(计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。)通过引入虚拟内存来解决物理寻址的带来的上述问题。
虚拟内存是物理内存和进程地址空间之间的中间层,它为进程隐藏了物理内存这一概念。虚拟内存提供了 3 个重要的能力:
Part I:虚拟寻址
CPU 通过生成一个虚拟地址(Virtual Address, VA)来访问主存,这个虚拟地址在被送到主存之前需要先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译(address translation)。
这一过程需要 CPU 硬件和操作系统的合作,CPU 芯片上叫做内存管理单元(memory Management Unit, MMU),利用操作系统管理的存放在主存中的查询表(Page Table)来动态的将虚拟地址翻译为物理地址。
Part II:虚拟内存使用主存作为缓存
虚拟内存被组织为一个由存放在磁盘上的 N 个连续的字节(Bytes)大小的单元组成的数组,每字节都有一个唯一的虚拟地址。磁盘上的数组的内容被缓存在主存中,根据需要在磁盘和主存之间传送数据。
通过查看 DRAM 时序,我们发现检索连续字节块的时间比访问单独一个字节的时间要短很多。对于磁盘来说,从一个扇区读取第一个字节的时间开销,要比读这个扇区内的连续字节要慢 100,000 倍。因此虚拟内存想要获取比较高的性能,磁盘(较低层级)上的数据被分割成块,这些块作为磁盘和主存(较高层级)之间的传输单元。
虚拟内存系统通过将将虚拟内存分割为称为虚拟页(Virtual Page, VP)的大小固定的块来处理这个问题。每个虚拟页的大小为 P=2^p 字节(虚拟页一般大小为 4kb ~ 2MB)。类似的,物理内存被分割成物理页(Physical Page, PP),大小为 P 字节(物理页也被称为页帧,page frame)。
任意时刻, 虚拟页面的集合分成 3 个不相交的子集:
上图中包含 8 个虚拟页的虚拟内存系统,VP0、VP3 未分配,VP1、VP4、VP6 分配并缓存在 DRAM 内存中,VP2、VP5、VP7 被分配了,但是没有缓存在 DRAM 内存中。
Part III:页表
每一个进程都有一份页表(Page Table),作为其上下文的一部分。页表由一系列页表条目(PTE,Page Table Entry)组成,每个页表条目都包含着虚拟页和物理页的映射关系。PTE 由一个有效位(valid bit,表明该虚拟页是否被缓存在 DRAM 中)和一个 n 位地址字段组成。
页表(page table)的数据结构存放在物理内存(DRAM)中,操作系统负责维护页表结构,每次 MMU(内存管理单元)中的地址翻译硬件将一个虚拟地址转换成物理地址时,都会读取页表。
MMU 通过页表来确定一个虚拟页是否缓存在 DRAM 中:
上图为包含 8个虚拟页,4 个物理页的系统的页表结构。
Part IV:页命中
页命中指的是当 MMU 需要根据虚拟地址输出物理地址时,这个地址所在的页已经被装载到物理内存中了(即对应的 PTE 的有效为 1)。
上图中,当 MMU 访问的虚拟地址对应到页表中 VP 2 时,地址翻译硬件发现该地址在页表当中有效位为 1,即被缓存在 DRAM 当中(称为页命中),则使用页表当中 PTE 所对应的物理内存地址,来访问数据。
Part V:缺页
上图中,当 MMU 访问的虚拟地址对应到页表中 VP 3 时,地址翻译硬件发现该地址在页表当中有效位为 0,即未被缓存在 DRAM 当中,称为缺页(Page Fault),触发一个缺页异常。
缺页异常的处理程序被启动,该程序会选择一个牺牲页,若是该牺牲页被标记为已经更改过,则内核会将其复制回磁盘,若是未更改过,调整牺牲页在页表中所对应的 PTE。接着,内核从磁盘(虚拟内存)当中将内容复制到牺牲页(物理内存)上,再次更新其PTE,随后返回。
当缺页异常处理程序返回时,原进程会重新启动导致缺页异常的指令,该指令会将导致缺页的虚拟地址重发送到地址翻译硬件,这时就会进行页命中的相关流程了。
上图中,触发缺页异常后,缺页异常处理程序选择 VP 4 作为牺牲页,并从磁盘上用 VP 3 的副本取代它。
在缺页异常处理程序重新启动导致缺页的指令之后,该指令将从内存中正常地读取字,而不会再产生缺页异常。
Part VI:分配新页
如上图,内核在磁盘上分配 VP 5,并将 PTE 5 指向这个新的位置。
Part VII:虚拟内存作为内存管理的工具
操作系统为每个进程提供了一个独立的页表,也就是每个进程独占一个独立的虚拟地址空间。
这样做的好处:
Part VIII:虚拟内存作为内存保护的工具
虚拟内存通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面的访问权限,通过虚拟内存可以提供页面级的内存保护。
4、地址翻译
Part I:地址翻译术语
符号 | 描述 |
---|---|
VPO(Virtual Page Offset) | 虚拟页面偏移量(字节) |
VPN(Virtual Page Number) | 虚拟页号 |
TLBI(TLB Index) | TLB 索引 |
TLBT(TLB Tag) | TLB 标记 |
3. 物理地址(PA)的组成部分
符号 | 描述 |
---|---|
PPO(Physical Page Offset) | 物理页面偏移量(字节) |
PPN(Physical Page Number) | 物理页号 |
CO(Byte offset within cache line) | 缓存行内的字节偏移量 |
CI(Cache index) | 高速缓存索引 |
CT(Cache tag) | 高速缓存标记 |
Part II:使用页表的地址翻译
在 CPU 中地址翻译由一个叫做 MMU(Memory Management Unit,内存管理单元)的硬件完成。MMU 接收一个虚拟地址,并且输出一个物理地址。如果这个虚拟地址在物理内存中存在,那么就叫做页命中。如果这个虚拟地址在物理内存中不存在,那么 MMU 将产生一个缺页错误。
n 位的虚拟地址包括两个部分:一个 p 位的虚拟页面偏移(Virtual Page Offset,VPO),和一个 n-p 位的虚拟页号(Virtual Page Number, VPN),MMU 利用 VPN 来选择适当的 PTE。
因为物理和虚拟页面都是 P 字节的,所以物理页面偏移(Physical Page Offset,PPO)和 虚拟页面偏移(Virtual Page Offset,VPO)是相同的,因此将 PTE 中的物理页号(Physical Page Number, PPN)与 VPO 串联起来,就得到了相应的物理地址。
2.缺页时的地址翻译
Part III:地址翻译加速
1.将 Cache 与虚拟内存整合在一起
从页命中的流程图中可以看出,CPU 每次需要请求一个虚拟地址,MMU 就需要从内存/Cache 中获取 PTE ,然后再根据 PTE 的内容去从物理内存中加载数据。如果在 PTE 在 Cache 中未命中,就需要从内存中获取 PTE。这部分由于 Cache Miss 造成的开销是巨大的。
如果我们将 PTE 存储到一个专门的 L1 Cache 中那么将会减少这部分开销,这个专门存放 PTE 的 L1 Cache 就是 TLB(Translation Lookaside Buffer,翻译后备缓冲器)。
2.利用 TLB 加速地址翻译
许多 MMU 包含一个名叫 TLB(Translation Lookaside Buffer,翻译后备缓冲器) 的 Cache。
TLB 将虚拟内存的 VPN 视为由组索引和行匹配组成,索引部分(TLBI)用来定位 TLB 中的缓存数据项,标记部分(TLBT)用来校验存储的数据项是否为指定的 VPN 对应的数据。
如果 TLB 命中了,那么所有的地址翻译步骤都是在 MMU 中执行的,所以非常快。
1. CPU 生成 1 个虚拟地址; 2. MMU 向 TLB 请求 PTE; 3. TLB 返回 PTE 到 MMU; 4. MMU 将这个虚拟地址翻译成一个物理地址,并且把它发送到高速缓存/主存; 5. 高速缓存将所请求的数据字返回给 CPU;
b.TLB未命中
理解 TLB 需要注意的是,因为不同进程的页表内容是不同的,因此在进程上下文切换时,会重置 TLB。
Part IV:多级页表
PTE 的数量由虚拟地址空间的大小和页大小决定。也就是:X=N/P。那如果我们有一个 32 位的物理地址空间、4KB 的页面和 一个 4 字节的 PTE。
即使程序只使用了一小部分虚拟地址空间,也总是需要一个 4MB( 4 X 232 / 212 )的页表常驻主存。对于 64 位的系统来说,情况将变得更加复杂。因此使用层次结构的页表来压缩页表。
1. 二级页表
上图展示了一个两级页表的层次结构。二级页表中的每个 PTE 项都负责一个 4KB 页面,而一级页表中的每个 PTE 负责 1024 个二级页表项。
如果页表层级太多,则增加缓存未命中的概率,一般层级是4。
2. K级页表
上图展示的是一个 K 级层次页表的结构图,起始就是将 VPN 部分划分为多个段,每个段都代表某一级页表。而每一级中的 PTE 的 Base addr 为下一级提供入口地址,最后一级的 Base addr 则表示最终物理地址的 PPN。
5、虚拟内存系统示例
本节里,我们通过一个具体的端到端的地址翻译示例来学习虚拟内存系统。
我们假设:
上图展示了虚拟地址和物理地址的格式。因为每个页面是 26= 64 字节,所以虚拟地址和物理地址的低 6 位分别作为 VPO 和 PPO。虚拟地址的高 8 位作为 VPN,物理地址的高 6 位作为 PPN。
TLB 是利用 VPN 的位进行虚拟寻址的。因为 TLB 有 4 个组,所以 VPN 的低 2 位就作为组索引(TLBI)。VPN 中剩下的高 6 位作为标记(TLBT),用来区别可能映射到同一个 TLB 组的不同的 VPN。
这个页表是一个单级设计,一共有28= 256 个页表条目(PTE)。然而,我们只对这些条目中的开头 16 个感兴趣。为了方便,我们用索引它的 VPN 来标识每个 PTE;但是要记住这些 VPN 并不是页表的一部分,也不储存在内存中。
另外,注意每个无效 PTE 的 PPN 都用一个“-”来表示,以加强一个概念:无论刚好这里存储的是什么位值,都是没有任何意义的。
直接映射的 L1 Cache 是通过物理地址中的字段来寻址的。因为每个块都是 4 字节,所以物理地址的低 2 位作为块偏移(CO)。因为有 16 组,所以接下来的 4 位就用来表示组索引(CI),剩下的 6 位作为标记(CT)。
过程如上图所示,给定了这种初始化设定,让我们来看看当 CPU 执行一条读地址 0x0369 处字节的加载指令时会发生什么(假定 CPU 读取 1 字节的字,而不是 4 字节的字)。
开始时,MMU 从虚拟地址中抽取出 VPN(0x0D),并且检查 TLB,看它是否因为前面的某个内存引用缓存了 PTE 0x0D 的一个副本。TLB 从 VPN 中抽取出 TLBI(TLB 索引 0x01)和 TLBT(TLB 标记 0x3),Set 0x1 的 Tag 03 条目中有效匹配,所以命中,然后将缓存的 PPN(0x2D)返回给 MMU。
现在,MMU 有了形成物理地址所需要的所有东西。它通过将来自 PTE 的 PPN(0x2D)和来自虚拟地址的 VPO(0x29)连接起来,这就形成了物理地址(0xB69)。
接下来,MMU 发送物理地址给 L1 d-cache 缓存,L1 d-cache 从物理地址中抽取出缓存偏移 CO(0x1)、缓存组索引 CI(0xA)以及缓存标记 CT(0x2D)。
因为 L1 d-cache 的组 0xA 与缓存组索引 CI(0xA)匹配,Set 0xA 的 Tag 2D 与 缓存标记 CT(0x2D)相匹配,所以缓存检测到一个命中,读出在偏移量 CO(0x1)处的数据字节(0x15),并将它返回给 MMU,随后 MMU 将它传递回 CPU。
(正文完)
end
Reference: