• 威斯康辛州大学操作系统书籍《Operating Systems: Three Easy Pieces》读书笔记系列之 Virtualization(虚拟化)。本篇为虚拟化技术的基础篇系列第三篇(Memory Virtualization),内存虚拟化。
  • 内存虚拟化又将分为两篇,本篇为第二篇内存虚拟化之分页

Chapter Index

  • TODO

Paging: Introduction

  • 操作系统解决空间管理的问题大致分为两种:
    • 是将空间分割成不同长度的分片,就像虚拟内存管理中的分段。但是将空间切成不同长度的分片以后,空间本身会碎片化(fragmented),随着时间推移,分配内存会变得比较困难。
    • 将空间分割成固定长度的分片。在虚拟内存中,我们称这种思想为分页。分页不是将一个进程的地址空间分割成几个不同长度的逻辑段(即代码、堆、段),而是分割成固定大小的单元,每个单元称为一页。相应地,我们把物理内存看成是定长槽块的阵列,叫作页帧(page frame)。每个这样的页帧包含一个虚拟内存页。
  • CRUX: 如何通过页来实现虚拟内存,从而避免分段的问题?

A Simple Example And Overview

  • 如图展示了一个只有 64 字节的小地址空间,有 4 个 16 字节的页(虚拟页 0、1、2、3)。真实的地址空间肯定大得多,通常 32 位有 4GB 的地址空间,甚至有 64 位。
    20200913150942
  • 物理内存如图所示,也由一组固定大小的槽块组成。在这个例子中,有 8 个页
    帧(由 128 字节物理内存构成,也是极小的)。从图中可以看出,虚拟地址空间的页放在物理内存的不同位置。图中还显示,操作系统自己用了一些物理内存。
    20200913151100
  • 可以看到,与我们以前的方法相比,分页有许多优点。可能最大的改进就是灵活性:通过完善的分页方法,操作系统能够高效地提供地址空间的抽象,不管进程如何使用地址空间。例如,我们不会假定堆和栈的增长方向,以及它们如何使用。
  • 另一个优点是分页提供的空闲空间管理的简单性。例如,如果操作系统希望将 64 字节的小地址空间放到 8 页的物理地址空间中,它只要找到 4 个空闲页。也许操作系统保存了一个所有空闲页的空闲列表(free list),只需要从这个列表中拿出 4 个空闲页。即上图所示的物理内存的页帧 2,3,5,7 对应了地址空间中的逻辑页。
  • 为了记录地址空间的每个虚拟页放在物理内存中的位置,操作系统通常为每个进程保存一个数据结构,称为页表(page table)。页表的主要作用是为地址空间的每个虚拟页面保存地址转换(address translation),从而让我们知道每个页在物理内存中的位置。即 VP 到 PF 的映射,上述例中即为 VP0 -> PF3,VP1 -> PF7,VP2 -> PF5,VP3 -> PF2
  • 这个页表是一个每进程的数据结构(我们讨论的大多数页表结构都是每进程的数据结构,我们将接触的一个例外是倒排页表,inverted page table)。如果在上面的示例中运行另一个进程,操作系统将不得不为它管理不同的页表,因为它的虚拟页显然映射到不同的物理页面(除了共享之外)。
  • 地址转换示例,设想拥有这个小地址空间(64 字节)的进程正在访问内存:
movl <virtual address>, %eax 
  • 为了转换(translate)该过程生成的虚拟地址,我们必须首先将它分成两个组件:虚拟页面号(virtual page number,VPN)和页内的偏移量(offset)。对于这个例子,因为进程的虚拟地址空间是 64 字节,我们的虚拟地址总共需要 6 位(2^6 = 64)。因此,虚拟地址可以表示如下,因为需要选择四个页,故使用前两位表示属于哪个页,剩余的作为偏移量。
    20200913152021
  • 假设我们访问的虚拟地址为 21,对应的二进制为 010101,即为虚拟页 1 的偏移量为 5 的地址。此时检索页表,将虚拟页转换成物理页,偏移量保持不变,即可获取到最终的物理地址 1110101(10进制为 117)
    20200913152150

