CSCI3150 L11 高级分页

课程：CSCI3150 Introduction to Operating Systems · 2022未核本讲：L11 高级分页，第 2 部分 / 共 2 部分 · 原件 L11-TLB与高级分页-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.19–40 定位：用分段和多级间接索引减少稀疏地址空间的页表开销。前后：前接 TLB；后接 L12 换页。

逐页伴读

p.19 是 Part II 标题。

p.20–21：大页缩表，但增大内部碎片

p.20 We usually have one page table for every process in the system.

Assume that 32-bit address space with 4KB pages and 4-byte page-table entry.

p.20 Page tables are too big and thus consume too much memory.

p.21 Page table are too big and thus consume too much memory.

Assume that 32-bit address space with 16KB pages and 4-byte page-table entry.

原题参数为 32 位虚拟空间、每项 4 B。4 KiB 页时，条目数 $2^{32}/2^{12}=2^{20}$ ，线性表4 MiB；改为16 KiB页，条目数 $2^{18}$ ，表1 MiB，缩小四倍。

代价是末页剩余空间可能更多。补充例子：单个1 B对象独占一页且不与别的分配共享时，4 KiB页内剩4095 B，16 KiB页内剩16383 B。这个极端例子说明粒度代价，不代表每个真实对象都独占一页。

p.22–24：表中大量无效项仍然占字节

p.22 Single page table for the entries address space of a process.

p.23 Most of the page table is unused, full of invalid entries.

p.24 In order to reduce the memory overhead of page tables.

Using base not to point to the segment itself but rather to hold the physical address of the page table of that segment.

The bounds register is used to indicate the end of the page table.

图 p.22–23 的16 KiB虚拟空间、1 KiB页共有16个VPN，实际只把代码、堆和栈的一些页映射出去。灰色未用区域仍在平铺表中占位置，设置 valid=0不等于释放那一项的存储。

p.24 的混合方案保留逻辑分段，但段 base 指向该段的页表，不再直接指向数据；bound限制表的范围。这样未用的段间大空白不必出现在各段的线性页表中。

p.25–27：段号选表，VPN 选项

p.25 Each process has three page tables associated with it.

When process is running, the base register for each of these segments contains the physical address of a linear page table for that segment.

p.25 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

p.26 The hardware gets the physical address from the page table.

The hardware uses the segment bits(SN) to determine which base and bounds pair to use.

The hardware then takes the physical address therein and combines it with the VPN as follows to form the address of the page table entry(PTE) .

课件伪代码（p.26，原页片段）

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

p.27 Hybrid Approach is not without problems.

If we have a large but sparsely-used heap, we can still end up with a lot of page table waste.

External fragmentation arises again.

p.25 的32位地址拆成2位段号、18位段内VPN、12位offset。段号01是code、10是heap、11是stack，00未用。p.26 先选 Base[SN]，再算 AddressOfPTE=Base[SN]+VPN*sizeof(PTE)；读出PTE后才能形成目标物理地址。

如果堆本身很大却使用稀疏，堆表仍然浪费。各段页表长短不一，若需连续存放，又带回外部碎片；所以混合方案并未彻底解决问题。

p.28–30：只分配真的需要的页表页

p.28 Turns the linear page table into something like a tree.

Chop up the page table into page-sized units.

If an entire page of page-table entries is invalid, don’t allocate that page of the page table at all.

To track whether a page of the page table is valid, use a new structure, called page directory.

p.29 Linear (Left) And Multi-Level (Right) Page Tables

p.29 PTBR=Page Table Base Address PDBR=Page Directory Base Address

p.30 Multi-level Page Tables: Page directory entries

p.30 The page directory contains one entry per page of the page table.

It consists of a number of page directory entries(PDE).

PDE has a valid bit and page frame number(PFN).

把线性表切成页，每个目录项PDE指向一页二级表。图 p.29 原线性表占PFN201–204四页；改后目录位于PFN200，只保留PFN201和204两页二级表，中间两页整页无效就不分配。页表结构由4页降为3页；别只算省了2页而忘记新增目录1页。

目录项的PFN指向的是页表页，叶级PTE的PFN才指向数据页。两级均有valid检查，一级目录无效就能提前停止。

补充：多级表为什么只在地址稀疏时节省。 把目录想成一排索引卡，每张卡指向一整页叶表；某一大片虚拟区域完全不用，就让对应卡无效并不分配叶表。不是删除所有无效PTE，而是以整页为单位省掉一组PTE。

用 p.33 的32位模型，每页叶表有1024项，每项覆盖一个4KiB数据页，故一张叶表覆盖4MiB虚拟范围。若两个已用数据页都在同一4MiB范围，只需根目录1页加叶表1页，共8KiB页表；若它们分处两个不同目录槽，需根1页加叶表2页，共12KiB。这里假设根与叶项均4字节，是自取的稀疏布局例子。两种情况只映射两个数据页，页表成本却不同，原因是分布位置不同。

