关于虚拟内存的页式实现

一、背景介绍

1.1 虚存出现之前

• 在运行程序或并行运行多个进程时，如果主存（注意讨论对象，不是Cache哦）的容量不足以支撑开销，在虚存出现之前，存在一种为了解决该问题的Overlay技术：编写程序时将其分为若干程序段（Overlay Set），用局部性原理将特定程序段加载到内存

• 这种解决方案的缺点很明显（所以我们需要虚拟内存）：
  • 使得程序员编写程序的过程十分枯燥繁琐且困难
  • 难以界定划分各个可以独立运行的程序段

1.2 虚存是什么

• 虚拟内存（Virtual Memory）是操作系统从外存硬盘中划分出来的一部分存储空间，该部分空间被操作系统逻辑上认为是主存的，可以被当作主存使用

• 硬盘中的存储空间被操作系统划归给了主存后（其大小由OS分配，页式实现中以页为基本单位）
  • Cache就可以通过（由虚拟地址映射转化而来的）物理地址，以各种映射策略（以访问主存的方式）访问到虚拟内存，就好像虚存真的就是主存的一部分一样
  • 这解决了主存空间（用于存放运行中的程序）不足的问题，并且无需程序员将程序分块
• 注意区分以下几个概念
  • 物理存储：实际存在的硬件存储结构，这是固定而无法改变的
  • 物理地址：指向实际的存储位置的地址，Cache只能处理物理地址
  • 逻辑/虚拟内存：操作系统（软件）许可的内存（让程序相信这块空间是内存并使用），而不是一个实际存在的硬件内存结构（其实际上是外存中的空间）
  • 逻辑/虚拟地址：需要被（MMU）转化为物理地址才能被Cache读懂
• 其中MMU（Memory Management Unit）是一个硬件结构，其用于通过操作系统管理的Lookup Table（Page Table）将虚拟地址转化为物理地址

1.3 虚存的好处

• 让程序编写从复杂的Overlay中解放出来
• 虚存将主存看成是磁盘地址空间的Cache，主存中保存热的数据，根据需要在磁盘和主存之间传送数据，以高效使用内存

二、页式实现

虚存有三种实现方式：Paging（页式）、Segmentation（段式）、Segmentation With Paging，此处我们只介绍页式实现

2.1 页的相关概念

• 下面两者采用全相联映射（Association Mapping），将虚存地址空间映射到主存地址空间，类比从主存映射到Cache
  • Page：一块连续的若干Word（一般长2K~16K），是主存和磁盘间相互转移的基本单位（此处的Page就好比主存和Cache间的Block一样）
  • Page Frame：主存中的一块区域，刚好放的下虚存的一个Page（类比Cache中的Line）

2.2 地址映射与页表

• 虚拟地址和物理地址都是一串若干位的二进制数，都有两部分组成
  • 虚拟地址（虚拟页的地址）
    • 高位（左侧）：虚拟页号（VPN, Virtual Page Number）
    • 低位（右侧）：偏移量（VPO, Offset），用于定位每个Page中的特定字节或Word
  • 物理地址（物理页的地址）
    • 高位：物理页号（PPN）
    • 低位：偏移量（PPO）
• 页表（Page Table）内存储着一堆页表项（PTE, Page Table Entry），每个页表项用于将虚拟地址映射到物理地址
  • VPN被用作页表中元素的索引，即可通过VPN从页表中找到对应的PTE
  • 页表被存放在主存中，我们可以通过页表基地址寄存器（PTBR, Page Table Base Register）来定位主存中的页表
• 页表项包含以下部分
  • Page Frame Number：传入的虚拟地址对应的物理地址的PPN，或指向磁盘对应位置的指针
  • Valid/Precense bit：标识主存中的这块Page的位置，是否被实际装载了一个Page
  • Modify bit：类比从主存到Cache中的写策略有透写和回写两种，只有回写使用了Dirty位，此处的Modify位即为Dirty位，因为此处使用的是回写（为何不用透写？因为无权限写穿）
  • Use/Reference bit：标识这一页是否最近被使用过
  • Access Control bit：控制位，控制如读、写、执行指令等操作
• 下图即MMU做的工作，通过页表将虚拟地址转为物理地址

• 页命中（Page Hit）：虚拟地址指向的那个Word存在于（被虚存扩容了的）主存中
• 缺页（Page Fault）：虚拟地址指向的那个Word不在主存中（类比Miss）

2.3 地址转换的例题

2.4 MMU内的TLB

• 将页表存放在主存中存在弊端，即我们需要先从主存中页表拿到物理地址，才能继而通过物理地址再次传入主存而拿到数据
• 地址变换高速缓存（TLB, Translation Look-aside Buffer）是MMU中的一个小型Cache，其中存放了页表的一部分

• TLB既然是某种Cache，那么我们类比CPU中的Cache和主存间的交互，TLB与主存中的页表也是同样的工作原理，也存在Hit和Miss
  • TLB Hit：命中，可以无需查询页表本体而直接通过TLB获取物理地址
  • TLB Miss：未命中，仍需进入主存查询页表本体，由于TLB很小，所以其Miss的频率会比Page Fault的频率高很多

2.5 页式实现的优缺

• 页式实现的缺点：
  • 内部碎片（Internal Fragmentation）问题：最后一页一般是存不满的，导致空间浪费
• 页的大小选取：
  • 大体积的优点：Page的Size越大，页表就越小，且实际应用中传输大页的效率比小页更高
  • 大体积的缺点：导致更多的空间浪费（内部碎片更大）