Where Are Page Tables Stored?

  • 页表可以变得非常大,比我们之前讨论过的小段表或基址/界限对要大得多。例如,想象一个典型的 32 位地址空间,带有 4KB 的页。这个虚拟地址分成 20 位的 VPN 和 12 位的偏移量。一个 20 位的 VPN 意味着,操作系统必须为每个进程管理 220个地址转换(大约一百万)。假设每个页表格条目(PTE)需要 4 个字节,来保存物理地址转换和任何其他有用的东西,每个页表就需要巨大的 4MB 内存!这非常大。现在想象一下有 100 个进程在运行:这意味着操作系统会需要 400MB 内存,只是为了所有这些地址转换!
  • 由于页表如此之大,我们没有在 MMU 中利用任何特殊的片上硬件,来存储当前正在运行的进程的页表,而是将每个进程的页表存储在内存中。现在让我们假设页表存在于操作系统管理的物理内存中,稍后我们会看到,很多操作系统内存本身都可以虚拟化,因此页表可以存储在操作系统的虚拟内存中(甚至可以交换到磁盘上)

What’s Actually In The Page Table?

  • 页表就是一种数据结构,用于将虚拟地址(或者实际上,是虚拟页号)映射到物理地址(物理帧号)。因此,任何数据结构都可以采用。最简单的形式称为线性页表(linear page table),就是一个数组。操作系统通过虚拟页号(VPN)检索该数组,并在该索引处查找页表项(PTE),以便找到期望的物理帧号(PFN)。现在,我们将假设采用这个简单的线性结构。
  • 至于每个 PTE 的内容,我们在其中有许多不同的位,值得有所了解。有效位(valid bit)通常用于指示特定地址转换是否有效。例如,当一个程序开始运行时,它的代码和堆在其地址空间的一端,栈在另一端。所有未使用的中间空间都将被标记为无效(invalid),如果进程尝试访问这种内存,就会陷入操作系统,可能会导致该进程终止。因此,有效位对于支持稀疏地址空间至关重要。通过简单地将地址空间中所有未使用的页面标记为无效,我们不再需要为这些页面分配物理帧,从而节省大量内存。
  • 还可能有保护位(protection bit),表明页是否可以读取、写入或执行。同样,以这些位不允许的方式访问页,会陷入操作系统。存在位(present bit)表示该页是在物理存储器还是在磁盘上(即它已被换出,swapped out)。脏位(dirty bit)也很常见,表明页面被带入内存后是否被修改过。参考位(reference bit,也被称为访问位,accessed bit)有时用于追踪页是否被访问,也用于确定哪些页很受欢迎,因此应该保留在内存中。
  • 图 18.5 显示了来自 x86 架构的示例页表项。它包含一个存在位(P),确定是否允许写入该页面的读/写位(R/W) 确定用户模式进程是否可以访问该页面的用户/超级用户位(U/S),有几位(PWT、PCD、PAT 和 G)确定硬件缓存如何为这些页面工作,一个访问位(A)和一个脏位(D),最后是页帧号(PFN)本身。
    20200913161620

Paging: Also Too Slow

  • 还是以上述例子为例,movl 21, %eax 我们只看对地址 21 的显式引用,而不关心指令获取。在这个例子中,我们假定硬件为我们执行地址转换。要获取所需数据,系统必须首先将虚拟地址(21)转换为正确的物理地址(117)。因此,在从地址 117 获取数据之前,系统必须首先从进程的页表中提取适当的页表项,执行转换,然后从物理内存中加载数据。硬件必须知道当前正在运行的进程的页表的位置。现在让我们假设一个页表基址寄存器(page-table base register)包含页表的起始位置的物理地址。为了找到想要的 PTE 的位置,硬件将执行以下功能:
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE)) 
  • 在我们的例子中,VPN MASK 将被设置为 0x30(十六进制 30,或二进制 110000),它从完整的虚拟地址中挑选出 VPN 位;SHIFT 设置为 4(偏移量的位数),这样我们就可以将VPN 位向右移动以形成正确的整数虚拟页码。例如,使用虚拟地址 21(010101),掩码将此值转换为 010000,移位将它变成 01,或虚拟页 1,正是我们期望的值。然后,我们使用该值作为页表基址寄存器指向的 PTE 数组的索引。
  • 一旦知道了这个物理地址,硬件就可以从内存中获取 PTE,提取 PFN,并将它与来自虚拟地址的偏移量连接起来,形成所需的物理地址。具体来说,你可以想象 PFN 被 SHIFT 左移,然后与偏移量进行逻辑或运算,以形成最终地址,如下所示。
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PFN << SHIFT) | offset
  • 最后,硬件可以从内存中获取所需的数据,并将其放入寄存器eax中。程序现在已经成功地从内存中加载了一个值。整个过程如下所示
