《操作系统导论》阅读笔记(十一)分页机制

/ 0评 / 1

阅读笔记主要来自原书第 18 章。该章对分页机制进行了详细的介绍。

0、前言

操作系统有两种方法,来解决大多数空间管理问题。第一种是将空间分割成不同长度的分片,就像虚拟内存管理中的分段。遗憾的是,这个解决方法存在固有的问题。具体来说,将空间切成不同长度的分片以后,空间本身会碎片化,随着时间推移,分配内存会变得比较困难。

因此,值得考虑第二种方法:将空间分割成固定长度的分片。在虚拟内存中,称这种思想为分页。分页不是将一个进程的地址空间分割成几个不同长度的逻辑段(即代码、堆、段),而是分割成固定大小的单元,每个单元称为一页。相应地,把物理内存看成是定长槽块的阵列,叫作页帧(page frame)。每个这样的页帧包含一个虚拟内存页。关键问题是:

如何通过页来实现虚拟内存,从而避免分段的问题?基本技术是什么?如何让这些技术运行良好,并尽可能减少空间和时间开销?

1、一个简单例子

为了让该方法看起来更清晰,用一个简单例子来说明。下图展示了一个只有 64 字节的小地址空间,有 4 个 16 字节的页(虚拟页0、1、2、3)。真实的地址空间肯定大得多,通常 32 位有 4GB 的地址空间,64 位有 256T 的空间(使用其中的 48 位)。

物理内存,如下图所示,也由一组固定大小的槽块组成。在这个例子中,有 8 个页帧(由 128 字节物理内存构成,也是极小的)。从图中可以看出,虚拟地址空间的页放在物理内存的不同位置。图中还显示,操作系统自己用了一些物理内存。

可以看到,与以前的方法相比,分页有许多优点。可能最大的改进就是灵活性:通过完善的分页方法,操作系统能够高效地提供地址空间的抽象,而不用管进程如何使用地址空间。例如,不会假定堆和栈的增长方向,以及它们如何使用。

另一个优点是分页提供的空闲空间管理的简单性。例如,如果操作系统希望将 64 字节的小地址空间放到 8 页的物理地址空间中,它只要找到 4 个空闲页。也许操作系统保存了一个所有空闲页的空闲链表,只需要从这个列表中拿出 4 个空闲页。在这个例子里,操作系统将地址空间的虚拟页 0 放在物理页帧 3,虚拟页 1 放在物理页帧 7,虚拟页 2 放在物理页帧 5,虚拟页 3 放在物理页帧 2。页帧 1、4、6 目前是空闲的。

为了记录地址空间的每个虚拟页放在物理内存中的位置,操作系统通常为每个进程保存一个数据结构,称为页表(page table)。页表的主要作用是为地址空间的每个虚拟页面保存地址转换,从而知道每个页在物理内存中的位置。

对于上面的简单示例,页表因此具有 4 个条目:虚拟页 0→物理帧 3、虚拟页 1→物理帧 7、虚拟页 2→物理帧 5 和虚拟页 3→物理帧 2。

重要的是要记住,这个页表是每个进程都有一个的数据结构。如果在上面的示例中运行另一个进程,操作系统将不得不为它管理不同的页表,因为它的虚拟页显然映射到不同的物理页面(共享除外)。

现在了解了足够的信息,可以完成一个地址转换的例子。设想拥有这个小地址空间(64 字节)的进程正在访问内存:

movl <virtual address>, %eax

具体来说,注意从地址 到寄存器 eax 的显式数据加载(忽略之前肯定会发生的指令获取)。

为了转换该过程生成的虚拟地址,我们必须首先将它分成两个组件:虚拟页面号(virtual page number,VPN)和页内的偏移量(offset)。对于这个例子,因为进程的虚拟地址空间是 64 字节,所以虚拟地址总共需要 6 位(2^6 = 64)。因此,虚拟地址可以表示如下:

在上图中,Va5 是虚拟地址的最高位,Va0 是最低位。因为知道页的大小(16 字节),所以可以进一步划分虚拟地址,如下所示:

页面大小为 16 字节,位于 64 字节的地址空间。因此我们需要能够选择 4 个页,地址的前 2 位就是做这件事的。因此,我们有一个 2 位的虚拟页号。其余的位告诉我们,感兴趣该页的哪个字节,在这个例子中是 4 位,称之为偏移量。

当进程生成虚拟地址时,操作系统和硬件必须协作,将它转换为有意义的物理地址。例如,假设上面的加载是虚拟地址 21:

movl 21, %eax

将“21”变成二进制形式,是“010101”,因此可以检查这个虚拟地址,看看它是如何分解成虚拟页号和偏移量的:

因此,虚拟地址“21”在虚拟页 1(“01”)的第 5 个(“0101”)字节处。通过虚拟页号,现在可以检索页表,找到虚拟页 1 所在的物理页面。在上面的页表中,物理帧号(物理页号,physical page number,PFN)是 7(二进制 111)。因此,可以通过用 PFN 替换 VPN 来转换此虚拟地址,然后将载入发送给物理内存。

2、页表存在哪里

页表可以变得非常大,比之前讨论过的小段表或基址/界限对要大得多。例如,想象一个典型的 32 位地址空间,页的大小为 4KB。虚拟地址分成 20 位的 VPN 和 12 位的偏移量(2^12 = 4KB)。