若整个4GiB都被映射，则1024张叶表全部需要，另加1张目录，总计1025×4KiB，比4MiB线性表略大。多级索引的优势在按需分配与增长灵活，不是任何输入都绝对更小。

p.29 两种页表的完整映射。 线性表的 16 项按 VPN 从 0 到 15 排列；valid=0 的项无需假装有可用 PFN。

VPN	valid	prot	数据 PFN
0	1	rx	12
1	1	rx	13
2	0	—	—
3	1	rw	100
4–7	0（四项分别无效）	—	—
8–11	0（四项分别无效）	—	—
12	0	—	—
13	0	—	—
14	1	rw	86
15	1	rw	15

多级目录的四项依次是 (valid=1,PFN=201)、(0,—)、(0,—)、(1,204)。第 0 项所指叶表保留 VPN0–3 的四项；第 3 项所指叶表保留 VPN12–15 的四项。201/204 是放表的页框，12/13/100/86/15 是放数据的页框，两列的数字不能混用。例如 VPN14 先选目录项 3，再取叶表内项 2，最终得到数据 PFN86。

p.31–32：节省空间，要多走一步

p.31 Multi-level Page Tables: Advantage & Disadvantage

p.31 Advantage

Only allocates the page-table space in proportion to the amount of address space you are using.

The OS can grab the next free page when it needs to allocate or grow a page table.

Disadvantage

Multi-level table is a small example of a time-space trade-off.

Complexity.

p.32 A multi-level structure can adjust level of indirection through use of the page directory.

Indirection can help us place page-table pages wherever we like in physical memory.

二级表可用任意空闲框存放，增长时无需把整张大表搬到一个连续区间。代价是TLB未命中时可能先读目录再读PTE，再读数据；在不计缓存的两级简化模型中共三次物理访问。TLB命中仍可直接取得最终PFN，并非每次必走两级。

p.33–34：32位地址为何拆成10、10、12

p.33 Assumptions:

Each page is 4 KB (12 bits to represent its offsets from 0x 000 - 0x fff )

The virtual space of a process: 4GB (32-bit to represent from 0x 00000000 – 0x ffffffff)

Each entry in the page table is 4 B

How big for the page table to one process (map 4GB virtual space to 4GB physical space)

How many entries in the page table: 4GB/4KB = 1 M

How big: 1M * 4 B = 4 MB

If we have one thousand of processes running

The page table of each process is 4MB

The page tables of one thousand of processes is 4GB (ONLY for tables)

原题：4 GiB虚拟空间、4 KiB页、4 B PTE。每页表页能装4096/4=1024项，故二级索引10位；总VPN20位，再拿10位选目录，最后12位留给页内偏移。

线性表每进程4 MiB，1000进程共4000 MiB=3.90625 GiB。课件把这个量近似写为4GB；若题目要求精确字节，应写4,194,304,000 B。图 p.34 的箭头顺序是PDBR→目录项→二级表项→页框；两次索引的单位都是条目，取地址时都乘条目字节数。

补充：相同数量的有效页，页表占用也可能不同。 沿本节 32 位、4KiB 页、4B 表项的模型，一个叶表页有 1024 项，可覆盖 1024 个虚拟页；根目录有 1024 项，每项指向一个这样的叶表页。只需用到其中一页数据时，也要给它所在的叶表分配一个表页。

算一遍（页数与分布是我为演示取的，讲义没给）：两页有效数据都落在同一个目录项覆盖范围，只需一页根目录加一页叶表，页表空间为 8KiB；若两页分别落在不同目录项覆盖范围，需要一页根目录加两页叶表，空间为 12KiB。两个场景的数据页本身都占 8KiB，不计其他结构。因此二级表的空间既取决于使用多少页，也取决于这些页在虚拟空间中怎样分散；“只按已用页数线性算”会漏掉表页的分配粒度。

p.35–37：14位地址的小型完整推导

p.35 To understand the idea behind multi-level page tables better, let’s do an example.

p.36 A Detailed Multi-Level Example: Page Directory Idx

p.36 The page directory needs one entry (4 bytes) per page of the page table

it has 16 entries.

The page-directory entry is invalid  Raise an exception (The access is invalid)

p.37 A Detailed Multi-Level Example: Page Table Idx

p.37 The PDE is valid, we have more work to do.

To fetch the page table entry(PTE) from the page of the page table pointed to by this page-directory entry.

This page-table index can then be used to index into the page table itself.

原图给16 KiB地址空间、64 B页、14位VA，p.36给每项4 B。因此offset6位，VPN8位，共256个虚拟页；每页表页能容16项，需16页叶级表才能覆盖全部空间。目录16项、64 B，恰好一页。地址按4位目录索引、4位二级索引、6位offset拆分。