1 // Extract the VPN from the virtual address
2 VPN = (VirtualAddress & VPN_MASK) >> SHIFT
3
4 // Form the address of the page-table entry (PTE)
5 PTEAddr = PTBR + (VPN * sizeof(PTE))
6
7 // Fetch the PTE 
8 PTE = AccessMemory(PTEAddr)
9
10 // Check if process can access the page
11 if (PTE.Valid == False)
12  RaiseException(SEGMENTATION_FAULT)
13 else if (CanAccess(PTE.ProtectBits) == False)
14  RaiseException(PROTECTION_FAULT)
15 else
16  // Access is OK: form physical address and fetch it
17  offset = VirtualAddress & OFFSET_MASK
18  PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
19  Register = AccessMemory(PhysAddr) 
  • 对于每个内存引用(无论是取指令还是显式加载或存储),分页都需要我们执行一个额外的内存引用,以便首先从页表中获取地址转换。工作量很大!额外的内存引用开销很大,在这种情况下,可能会使进程减慢两倍或更多。故存在两个问题:系统运行速度过慢,并占用太多内存

A Memory Trace

  • 简单内存访问示例如下:
int array[1000];
...
for (i = 0; i < 1000; i++)
 array[i] = 0; 
  • 对应的汇编代码为:
    • 第一条指令将零值(显示为$0x0)移动到数组位置的虚拟内存地址,这个地址是通过取%edi 的内容并将其加上%eax 乘以 4 来计算的。因此,%edi 保存数组的基址,而%eax 保存数组索引(i)。我们乘以 4,因为数组是一个整型数组,每个元素的大小为 4 个字节。
    • 第二条指令增加保存在 %eax 中的数组索引
    • 第三条指令将该寄存器的内容与十六进制值 0x03e8 或十进制数 1000 进行比较。如果比较结果显示两个值不相等(这就是 jne 指令测试),第四条指令跳回到循环的顶部。
0x1024 movl $0x0,(%edi,%eax,4)
0x1028 incl %eax
0x102c cmpl $0x03e8,%eax
0x1030 jne 0x1024 
  • 针对如上例子,我们假设一个大小为 64KB 的虚拟地址空间(不切实际地小)。我们还假定页面大小为 1KB。现在需要知道页表的内容,以及它在物理内存中的位置。假设有一个线性(基于数组)的页表,它位于物理地址 1KB(1024)。
  • 我们只需要关心为这个例子映射的几个虚拟页面。首先,存在代码所在的虚拟页面。由于页大小为 1KB,虚拟地址 1024 驻留在虚拟地址空间的第二页(VPN = 1,因为 VPN = 0 是第一页)。假设这个虚拟页映射到物理帧 4(VPN 1→PFN 4)。接下来是数组本身。它的大小是 4000 字节(1000 整数),我们假设它驻留在虚拟地址40000 到 44000(不包括最后一个字节)。它的虚拟页的十进制范围是 VPN = 39……VPN = 42。因此,我们需要这些页的映射。针对这个例子,让我们假设以下虚拟到物理的映射:
(VPN 39 → PFN 7), (VPN 40 → PFN 8), (VPN 41 → PFN 9), (VPN 42 → PFN 10) 
  • 下图展示了前 5 次循环迭代的整个过程。最下面的图显示了 y 轴上的指令内存引用(黑色虚拟地址和右边的实际物理地址)。中间的图以深灰色展示了数组访问(同样,虚拟在左侧,物理在右侧);最后,最上面的图展示了浅灰色的页表内存访问(只有物理的,因为本例中的页表位于物理内存中)。整个追踪的 x 轴显示循环的前 5 个迭代中内存访问。每个循环有 10 次内存访问,其中包括 4 次取指令,一次显式更新内存,以及 5 次页表访问,为这 4 次获取和一次显式更新进行地址转换。
    20200913172106

Summary

  • 我们已经引入了分页(paging)的概念,作为虚拟内存挑战的解决方案。与以前的方法(如分段)相比,分页有许多优点。首先,它不会导致外部碎片,因为分页(按设计)将内存划分为固定大小的单元。其次,它非常灵活,支持稀疏虚拟地址空间。
  • 然而,实现分页支持而不小心考虑,会导致较慢的机器(有许多额外的内存访问来访问页表)和内存浪费(内存被页表塞满而不是有用的应用程序数据)。