缩小页表

上一篇 《TLB - 加速地址翻译》 介绍了加速虚拟地址翻译的机制和策略,但是还有个问题没有很好的解决,那就页表很占内存的问题。

一个 32-bit 的虚拟地址空间(2^32),有着 4KB(2^12) 的页大小,则可能有 2^20=2^(32 - 12) 个(大约 100 多万)个 PTE,假设每个 PTE 4 字节大小,则这个进程的整个页表可能高达 4MB,假设有 100 个进程在操作系统中运行着,那么所占内存将达到 400MB!

因此,我们要想办法,减少页表的大小。

一个简单的办法,更大的 Page Size

还是用 32-bit 的虚拟地址空间,但是这次 Page 大小是 16KB,我们有着 18-bit 大小的 VPN 和 14-bit 大小的偏移,这时候大概有 2^18 (大约 26 万多)个 PTE,假设 PTE 依旧是 4 字节大小,这时候页表总大小大约是 1MB。是之前方案的 4 倍小。

然而,更大的页也会带来内部碎片问题,内部空间可能会被大量的浪费掉,大量可用内存得不到有效的利用。

因此,大部分操作系统宁愿选择更小的页面,比如 4KB(x86的)或者 8KB(SPARCv9),转而寻找其他方法来减少页表大小。

混合方案,分页 + 分段

与其让进程有一张大而且空旷的页表,不然让进程拥有三个页表对应三个不同用途的分段:代码段、堆、栈。

每个段所使用的内存地址由 base register(基址寄存器) 和 bound register(边界寄存器) 标识(回忆请看《段式内存管理》

基址寄存器标识了这一分段的起始内存地址,边界寄存器用哪个来检测这一分段的边界,防止非法访问。

我们来看个具体的例子。

虚拟地址空间依旧是 32-bit,页大小依旧是 4KB,但是我们对一个虚拟地址的解释稍微不一样。最高两位被用来标识不同的段 。
00

硬件层面上,必须知道有三对 ,在进程切换的时候,这些寄存器也必须被相应的切换到对应进程的值,以便找到对应的页表。
在发生 TLB miss 的时候,由硬件处理的 TLB miss 也得利用 base register 来找到 PTE,

SN           = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN          = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

相比用一个线性表来处理存页表,分段之后的页表可以更小了,因为减少了给尚未使用的空间分配 PTE,所以可以缩小页表。

原文:

In this manner, our hybrid approach realizes a significant memory savings compared to the linear page table; unallocated pages between the stack and the heap no longer take up space in a page table (just to mark them as not valid).

然而,这种方式也是有些问题的,就如前面介绍段式内存管理时候介绍的,它不太灵活,必须假定进程模型是由三个段组成的,而且也没有很好的解决页表中空闲空间的浪费问题(对于一个大的段而言),另外,查找空闲内存给一个进程也会比较复杂。

原文:

However, as you might notice, this approach is not without problems. First, it still requires us to use segmentation; as we discussed before, seg- mentation is not quite as flexible as we would like, as it assumes a certain usage pattern of the address space; if we have a large but sparsely-used heap, for example, we can still end up with a lot of page table waste. Second, this hybrid causes external fragmentation to arise again. While most of memory is managed in page-sized units, page tables now can be of arbitrary size (in multiples of PTEs). Thus, finding free space for them in memory is more complicated. For these reasons, people continued to look for better ways to implement smaller page tables.

多级页表

把线性表转换成一颗树。

首先,把页表也切分成像页一样一节一节大小的。如果一整页的 PTE 都是无效的,那属于页表中的这一 就不需要分配出来占内存了。为了记录页表中的一 是否有效(有效,则必须在内存中),操作系统使用了一个新的数据结构,页表目录(Page Directory)。这个结构可以用来告知,页表中的一 在哪里,这一 中是否有无效的 PTE。

01

左边是一个线性表组成的页表,右边是多级页表的组成。
页表目录记录了有两个 (PFN=201 和 PFN=204) 是有效的,因此只有这两 被分配到了实际的物理内存,

页表目录由一系列 Page Directory Entry(PED) 构成,最小的 PDE 如上图看到的,有一个有效位和页框号(Page Frame Number, PFE)组成,有点像 PTE。
有效位表明了,这一页框号对应的 中的 PTE 至少有一个是有效的。

多级页表有些很明显的优点,比如说页表更小了,因为它只分配有效的被使用的页面。还有,如果被精心组织的话,页表中的每一个部分都能被安排到一个页当中,操作系统就比较容易地管理内存分配。相比必须常驻大块连续内存的线性表实现的页表,实际占用的内存更少了。For a large page table (say 4MB), finding such a large chunk of unused con- tiguous free physical memory can be quite a challenge. (这句话没有理解,书中似乎也没提到线性页表的空闲空间查找策略)

这种方法被现代操作系统广泛采用。

但是这样也会带来了代价。

在发生 TLB miss 时,必须要读取两次内存才能从页表中得到正确的地址(一次是读取页表目录,一次是为了读取 PTE)。这就是看时间和空间怎么权衡(time-space trade off)了。
还有一个就是增加了复杂度。操作系统在页表中查找一个 PTE 时的逻辑会比线性表复杂很多。需要操作系统更消息的实现。

不过,通常情况下,我们是愿意增加复杂度来换取空间或时间的减少的,这意味着我们有更多的资源来做其他事情,这里的多级页表就是一个例子。

详细举例一个多级页表

14-bit 的虚拟地址空间,8-bit VPN 和 6-bit 的偏移。Page Size 是 64(2^6) 字节大小 一个线性表实现的页表将有 2^8(256)个 PTE,整个页表大小是 1KB(256 x 4B)

02

虚拟页页 0、1用户代码段,虚拟页 4、5 用于堆,最后的虚拟页 254、255 用于栈,剩下的虚拟页尚未被使用。
我们有 256 个 PTE,每个 PTE 是 4 字节大小,因此一个虚拟页(物理页)将能容纳 16(64 / 4) 个 PTE,因此这些 PTE 将要分布在 16(256 / 16) 个页中。我们需要 2^4 (16)个数字才能检索所有这些页,也就说说需要将 VPN 的标志位拿出 4 位来作为 Page Directory Index。

03

我们从 VPN 中抽取出 Page Directory Index 之后,就可以从页表目录找到 PDE
PDEAddr = PageDirBase + (Page Directory Index) * sizeof(PDE)
接着,如果 PDE 的有效标志位是标记着无效的话,我们知道此时这个访问是非法的,抛出异常。
如果是有效的,我们继续从 VPN 中提取出 Page Table Index,目的是为了找到 PTE。
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))

