问题：页表很大

  • 32位地址空间(4GB)，带有4KB的页：20位的VPN，12位的offset
    • 单个页表大小： $4 MB= 2^{20} entries * 4 Bytes$

方案1：采用更大的页

  • 32位地址空间(4GB)，带有16KB的页
    • 单个页表大小 $=\frac{2^{32}}{2^{14}} *4 B = 1 MB$

问题：线性页表

  • 为一个进程的整个地址空间提供一个线性页表
  • 大量页表项是无效的！

enter image description here

方案2：段页式地址转换(混合方法)

为每个段分配一个页表

enter image description here

假设有3个段，每个进程有3个页表(段页表)，4GB地址空间，4KB的页面，地址该如何表示？

enter image description here

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

问题：段页式地址转换(混合方法)

  • 混合方法在特定情况下表现仍然不好
    • 分段本质上不够灵活，假定地址空间有使用模式
    • 如果有一个大而稀疏的堆，仍然导致页表的浪费
    • 这种混合仍然可能导致外部碎片的出现
      • 页表现在可以是任意大小

方案3：多级页表(multi-level PT)

  • 页表的本质是数据结构
    • 除开线性页表，我们还可以利用什么数据结构？
  • 以树的形式组织页表
    • 将页表分成许多单元，每个单元为1个页大小
    • 如果一个单元中所有页表项都无效， 则不分配该单元所需内存
  • 引入页目录(page directory)
    • 目的是追踪页表的页是否有效，以及它在内存中的位置
      • 目的是追踪页表的页是否有效，以及它在内存中的位置
      • 或者告知页表的整个页不包含有效页
  • 每个页目录项(PDE)描述一个二级页表
    • 包含一个有效位和页帧号

enter image description here

  • 页目录索引 PDI (page directory index)
  • 页表索引PTI (page table index)

enter image description here

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:  # perform the full multi-level lookup
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = AccessMemory(PDEAddr)
    if (PDE.Valid == False):
        RaiseException(SEGMENTATION_FAULT)
    else:  # PDE is Valid: now fetch PTE from PT
        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()

enter image description here

eg：采用线性页表时，计算需要多少页来存储页表？

Ans：16

采用二级页表时，地址如何表示？

  • 地址空间：16KB，页大小：64B
  • 每个二级页表/页目录包含16个表项(每个占4B)

enter image description here

方案3：更多级的页表

二级页表有时候可能不满足需求（需要更深的树结构）

eg：

enter image description here

enter image description here

其他方案：反向页表

  • 思考一下普通页表的转换方式
    1. VPN -> PFN
    2. 每个进程一个页表

enter image description here

  • 如果从物理页帧出发，反向记录
    • PFN -> PID、VPN
    • 所有进程共用

enter image description here

“使页表变小”小结

  • 线性页表的问题：页表太大，耗费内存
    • 方法1：采用更大的页
    • 方法2：段页式地址转换
    • 方法3：多级页表
    • 方法4：反向页表
    • 优缺点分别是什么？

页面是不是一定能放入内存？