分页 | Siriusuna

机制介绍

虽然我们在此前尝试, 让操作系统将空间分为不同长度的分片来管理空间,
就好像空闲空间管理管理堆空间一样, 使用分段.

但是这样会造成空间碎片化, 随着时间推移, 越来越难以分配内存.

因此我们考虑: 将空间分为固定长度的分片, 也就是分页.
我们不将一个进程的地址空间分割为不同长度的逻辑段, 而是分割成固定大小的单元, 也就是页.
相应的, 我们吧物理内存看作定长槽块的阵列, 称之为页帧, 每个页帧宝库爱一个虚拟内存页.

这样有两个优点:

灵活性: 操作系统可以高效地提供地址空间的抽象, 不管进程如何使用地址空间.
简单性: 只需要一个记录空闲页面的列表, 需要的时候拿出空闲页, 并和虚拟地址绑定.

为了记录地址空间每个空闲也放在物理内存的位置, 操作系统通常需要为每个进程保存一个页表.
页表用于为每个虚拟页面保存地址转换, 映射到正确的物理内存位置.

映射机制

Vitual Address

为了转换虚拟地址, 我们需要划分地址为两部分: VPN, Offset.

$V PN = AddressBits - OffsetBits = lo g_{2} (\frac{AddressSpace}{PageSize})$ bits
$O ff se t = lo g_{2} (PageSize)$ bits

我们可以通过页表, 找到虚拟页号对应的物理页(帧)号(PFN, PPN)并替换, 偏移量保持不变.

Address Translation

页表位置

页表可能可以非常大, 操作系统需要管理 $2^{V PN}$ 个地址的转换.

因此我们没有在 MMU 上设置片上硬件, 而是将其存储在内存中.

页表内容

页表是一种数据结构, 将虚拟地址映射到物理地址, 最简单的形式就是线性页表, 也就是一个数组.
操作系统通过 VPN 检索数组, 在索引出查找页表项 PTE, 以便找到 PFN(PPN).

至于每个 PTE, 有许多不同的位:

有效位(valid bit): 指示特定地址转换是否有效.
保护位(protect bit): 表明页是否可以读取, 写入或执行.
存在位(present bit): 表明该页是在物理存储器还是磁盘(是否 swapped out)
脏位(dirty bit): 表明页面被带入内存后是否被修改过.
参考位(reference bit, 也叫访问位, accessed bit): 有时用于追踪页面是否被访问, 也用于确定那些页受欢迎因此应该保留与内存. 在页面替换中非常重要.

效率与性能

使用页表也会让速度变慢, 对于每个内存引用, 无论是取指令, 或者显式加载或存储,
分页都需要我们执行一个额外的内存引用, 以便于首先从页表中获取地址转换.

伪代码如下:

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PTBR + (VPN * sizeof(PTE))
PTE = AccessMemory(PTEAddr)         # 一次额外的内存引用, 找到对应页表项
if PTE.valid == False:
    raise SegmentationFault
elif CanAccess(PTE.ProtectionBits) == False:
    raise ProtectionFault
else
    offset = VirtualAddress & OFFSET_MASK
    PhysAddr = (PFN << SHIFT) | offset
    Register = AccessMemory(PhysAddr)

优点与不足

分页有许多优点:

不会导致外碎片;
非常灵活, 支持稀疏地址空间.

但是也有一些要注意的地方, 如果不小心考虑, 可能会:

导致机器较慢(有许多额外内存访问来访问页表);
内存浪费(内存被页表塞满)

因此我们以下解决这两个问题.

快速地址转换(TLB)

在这里, 我们将要解决使用分页的第一个问题:
转换虚拟地址的时候, 需要查询页表, 导致一次额外的内存访问, 因此访存速度相对比较慢.

但是得益于空间局部性和时间局部性, 我们可以对一些页面的地址转换做缓存, 从而提升效率.

解决这个问题, 我们需要避免一些额外的内存访问, 因此要一些硬件的支持.
我们要增加地址转换旁路缓冲存储器(TLB), 也就是常言的快表.
每次对内存访问, 硬件先检查 TLB, 看看其中是否有期望的转换映射, 如果有就直接完成转换, 不用访问页表.

TLB 的基本算法

根据设计哲学的不同, 有硬件管理和操作系统管理的 TLB.

对于硬件管理的 TLB, 硬件必须知道页表在内存的确切位置(通过页表基址寄存器), 以及页表确切格式.
发生未命中的时候, 硬件自己进行页表遍历, 找到正确页表项并将映射关系存入 TLB, 例如 x86.