我们看下面的页表目录
04

我们使用最后一条 PDE 作为例子。我们要访问地址 0x3F80(二进制 11 1111 1000 0000),

  1. 此时 Page Directory Index = 1111,对应的就是页表目录里第 15 个 PDE
  2. 这个 PDE 告诉我们这一 在 101 处,利用接下来的 4 位 1110 我们将能找到想要的 PTE
  3. 这个 PTE 在那一 的第 14 偏移处。这个PTE告诉我物理页号 PFN=55
  4. PhyAddr = (PFN.PFN << SHIFT) + offset = 00 1101 1100 0000 = 0x0DC0

    其中 SHIFT=6,右移 6 位

地址翻译过程:加上 TLB

直接看代码吧,操作系统的多级页表控制流程:

VPN = (VirtualAddress & VPN_MASK) >> SHIFT

(Success, TlbEntry) = TLB_Lookup(VPN)

if (Success == True) {   // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True) {
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)   // 访问内存
    } else {
        RaiseException(PROTECTION_FAULT)
    }
} else {
    // first, get page directory entry
    PDIndex = (VPN & PD_MASK) >> PD_INDEX
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = AccessMemory(PDEAddr) // 访问内存

    if (PDE.Valid == False) {
        RaiseException(SEGMENTATION_FAULT)
    } else {
        // PDE is valid: now fetch PTE from page table
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
        PTE = AccessMemory(PTEAddr)
        if (PTE.Valid == False) {
            RaiseException(SEGMENTATION_FAULT)
        } else if (CanAccess(PTE.ProtectBits) == False) {
            RaiseException(PROTECTION_FAULT)
        } else {
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()
        }
    }
}

可以看到,当发生 TLB miss 时候,需要额外的两次访问内存来达到正确的翻译,一次是在查页表目录,一次是查询 PTE;而使用线性页表只需要额外的一次。

反转页表

一个更省内存的方法是 反转页表(inverted page tables)

与其每个进程保存一张页表,不如整个操作系统只保留一张追踪物理内存使用情况的表。表里的每一个元素告诉我们哪一个进程正在使用着这 内存,进程的哪一个虚拟页正映射到这 物理内存。

如果还是线性地搜索页表这时候就会变得很慢,因为地址空间可能很大,这时候用哈希表就会好些。PowerPC 就是一个例子(参见引用)。

反转页表的详细可以 Google,也可参照下面引用的一篇文章《《Inverted Page Tables, CS162, UC Berkeley》》。

线性反转页表

下面介绍翻译虚拟地址的过程。

首先从虚拟地址中抽取出 虚拟页号 VPN,然后以 <进程的ID,虚拟页号> 线性地去搜索页表,如果匹配了,就从中取出物理地址再加上偏移就能访问到物理地址,如果没有找到,就抛出 Page Fault 异常。

06

线性搜索的效率会很慢,举例子来说,512MB 内存的,页面是 4KB (2^12)大小,那么总共有 128K (2^(29-12))个物理页面。
我们用 16-bit 来保存进程 ID,52-bit 来检索虚拟页页号,12-bit 存储页面的信息,那么总共需要 80-bit(10 字节) 来标识一个物理页面,则页表总共的大小是 10 * 128K,大约 1.3MB。

线性搜索的代价上限将会是 128K 次内存访问(TLB miss all the times!),这是极大的性能损失。即使平均一下,也需要 64K 次内存访问,这样的性能还是不能接受。

哈希反转页表

哈希反转页表需要一个额外的哈希表来存储 <进程的ID,虚拟页号> 到 PTE 的映射。现在的虚拟地址映射将会先计算 <进程的ID,虚拟页号> 这个元素的哈希值,然后得到哈希表的一个元组,通过这个元素知道 PTE 的信息。如果找不到哈希表里对应的元组或者 PTE 无效,将会抛出 Page Fault 异常。

假设哈希函数被设计得很好,每个哈希表的链长是 1.5,那么只需要 2.5 次内存访问就能获得到 PTE 了。大大地降低了内存访问的次数,加速了地址翻译过程。

07

反转页表与 TLB

在于 TLB 的交互上,用反转页表的方式与用多级页表没有多大差别,发生 TLB miss 时把去查找反转链表然后 PTE 给 load 进来

把页表换到硬盘中去

页表是由操作系统内核维护的,那么内核空间不可能容纳所有进程的页表,而且也要考虑到在采用反转页表的实现方式来实现页表结构时,两个进程的 VPN 映射到相同的 PFN 时该怎么处理。

因此必须要考虑到操作系统如果借用外部存储来存放页表,详细的会在介绍外部存储的章节去介绍。

总结

引用
《PowerPC》
《Inverted Page Tables, CS162, UC Berkeley》

Comments
Write a Comment