一个 20 位的 VPN 意味着,操作系统必须为每个进程管理 2^20 个地址转换(大约一百万)。假设每个页表条目(page table entry,PTE)需要 4 个字节,来保存物理地址转换和任何其他有用的东西,每个页表就需要巨大的 4MB 内存!这非常大。现在想象一下有100个进程在运行:这意味着操作系统会需要 400MB 内存。

由于页表如此之大,我们没有在 MMU 中利用任何特殊的片上硬件,来存储当前正在运行的进程的页表,而是将每个进程的页表存储在内存中。稍后会看到,很多操作系统内存本身都可以虚拟化,因此页表可以存储在操作系统的虚拟内存中(甚至可以交换到磁盘上)。现在假设页表存在于操作系统管理的物理内存中。下图展示了操作系统内存中的页表,看到其中的一小组地址转换了吗?(虚拟页 0→物理帧 3、虚拟页 1→物理帧 7、虚拟页 2→物理帧 5 和虚拟页 3→物理帧 2)

3、页表中究竟有什么

现在来谈谈页表的组织。页表就是一种数据结构,用于将虚拟地址(或者实际上,是虚拟页号)映射到物理地址(物理帧号)。因此,任何数据结构都可以采用。最简单的形式称为线性页表,就是一个数组。操作系统通过虚拟页号检索该数组,并在该索引处查找页表项(PTE),以便找到期望的物理帧号(PFN)。现在,假设采用这个简单的线性结构。

至于每个 PTE 的内容,在其中有许多不同的位,值得了解。

  1. 有效位(valid bit)通常用于指示特定地址转换是否有效。例如,当一个程序开始运行时,它的代码和堆在其地址空间的一端,栈在另一端。所有未使用的中间空间都将被标记为无效,如果进程尝试访问这种内存,就会陷入操作系统,可能会导致该进程终止。因此,有效位对于支持稀疏地址空间至关重要。通过简单地将地址空间中所有未使用的页面标记为无效,我们不再需要为这些页面分配物理帧,从而节省大量内存。
  2. 保护位(protection bit),表明页是否可以读取、写入或执行。同样,以这些位不允许的方式访问页,会陷入操作系统。
  3. 存在位(present bit)表示该页是在物理存储器还是在磁盘上(即它已被换出)。当研究如何将部分地址空间交换到磁盘,从而支持大于物理内存的地址空间时,我们将进一步理解这一机制。交换允许操作系统将很少使用的页面移到磁盘,从而释放物理内存。
  4. 脏位(dirty bit)也很常见,表明页面的内容是否被修改过。
  5. 参考位(reference bit,也被称为访问位,accessed bit)有时用于追踪页是否被访问,也用于确定哪些页很受欢迎,因此应该保留在内存中。

下图显示了来自 x86 架构的示例页表项。它包含一个存在位(P),确定是否允许写入该页面的读/写位(R/W) ,确定用户模式进程是否可以访问该页面的用户/超级用户位(U/S),有几位(PWT、PCD、PAT 和 G)确定硬件缓存如何为这些页面工作,一个访问位(A)和一个脏位(D),最后是页帧号(PFN)本身。

4、分页:也很慢

内存中的页表,已经知道它们可能太大了。事实证明,它们也会让速度变慢。以简单的指令为例:

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,移位将它变成 000001,或虚拟页 1,正是所期望的值。然后,使用该值作为页表基址寄存器指向的 PTE 数组的索引。

一旦知道了这个物理地址,硬件就可以从内存中获取 PTE,提取 PFN,并将它与来自虚拟地址的偏移量连接起来,形成所需的物理地址。具体来说,你可以想象 PFN 被 SHIFT 左移,然后与偏移量进行逻辑或运算,以形成最终地址。

offset   = VirtualAddress & OFFSET_MASK 
PhysAddr = (PFN << SHIFT) | offset

最后,硬件可以从内存中获取所需的数据并将其放入寄存器 eax。程序现在已成功从内存中加载了一个值!总之,我们现在描述了在每个内存引用上发生的情况的初始协议。基本方法如下所示。

// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

// Fetch the PTE
PTE = AccessMemory(PTEAddr)

// Check if process can access the page
if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)
else
    // Access is OK: form physical address and fetch it
    offset   = VirtualAddress & OFFSET_MASK
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    Register = AccessMemory(PhysAddr)

对于每个内存引用(无论是取指令还是显式加载或存储),分页都需要我们执行一个额外的内存引用,以便首先从页表中获取地址转换。工作量很大!额外的内存引用开销很大,在这种情况下,可能会使进程减慢两倍或更多。

现在你应该可以看到,有两个必须解决的实际问题。如果不仔细设计硬件和软件,页表会导致系统运行速度过慢,并占用太多内存。

5、小结

本章引入了分页的概念,作为虚拟内存挑战的解决方案。与以前的方法(如分段)相比,分页有许多优点。首先,它不会导致外部碎片,因为分页(按设计)将内存划分为固定大小的单元。其次,它非常灵活,支持稀疏虚拟地址空间。

然而,实现分页支持而不小心考虑,会导致较慢的机器(有许多额外的内存访问来访问页表)和内存浪费(内存被页表塞满而不是有用的应用程序数据)。因此,不得不努力想出一个分页系统,它不仅可以工作,而且工作得很好。

发表回复

您的电子邮箱地址不会被公开。