VPN = (VirtualAddress & VPN_MASK)
(Success, TlbEntry) = TLB_Lookup(VPN)
if Success == True:
    if canAccess(TlbEntry.ProtectBits) == True:
        Offset = VirtualAdress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    else:
        raise ProtectionFault
else:  # TLB Miss
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if PTE.valid == False:
        raise SegmentationFault
    elif CanAccess(PTE.ProtectBits) == False:
        raise ProtectionFault
    else:
        TLB_insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()  # 重新执行由于 TLB Miss 执行失败的指令

而对于更现代的 RISC 指令集计算机, 发生 TLB 未命中的时候, 硬件系统会抛出一个异常,
这会暂停当前的指令流, 将特权提升至内核模式, 跳转至陷阱处理程序, 处理 TLB Miss.
这段代码在运行时会查找页表中的转换映射, 用特权指令更新 TLB, 并从陷阱返回.

VPN = (VirtualAddress & VPN_MASK)
(Success, TlbEntry) = TLB_Lookup(VPN)
if Success == True:
    if canAccess(TlbEntry.ProtectBits) == True:
        Offset = VirtualAdress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else:
        raise ProtectionFault
else:  # TLB Miss
    raise TLBMiss  # 注意, 从这个异常返回, 应该回到导致陷阱的指令, 而不是下一条.

使用操作系统来处理 TLB 未命中, 有一大优势: 灵活性.
操作系统可以用任意数据结构来实现页表, 而不需要改变硬件.
硬件不需要对未命中做太多工作, 只要抛出异常, 操作系统的处理程序会负责剩下的任务.

不过也有要注意的地方: 防止 TLB 未命中的无限递归.
具体地, TLB 未命中的陷阱处理程序可以直接放到物理内存而不进行地址转换;
或者在 TLB 保留一些永久有效的项, 并且把一些项留给 TLB 未命中的陷阱处理程序本身.
否则可能出现 TLB Miss → 陷阱处理 → 读取指令的时候 TLB Miss → 陷阱处理 → …

TLB 内容

VPN | PFN | 其他位

其中, 其他位中包括:

有效位(V): 用来标识该项是不是有效地址转换映射.
注意与 PTE 的有效位不同, PTE 中表明的是页面是否被进程申请使用, TLB 表明的是缓存的转换是否有效.
保护位: 标识该页是否有访问权限, 例如代码页为可读可执行, 堆栈页位可读可写.
空间标识符(asid)
脏位(D): 改写是否被写入过数据
全局位(G): 指示页面是不是所有进程全局共享, 若置为 1, 则忽略 ASID.
一致性位(C)

A MIPS TLB Entry

上下文切换时 TLB 的处理

有了 TLB, 伴随在进程间切换时的地址空间切换, 会面临一些新问题:
TLB 包含的虚拟地址到物理地址的映射, 只对当前进程有效, 而对其余进程没有意义.
所以如果在 TLB 对映射来源的进程不加区分, 那么就会分不清哪个项来自哪个进程, 导致错误访问.

一个简单地解决办法是在切换进程时清空 TLB, 但这样会在每次切换完进程后一段时间造成大量 TLB Miss.

还有一些系统提供了硬件支持, 例如添加了地址空间标识符(Address Space Identifier, ASID).
每个进程唯一, 用于区分映射条目的进程来源.

有了 ASID 后, TLB 可以同时缓存多个不同进程的地址空间映射而不冲突.
当然, 硬件需要知道当前运行中的进程的 ASID, 以便地址转换, 所以需要一个特权寄存器, 记录当前的 ASID.

一些问题

TLB 并不能满足所有程序需求.

若一个程序短时间内访问的页面数超过了 TLB 中的页数, 就会产生大量 TLB 未命中, 运行速度就会变慢.
这被称为超出 TLB 覆盖范围.
一种解决方案是支持更大的页, 把关键数据结构存在某些区域, 然后将其映射到更大的页, 在这 DBMS 常用.
访问 TLB 容易成为 CPU 流水线瓶颈.
如果对 cache 的访问使用物理地址作为 index, 那么在访问 cache 前必须转换地址, 这会导致操作变慢.
现在常用的是 VIPT, 用虚拟地址作为 index, 用物理地址作为 tag, 让对 cache 的查询和地址转换同时进行, 然后再检查.

分级页表

在此处, 我们将要解决页表的第二个问题:
页表太大, 消耗的内存太多.

一些解决方案

更大的页

使用更大的页, 页数少了, 页表条目就少了, 页表自然小了, 但是大的页面会造成内碎片.

分页和分段混合