p.35旧PDF兼容图片误显周转时间式；PPTX正文层该行实际写2^8（256），表示页表项数，不是每项字节数。4B依据仍取自p.36。补充地址例：VA=0x1234=4660，目录索引4，二级索引8，offset52，因为 $4660=4\times1024+8\times64+52$ 。若相应PTE给PFN20，PA= $20\times64+52=1332$ ；没有PTE内容时只能算索引，不能凭空给出PFN。

补充：把前面的 0x1234 例子继续走到两次查表的地址。 仍用 14 位 VA、64 B 页、4 B 表项，目录索引 4、页表索引 8、偏移 52。下面另设目录起点 PDBR=64，目录第 4 项指向 PFN=5，那个页表的第 8 项指向数据 PFN=20，且两项有效、权限允许。这里所有地址都以字节计。

目录在物理页框 1，所以目录起点是 1×64=64。第 4 个 PDE 在 64+4×4=80；从地址 80 读出 PDE，得到下一层的 PFN=5。
页表起点不是 5，而是 5×64=320。第 8 个 PTE 在 320+8×4=352；从地址 352 读出 PTE，得到数据 PFN=20。
数据页起点是 20×64=1280，加页内偏移 52，得到最终物理地址 1332。到这里才读取用户需要的数据。

因此这一回的物理访问顺序是 80（目录项）→352（页表项）→1332（数据）。查表时乘 4，是因为一个表项占 4 B；从 PFN 求页起点时乘 64，是因为一页占 64 B。这两个乘数服务于不同单位，不能交换。PDE 无效就停在第一层；PTE 无效就停在第二层，都不能把无效项中的数字当作有效 PFN 继续访问。

p.38–40：三进程例图，先找各自的根

p.40 TLB (Translation Lookaside Buffer)

Part of the chip’s memory-management unit(MMU).

A hardware cache of popular virtual-to-physical address translation.

Advanced Paging

Big page size

Hybrid approach (paging + segmentation)

Multi-level page table

Next: Swapping (Chapters 21, 22)

p.38 物理图把位置0、1、2标为三个进程的目录根，根项分别含1、2、3；指向物理PFN1、2、3中的下级表。图中每框容4个表格单元，故位置与PFN必须除以4区分。下级表首项分别为4、5、6，p.39新增彩色箭头把三个进程的首个虚拟页连到PFN4、5、6，即起始位置16、20、24。

图未填出所有堆、栈映射，所以不能声称整张页表已经求完。可确定的三条路径为根位置0→框1→框4、根位置1→框2→框5、根位置2→框3→框6。p.40 收束为三种缩表办法：大页、分段混合、多级表；比较时同时写出空间收益与相应代价。

自测：目录项给出的PFN为何不能直接加原offset得到数据地址？

目录项指向的是页表页，那个页中的内容是PTE集合。先将目录PFN乘页长得到叶表起点，再加叶索引乘PTE字节数，读取叶PTE后才得到数据PFN。原offset一路保留，直到最后与数据框起点相加。每一级的“页号”和“项下标”都要标明属于哪一层。

图（p.38–39，已按渲染页重读）：三个进程用不同的根信息访问各自代码页。元素：每个虚拟地址空间画出 0–15；代码区从 0 起，堆区从 4 起，栈在 12–15。右侧物理地址画出 0–31，每 4 格分为一个 PFN。三个 PDBR 分别为 0、1、2，虚线先到物理位置 0、1、2，其内容分别为 1、2、3；随后对应页表的第一项位于地址 4、8、12，内容分别为 4、5、6。p.39 再画出三个代码页指向物理地址 16、20、24 的箭头。看什么：图上同一个数字可能是“当前位置”或“该位置存的页框号”，必须按箭头分步取值。

按图给出的四格一页单位，进程 1 的第一条路径是：PDBR=0 → 位置 0 的值 1 → PFN1 起点 4 → 位置 4 的值 4 → PFN4 起点 16。进程 2 是 1 → 值 2 → 地址 8 → 值 5 → 地址 20；进程 3 是 2 → 值 3 → 地址 12 → 值 6 → 地址 24。这只解释图中画出的代码首部路径；其余空白单元没有给出完整映射，不能从颜色自行编造所有堆栈 PTE。图没有给这些“格”统一的字节大小，因此这里按图的地址单位演算，不把 4 格擅自说成 4KiB。

本讲核心考点

[C] 根据地址位数、页长、项长计算线性表与各级索引位数。
[C] 从稀疏映射图计算已分配页表页，并计入根目录。
[C] 区分目录项指向页表页与PTE指向数据页。
[C] 解释TLB命中与未命中时的多级访存差别。

附录

本份没有需要移至附录的长推导；计算过程已在对应页正文写全。

来源与证据

原件：L11-TLB与高级分页-2022未核.pptx（本地课件）；PDF副本（本地课件） p.19–40。本文页码均为 PDF 页号。
考试证据：读了课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无
2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。