结合[[地址转换机制|#分段]]与分页:
为每个逻辑分段提供一张页表, 然后基址寄存器指向页表该段开头的物理地址, 界限寄存器指示页表有多少项.

实质上是: 将逻辑分段的内存分配粒度变大, 使得段内按页分配(减少外碎片), 段间按需分配(减少内碎片), 达到互补效果.

但是这仍旧要求使用分段, 这一方法并不怎么灵活, 他假定我们使用地址空间有一定模式, 不是完全无感.
并且如果有一个大而稀疏的堆, 仍然会造成大量页表浪费.

多级页表

毕竟页表是一种数据结构, 只要可以完成基本的映射功能, 我们可以随意安排其组织形式, 来达到我们的目的.

在这里, 我们把线性页表变为类似树的东西.

首先, 将页表分成页大小的单元. 如果整页的 PTE 都无效, 就不分配该页的页表. 然后, 我们建立一个页目录的结构, 这是一种类似页表的结构, 其中的条目都是页表页的映射, 以及追踪其有效性.
在一个简单的二级页表中, 页目录为每页页表包含了一项 PDE, PDE 至少拥有有效位和页帧号(PFN).
但是有效位含义略微不同, 如果有效, 说明该项指向的页表至少一项 PTE 有效; 否则无效.

如果仔细构建, 页表每个部分可以整齐放入一页, 从而更容易管理内存, 在需要分配增长页表的时候简单获取一个空闲页.

也就是, 其实质为, 释放一些空闲的页表的空间; 并且不再强迫使用大量连续空闲内存, 而是可以在内存任何地方.
然后用页目录记录哪些页表被分配, 分配到哪里.
因此他的空间很紧凑, 和我们目前使用的地址空间内存量成比例, 并且很好地支持了稀疏地址空间.

当然, 多级页表也有代价

TLB 未命中的时候, 要从内存加载两次才能从页表获取正确的地址转换信息.(这说明多级页表是一个以时间换空间的方案)
复杂性, 比线性页表复杂得多.

多级页表查询

首先明确多级页表下的地址格式, 以及各个部分位数的确定

| VPN |Offset| |PDX|PTX|offset|

$PDE Entries Number = Page Table Page Numbers$
$P D X = l o g_{2} PDE Entries Number$
$V PN = P D X + PTX$

根据页目录索引, 我们可以很简单找到 PDE 地址:
$P D E A dd r = P a g eD i r B a se + (P D I n d e x \times s i zeo f (P D E))$

如果页目录无效, 就会引发异常进行处理; 如果有效, 那么要从页目录指向的页表中获取页表项.
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))

但记住, 在访问页表前, 硬件会首先检查 TLB, 只有在未命中时才需要执行完成多级查找.

VPN = (VirtualAddress & VPN_MASK)
(Success, TlbEntry) = TLB_Lookup(VPN)
if Success == True:
    if canAccess(TlbEntry.ProtectBits) == True:
        Offset = VirtualAdress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else:
        raise ProtectionFault
else:  # TLB Miss
    # To get PDE
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = AccessMemory(PDEAddr)
    if PDE.Valid == false:
        raise SegmentationFault
    else:
        # Valid PDE: fetch PTE
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
        PTE = AccessMemory(PTEAddr)
        if PTE.Valid == False:
            raise SegmentationFault
        elif CanAccess(PTE.ProtectBits) == False:
            raise ProtectionFault
        else:
            TLB_insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()

超过两级的页表

更深的树也是可能的! 当我们的页目录也足够大到很难连续存储, 我们可以为页目录建立页目录, 原理一致.

反向页表

正如我们之前所说, 页表作为数据结构, 我们可以自由安排数据存在形式.

例如在反向页表中, 每一项代表每个物理页, 每一项记录哪个进程正在使用此页, 以及哪个虚拟页映射到此页.
而没有每个进程一个的页表, 记录虚拟页到物理页的映射关系.

而要在这个数据结构找到正确的项, 一般都通过建立散列表加速查找.

交换到磁盘

即使我们有如此多的技巧减小页表大小, 对我们的物理内存而言, 页表可能还是太大, 无法一次装入内存.

因此一些系统将这样的页表放入内核虚拟内存, 允许系统在内存压力较大的时候将其中一部分交换到磁盘.

权衡

正如刚刚所述, 页表是一个数据结构, 具体结构的选择是空间和时间的 Trade-off.
页表大, 那么 TLB 未命中可以处理更快, 但是空间占用大;
页表小, 那么 TLB 未命中的处理就会慢, 但是空间占用小.

结构的正确选择依赖于环境约束.

シリウスの砂

探索

分页